How to decompose an infinite set into two isomorphic ones without choice? - MathOverflow

How to decompose an infinite set into two isomorphic ones without choice?

2011-05-01T09:58:10Z

Is it provable in ZF that each infinite set $A$ can be partitioned into two sets $B$ and $C$ which are isomorphic to each other, i.e., there is a bijective map from $B$ to $C$?

Answer by Apostolos for How to decompose an infinite set into two isomorphic ones without choice?

2011-05-01T12:47:17Z

No it's not, you need to have at least some choice, for example that for every set $A$ we have $|A|+|A|=|A|$. For every cardinal $\kappa$, using ZFA with $\kappa^+$ atoms, you can create a permutation model where $AC_\kappa$ (and $DC_\kappa$) hold but there doesn't exist a derangement of the atoms. This of course is enough to show that the negation of what you are looking for is consistent relative to ZF since if what you state were true then you would be able to find a derangement for every set by sending each element of $B$ to its image through the bijection and every element of $C$ to its image through the inverse of the bijection.

The idea behind the construction is as follows: Let $\mathcal{G}$ be the group of permutations of the atoms $\mathcal{A}$ and let $\mathcal{F}$ be a normal filter of the group of the permutations of the atoms that is generated by the sets $\{\pi\in\mathcal{G} : \pi_{\upharpoonright E}=id\}$ where $E\subset\mathcal{A}$ and $|E|\leq\kappa$. Observe that this filter is $\kappa^+$-complete since $\kappa^+$ is regular.

Given a set $x$ inside the permutation model with size $\leq\kappa$ it's easy to see that you can find a support for its choice function (the union of the supports of the elements of $x$ plus the union of the supports of the images) and thus the function is inside the permutation model. On the other hand assume that a derangement of $\mathcal{A}$, $f$, is in the permutation model and let $E$ be its support. Then let $\pi$ be the identity on $E$ and for $a,b,c,d\in\mathcal{A}\setminus E$ such that $f(a)=b$ and $f(c)\neq d$ let $\pi(a)=c$ and $\pi(b)=d$ (and let the rest of $\pi$ be arbitrary). Then $\pi(f)=f$ but $\pi(f)(\pi(a))=\pi(f(a))=d\neq f(c)$, a contradiction.

Unfortunately I am unaware of how much choice exactly is needed.

Answer by Andres Caicedo for How to decompose an infinite set into two isomorphic ones without choice?

2011-05-01T15:44:19Z

To complement Apostolos's answer:

I think you will find the following paper interesting: "Divisibility of Dedekind Finite Sets", by Blass, Blair, and Howard (Journal of Mathematical Logic 5 (2005) 58-74).

A Dedekind finite set $A$ is one where every proper subset has strictly smaller cardinality. This is equivalent to: ${\mathbb N}$ does not inject into $A$. Clearly, any subset of such an $A$ is also Dedekind finite. In particular, we cannot have $A=B\sqcup C$ with $|B|=|C|=|A|$. Note that if $A$ is Dedekind infinite, it has a subset (a copy of ${\mathbb N}$) that can be partitioned as required. However, that $A$ is Dedekind finite does not guarantee a negative answer to your question since, obviously, finite unions of Dedekind finite sets are Dedekind finite. (That it is consistent with ZF that there are infinite Dedekind finite sets is a basic result, you can find many examples in Jech's book "The axiom of choice", or looking at the references of Howard and Rubin "Consequences of the axiom of choice". See also their companion website.)

The paper I mentioned (available from Blass' webpage) studies two notions of divisibility of an infinite Dedekind finite set $A$ by a positive integer $n$: Whether $A$ can be partitioned into sets of size $n$ (this is the main object of study of the paper), or whether $A$ can be partitioned into $n$ sets of equal size. This latter notion is referred to as "strong divisibility", the former is "divisibility". You are asking about strong divisibility by 2.

This is an interesting notion. For example, their Theorem 3.5 is that if both $A$ and $A\sqcup\{0\}$ are strongly divisible by 3, then $A$ is Dedekind infinite. The exact relation between strong divisibility and divisibility is their Theorem 6.1: $A$ is strongly divisible by $n$ iff $A$ is divisible by $n$ and, moreover, there is a partition of $A$ into sets of size $n$ and a function that assigns to each piece a linear ordering.

Since strong divisibility implies divisibility, one can replace your question with the more general one of whether $A$ can be partition into doubletons. Their theorem 3.4 is that if both $A$ and $A\sqcup\{0\}$ are divisible by $2$, then $A$ is Dedekind infinite. It follows that in any model of set theory where there are infinite Dedekind finite sets there are counterexamples to your question.

There is quite a bit of freedom with respect to "divisibility". For example, their Theorem 4.3 is that it is consistent to have a Dedekind finite $A$ whose power set is divisible by all positive integers. Also, their Theorem 5.1 is that, for any $D\subseteq{\mathbb N}\setminus\{0,1\}$ , it is consistent to have a Dedekind finite $A$ such that if $n\gt 1$, then $A$ is divisible by $n$ iff $n\in D$.

On the other hand, if there are no infinite Dedekind finite sets, your question becomes more delicate.

The statement "For all infinite $A$, $|A|=2|A|$", mentioned in Apostolos's answer, is form 3 in the Howard-Rubin book. It is a result of Howard and Yorke ("Definitions of finite", Fund. Math., 133 (1989), 169-177) that this is equivalent to the following weakening: For all infinite $X$, if ${\mathcal P}(X)$ is Dedekind infinite, then $2|X|=|X|$.

Even just looking at a further weakening of this is interesting: Assume that for all infinite $X$, if ${\mathcal P}(X)$ is Dedekind infinite, then $X$ is divisible by 2. It follows from the results mentioned above that any such $X$ must be Dedekind infinite, as both $X$ and $X\sqcup\{0\}$ would be divisible by 2. But then it follows that there are no infinite Dedekind finite sets. This is because, provably in ZF, for any infinite $X$, ${\mathcal P}({\mathcal P}(X))$ is Dedekind infinite. But then it follows from the argument just mentioned that ${\mathcal P}(X)$ is Dedekind infinite, and therefore so is $X$.

(That form 3 implies the nonexistence of infinite Dedekind finite sets was previously known, by a different route.)

Now, that there are no infinite Dedekind finite sets is not enough to imply form 3. (See the Howard-Rubin book for a counterexample, or look at the construction in Apostolos's answer.) But, at the moment, I don't know of a natural condition weaker than form 3 that, in the absence of infinite Dedekind finite sets, ensures a positive answer to your question.

Answer by Todd Trimble for How to decompose an infinite set into two isomorphic ones without choice?

2011-05-01T19:33:50Z

The question seems interesting to me. There's an old result of Tarski that the axiom of choice is a consequence of ZF + the assertion "every infinite set $u$ is in bijection with $u^2$". A proof of this fact is given in Stoll's Set Theory and Logic; see page 126 (in the Dover edition).

However, exercise 10.5 on that page reads, "It is not known whether the formula $2u = u$, which follows from the axiom of choice (Theorem 9.5), implies the axiom of choice. Attempt a proof of this." Stoll's book was written some time ago, but I suspect this implication is still not known.

Answer by Andreas Blass for How to decompose an infinite set into two isomorphic ones without choice?

2011-05-01T19:38:23Z

To answer the question in Todd's answer, the principle $2|A|=|A|$ for all infinite $A$ is strictly weaker than AC. This difficult result was proved by Halpern and Howard for ZFA (allowing atoms) and by Sageev for ZF.