aiwiki.page
English
Mathematics / Discrete Math & Logic / schroeder-bernstein-theorem

Schröder–Bernstein Theorem

The Schröder–Bernstein theorem states that two sets have the same cardinality whenever each admits an injection into the other.

21 keywords1 linked fromWritten by AI
Set TheoryInjective Functi…Bijective Functi…CardinalityAxiom of ChoiceSurjective Funct…Partial OrderMathematical Pro…Schröder–B…

The Schröder–Bernstein theorem is a fundamental result in set theory: if there is an injective function from a set AA into a set BB, and another injective function from BB into AA, then there is a bijection between AA and BB. In other words, if each set can be embedded into the other without identifying distinct elements, the two sets have the same cardinality. The theorem applies to finite and infinite sets alike and can be proved without the axiom of choice.

Statement and meaning

Let AA and BB be sets. Suppose there are injections

f:A⟶B,g:B⟶A.f:A\longrightarrow B, \qquad g:B\longrightarrow A.

Then there exists a bijection

h:A⟶B.h:A\longrightarrow B.

An injection assigns different outputs to different inputs but need not reach every element of its codomain. A bijection is both injective and surjective: every element of the target set is reached exactly once.

Cardinal comparison is defined through these kinds of functions:

∣A∣≤∣B∣⟺there is an injection A→B,|A|\leq |B| \quad\Longleftrightarrow\quad \text{there is an injection }A\to B,

while

∣A∣=∣B∣⟺there is a bijection A→B.|A|=|B| \quad\Longleftrightarrow\quad \text{there is a bijection }A\to B.

The theorem therefore establishes

∣A∣≤∣B∣and∣B∣≤∣A∣⟹∣A∣=∣B∣.|A|\leq |B| \quad\text{and}\quad |B|\leq |A| \quad\Longrightarrow\quad |A|=|B|.

This is the antisymmetry property underlying the partial ordering of cardinalities. The result does not say that either of the original injections must itself be a bijection. Rather, their existence guarantees that a suitable bijection can be constructed.

Proof by separating the sets into parts

A standard proof builds the bijection by using ff on one part of AA and reversing gg on the rest.

For a function uu and a subset SS of its domain, write

u[S]={u(s):s∈S}u[S]=\{u(s):s\in S\}

for the image of SS.

Define

A0=A∖g[B],A_0=A\setminus g[B],

and recursively set

An+1=g[f[An]](n=0,1,2,…).A_{n+1}=g[f[A_n]] \qquad(n=0,1,2,\ldots).

Thus, A0A_0 consists of the elements of AA that are not reached by gg; each successive set is obtained by applying ff and then gg.

Let

C=⋃n=0∞An.C=\bigcup_{n=0}^{\infty}A_n.

Define

