Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to prove the following statement (an exercise in Bourbaki's Set Theory):

If $E$ is an infinite set, the set of subsets of $E$ which are equipotent to $E$ is equipotent to $\mathfrak{P}(E)$.

As a hint, there is a reference to a proposition of the book, which reads:

Every infinite set $X$ has a partition $(X_\iota)_{\iota\in I}$ formed of countably infinite sets, the index set $I$ being equipotent to $X$.

I don't have any idea how that proposition might help.

If $E$ is countable, then a subset of $E$ is equipotent to $E$ iff it is infinite. But the set of all finite subsets of $E$ is equipotent to $E$. So its complement in $\mathfrak{P}(E)$ has to be equipotent to $\mathfrak{P}(E)$ by Cantor's theorem. Hence the statement is true if $E$ is countable. Unfortunately, I don't see a way to generalize this argument to uncountable $E$.

I'd be glad for a small hint to get me going.

share|improve this question
6  
I just want to make a comment that Bourbaki is not the best source for set theory. –  Asaf Karagila May 20 '11 at 19:19
1  
Are you assuming the Axiom of Choice? –  Arturo Magidin May 20 '11 at 19:19
1  
@Arturo: You have too. It is not true otherwise. –  Asaf Karagila May 20 '11 at 19:20
2  
@Stefan: That might be, but there are better sources of set theoretic exercises and readings around. –  Asaf Karagila May 20 '11 at 19:36
2  
@Asaf: I am genuinely curious to know how you can assert that Bourbaki is not the best source for set theory (note the is, no I think, no might not be here, just plain is) and at the same time admit that you have never read anything by Bourbaki. Is there more than hearsay and automatic bashing here? –  Did May 20 '11 at 20:19

2 Answers 2

up vote 9 down vote accepted

Using the axiom of choice, every infinite set $X$ can be divided into two disjoint sets $X_0\sqcup X_1$, both of which are equinumerous with $X$. (Just well-order $X$, and take every other point in the enumeration.)

Now, consider all sets of the form $X_0\cup A$ for any $A\subset X_1$. There are $2^X$ many such $A$ and hence $2^X$ many such sets, and each is equinumerous with the original set $X$. So we've got $2^X$ many sets as desired, and there cannot be more than this, so this is the precise number.

Incidently, the stated answer to this question does in fact depend on the axiom of choice, since it is known to be consistent with $ZF+\neg AC$ that there are infinite Dedekind finite sets, and these are not equinumerous with any proper subsets of themselves. So for such an infinite set $X$, there would be only one subset to which it is equinumerous.

share|improve this answer
    
This reminds me of the answer I gave here: math.stackexchange.com/questions/3097/… –  Asaf Karagila May 20 '11 at 19:28
    
Thank you very much! –  Stefan Walter May 20 '11 at 20:00

Another approach would make use of the fact that $\kappa_1 + \kappa_2 = \max(\kappa_1,\kappa_2)$ when $\kappa_1,\kappa_2$ are cardinals at least one of which is infinite. From this it follows that, for any subset of $S \subset X$, either $S$ or its complement has cardinality $|X|$. Since more straightforward cardinal arithmetic shows there are as many complementary pairs of subsets as there are subsets of $X$, we get the result.

By the way, JDH's approach could allow you to show the (slightly) stronger statement that there are $2^X$ sets $S \subset X$ with both of $S$ and $X - S$ equipotent to $X$. Simply write $X$ as a disjoint union $X = X_0 \cup X_1 \cup X_2$ with all parts equipotent to $X$ and consider subsets of the form $X_0 \cup A$ where $A \subset X_1$.

An interesting follow-up question might be to see if you can produce $2^X$ sets $S \subset X$ so that $|S|=|X|$, but $|X-S| < |X|$.

share|improve this answer
2  
Regarding your last follow-up question, the number of such $S$ is precisely $2^{\lt|X|}$, which can be less than $2^{|X|}$ in size. For example, $2^{\lt\omega}=\omega$, and more generally, it is quite common that $2^{\lt\kappa}=\kappa\lt 2^\kappa$, although it is also consistent that $2^{\lt\kappa}=2^\kappa$, for example, under $MA_{\omega_1}$ it is true that $2^{\lt\omega_1}=2^{\omega_1}$. –  JDH May 21 '11 at 0:33
    
@JDH: Thanks! I did know my question was a trap, but your consistency comment is very interesting! –  Mike F May 23 '11 at 5:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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