Mathlib theorem · Existing formal mathematics
ProofAtlas

Existing in Mathlib · Set theory

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.

Exact theorem

Exact Mathlib statement

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

The theorem at a glance

Schröder–Bernstein Theorem at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

Two particular injections in opposite directions imply the existence of a new bijection; neither input map is presented as bijective. Explanatory diagram.
Detailed visual description

The top half displays separate forward and backward injections with unused target points. Alternating chains appear in a middle proof-intuition strip. The lower half reorganizes the two point fields into one exact pairing h, next to separate injective and surjective cues and an explicit scope footer.

Statement structure

Statement and scope

Statement map for Schröder–Bernstein TheoremInjections in both directions between two types imply a bijection between them. Claim boundary: 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. The pinned upstream declaration is Function.Embedding.schroeder_bernstein. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingInjections in bothdirections between twotypes imply a bijectionbetween them.Claim boundaryThe selected declarationconcludes that abijective function α → βexists from hypothesesthat particularfunctions f and g areinjective. It does notassert that either giveninjection is itselfbijective, and the pagedoes not claim a newconstruction.Pinned declarationmathlib ·Function.Embedding.schroeder_bernsteinStatement map for Schröder–Bernstein TheoremInjections in both directions between two types imply a bijection between them. Claim boundary: 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. The pinned upstream declaration is Function.Embedding.schroeder_bernstein. The complete formal statement is available in the Exact Mathlib statement section.Mathematical readingInjections in bothdirections between twotypes imply a bijectionbetween them.Claim boundaryThe selected declarationconcludes that abijective function α → βexists from hypothesesthat particularfunctions f and g areinjective. It does notassert that either giveninjection is itselfbijective, and the pagedoes not claim a newconstruction.Pinned declarationmathlib ·Function.Embedding.schroeder_bernstein

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

Two injections are decomposed into alternating components and resolved into a bijection. Explanatory scientific diagram.
Detailed visual description

Two source-and-target diagrams on the left show total injections in opposite directions. Alternating colored chains and a loop occupy the center. On the right, isolated emerald and cobalt nodes are paired exactly once by clean horizontal segments, with no within-column links.

Why it matters

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.

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.

  1. Reduce to the stronger construction

    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.

  2. Choose the least fixed-point region

    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.

  3. 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.

    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.

  4. 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.

    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.

  5. Prove one-to-one and conclude

    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.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally
Locally reproducedExact upstream declaration replayed
Reviewed pageCurrent public presentation reviewed
Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

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.

Source and local evidence

Where the theorem comes from

Existing declaration
Function.Embedding.schroeder_bernstein in mathlib
Relationship
The checked artifact is the upstream declaration itself
Local Lean evidence
artifact.library.mathlib.schroeder-bernstein.v001
Source
Open the pinned upstream reference