Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
5  
Joel: There is a nice reference. The theme of your question is precisely addressed in the paper by Blass et al. I mention in this answer: mathoverflow.net/questions/63596/… –  Andres Caicedo Jul 4 '11 at 14:40
    
Thanks very much, Andres! Perhaps you can post as an answer? –  Joel David Hamkins Jul 5 '11 at 10:51
2  
@Andres: Thanks for pointing out my paper. Having often benefited from the convention in mathematics that authors are listed in alphabetic order, I must, in fairness, point out that this paper is "Blair et al." My co-authors are David Blair (who did part of this work in an REU project) and Paul Howard. –  Andreas Blass Jul 6 '11 at 0:14
    
So, this will show my ignorance of these things. It seems that in the split-in-half case, you suppose that your set comes with a partition into two pieces, $A_0$ and $A_1$, and with a distinguished bijection $A_0 \overset\sim\to A_1$. In the split-into-pairs case, you suppose that your set comes with a partition, and that "every equivalence class has exactly two elements". I've never known how to understand the latter style claim. Certainly you are not saying that "every equivalence class comes with a distinguished bijection to $\lbrace 0,1\rbrace$, as then I think you have (continued) –  Theo Johnson-Freyd Jul 7 '11 at 0:50
2  
@Theo: I'd omit "distinguished" in both versions. In the cut-in-half case, from the mere existence of a bijection, we can conclude the existence of a splitting into pairs. Every bijection can be explicitly converted into a partition into pairs. (If we had a distinguished bijection, that would give a distinguished partition into pairs, but that's not required by the definition of split-into-pairs.) On the other hand, from a partition into pairs and (therefore) the existence of bijections to {0,1} for each of these pairs, I can't conclude much without choice. –  Andreas Blass Jul 7 '11 at 2:32

2 Answers 2

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

share|improve this answer
    
Isn't the model you describe in the last two paragraphs the same as the one used to prove the Jech-Sochor and Pincus transfer theorems? I guess the general proof of the transfer theorems would use larger cardinals in place of $\omega$, but that would be needed only to transfer statements that look at higher ranks in the permutation model. –  Andreas Blass Dec 19 '11 at 21:17
    
@Andreas: It is possible, yes. However the assertion that every infinite set is splittable would be an unbounded statement, so even if I did come up with a way to prove that in the permutation model - I don't see an immediate argument why any of the transfer theorems (which I know, at least) can take it into a model of ZF. –  Asaf Karagila Dec 19 '11 at 21:23

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 Conways work on Effective implications between the "finite" choice axioms

share|improve this answer
    
Thanks for your answer Aaron. Regarding your question (2), for a set $V$ to be cut in half means that there are disjoint sets $V_1$ and $V_2$ whose union is $V$, such that there is a bijection between $V_1$ and $V_2$. You don't need AC to pick this bijection, since this is just one choice. I agree completely with Andreas's remarks on Theo's comment. –  Joel David Hamkins Dec 19 '11 at 20:45
    
So could we say that for a set $S=\lbrace a,b \rbrace$ that the set $V=\lbrace (a,b),(b,a) \rbrace$ can be split into a pair of disjoint sets $(\lbrace(x,y)\rbrace,\lbrace(y,x)\rbrace)$ where $x$ is either $a$ or $b$? and could we say that then we had a made a choice of $x$ (say) from $S$. –  Aaron Meyerowitz Dec 19 '11 at 23:27
    
Well, in this case, yes, but choice on finite families is provable without any extra axioms, and we could have equivalently asked for an unordered pair when splitting in half, rather than an ordered pair (it is equivalent). Nevertheless, I share your sense that the general possibility is related to the principle of choice for pairs (and this is my third question), but don't see a proof yet. –  Joel David Hamkins Dec 20 '11 at 2:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.