鴿籠原理

數學敘述

對完整有限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。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 基本計數原理 — 有限計數。
• 集合基數比較 — domain/codomain大小。
• 函數映射 — total map與injectivity。

驗證界線

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

not_formalized

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

下一個義務

加入inclusion-exclusion與generalized applications。

同源結構化資料

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