# Does ZF prove that there are more cardinals than elements of any set?

In ZFC, it is easy to prove there are more cardinals than elements of any set. Specifically, given a set $$X$$, pick a well-ordering of $$X$$, and then you can inject $$X$$ into the cardinals by mapping its $$\alpha$$th element to $$\aleph_\alpha$$.

My question is whether this can be proved in ZF (where "cardinal" is interpreted in the appropriate way in the absence of choice, not restricted to well-ordered cardinalities). To be precise, can ZF prove the following?

For any set $$X$$, there exists a function $$f$$ on $$X$$ such that for any distinct $$x,y\in X$$, there is no bijection between $$f(x)$$ and $$f(y)$$.

I imagine the answer is no but don't really know anything about how you could prove such a global statement about the cardinals in a model of ZF in order to get a counterexample.

• @QiaochuYuan Am I missing something, or does $Y=\mathcal{P}(\bigcup_{x\in X}f(x))$ do the job immediately for your version of the question? Jan 20 at 6:53
• @bof: Noah asked this in an even more restricted way. Jan 20 at 9:02
• I vaguely recall learning that if there are any Dedekind-finite infinite cardinals then there are continuum many of them. Is that true or is it a false memory?
– bof
Jan 20 at 10:41
• @Noah: That's not false. It's an easy theorem of Tarski. See also my very first blog post Jan 20 at 20:23
• @bof: That's correct, if $A$ is DF, let $S(A)$ be the set of injective finite sequences from $A$, then $S(A)$ is DF as well. Then for every $X\subseteq\omega$ consider $\{f\in S(A)\mid\operatorname{dom}(f)\in X\}$. Finally, take a chain of type $[0,1]$ in $\mathcal P(\omega)$ and consider the $S_X$'s on that chain. Because they are DF, the inclusions mean different cardinalities. Jan 20 at 20:25

Start with a model of ZFA with a countable set $$A$$ of atoms. Label the elements of $$A$$ as $$a_n^i$$ with $$n<\omega$$ and $$i<2$$. Think of $$a_n^0, a_n^1$$ of pairs and the set $$A$$ as an infinite set of these pairs. Let $$G$$ be the group of permutations $$\pi$$ of $$A$$ that maybe swap pairs, but do not do anything else, i.e. $$\pi(a_n^i)\in\{a_n^i, a_n^{1-i}\}$$ for all $$n<\omega, i<2$$. Let $$\mathcal F$$ be the filter generated by $$\mathrm{fix}_G(E)$$, where $$E$$ ranges over the finite subsets of $$A$$. This induces a permutation model $$\mathcal V$$ of hereditarily symmetric sets. Note that the group $$G$$ is commutative. This has the following consequence: As usual, any $$\pi\in G$$ exptends to an automorphism $$\pi^+$$ of $$\mathcal V$$. If $$X\in\mathcal V$$ then $$\pi^+\upharpoonright X:X\rightarrow\pi^+(X)$$ is a bijection that lies in $$\mathcal V$$. The reason being that $$\pi^+$$ commutes with any other $$\mu^+$$, $$\mu\in G$$, which is enough to see that $$\pi^+\upharpoonright X$$ is (hereditarily) symmetric.
If $$f:A\rightarrow\mathcal V$$ is a function in $$\mathcal V$$, then for cofinitely many $$n$$, $$f(a_n^0)$$ and $$f(a_n^1)$$ cannot be significantly different (as that would violate symmetry). In particular they cannot have differnt size: Let $$\mathrm{fix}_G(E)$$, $$E\subseteq A$$ finite, be a support for $$f$$. Find any $$n<\omega$$ such that $$a_n^0, a_n^1\notin E$$ and let $$\pi$$ be the permutation of $$A$$ that swaps $$a_n^0, a_n^1$$ and is the identity everywhere else (observe that $$\pi\in\mathrm{fix}_G(E)$$). Then $$f(a_n^1)=f(\pi(a_n^0))=\pi(f)(\pi(a_n^0))=\pi(f(a_n^0))$$ Now $$\pi^+\upharpoonright f(a_n^0)$$ is a bijection between $$f(a_n^0)$$ and $$\pi(f(a_n^0))=f(a_n^1)$$ in $$\mathcal V$$.