Can one prove the Cantor-Bernstein (or Schröder-Bernstein) theorem without using the Axiom of Infinity?
$\begingroup$
$\endgroup$
4
asked Mar 13, 2010 at 7:35
-
1$\begingroup$ By the way, Bjørn, it's very nice to see you on MO! $\endgroup$– François G. DoraisCommented Mar 15, 2010 at 14:53
-
1$\begingroup$ Yes, Bjørn, welcome to MO! $\endgroup$– Joel David HamkinsCommented Mar 15, 2010 at 17:34
-
$\begingroup$ Nice to see you guys, and thanks for the good answers. $\endgroup$– Bjørn Kjos-HanssenCommented Mar 15, 2010 at 20:48
-
1$\begingroup$ Very nice question. If anybody had asked me this before I knew the answers below, I would have answered "Of course we need $\omega$!". $\endgroup$– Martin BrandenburgCommented Sep 3, 2010 at 23:04
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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.
answered Mar 15, 2010 at 14:08
-
$\begingroup$ Okay, so the proof uses the class $\omega$ but is noncommittal as to whether it is a set, that makes sense. $\endgroup$ Commented Mar 15, 2010 at 20:40
-
$\begingroup$ The wikipedia article has changed a bit: scroll down to the alternate proof after following the link. $\endgroup$ Commented Dec 19, 2012 at 14:37
$\begingroup$
$\endgroup$
7
(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.
answered Mar 13, 2010 at 17:55
-
5$\begingroup$ 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. $\endgroup$ Commented Mar 13, 2010 at 22:08
-
$\begingroup$ Thanks, François, that is a great observation! When I wrote my answer, I had wondered about what happens with Dedekind finite sets... $\endgroup$ Commented Mar 14, 2010 at 0:08
-
$\begingroup$ 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? $\endgroup$ Commented Mar 14, 2010 at 19:06
-
1$\begingroup$ 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. $\endgroup$ Commented Mar 14, 2010 at 20:19
-
3$\begingroup$ Neat! But if I may be permitted to state the obvious, this argument does depend on PEM. Of course, CSB itself depends on PEM, but only on PEM for $\Delta_0$ formulas (e.g. it holds in a Boolean topos). By contrast, this argument seems to require PEM for an unbounded quantifier ("either there exists an infinite set, or there doesn't"). $\endgroup$ Commented Mar 15, 2010 at 3:25
$\begingroup$
$\endgroup$
2
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.
answered Mar 13, 2010 at 8:05
-
$\begingroup$ Beat me to it by 10 seconds :-) $\endgroup$ Commented Mar 13, 2010 at 8:08
-
2$\begingroup$ 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.) $\endgroup$ Commented Mar 15, 2010 at 1:50
$\begingroup$
$\endgroup$
Yes, there is a way to prove Cantor-Bernstein theorem from Tarski's fixed point theorem, see a proof outline on MathWorld.
answered Mar 13, 2010 at 8:08