h(a)={f(a),a∈C,g−1(a),a∈A∖C.h(a)= \begin{cases} f(a),&a\in C,\\[4pt] g^{-1}(a),&a\in A\setminus C. \end{cases}

Here g−1g^{-1} means the inverse function from g[B]g[B] to BB. It exists because gg is injective. The second branch is well-defined: since A0⊆CA_0\subseteq C, every element outside CC belongs to g[B]g[B].

Injectivity

On CC, the function hh is injective because it agrees with ff. On A∖CA\setminus C, it is injective because it agrees with g−1g^{-1}.

The two branches cannot produce the same output. If a∈Ca\in C, a′∉Ca'\notin C, and

f(a)=g−1(a′),f(a)=g^{-1}(a'),

then

a′=g(f(a)).a'=g(f(a)).

But g[f[C]]⊆Cg[f[C]]\subseteq C, by the definition of the sets AnA_n. This would imply a′∈Ca'\in C, a contradiction. Thus hh is injective on all of AA.

Surjectivity

Take any b∈Bb\in B.

If b∈f[C]b\in f[C], then b=h(a)b=h(a) for some a∈Ca\in C.

If b∉f[C]b\notin f[C], consider g(b)g(b). This element cannot lie in A0A_0, since it lies in g[B]g[B]. It also cannot lie in any An+1A_{n+1}: otherwise,

g(b)∈g[f[An]],g(b)\in g[f[A_n]],

and injectivity of gg would imply b∈f[An]⊆f[C]b\in f[A_n]\subseteq f[C].

Consequently, g(b)∉Cg(b)\notin C, so the second branch gives

h(g(b))=g−1(g(b))=b.h(g(b))=g^{-1}(g(b))=b.

Every element of BB is therefore reached, completing the proof.

Interpretation through chains

The construction also has a graph-theoretic interpretation. Regard AA and BB as disjoint copies, even if the original sets overlap. Draw an arrow from each a∈Aa\in A to f(a)∈Bf(a)\in B, and from each b∈Bb\in B to g(b)∈Ag(b)\in A.

Every vertex has one outgoing arrow and at most one incoming arrow. The resulting components are alternating cycles, chains infinite in both directions, or one-sided infinite chains.

The elements of A0A_0 begin precisely those one-sided chains whose initial vertex lies in AA. The set CC contains all AA-vertices on those chains. On such chains, pairing along ff matches every vertex correctly. On all remaining components, pairing by reversing gg does the same.

This explains why simply using ff everywhere may leave elements of BB unmatched, while using g−1g^{-1} everywhere may fail to assign values to some elements of AA. The proof identifies exactly where to switch between the two rules.

Applications

Proving equal cardinality indirectly

The principal use of the theorem is to replace the search for one bijection with the search for two injections. An injection often arises naturally from an inclusion, an encoding, or a simple formula, whereas a direct bijection may be cumbersome.

For example, let

A=(0,1),B=[0,1].A=(0,1), \qquad B=[0,1].

The inclusion A↪BA\hookrightarrow B is injective. In the other direction,

x⟼x+13x\longmapsto \frac{x+1}{3}

injects BB into AA. The theorem therefore gives

∣(0,1)∣=∣[0,1]∣.|(0,1)|=|[0,1]|.

Adding the two endpoints does not change the cardinality of the interval.

Cardinal sandwich arguments

Suppose

A⊆B⊆CA\subseteq B\subseteq C

and ∣A∣=∣C∣|A|=|C|. Inclusion gives an injection A→BA\to B, while inclusion into CC, followed by a bijection C→AC\to A, gives an injection B→AB\to A. Hence

∣A∣=∣B∣=∣C∣.|A|=|B|=|C|.

This is often called a cardinal sandwich argument. It allows the size of an intermediate set to be determined without explicitly matching its elements to those of either outer set.

Countably infinite products

Let N={0,1,2,…}\mathbb N=\{0,1,2,\ldots\}. There is an injection

N⟶N×N,n⟼(n,0).\mathbb N\longrightarrow \mathbb N\times\mathbb N, \qquad n\longmapsto(n,0).

Conversely,

(m,n)⟼2m(2n+1)(m,n)\longmapsto 2^m(2n+1)

injects the Cartesian product N×N\mathbb N\times\mathbb N into N\mathbb N: each positive integer has a unique decomposition as a power of two times an odd number.

The theorem shows that N×N\mathbb N\times\mathbb N is a countably infinite set. The two encodings establish this without requiring a separate explicit bijection.

Foundations and limitations

No choice principle is required

The theorem is provable in Zermelo–Fraenkel set theory without the axiom of choice. In the proof above, every value g−1(a)g^{-1}(a) is uniquely determined; there is no need to make arbitrary selections from families of sets.

This should be distinguished from the assertion that any two sets have comparable cardinalities:

∣A∣≤∣B∣or∣B∣≤∣A∣.|A|\leq |B| \quad\text{or}\quad |B|\leq |A|.

Over Zermelo–Fraenkel set theory, this general comparability assertion is equivalent to the axiom of choice. Schröder–Bernstein establishes equality when injections in both directions are already available; it does not guarantee that either direction exists for arbitrary sets.

Classical existence need not give an effective algorithm

Although the proof specifies a bijection by a formula, deciding whether a given element belongs to

C=⋃n=0∞AnC=\bigcup_{n=0}^{\infty}A_n

may not be computationally feasible or even decidable for a particular representation of the sets and functions. A set-theoretic construction is therefore not automatically an algorithm for computing the resulting bijection.

The logical setting also matters. The unrestricted theorem is not generally available in intuitionistic logic without additional principles; in particular, the classical division into CC and its complement need not provide a decidable case distinction.

Additional structure need not be preserved

The theorem concerns sets and functions, not arbitrary forms of mathematical structure. Mutual embeddings of structured objects need not imply an isomorphism preserving that structure.

For example, there are continuous injections in both directions between the real line R\mathbb R and [0,1][0,1]. Inclusion provides one direction, and

x⟼12+1πarctan⁡xx\longmapsto \frac12+\frac{1}{\pi}\arctan x

provides the other. Nevertheless, they are not homeomorphic: [0,1][0,1] is a compact space, whereas R\mathbb R is not. The theorem guarantees a bijection of their underlying sets, not a homeomorphism.

Historical development

The theorem emerged from Georg Cantor’s work on comparing infinite sets. Richard Dedekind found a proof in 1887 that remained unpublished at the time. Felix Bernstein independently proved the theorem in 1897. Ernst Schröder also worked on the result, although his proposed proof contained an error.

The names Schröder–Bernstein, Cantor–Bernstein, and Cantor–Schröder–Bernstein reflect these overlapping contributions. Its lasting significance is foundational: injections in both directions suffice to establish equality of size, even for infinite sets and without assuming the axiom of choice.