Axiom of Infinity needed in Cantor-Bernstein? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T12:08:49Z http://mathoverflow.net/feeds/question/18042 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18042/axiom-of-infinity-needed-in-cantor-bernstein Axiom of Infinity needed in Cantor-Bernstein? Bjørn Kjos-Hanssen 2010-03-13T07:35:32Z 2010-03-15T14:08:27Z <p>Can one prove the Cantor-Bernstein (or Schröder-Bernstein) theorem without using the Axiom of Infinity?</p> http://mathoverflow.net/questions/18042/axiom-of-infinity-needed-in-cantor-bernstein/18046#18046 Answer by Robin Chapman for Axiom of Infinity needed in Cantor-Bernstein? Robin Chapman 2010-03-13T08:05:39Z 2010-03-13T08:05:39Z <p>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.</p> http://mathoverflow.net/questions/18042/axiom-of-infinity-needed-in-cantor-bernstein/18047#18047 Answer by Andrej Bauer for Axiom of Infinity needed in Cantor-Bernstein? Andrej Bauer 2010-03-13T08:08:10Z 2010-03-13T08:08:10Z <p>Yes, there is a way to prove Cantor-Bernstein theorem from Tarski's fixed point theorem, see <a href="http://mathworld.wolfram.com/TarskisFixedPointTheorem.html" rel="nofollow">a proof outline on MathWorld</a>.</p> http://mathoverflow.net/questions/18042/axiom-of-infinity-needed-in-cantor-bernstein/18079#18079 Answer by Joel David Hamkins for Axiom of Infinity needed in Cantor-Bernstein? Joel David Hamkins 2010-03-13T17:55:04Z 2010-03-13T18:13:11Z <p>(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.)</p> <p>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 &le; m &le; n for natural numbers, then n = m. </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/18042/axiom-of-infinity-needed-in-cantor-bernstein/18267#18267 Answer by François G. Dorais for Axiom of Infinity needed in Cantor-Bernstein? François G. Dorais 2010-03-15T14:08:27Z 2010-03-15T14:08:27Z <p>Actually, the usual proof of the Cantor-Schröder-Bernstein Theorem does not use the Axiom of Infinity (nor the Axiom of Powersets). </p> <p>By the usual proof, I mean the one found on <a href="http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem#Proof" rel="nofollow">Wikipedia</a>, 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:</p> <p><code>$C_0 = \{x \in A: \forall y \in B\,(x \neq g(y))\}$</code></p> <p><code>$C_n = \{x \in A: \exists s\,(s:\{0,\dots,n\}\to A \land s(0) \in C_0 \land (\forall i &lt; n)(s(i+1) = g(f(s(i)))) \land s(n) = x\}$</code>,</p> <p>where abbreviations such as <code>$s:\{0,\dots,n\}\to A$</code> 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</p> <p><code>$C = \{x \in A: \exists n\,(\mathrm{FinOrd}(n) \land x \in C_n)\}$</code>,</p> <p>where <code>$x \in C_n$</code> 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</p> <p><code>$C = \{x \in A: \forall D\,(C_0 \subseteq D \subseteq A \land g[f[D]] \subseteq D \to x \in D)\}$</code>,</p> <p>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. </p> <p>In conclusion, it looks like the proof could work in <a href="http://en.wikipedia.org/wiki/Kripke%E2%80%93Platek_set_theory" rel="nofollow">Kripke-Platek Set Theory</a> &mdash; which has neither the Axiom of Infinity nor the Axiom of Powersets &mdash; 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.</p>