Cardinality comparison of sets

Mathematical statement

This slice is limited to complete finite sets. An injection A→B certifies |A|≤|B|, a surjection certifies |A|≥|B|, and a bijection certifies equality. If |A|>|B| there is no injection. Reverse comparison from a surjection for infinite sets requires additional choice or section obligations and is outside this slice.

Representative formula (exact TeX)

C(A,B)

Assumptions

• Source and target are complete lists of distinct elements, and the mapping list has exactly the source length.
• Every image belongs to the target, and the certificate covers only those specified finite sets.

Symbol scope

• C — cardinality comparison
• A — source set
• B — target set

Intuition, definition, and misconceptions

First verify a total mapping whose images lie in the target.

Injectivity and surjectivity are separate obligations.

The pigeonhole obstruction is finite-only and is not extended to infinite cardinalities.

Injectivity cannot be discussed without fixing source and target, and the finite surjection comparison cannot be extended unconditionally to infinite sets.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Injectivity and distinct inputs — An injection supplies one direction of comparison.
• Surjectivity and codomain coverage — A surjection supplies the reverse comparison for finite sets.
• Bijectivity and unique preimages — A bijection gives equality of cardinalities.
• Set — The mapping is bound to explicit source and target sets.

Verification boundary

Only explicit finite sets are handled; infinite comparison and choice are outside this slice.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add at-most-countable sets.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.