Set theory · existing Mathlib theorem

Schröder–Bernstein Theorem

If there is a one-to-one function from α into β and another one-to-one function from β into α, then there is a function from α to β that is both one-to-one and onto.

injections
bijections
cardinality
infinite sets

Four separate status axes

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.

Formal orientation

Statement map

This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.

The theorem at a glance

Schröder–Bernstein Theorem at a glance

A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.

An ivory theorem poster shows injective maps from alpha to beta and beta to alpha, subordinate alternating-chain intuition, and a newly constructed bijective map pairing every displayed point exactly once. — Two particular injections in opposite directions imply the existence of a new bijection; neither input map is presented as bijective.

Opposing one-to-one arrows between emerald and cobalt nodes are reorganized into alternating chains and loops, then into a complete row-by-row pairing. — Two injections are decomposed into alternating components and resolved into a bijection.

Complementary intuition

A mathematical landmark

Schröder–Bernstein turns two cardinal inequalities into an equality of cardinality. It is fundamental to comparing infinite sets without first constructing a bijection directly.

The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.

Authoritative formal type

Exact Mathlib statement

Function.Embedding.schroeder_bernstein {α : Type u} {β : Type v} {f : α → β} {g : β → α} (hf : Function.Injective f) (hg : Function.Injective g) : ∃ h : α → β, Function.Bijective h

Selected evidence declaration text

theorem Function.Embedding.schroeder_bernstein {α : Type u} {β : Type v} {f : α → β} {g : β → α} (hf : Function.Injective f) (hg : Function.Injective g) : ∃ h : α → β, Function.Bijective h

Proof architecture

How two injections produce a new bijection

5 curated stages

Mathlib's selected theorem specializes a stronger relation-preserving construction: choose a least fixed-point region, transport its complement through a partial inverse, define a piecewise map, prove it surjective and injective, and discard the trivial relation witness.

These source-anchored stages explain the retained Mathlib proof route. They are generated explanations, not proof evidence or an extracted Lean proof-term dependency graph.

Reduce to the stronger construction
Reduce to the stronger construction
The selected theorem delegates to a stronger relation-preserving construction, with the empty case closed first.
Open original image in a new tab
The selected theorem delegates to a stronger relation-preserving construction, with the empty case closed first.
schroeder_bernstein_of_rel hf hg (fun _ _ ↦ True) ...
schroeder_bernstein calls schroeder_bernstein_of_rel with the constantly true relation. Inside that helper, if β is empty then injectivity of f forces α empty and the empty equivalence supplies the result; the nonempty branch carries the fixed-point construction.
Choose the least fixed-point region
Choose the least fixed-point region
A monotone complement-image operator selects the least source region on which the forward injection will be used.
Open original image in a new tab
A monotone complement-image operator selects the least source region on which the forward injection will be used.
F s = (g '' (f '' s)ᶜ)ᶜ; s = F.lfp
The operator sends a source subset to the complement of g applied to the complement of its f-image. Mathlib takes F.lfp and uses F.map_lfp to identify the chosen region with its image under this operator; complement injectivity yields the corresponding identity for the outside region.
Transport the complement through a partial inverse
Transport the complement through a partial inverse
The partial inverse of the backward injection sends the outside region onto precisely the target points missed by the forward branch.
Open original image in a new tab
The partial inverse of the backward injection sends the outside region onto precisely the target points missed by the forward branch.
g' '' sᶜ = (f '' s)ᶜ
leftInverse_invFun turns g' into a left inverse of g. Combining that fact with the fixed-point complement identity proves g' '' sᶜ = (f '' s)ᶜ, which is the exact coverage relation needed by the piecewise map.
Define the piecewise map and cover the target
Define the piecewise map and cover the target
The new map uses f on the least fixed-point region and the partial inverse of g outside it; the two images cover complementary target regions.
Open original image in a new tab
The new map uses f on the least fixed-point region and the partial inverse of g outside it; the two images cover complementary target regions.
h = s.piecewise f g'; Function.Surjective h
Mathlib defines h by Set.piecewise. range_piecewise splits its range into the f-image of s and the g'-image of sᶜ; substituting the complement identity and union_compl_self proves Surjective h.
Prove one-to-one and conclude
Prove one-to-one and conclude
Branchwise injectivity and complement separation make the new surjective map one-to-one, yielding the required bijection.
Open original image in a new tab
Branchwise injectivity and complement separation make the new surjective map one-to-one, yielding the required bijection.
∃ h : α → β, Function.Bijective h
injective_piecewise_iff uses hf on the selected region, the left-inverse law for g' on the complement, and the fact that an outside target cannot lie in f '' s. The helper returns h with both properties, and schroeder_bernstein specializes its relation to True and keeps the bijectivity witness.

Claim boundary

No new theorem is claimed

The selected declaration concludes that a bijective function α → β exists from hypotheses that particular functions f and g are injective. It does not assert that either given injection is itself bijective, and the page does not claim a new construction.

Proof Atlas did not originate the Schröder–Bernstein theorem or Mathlib's declaration.
The direct upstream theorem, not a local wrapper, is the canonical mathematical object.
A historical or future review cannot be inferred from the build evidence alone.

Provenance

Origin and evidence stay separate

Existing declaration: Function.Embedding.schroeder_bernstein in mathlib
Relationship: The checked artifact is the upstream declaration itself
Preferred checked artifact: artifact.library.mathlib.schroeder-bernstein.v001
Source handling: Verified upstream reference; no mirrored source package

Statement map

Schröder–Bernstein Theorem at a glance

A mathematical landmark

Exact Mathlib statement

How two injections produce a new bijection

Reduce to the stronger construction

Choose the least fixed-point region

Transport the complement through a partial inverse

Define the piecewise map and cover the target

Prove one-to-one and conclude

No new theorem is claimed

Origin and evidence stay separate