# Pigeonhole principle

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A total map from a larger finite domain into a smaller finite codomain sends two distinct source elements to the same value.

mko-pigeonhole-principle · theorem · v0.10.0



## 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

[Collision and ceiling load in a complete map](https://ocme.evemisslab.com/en/derivations/derivation-mko-pigeonhole-principle-01/)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](https://ocme.evemisslab.com/en/mko/mko-counting-principle/) — The data use complete finite counts.
- [Cardinality comparison of sets](https://ocme.evemisslab.com/en/mko/mko-cardinality-comparison/) — Domain and codomain sizes are compared.
- [Function mapping](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/pigeonhole-principle.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-pigeonhole-principle/index.md)