An interesting question has arisen over at this
math.stackexchange
question
about two concepts of even in the context of infinite
cardinalities, which are equivalent under the axiom of
choice, but which it seems might separate when choice
fails.
On the one hand, a set $A$ can be even in the sense that it
can be split into pairs, meaning that there is a
partition of $A$ into sets of size two, or in other words,
if there is an equivalence relation on $A$, such that every
equivalence class has exactly two elements.
On the other hand, a set $A$ can be even in the sense that
it can be cut in half, meaning that $A$ is the union of
two disjoint sets that are equinumerous.
Note that if $A$ can be cut in half, then it can be split
into pairs, since if $A=A_0\sqcup A_1$ and $f:A_0\cong A_1$
is a bijection, then $A$ is the union of the family of
pairs $\{x,f(x)\}$ for $x\in A_0$. And this argument does
not use the axiom of choice.
Conversely, if $A$ can be split into pairs, and if we
have the axiom of choice for sets of pairs, then we may
select one element from each pair, and $A$ is the union of
this choice set and its complement in $A$, which are
equinumerous.
Thus, when the axiom of choice for sets of pairs holds,
then the two concepts of even are equivalent. Note also
that every infinite well-orderable set is even in both
senses, and so in ZFC, every infinite set is even in both
senses. My question is, how bad can it get when choice
fails?
-
Is there a model of ZF in which every infinite set can be
split into pairs, but not every infinite set can be cut in
half? -
Is there a model of ZF having at least one infinite set
that can be split into pairs, but not cut in half? -
What is the relationship between the equivalence of the two concepts of even and the axiom of choice for sets of pairs?
Best Answer
(I have removed my CW answer since it was irrelevant and somewhat wrong, I just did not know that back then.)
First we'll answer the easiest question: We shall construct a model with a 2-amorphous set, which is an amorphous set which can be partitioned into pairs but cannot be cut into two infinite sets.
We start with a model of ZFA where the set of atoms is countable (for instance), write it $A=\coprod_n P_n$ where the $P_n$ are pairs.
Now take $\mathscr G$ to be a group of permutations such that $\pi P_n = P_k$ (that is, the permutation respect this partition), along with the ideal of finite subsets for support. Let $\mathfrak A$ be the permutation model defined by those permutations and the chosen support.
Claim I: If $B\subseteq A$ is infinite and in the permutation model then only for finitely many $P_n$ we have $|P_n\cap B|=1$.
Proof: Assume by contradiction, let $E$ be a finite support of $B$ and $P_k=\{a,b\}$ a pair which meet $B$ at a single point (suppose $a\in B$), as well $P_k\cap E=\varnothing$. Define $\pi(a)=b, \pi(b)=a$ and $\pi(x)=x$ otherwise. It is clear that $\pi$ fixes $E$, but $\pi B\neq B$. $\square$
Claim II: If $B\subseteq A$ is infinite and in the permutation model, then it is cofinite.
Proof: Suppose otherwise, let $E$ be a support of $B$ and $F$ be a support of $A\setminus B$. We can assume without loss of generality that $E=F$ (take union of both otherwise). By the previous claim we have $\{a_k,b_k\}=P_k\subseteq B$ and $\{a_n,b_n\}=P_n\subseteq A\setminus B$ such that $E\cap (P_n\cup P_k)=\varnothing$. Take $\pi$ to be a permutation for which $\pi(x_k)=x_n, \pi(x_n)=x_k$ (for $x=a,b$) and the identity otherwise.
Again it is clear that $\pi$ fixes $E$ alas $\pi E\neq E$, which is a contradiction. $\square$
Claim III: The partition $\mathbb P = \{P_n\}$ is in the permutation model (however clearly not a countable set there).
Proof: It is clear that every permutation in our chosen group has $\pi(\mathbb P)=\mathbb P$. $\square$
Use any transfer theorem (Jech-Sochor, Pincus, etc.) to have this in a model of ZF, thus answering the question that it is in fact possible to have a set which can be split to pairs but not cut in half.
One can take instead a variation on the second Cohen model. In this model we add countably many real numbers indexed as $\{x_{n,\varepsilon,i}\mid n,i\in\omega,\varepsilon\in 2\}$. We then take $X_{n,\varepsilon}=\{x_{n,\varepsilon,i}\mid i\in\omega\}$ and $P_n=\{X_{n,0}, X_{n,1}\}$.
Cohen's took permutations of $\omega\times 2\times\omega$ which preserve the $P_n$'s. We can instead take permutations which only preserve the partition and have the same result as above.
This model, I believe should answer positively the first question (I cannot see why, yet).In this model we have that the collection of the $X_{n,\varepsilon}$ can be split into pairs, however the index set of these pairs need not be split into pairs itself. Indeed such splitting would induce a partition into sets of $4$ elements, which would also be splittable and so inducing a partition of $8$ elements, and so on to have every $2^n$ size of partition. I doubt that this is the case in the variant I have described above.
It also remains to check these properties on the set of all our generic reals - whether it is countable, or uncountable (but not well-orderable), and can that collection be split too?