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?

Improve this question
$\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$
    – Emil Jeřábek
    Commented 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$
    – Joel David Hamkins
    Commented Apr 28, 2015 at 20:02

1 Answer 1

Reset to default
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.)

Improve this answer
$\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$
    – Garabed Gulbenkian
    Commented 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$
    – Garabed Gulbenkian
    Commented 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 ♦
    Commented 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$
    – Garabed Gulbenkian
    Commented 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 ♦
    Commented May 4, 2015 at 22:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .