Number of elements in an equivalence class

Question

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.

Answer 1

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

Answer 2

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.