完整映射的碰撞與ceil負載

目標與範圍

從全部fibers證碰撞及廣義下界。

有限total map、非空codomain；不由抽樣推一般映射。

已知條件與符號

• work

• G1 — A={0,1,2,3,4}，B={a,b}，f的完整table為(a,b,a,b,a)。

• ℓ_b — box b的load
• m,k — domain與codomain大小

規則與來源

• mko_definition · cited — 對完整有限A、B與total f:A→B，|A|>|B|推出存在a1!=a2且f(a1)=f(a2)。|A|<=|B|不保證給定map單射；generalized版本的最大load至少ceil(|A|/|B|)須另行明示。 · mko-pigeonhole-principle
• work · prerequisite — finite total map的fibers形成partition；load總和等於domain大小；ceil(r)-1<r。

逐步主鏈

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}

局部子步與引理

本稿無局部子步。

逐步反向審查

• S08 · premise_audit · G1, S07, work — 小domain不強迫任意map單射。
• S07 · premise_audit · G1, S06, work — ceil定義給q-1<m/k，乘正k保序。
• S06 · premise_audit · G1, S05, work — codomain非空才有此商。
• S05 · premise_audit · G1, S04, work — f(0)=f(0)不是合法不同元素witness。
• S04 · premise_audit · G1, S03, work — load總和3+2=5作完整性核對。
• S03 · premise_audit · G1, S02, work — 0、2、4為三個不同原像。
• S02 · premise_audit · G1, S01, work — 相等大小不由此定理保證碰撞。
• S01 · premise_audit · G1, work — 不能省略4的entry。

錯誤控制與反例

total性

五個entry全列且值皆在B。

ceil

5除2向上取整為3，不用截斷除法。

• f(0)=f(0)就是碰撞證書。 → reject — 原像必須不同。
• |A|≤|B|就強迫f單射。 → reject — g=(a,a)是完整反例。
• 最大load下界為floor(5/2)=2即可exact表示廣義定理。 → reject — 定理下界為ceil=3，兩者不可混用。

結論與限制

0與2碰撞，最大load3=ceil(5/2)；大小逆條件不保證單射。

驗證及來源綁定

2 個本稿宣告算術檢查；只支持所列算式。

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

同源完整 JSON（含公式、AST、反控制與修訂記錄）