Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite.

In ZF, can you prove that every infinite set is the union of two disjoint infinite set? If not, is this property equivalent to anything well known over ZF?

I can't seem to prove this without assuming some form of choice. Thanks for any help you can provide.

share|improve this question
    
I don't see why [reverse-math] or [proof-theory] fit in here... –  Asaf Karagila Aug 28 '11 at 6:24
    
Although Reverse Math usually works in second order arithmetics, the question is to determine the proof theoretic strength of some statement using some other collection of axiom. The nature of the question is very much like those of reverse math. –  William Aug 28 '11 at 6:38
2  
I only see a question about splitting infinite sets in ZF with or without choice. Nothing about proof theory or reverse mathematics. –  Asaf Karagila Aug 28 '11 at 6:43
    
The question is not so much to prove this statement in ZF + something but to determine exactly what is needed to prove the statement. That ZF + X prove disjoint property and ZF + disjoint union propery can prove X. This sort of question is very much like "over RCA, X is equivalent to Y" that is often seen in reverse math. –  William Aug 28 '11 at 7:17
1  
Regardless to that. This is not a question about reverse math, nor about proof theory. This is a question about set theory, the axiom of choice, and perhaps cardinals. Your argument, applied to other issues can be used to say that many of the questions are reverse mathematics because we wish to determine the required assumptions for some theorem. Or that everything is [logic] because we ask whether or not something follows from an assertion or a theory, and how. –  Asaf Karagila Aug 28 '11 at 7:23

1 Answer 1

up vote 15 down vote accepted

Yes. You need some choice. The assertion "Every infinite set has a countable subset" is more than enough, and we can use even less (although people often go with more and assume axiom of countable choice).


A set is called Dedekind infinite when it has a proper subset with the same cardinality. That is $A$ is Dedekind infinite when there is some $B\subsetneq A$ such that $|A|=|B|$. In ZFC every infinite set is Dedekind infinite.

A set which is infinite but not Dedekind infinite is called infinite Dedekind finite set (commonly abbreviated to iDf or Dedekind finite). That is $A$ is iDf if for every $B\subsetneq A$ we have $|B|<|A|$. It does not mean that you cannot split an iDf into two infinite sets.

For example, take two disjoint iDf sets $A,B$ then $A\cup B$ is also iDf but can be split into $A$ and $B$.

Important classification of Dedekind infinite sets is as follows: $$A\text{ is Dedekind infinite}\iff\aleph_0\le|A|$$ We do not require that $A$ will be well orderable, but we do require it will have a countable subset. In particular this shows how assuming the above gives us that every infinite set can be split into two infinite subsets.

This still not enough to prove that for every infinite $A$ there are $B,C\subseteq A$ such that $|A|=|B|=|C|$ and $B\cap C=\emptyset$. However it was proved that the axiom of choice does not follow from the following fact:

For every infinite cardinal $\mathfrak p$ we have: $\mathfrak p = \mathfrak p+\mathfrak p$. (I am unfamiliar with the proof, announced by Sageev in 1973 and published a couple years later).

This means that you can have that every cardinal can be split into two equinumerous parts without the axiom of choice.

Lastly, $A$ is called amorphous if $A$ cannot be split into two infinite subsets. That is to say, $B\subseteq A$ then either $B$ finite or $A\setminus B$ finite. This is a stronger notion than that of infinite Dedekind finite. This is due to the fact that it may be possible to linearly order an infinite Dedekind finite set, while it is impossible to linearly order an amorphous set.

The proof for this fact is as follow: Suppose $<$ is a linear ordering of $A$, take the cut at $a\in A$ to be $\langle a\!\!\mid =\{b\in A\mid b<a\}$. Clearly $a\mapsto\langle a\!\!\mid$ is a bijection between $A$ and the set of cuts in $<$, therefore the set of cuts is also amorphous. Since every cut is a subset of $A$ it is either finite or co-finite, and every set of cuts is finite or co-finite (with respect to the set of all cuts).

