## Axiom of Infinity needed in Cantor-Bernstein?

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

-
By the way, Bjørn, it's very nice to see you on MO! – François G. Dorais Mar 15 2010 at 14:53
Yes, Bjørn, welcome to MO! – Joel David Hamkins Mar 15 2010 at 17:34
Nice to see you guys, and thanks for the good answers. – Bjørn Kjos-Hanssen Mar 15 2010 at 20:48
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 2010 at 23:04

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.

-
 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 2010 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 at 14:37

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.

-
Beat me to it by 10 seconds :-) – Andrej Bauer Mar 13 2010 at 8:08
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 2010 at 1:50

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

-

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

-
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 2010 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 2010 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 2010 at 19:06
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 2010 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 2010 at 0:56