# Cantor–Bernstein–Schroeder theorem

﻿
Cantor–Bernstein–Schroeder theorem

In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions "f" : "A" → "B" and "g" : "B" → "A" between the sets "A" and "B", then there exists a bijective function "h" : "A" → "B". In terms of the cardinality of the two sets, this means that if |"A"| ≤ |"B"| and |"B"| ≤ |"A"|, then |"A"| = |"B"|; "A" and "B" are said to be "equipollent". This is obviously a very useful feature in the ordering of cardinal numbers.

Proof

Idea of the proof: Redefine "f" in certain points to make it surjective. At first, redefine it on the image of "g" for it to be the inverse function of g. However, this might destroy injectivity, so correct this problem iteratively, by making the amount of points redefined smaller, up to a minimum possible, shifting the problem "to infinity" and therefore out of sight. More precisely, this means to leave "f" unchanged initially on "C"0 := A "g" ["B"] . However, then every element of "f" ["C"0] has two preimages, one under "f" and one under "g" –1. Therefore, leave "f" unchanged on the union of "C"0 and "C"1 := "g" ["f" ["C"0] . However, then every element of "f" ["C"1] has two preimages, correct this by leaving "f" unchanged on the union of "C"0, "C"1, and "C"2 := "g" ["f" ["C"1] and so on. Leaving "f" unchanged on the countable union "C" of "C"0 and all these "C""n"+1 = "g" ["f" ["C""n"] solves the problem, because "g" ["f" ["C"] is a subset of "C" and no additional union is necessary.

Proof: Define

:$C_0=Asetminus g \left[B\right] ,qquad C_\left\{n+1\right\}=g \left[f \left[C_n\right] quad mbox\left\{ for all \right\}nge 0,$

and

:

Then, for every "a" ∈ "A" define

:

If "a" is not in "C", then, in particular, "a" is not in "C"0. Hence "a" ∈ "g" ["B"] by the definition of "C"0. Since "g" is injective, its preimage "g" –1("a") is therefore well defined.

It remains to check the following properties of the map "h" : "A" → "B" to verify that it is the desired bijection:

* Surjectivity: Consider any "b" ∈ "B". If "b" ∈ "f" ["C"] , then there is an "a" ∈ "C" with "b" = "f"("a"). Hence "b" = "h"("a") by the definition of "h". If "b" is not in "f" ["C"] , define "a" = "g"("b"). By definition of "C"0, this "a" cannot be in "C"0. Since "f" ["C""n"] is a subset of "f" ["C"] , it follows that "b" is not in any "f" ["C""n"] , hence "a" = "g"("b") is not in any "C""n"+1 = "g" ["f" ["C""n"] by the recursive definition of these sets. Therefore, "a" is not in "C". Then "b" = "g" –1("a") = "h"("a") by the definition of "h".

* Injectivity: Since "f" is injective on "A", which comprises "C", and "g" –1 is injective on "g" ["B"] , which comprises the complement of "C", it suffices to show that the assumption "f"("c") = "g" –1("a") for "c" ∈ "C" and "a" ∈ "A" "C" leads to a contradiction (this means the original problem, the lack of injectivity mentioned in the idea of the proof above, is solved by the clever definition of "h"). Since "c" ∈ "C", there exists an integer "n" ≥ 0 such that "c" ∈ "C""n". Hence "g"("f"("c")) is in "C""n"+1 and therefore in "C", too. However, "g"("f"("c")) = "g"("g" –1("a")) = "a" is not in "C" — contradiction.

Note that the above definition of "h" is nonconstructive, in the sense that there exists no "general" method to decide in a finite number of steps, for any given sets "A" and "B" and injections "f" and "g", whether an element "a" of "A" does not lie in "C". For special sets and maps this might, of course, be possible.

Visualization

The definition of "h" can be visualized with the following diagram.

Displayed are parts of the (disjoint) sets "A" and "B" together with parts of the mappings "f" and "g". If the set "A" ∪ "B", together with the two maps, is interpreted as a directed graph, then this bipartite graph has several connected components.

These can be divided into four types: paths extending infinitely to both directions, finite cycles of even length, infinite paths starting in the set "A", and infinite paths starting in the set "B" (the path passing through the element "a" in the diagram is infinite in both directions, so the diagram contains one path of every type). In general, it is not possible to decide in a finite number of steps which type of path a given element of "A" or "B" belongs to.

The set "C" defined above contains precisely the elements of "A" which are part of an infinite path starting in "A". The map "h" is then defined in such a way that for every path it yields a bijection that maps each element of "A" in the path to an element of "B" directly before or after it in the path. For the path that is infinite in both directions, and for the finite cycles, we choose to map every element to its predecessor in the path.

Another proof

Below follows an alternate proof, attributed to Julius König.

Assume without loss of generality that "A" and "B" are disjoint. For any "a" in "A" or "b" in "B" we can form a unique two-sided sequence of elements that are alternatively in "A" and "B", by repeatedly applying "$f$" and "$g$" to go right and "$g^\left\{-1\right\}$" and "$f^\left\{-1\right\}$" to go left (where defined).

:"$cdots ightarrow f^\left\{-1\right\}\left(g^\left\{-1\right\}\left(a\right)\right) ightarrow g^\left\{-1\right\}\left(a\right) ightarrow a ightarrow f\left(a\right) ightarrow g\left(f\left(a\right)\right) ightarrow cdots$"

For any particular "a", this sequence may terminate to the left or not, at a point where "$f^\left\{-1\right\}$" or "$g^\left\{-1\right\}$" is not defined.

Call such a sequence (and all its elements) an "A-stopper", if it stops at an element of "A", or a "B-stopper" if it stops at an element of "B". Otherwise, call it "doubly-infinite" if all the elements are distinct or "cyclic" if it repeats.

By the fact that "$f$" and "$g$" are injective functions, each "a" in "A" and "b" in "B" is in exactly one such sequence to within identity, (as if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by definition).

By the above observation, the sequences form a partition of the whole of the disjoint union of "A" and "B", hence it suffices to produce a bijection between the elements of "A" and "B" in each of the sequences separately.

For an "A-stopper", the function "$f$" is a bijection between its elements in "A" and its elements in "B".

For a "B-stopper", the function "$g$" is a bijection between its elements in "B" and its elements in "A".

For a "doubly infinite" sequence or a "cyclic" sequence, either "$f$" or "$g$" will do.

Original proof

An earlier proof by Cantor relied, in effect, on the axiom of choice by inferring the result as a corollary of the well-ordering theorem. The argument given above shows that the result can be proved without using the axiom of choice.

The theorem is also known as the Schroeder-Bernstein theorem, but the trend has been to add Cantor's name, thus crediting him for the original version. It is also called the Cantor-Bernstein theorem.

*Schröder–Bernstein theorems for operator algebras
*Schroeder-Bernstein theorem for measurable spaces

References

* "Proofs from THE BOOK", p. 90. ISBN 3540404600
*
* [http://www.mathpath.org/proof/Sch-Bern/proofofS-B.htm MathPath - Explanation of and remarks on the proof of Cantor-Bernstein Theorem ]

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Schroeder — an umlaut converted representation of Schröder is a common German surname. It can specifically refer to several people: * Andreas Schroeder, a German born Canadian poet, novelist, and nonfiction writer * Barbet Schroeder, a Swiss movie director… …   Wikipedia

• Schroeder-Bernstein theorem for measurable spaces — The Cantor Bernstein Schroeder theorem of set theory has a counterpart for measurable spaces, sometimes called the Borel Schroeder Bernstein theorem , since measurable spaces are also called Borel spaces. This theorem, whose proof is quite easy,… …   Wikipedia

• Cantor's theorem — Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols. In elementary set theory, Cantor s theorem states that, for any set A , the set of all subsets of A (the power… …   Wikipedia

• Bernstein — It may refer to:People* Dan Bern, American musician who previously performed under the name Bernstein * Eric Berne, American psychiatrist and writer * Aaron Bernstein * Alexander Bernstein, Baron Bernstein of Craigweil, British television… …   Wikipedia

• Georg Cantor — Infobox Scientist name = Georg Ferdinand Ludwig Cantor image width=225px caption = birth date = birth date|1845|3|3 birth place = Saint Petersburg, Russia death date = death date and age|1918|1|6|1845|3|3 death place = Halle, Germany residence =… …   Wikipedia

• Knaster–Tarski theorem — In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:: Let L be a complete lattice and let f : L → L be an order preserving function. Then the set …   Wikipedia

• Space-filling curve — 3 iterations of a Peano curve construction, whose limit is a space filling curve. In mathematical analysis, a space filling curve is a curve whose range contains the entire 2 dimensional unit square (or more generally an N dimensional hypercube) …   Wikipedia

• Cardinal number — This article describes cardinal numbers in mathematics. For cardinals in linguistics, see Names of numbers in English. In mathematics, cardinal numbers, or cardinals for short, are generalized numbers used to measure the cardinality (size) of… …   Wikipedia

• List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

• List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia