3
$\begingroup$

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.

  • 6
    I just want to make a comment that Bourbaki is not the best source for set theory.2011-05-20
  • 1
    Are you assuming the Axiom of Choice?2011-05-20
  • 1
    @Arturo: You have too. It is not true otherwise.2011-05-20
  • 0
    @Arturo: Yes. @Asaf: I'm aware of that, I'm doing the exercises just for fun.2011-05-20
  • 2
    @Stefan: That might be, but there are better sources of set theoretic exercises and readings around.2011-05-20
  • 0
    @Asaf: I don't think there is an objective truth in this matter, but in my view the Bourbaki exercises are of a very high quality and not in the least as dry as the text. Have you ever had a closer look at them? (I can only speak of Chapter 3, the first two chapters really look extremely boring.)2011-05-20
  • 0
    @Stefan: I have to admit that I have never read anything by Bourbaki. I do know that they approach things from a proto-categorical view which I am not a fond of. At all. Amusingly enough, just today I read Mathias' "*The Ignorance of Bourbaki*". Very interesting text about the set theoretical approach of the group.2011-05-20
  • 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?2011-05-20
  • 0
    @Didier: Yes, it is hearsay and it is somewhat of less professional. However I do not recall a *single* logician or set theorist amongst the Bourbaki group. I am aware that Azriel Levy, Thomas Jech and several other good reads in set theory have been written by actual set theorists, and were the choice for many set theorists when designing a course. So perhaps I am not the rightmost person for this comment. It does seem, however, this it does somewhat reflect the set theoretic spirit, and since "Bourbaki is dead" this will never be corrected.2011-05-20
  • 0
    @Asaf: Two facts. First, the *Livre I* of the *Éléments de mathématique* is called *Théorie des ensembles* and it was the first volume of the collection to be written and published. Second, this volume of the *Éléments*, and every other one, are available on the web http://portail.mathdoc.fr/archives-bourbaki/ hence nothing should prevent you to reach your own judgement.2011-05-20
  • 1
    Meanwhile, one may find Adrian Mathias' articles here http://www.dpmms.cam.ac.uk/~ardm/, including some riotous essays concerning Bourbaki's logical system and the Bourbaki set theory specifically.2011-05-20
  • 0
    @Didier: My French is a wee bit rusty. And regardless to whether or not I read it. I do see the actual results in the field, not many set theorists that I know have read Bourbaki in depth at all. Many of those who did read Bourbaki occasionally clash with set theorists on key issues, e.g. definition of functions (cf. http://mathoverflow.net/questions/31358/31508#31508 and http://mathoverflow.net/questions/30381 for some discussion). Whether or not it is a good read, it seems to be having some undesired results. By that virtue alone it seems likely to recommend a different read for set theory.2011-05-20
  • 0
    @Asaf: Thanks for the links (actually, the second one).2011-05-20

2 Answers 2

9

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.

  • 0
    This reminds me of the answer I gave here: http://math.stackexchange.com/questions/3097/counting-equivalence-relations/3100#31002011-05-20
2

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|$.

  • 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}$.2011-05-21
  • 0
    @JDH: Thanks! I did know my question was a trap, but your consistency comment is very interesting!2011-05-23