Collision and ceiling load in a complete map

Goal and scope

Use all fibres to prove a collision and the generalized lower bound.

A finite total map with nonempty codomain; no sampling inference about general maps.

Givens and symbols

• work

• G1 — A={0,1,2,3,4}, B={a,b}, with complete f table(a,b,a,b,a).

• ℓ_b — load of box b
• m,k — domain and codomain sizes

Rules and sources

• mko_definition · cited — 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. · mko-pigeonhole-principle
• work · prerequisite — Fibres of a finite total map form a partition; loads sum to the domain size; ceil(r)-1<r.

Main derivation

f=(a,b,a,b,a)

\forall x\in A:\ \exists!y\in B:\ f(x)=y

|A|=5,\quad|B|=2

|A|>|B|

f^{-1}(a)

\{0,2,4\},\quad\ell_a=3

f^{-1}(b)

\{1,3\},\quad\ell_b=2

0\ne2,\quad f(0)=a=f(2)

f\text{ is not injective}

\lceil|A|/|B|\rceil=\lceil5/2\rceil

\max(\ell_a,\ell_b)=3\ge3

\ell_b\le q-1\text{ for every box},\quad q=\lceil m/k\rceil

m=\sum_b\ell_b\le k(q-1)<m\quad(k\ge1)

A'=\{0,1\},\ B'=\{a,b\},\ g=(a,a)

|A'|\le|B'|\quad\text{but }g\text{ not injective}

Substeps and lemmas

No substeps in this guide.

Reverse audits

• S08 · premise_audit · G1, S07, work — A smaller domain does not force an arbitrary map to be injective.
• S07 · premise_audit · G1, S06, work — The ceiling definition gives q-1<m/k; multiply by positive k.
• S06 · premise_audit · G1, S05, work — A nonempty codomain is required for this quotient.
• S05 · premise_audit · G1, S04, work — f(0)=f(0) is not a witness using distinct elements.
• S04 · premise_audit · G1, S03, work — The load sum3+2=5 cross-checks completeness.
• S03 · premise_audit · G1, S02, work — 0,2,4 are three distinct preimages.
• S02 · premise_audit · G1, S01, work — Equal sizes would not trigger this collision guarantee.
• S01 · premise_audit · G1, work — The entry for4 cannot be omitted.

Error controls and negative controls

Totality

List all five entries with values in B.

Ceiling

Round5/2 upward to 3, not truncation.

• f(0)=f(0) is a collision certificate. → reject — The preimages must be distinct.
• |A|≤|B| forces f injective. → reject — g=(a,a) is a complete counterexample.
• Floor(5/2)=2 is the exact generalized bound. → reject — The theorem's bound is the ceiling3, not the floor2.

Result and limitations

0 and 2 collide and maximum load3=ceil(5/2); the reverse size condition does not ensure injectivity.

Verification and source binding

2 declared checks for this guide; only the listed expressions are covered.

• source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
• adopted source SHA-256: 48e01e622b425eb10256bc6b5df9a4828d74b8b553ae3c51ccf7fa2cb0e937d4
• original source SHA-256: f37dc77a23f2d409b8bd4520337371982021634ea482500e91e66470d7d0c189
• Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

Same-source full JSON (formulas, ASTs, controls and revision log)