MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are two questions here, an explicit one, and another (more vague) one that motivates it:

I am pretty certain the following should have a negative answer, but at the moment I'm not seeing how to argue about this and cannot locate an appropriate reference.

In set theory without choice, suppose $X$ is an infinite set such that for every positive integer $n$, we can split $X$ into $n$ (disjoint) infinite sets. Does it follow that $X$ can be split into infinitely many infinite sets? What would be a reasonably weak additional assumption to ensure the conclusion.

("Reasonably weak" would ideally be something that by itself does not suffice to give us that $X$ admits such a splitting, but I am flexible.)

This was motivated by a question at Math.SE, namely whether an infinite set can be partitioned into infinitely many infinite sets. This is of course trivial with choice. In fact, all we need to split $X$ is that it can be mapped surjectively onto ${\mathbb N}$.

However, without choice there may be counterexamples: A set $X$ is amorphous iff any subset of $X$ is either finite or else its complement in $X$ is finite. It is consistent that there are infinite amorphous sets. If $X$ is infinite and a finite union of amorphous sets, then $X$ is a counterexample. The question is a baby step towards trying to understand the nature of other counterexamples.

Note that any counterexample must be an infinite Dedekind finite (iDf) set $X$. One can show that for any iDf $X$, ${\mathcal P}^2(X)$ is Dedekind infinite. For any $Y$, if ${\mathcal P}(Y)$ is Dedekind infinite, then $Y$ can be mapped onto $\omega$ (this is a result of Kuratowski, it appears in pages 94, 95 of Alfred Tarski, "Sur les ensembles finis", Fundamenta Mathematicae 6 (1924), 45–95). As mentioned above, our counterexample $X$ cannot be mapped onto $\omega$, so ${\mathcal P}(X)$ must also be an iDf set.

The second, more vague, question asks what additional conditions should a counterexample satisfy.

share|cite|improve this question
If X is infinite, then 2^X can be mapped onto omega. This is provable in ZF and has nothing to do with X being Dedekind finite. – Ricky Demer Jan 5 '11 at 2:18
@Ricky: Sure. That was poorly phrased. I've changed the sentence into what I really meant. – Andrés Caicedo Jan 5 '11 at 2:53
Could one of the compactness theorems of logic be used here? – Michael Hardy Jan 6 '11 at 7:47
@Michael: I am not sure I see how. Given $X$ you would need to devise a theory (presumably with infinitely many relational symbols that would play the role of the partition) for which there is a model with universe equipotent to $X$. This seems very delicate (we do not have the Löwenheim–Skolem theorem without choice). Moreover, we need to ensure that the theory has no models of size $Y$ for any amorphous $Y$. Plus, we would need to anticipate (to set up the language!) the infinite set $Z$ such that $X$ is a union indexed by $Z$ of infinite sets (I think $Z$ doesn't need to be countable). – Andrés Caicedo Jan 6 '11 at 7:58
@Michael: Given $X$, the other possibility I can think of would be to have the language contain a relational symbol $R$ and a function symbol $f$, and set up a theory that would have a model of the form $X\sqcup Y$ where $R$ is interpreted by $X$, $Y$ is infinite, and $f\upharpoonright X$ is a function from $X$ onto $Y$ with the preimage of each element of $Y$ being infinite. Again, the lack of an appropriate version of Löwenheim–Skolem is a serious issue here. – Andrés Caicedo Jan 6 '11 at 8:01
up vote 7 down vote accepted

Define a permutation model of ZFA as follows. Starting as usual (Ch 4 of Jech's Axiom of Choice) from a well-founded model $\mathcal M$ of ZFAC with infinite set $A$ of atoms, let $G$ be the group of all permutations of $A$; so $G$ can be identified with the group of all automorphisms of $\mathcal M$. For each finite partition $T$ of $A$, let $G_{(T)}$ be the group of permutations in $G$ which fix each element of $T$ (meaning $\sigma\in G_{(T)}$ iff for each $B\in T$ we have that $b\in B$ implies $\sigma b\in B$). Let $\mathcal F$ be the set of subgroups of $G$ which contain $G_{(T)}$ for some finite partition $T$; then $\mathcal F$ is a normal filter of subgroups of $G$, and contains the stabilizer subgroup of each atom in $A$. As usual, a set or atom $x\in\mathcal M$ is called symmetric if its stabilizer subgroup is a member of $\mathcal F$, and we let $\mathcal N$ be the class of hereditarily symmetric elements of $\mathcal M$.

Then $\mathcal N$ is a model of ZFA providing a counterexample. The model $\mathcal N$ has all the finite partitions of $A$ found in $\mathcal M$, but every infinite partition of $A$ into non-singletons would fail to be symmetric.

share|cite|improve this answer
Hi Eric. Welcome to MO! Many thanks; I definitely need to become more comfortable with this technique. – Andrés Caicedo Jan 9 '11 at 15:14
Hello and thanks. Yes, if you like this kind of question, then the technique is worthwhile. But permutation groups may not be necessary. If you prefer, you could think about $L(S)$, where, in a model of ZFAC, $S$ is the set of finite partitions of the set of atoms. (Does anyone in fact prefer to think of it that way?) So far, I don't have an answer to your second question. – Eric Hall Jan 9 '11 at 16:26

Your Answer


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.