If only finite many cuts are finite, then only finitely many cuts are co-finite, which is a contradiction to the fact there are infinitely many cuts and each is a subset of $A$. The same argument shows that there cannot be only finitely many infinite cuts.

In Cohen's first model showing that ZF is consistent with the negation of AC was given by adding an iDf set of reals, which can be linearly ordered (but not well ordered). In particular in this model every set can be linearly ordered (for a slightly more detailed survey, see my answer here).


A note on consistency strength:

From the assumption that ZF is consistent you have that ZFC is consistent, and by forcing you have that "ZF+There is an iDf set+Every set if linearly orderable" is consistent, and by a different forcing you have that "ZF+Amorphous" is consistent. The last two clearly proving the consistency of ZF (if indeed they are consistent).

However, if we measure the consistency by how much we contradict the axiom of choice... well, in this case just as "axiom of countable choice" is stronger than "Every infinite set is Dedekind infinite" (i.e. the former assertion proves the latter over ZF), we have that:

"There exists an amorphous set" proves "There exists an iDf set", while the opposite is not true, as witnessed by the consistency of "ZF+There exists iDf set+Every set can be linearly ordered", since the last assertion is inconsistent with amorphous sets but still consistent with iDf sets.

And by its definition an iDf set which is not amorphous can be written as the disjoint union of two infinite sets. Therefore assuming that there exists an iDf set, but there are no amorphous sets is enough to ensure that every infinite set splits into two infinite sets. Whether or not this implies any other forms of choice (multiple choice, finite choice, choice from pairs, choice from well orderable sets, choice from a well orderable collection of well ordered sets, etc etc.), I do not know the answer for that. I'd be happy to look into this question, but this may take a few days due to prior engagements I have.


Lastly, two papers which may be interesting to this topic of conversation:

  1. J.K.Truss, Classes of Dedekind Finite Cardinals, Fundamenta Mathematicae 84, 187-208, 1974.
    In which seven notions of Dedekind finite cardinals (five in addition to finite sets and the one mentioned in my answer, which is the "canonical type" of infinite Dedekind finite cardinals). The paper is not very technical (I think) and I think that one can understand most of the results given without deep background in forcing or permutation models.

  2. J.K.Truss, The structure of amorphous sets, Annals of Pure and Applied Logic, 73 (1995), 191-233.
    This paper deals with amorphous sets, it is longer and more difficult than the previous one.

(I had to dig quite deep into the internet to find these online, and I cannot recall where I had found both papers. Many, many many thanks to Theo for finding the links.)

share|improve this answer
    
I could drone forever about this topic, and I may sprinkle a few more words, proofs and/or references later today. If you have any special requests, we're taking orders through comments. –  Asaf Karagila Aug 28 '11 at 6:27
    
@Theo: Nothing from the top of my mind, but you can procure amorphous sets in permutation models of ZFA and use Jech-Sochor to obtain them in ZF. –  Asaf Karagila Aug 28 '11 at 6:38
    
Can you make the subset in the definition of dedekind infinite also coinfinite within the original. If so, from what you wrote something weaker than countable choice can prove that every imfinite set.can be split. However this is still much stronger than my statement. Can you prove there exist.this splitting without proving every infinite set is dedekind infinite –  William Aug 28 '11 at 7:06
1  
Sageev’s proof apparently doesn’t invite easy familiarity: a footnote in Kuratowski & Mostowski, Set Theory, describes it as ‘very difficult’. –  Brian M. Scott Aug 28 '11 at 8:44
3  
Ah, those Polish guys hide their virtual library quite well :) Here's Truss's paper in Fund. Math and here's the (paywalled) Ann. Pure. Appl. Logic one and here's Truss's homepage (without the paper, of course). Signed, your own personal Mr Libraryman. –  t.b. Aug 29 '11 at 7: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.