Question. Is there is a model of ZF set theory with a set $X$ that does not inject into the cardinals?

I use the term "cardinal" here in the ZF sense, so they are not necessarily well-orderable.

To be more precise, I am asking whether there is a model of ZF with a set $X$ for which there is no assignment $$a\mapsto B_a,$$ such that whenever $a\neq b$ are distinct elements of $X$, then $B_a$ and $B_b$ are not equinumerous.

If $X$ is well-orderable, then we may map the $\alpha^{th}$ element of $X$ to the cardinal $\aleph_\alpha$. So no model of ZFC will have such a set $X$ with no assignment. Thus, the question is about models of ZF where AC fails.

  • 2
    $\begingroup$ Is there a reason that you ask about ZF models, rather than the ZF provability of "every set injects into the cardinals"? Or perhaps more precisely, the provability of "every set is the domain of some function whose range contains no two elements in bijective correspondence"? $\endgroup$ – Matt F. May 21 '14 at 20:13
  • 2
    $\begingroup$ @Matt, by Gödel's completeness theorem, aren't these the same question? $\endgroup$ – Monroe Eskew May 21 '14 at 20:39
  • 2
    $\begingroup$ I asked it my way only because I think that there will be a counter example rather than a proof that all sets embed. $\endgroup$ – Joel David Hamkins May 21 '14 at 20:42
  • 3
    $\begingroup$ Annoying question, isn't it? I've been intrigued by a family of questions of which this is one, for years. The dual version asks whether for every $X$ there is a set $Y$ all of whose elements have different sizes, and such that $Y$ surjects onto $X$. $\endgroup$ – Andrés E. Caicedo May 21 '14 at 23:57
  • 3
    $\begingroup$ @Andres: Soon... soon... :-) $\endgroup$ – Asaf Karagila May 22 '14 at 0:00

This is a summary of my comments above showing that there is such a model of set theory with atoms (ZFA).

If $X$ and $B\colon a\mapsto B_a$ are as in the question, let me call $B$ an assignment function for $X$. The basic observation is that assignment functions do not like automorphisms.

Lemma 1: $\def\zfa{\mathrm{ZFA}}\zfa(F)$ proves that if $B$ is an assignment function for $X$, and $F$ is an automorphism of the universe such that $F(B)=B$, then $F(a)=a$ for every $a\in X$.

Proof: Since $X=\operatorname{dom}(B)$, we have $F(a)\in F(X)=X$. Moreover, $F(B_a)=B_{F(a)}$, hence the restriction $F\restriction B_a$ is a bijection between $B_a$ and $B_{F(a)}$. This implies $a=F(a)$ as $B$ is an assignment function.$\qquad\Box$

Now let us see what this gives for permutation models. I will first briefly recall the construction to fix the notation. We work in a model of ZFA with a set of atoms $A$. We fix a group of permutations $G\le\mathrm{Sym}(A)$, and a normal (i.e., closed under conjugation) filter $F$ of subgroups of $G$ which contains all point stabilizers $G_a=\{g\in G:g(a)=a\}$, where $a\in A$. Using $\in$-induction, every permutation $g\in G$ extends uniquely to an automorphism $\hat g$ of the universe. A set $X$ is symmetric if its stabilizer $G_X=\{g\in G:\hat g(X)=X\}$ is in $F$, and hereditarily symmetric if all elements of its transitive closure are symmetric. The class $M$ of all hereditarily symmetric sets is a transitive model of ZFA, and each $\hat g$ for $g\in G$ is an automorphism of $M$.

We need automorphisms satisfying replacement in Lemma 1. If $M\models\zfa(\hat g)$, then $g=\hat g\restriction A\in M$, and conversely, if $g\in M$, the construction of $\hat g$ by well-founded recursion can be carried out in $M$, so $\hat g$ is definable in $M$ with parameter $g$. Since $\hat f(g)=f\circ g\circ f^{-1}$, the stabilizer of $g$ is just the centralizer $C(g)$. Thus:

Lemma 2: For $g\in G$, $M\models\zfa(\hat g)$ iff $C(g)\in F$.

Note that if the trivial group $1$ is in $F$, then all sets are hereditarily symmetric, so the model trivializes.

Theorem: Let $M$ be a permutation model of ZFA defined using $G$ and $F$ as above. If $C(g)\in F$ for every $g\in G$, and $1\notin F$, then $M\models{}$“$A$ has no assignment function”.

Proof: Assume that $B\in M$ is an assignment function for $A$. On the one hand, $B$ is symmetric, so its stabilizer $G_B$ is in $F$. On the other hand, if $g\in G_B$, then $g=\mathrm{id}$ by Lemmas 1 and 2, thus $G_B=1$, contradicting the assumptions.$\qquad\Box$

Examples of models satisfying the conditions from the theorem are easy to find: for instance, fix a partition of $A$ into pairs, let $G$ be the group of permutations that respect the partition, and let $F$ be the filter generated by point stabilizers. Then $G$ is abelian (a direct product of two-element groups), so the condition on centralizers trivially holds, and $1\notin F$ as long as $A$ is infinite.

In view of Andres Caicedo’s comment above, let a dual assignment function for $X$ be a surjection $D\colon Y\to X$ such that elements of $Y$ have pairwise different cardinalities. Lemma 1 holds for dual assignment functions, too (if $F(D)=D$ and $x=D(y)\in X$, $F$ induces a bijection of $y$ and $F(y)$, hence $F(y)=y$, hence $F(x)=x$). Thus, under the assumptions of the theorem, $M$ also satisfies that $A$ has no dual assignment function.

  • $\begingroup$ I realized that “respect the partition” is ambiguous. I hope it would be clear from the context, but to be sure, I meant that each pair is mapped to itself. $\endgroup$ – Emil Jeřábek May 22 '14 at 17:32
  • $\begingroup$ I was under the impression that the theorem of Jech-Sochor gives an $\in$-isomorphism between any given permutation model of ZFA and a model $N$ of ZF, up to any desired level $\alpha$ in the cumulative hierarchy. Doesn't it imply that we can "transfer" your set $F$ into a model of ZF ? But I guess I am missing something since no one made the remark and I am far from an expert on the field. $\endgroup$ – Mathieu Baillif May 22 '14 at 20:39
  • $\begingroup$ The problem is that “$X$ has no assignment function” is an unbounded statement, $B$ could be found arbitrarily high in the hierarchy. $\endgroup$ – Emil Jeřábek May 22 '14 at 20:47

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.