3
$\begingroup$

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?

$\endgroup$
2
  • 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$ Apr 28, 2015 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$ Apr 28, 2015 at 20:02

1 Answer 1

5
$\begingroup$

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

$\endgroup$
6
  • $\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$ Apr 29, 2015 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$ Apr 30, 2015 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, 2015 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$ May 1, 2015 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, 2015 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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