# 鴿籠原理

有限total map的domain比codomain大時必有兩個不同元素共享像。

mko-pigeonhole-principle · theorem · v0.10.0



## 數學敘述

對完整有限A、B與total f:A→B，|A|>|B|推出存在a1!=a2且f(a1)=f(a2)。|A|<=|B|不保證給定map單射；generalized版本的最大load至少ceil(|A|/|B|)須另行明示。





## 代表公式（精確 TeX）

f:A\to B





## 成立條件


- A與B有限且mapping對A每個元素恰有一個B中值。
- codomain非空；generalized負載用exact integer ceiling。





## 符號作用域


- f — 有限全函數
- A — 定義域





## 直觀、定義與常見誤解

collision witness包含兩個不同domain indices。

complete map使有限實例核對是exact而非sample。

converse不成立；小domain仍可有collision。

由|A|<=|B|斷言任意f都是injective。





## 已採用的推導導讀

[完整映射的碰撞與ceil負載](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-pigeonhole-principle-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [基本計數原理](https://ocme.evemisslab.com/zh-Hant/mko/mko-counting-principle/) — 有限計數。
- [集合基數比較](https://ocme.evemisslab.com/zh-Hant/mko/mko-cardinality-comparison/) — domain/codomain大小。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — total map與injectivity。





## 驗證界線

只處理完整有限maps；抽樣collision不證一般映射命題。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入inclusion-exclusion與generalized applications。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/pigeonhole-principle.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-pigeonhole-principle/index.md)