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

Can one prove the Cantor-Bernstein (or Schröder-Bernstein) theorem without using the Axiom of Infinity?

share|improve this question
1  
By the way, Bjørn, it's very nice to see you on MO! –  François G. Dorais Mar 15 '10 at 14:53
1  
Yes, Bjørn, welcome to MO! –  Joel David Hamkins Mar 15 '10 at 17:34
    
Nice to see you guys, and thanks for the good answers. –  Bjørn Kjos-Hanssen Mar 15 '10 at 20:48
1  
Very nice question. If anybody had asked me this before I knew the answers below, I would have answered "Of course we need $\omega$!". –  Martin Brandenburg Sep 3 '10 at 23:04
add comment

4 Answers 4

up vote 7 down vote accepted

Actually, the usual proof of the Cantor-Schröder-Bernstein Theorem does not use the Axiom of Infinity (nor the Axiom of Powersets).

By the usual proof, I mean the one found on Wikipedia, for example. Using the notation from that proof, the main point of contention is whether we can form the sets $C_n$ and $C = \bigcup_{n=0}^\infty C_n$. These sets exist by comprehension:

$C_0 = \{x \in A: \forall y \in B\,(x \neq g(y))\}$

$C_n = \{x \in A: \exists s\,(s:\{0,\dots,n\}\to A \land s(0) \in C_0 \land (\forall i < n)(s(i+1) = g(f(s(i)))) \land s(n) = x\}$,

where abbreviations such as $s:\{0,\dots,n\}\to A$ should be replaced by the equivalent (bounded) formulas in the language of set theory. The definition of $C_n$ is uniform in $n$, and so

$C = \{x \in A: \exists n\,(\mathrm{FinOrd}(n) \land x \in C_n)\}$,

where $x \in C_n$ should be replaced by the above definition and $\mathrm{FinOrd}(n)$ is an abbreviation for "$n$ is zero or a successor ordinal and every element of $n$ is zero or a successor ordinal." An alternate definition of $C$ is

$C = \{x \in A: \forall D\,(C_0 \subseteq D \subseteq A \land g[f[D]] \subseteq D \to x \in D)\}$,

which shows that $C$ is $\Delta_1$-definable. The rest of the proof uses induction on finite ordinals, but since the definition of the sets $C_n$ is uniform these are special cases of transfinite induction.

In conclusion, it looks like the proof could work in Kripke-Platek Set Theory — which has neither the Axiom of Infinity nor the Axiom of Powersets — provided that the two definitions of $C$ given above are provably equivalent. I haven't tried to check whether the two definitions are provably equivalent but, in any case, the proof can be carried out in Kripke-Platek Set Theory with $\Sigma_1$-Comprehension.

share|improve this answer
    
Okay, so the proof uses the class $\omega$ but is noncommittal as to whether it is a set, that makes sense. –  Bjørn Kjos-Hanssen Mar 15 '10 at 20:40
    
The wikipedia article has changed a bit: scroll down to the alternate proof after following the link. –  François G. Dorais Dec 19 '12 at 14:37
add comment

(I also like the fixed-point proof mentioned by Andrej and Robin, and indeed, this is the proof I usually use of this theorem. But I claim that there is another more general way to answer the question.)

My answer is that any of the standard proofs can be transformed into a proof not using the Infinity axiom as an assumption. The reason is that if Infinity fails, then every set is finite, and in this case, the Cantor-Schroeder-Bernstein statement becomes trivial---it's just the pigeonhole principle that if n ≤ m ≤ n for natural numbers, then n = m.

So, take any proof of CSB using Infinity and make a new argument omitting that assumption, by simply splitting into cases. Case 1, if Infinity holds, use the original argument. Case 2, if Infinity fails, then CSB becomes trivial.

For this reason, I find the question perhaps to be somewhat odd. The power and usefulness of the Cantor-Schroeder-Bernstein theorem seems to lay largely in the case when there ARE infinitely sets, and is trivialized when there are none.

share|improve this answer
3  
Note that the CSB is also trivial is when the sets are Dedekind finite, so there is no need to assume that finite sets are equipotent with finite ordinals. If there is a Dedekind infinite set, then $\omega$ exists and the usual proof of CSB works. So your argument works without assuming the Axiom of Choice. –  François G. Dorais Mar 13 '10 at 22:08
    
Thanks, François, that is a great observation! When I wrote my answer, I had wondered about what happens with Dedekind finite sets... –  Joel David Hamkins Mar 14 '10 at 0:08
    
Francois points to maybe the key thing I was missing - how obvious is it that if there is a Dedekind infinite set then $\omega$ exists? –  Bjørn Kjos-Hanssen Mar 14 '10 at 19:06
1  
Bjorn, I think François intends us to argue like this: a set A is Dedekind infinite iff there is a bijection f of A with a proper subset of A. If x is in A - ran(f), then the orbit of x under f (the iterates of x under f) cannot be cyclic and so forms an inductive set, where f acts as the successor operation. This gives omega. –  Joel David Hamkins Mar 14 '10 at 20:19
    
And the orbit exists because it is the intersection of all subsets of $A$ that are closed under $f$... nice. –  Bjørn Kjos-Hanssen Mar 15 '10 at 0:56
show 2 more comments

One of the standard proofs avoids the Axiom of Infinity. It's based on the Tarski fixed-point theorem, see for instance www.cs.ucla.edu/~palsberg/course/cs232/papers/bernstein.pdf . But it does use the Power Set Axiom in an essential way.

share|improve this answer
    
Beat me to it by 10 seconds :-) –  Andrej Bauer Mar 13 '10 at 8:08
2  
Note that the use of the Powerset Axiom is not essential in this proof. The smallest fixed-point $Y \subseteq T$ in Palsberg's proof exists by Comprehension Axiom. Using Palsberg's notation, the set $Y$ consists of all $y \in T$ such that for all sets $Z$, if $Z \subseteq T$, $T \setminus f^*(S) \subseteq Z$, and $f^*(g^*(Z)) \subseteq Z$, then $y \in Z$. (I hope this is clear, this comment box is less than ideal to write a nice formula.) –  François G. Dorais Mar 15 '10 at 1:50
add comment

Yes, there is a way to prove Cantor-Bernstein theorem from Tarski's fixed point theorem, see a proof outline on MathWorld.

share|improve this answer
add comment

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.