19
$\begingroup$

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.

$\endgroup$
13
  • 2
    $\begingroup$ @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? $\endgroup$ Jan 20 at 6:53
  • 1
    $\begingroup$ @bof: Noah asked this in an even more restricted way. $\endgroup$
    – Asaf Karagila
    Jan 20 at 9:02
  • 1
    $\begingroup$ 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? $\endgroup$
    – bof
    Jan 20 at 10:41
  • 2
    $\begingroup$ @Noah: That's not false. It's an easy theorem of Tarski. See also my very first blog post $\endgroup$
    – Asaf Karagila
    Jan 20 at 20:23
  • 2
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila
    Jan 20 at 20:25
6
$\begingroup$

At least ZFA cannot prove this assertion. The model constructed here should be the standard model of ZFA where choice for families of sets of size 2 fails.

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

I am not quite sure at the moment how to turn this into a model of ZF with the same property...

$\endgroup$
3
  • $\begingroup$ The problem with adding Cohen reals and treating them as atoms is that Cohen reals have an innate linear order, whereas atoms do not. So in lieu of atoms you need to have an infinite set of Cohen reals per atom. $\endgroup$
    – Asaf Karagila
    Jan 20 at 20:22
  • $\begingroup$ You are totally right! These symmetric extensions always confuse me. For the moment I retract the ZF version (after thinking through it more carefully there are some problems that dont come up in the ZFA version which I dont know how to fix... :( ) $\endgroup$ Jan 20 at 21:43
  • $\begingroup$ I'll take a look tomorrow. Maybe I'll have an idea. $\endgroup$
    – Asaf Karagila
    Jan 21 at 1: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.