Let a set X = {1, 2, 3, 4, ... , 2015} and a set Y = {1, 2, 3, 4, ... , 271}. Let S be the relation on P(X) defined by:

For all sets A, B, that are elements of P(X), (A,B) are elements of S if and only if |A n Y| = |B n Y|

How many equivalence classes are there? How many elements are in the equivalence class [{271}]?

I calculated there to be 272 equivalence classes, because Y has 271 elements, the number of elements that A can share with Y is 272, from 0 - 271.

However, for the next question, I don't know if I'm interpreting this right, but I think it's asking for the number of sets where A shares 271 elements with Y. However, since A is an element of the power set of X, it has 2^2015 sets, and if you remove the 271 elements that A shares with Y, there is still 2^1744 sets in A. Each one of those can match up to 2^1744 sets in B, and at this point I think I'm already very wrong. However, I just don't see any other way of going about this question, unless I'm misinterpreting the question itself.

Any help would be greatly appreciated. Thank you.


Your answer to the first question is correct. You’ve misunderstood the second question, however. Let $A=\{271\}\in\wp(X)$. Note that $A\subseteq Y$, so $|A\cap Y|=|A|=1$. Thus, for each $B\in\wp(X)$ we have $\langle A,B\rangle\in S$ if and only if $|B\cap Y|=1$. Now $[\{271\}]$ denotes the equivalence class of $\{271\}$, i.e., the equivalence class of $A$, so

$$[\{271\}]=\{B\in\wp(X):|B\cap Y|=1\}\;.$$

To answer the question, then, we must determine how many subsets of $X$ have a one-element intersection with $Y$.

Let $B$ be such a subset of $X$. Then $B\cap Y=\{k\}$ for some $k\in Y$, and $B\setminus Y$ can be any subset at all of $X\setminus Y$. As you’ve already observed, $|X\setminus Y|=1744$, so there are $2^{1744}$ choices for $B\setminus Y$. Since there are clearly $271$ choices for $k$, the final answer is that $[\{271\}]$ has $271\cdot2^{1744}$ elements.


Equivalence classes are determined by the intersection with $Y$, and so are in correspondence with subsets of $Y$.

  • $\begingroup$ Hmm, I think I see what you're saying. Since only one subset of Y works for this intersection, then there should only be one element in the equivalence class of [{271}]? $\endgroup$ – Tempo Apr 10 '15 at 3:18
  • 1
    $\begingroup$ No, they are not: the OP is correct in saying that they are identified with cardinalities of subsets of $Y$. $\endgroup$ – Brian M. Scott Apr 10 '15 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.