Pigeonhole principle

Mathematical statement

For complete finite A,B and total f:A→B, |A|>|B| implies distinct a1,a2 with f(a1)=f(a2). The reverse size condition does not generally certify a given map injective. The generalized maximum-load bound is ceil(|A|/|B|), with a nonempty codomain.

Representative formula (exact TeX)

f:A\to B

Assumptions

• A and B are finite and every source element has exactly one in-range image.
• The codomain is nonempty and generalized loads use the exact integer ceiling.

Symbol scope

• f — finite total map
• A — domain

Intuition, definition, and misconceptions

A collision witness has two distinct source indices.

A complete map makes the finite instance check exact rather than sampled.

The general converse fails; a domain no larger than its codomain can still have a collision.

The general condition |A|≤|B| does not justify assuming every supplied map injective.

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

• Basic counting principles — The data use complete finite counts.
• Cardinality comparison of sets — Domain and codomain sizes are compared.
• Function mapping — Totality and injectivity have separate obligations.

Verification boundary

Only complete finite maps are handled; sampled collisions do not establish a general mapping theorem.

not_formalized

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

Next obligation

Add inclusion-exclusion and generalized applications.

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.