Assume that we are working in ZF set theory without the Axiom of Choice. If S is an infinite set, let $S(f)$ denote the set of all finite subsets of $S$, let $S(I)$ denote the set of all infinite subsets of $S$ and let $\operatorname{Card}(S)$ denote the cardinal number of $S$.

Even though we can prove Cantor's theorem which states that the Power Set of $S$ always has a greater cardinal number than $\operatorname{Card}(S)$, could there exist an uncountable set $X$ such that we could not disprove the statement $\operatorname{Card}(X)=\operatorname{Card}(X(f))=\operatorname{Card}(X(I))$?

The answer would, of course, be negative if-without the Axiom of Choice-one could prove in ZF that, given any infinite set $S$, $\operatorname{Card}(S(I))$ is always greater than $\operatorname{Card}(S)$. Is this possible?

  • 2
    $\begingroup$ Unless I’m missing something, $|X|=|X(f)|=|X(I)|$ implies $|P(X)|\le2|X|$, and it is easy to see that $|X(f)|\le|X|$ implies $2|X|\le|X|$, so this is not possible. $\endgroup$ – Emil Jeřábek Apr 28 '15 at 19:15
  • 2
    $\begingroup$ One can also argue like this: if $X$ is infinite Dedekind finite, then $X$ is strictly smaller than $X(f)$, since it injects into $X(f)$ by the map $x\mapsto\{x\}$, and so if they were bijective than $X$ would be bijective with a strictly smaller set, a contradiction. $\endgroup$ – Joel David Hamkins Apr 28 '15 at 20:02

For the first equality, the answer is true.

It is quite easy to construct examples where the set of finite subsets is strictly larger. For example if $X$ is an infinite Dedekind-finite set which is the countable union of finite sets (e.g. Russell socks sets), then the set $X(f)$ is not Dedekind-finite anymore, since there is a countably infinite subset to it.

Finally, $\operatorname{Card}(X)=\operatorname{Card}(X(I))$ is provably false, unless $X=\varnothing$, in which case both cardinals are $0$. And if $X$ is non-empty finite, then $X(I)$ is empty while $X$ is not, so there is no equality.

If $\operatorname{Card}(X)=\operatorname{Card}(X(I))$, then $\operatorname{Card}(\mathcal P(X))=\operatorname{Card}(X(I))+\operatorname{Card}(X(f))=\operatorname{Card}(X)+\operatorname{Card}(X(f))$.

But since if $X$ is infinite, then there is at least an injection from the finite subsets to the infinite subsets: $A\mapsto X\setminus A$. So it follows that $\operatorname{Card}(X(f))=\operatorname{Card}(X(I))$ so we have:

$$\operatorname{Card}(\mathcal P(X))=2\cdot\operatorname{Card}(X)$$

But this is a contradiction, since if $\operatorname{Card}(X)>4$, then $$2\cdot\operatorname{Card}(X)<2^{\operatorname{Card}(X)}=\operatorname{Card}(\mathcal P(X)).$$ (See here for a sketch of the proof of that last inequality.)

  • $\begingroup$ Thanks for the neat proof-in ZF without the Axiom of Choice-that CARD(X(I)) is greater than CARD(X) when X is infinite. $\endgroup$ – Garabed Gulbenkian Apr 29 '15 at 20:52
  • $\begingroup$ In ZF set theory without the Axiom of Choice, there exist infinite sets X which are neither Alephs nor Dedekind-finite. Is it still true for such sets that CARD(2^X) is greater than 2*CARD(X)? $\endgroup$ – Garabed Gulbenkian Apr 30 '15 at 19:09
  • $\begingroup$ Does the last paragraph uses anywhere that the set is Dedekind finite? Only that it has five different elements. $\endgroup$ – Asaf Karagila Apr 30 '15 at 21:40
  • $\begingroup$ You are right. I was finally able to digest all the steps of your proof. Proving theorems about all infinite cardinal numbers can be quite tricky when the Axiom of Choice is not available. $\endgroup$ – Garabed Gulbenkian May 1 '15 at 19:38
  • 1
    $\begingroup$ I noticed a minor mistake in the answer; it is possible that $\operatorname{Card}(X)^2\nleq \operatorname{Card}(2^X)$; but it's always provable that if $X$ has more than four elements, then $\operatorname{Card}(2^X)\nleq\operatorname{Card}(X)^2$. We only need the one direction, as I point out in that Math.SE answer; so the second one has no business being here. $\endgroup$ – Asaf Karagila May 4 '15 at 22:11

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.