On the difference between two concepts of even cardinalities: Is there a model of ZF set theory in which every infinite set can be split into pairs, but not every infinite set can be cut in half?

Question

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?

Answer 1

(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?

Answer 2

Here is a somewhat informal example which seems relevant: We know that the binomial coefficient $\binom{n}{2}=\frac{n(n-1)}2$ is an integer because the numerator is even. One explanation is "well, $n$ is even or else $n-1$ is even so either way the numerator is even." A combinatorial view is that this says that $(\mathbf{n})_2$ is even where $\mathbf{n}=\lbrace0,1,\cdots,n-1\rbrace$ and for each set $S$ we let $(S)_2=\lbrace(a,b) \mid a \ne b\rbrace. $

In what sense is it true that $(S)_2$ is "even" for arbitrary sets $S?$ In particular is it different for the two notions of "even"?

There is an obvious way to split $(S)_2$ into couples. (I changed the phrase since the elements of $(S)_2$ are themselves pairs) If we assume that $S$ has a distinguished order then there is a natural way to cut $(S)_2$ in half. Otherwise there is not a clear way to do it.

Consider the question

In what sense is $S \cup (S \times S)$ even?

We can couple $s$ with the pair $(s,s)$ and treat the remaining pairs as before. Again, cutting in half seems less natural.

I am not as sure just how tie this into formal models of ZF. (topoi? equivariant sets?) Maybe Asaf's answer which deserves closer scrutiny than I have given it.

Later thoughts

1. It would seem to me that saying $(S)_2$ can always be cut in half should be equivalent to the axiom of choice for 2-element sets. I suppose that this is not so clear because it depends on the intuition that $(a,b)$ and $(b,a)$ would never be in the same half. It is hard to imagine how they could be if we have no special knowledge about $S$ but maybe it does not follow axiomatically.

2. I don't think that this is what Theo was asking about in his comment, but does cutting $V$ in half mean that we have an ordered pair $(V_1,V_2)$ of disjoint sets with union $V$ and a bijection OR does it mean that we have a set $\lbrace Y,Z\rbrace$ of disjoint sets with union $V$ and a bijection? In other words, does it say that we have a directed graph with vertex set $V$ and total degree (in plus out) $1$ or does it mean we have an undirected graph with vertex set $V$ regular of degree 1? In the former case we do have choice for pairs.

3. I am reminded of John Conway's work on Effective implications between the "finite" choice axioms