# Quod Erat Demonstrandum

## 2008/07/15

### 婚姻定理

Filed under: Additional / Applied Mathematics,Pure Mathematics — johnmayhk @ 11:55 下午

$A_1 =$ {1 , 2 , 3}
$A_2 =$ {1 , 2 , 4}
$A_3 =$ {2 , 4}
$A_4 =$ {3 , 1}

$A_1 :$ {2}
$A_2 :$ {1}
$A_3 :$ {4}
$A_4 :$ {3}

$A_1 =$ {1 , 2 , 3 , 4}
$A_2 =$ {1 , 3 , 4 , 5 , 8}
$A_3 =$ {3 , 5 , 7}
$A_4 =$ {2 , 4}
$A_5 =$ {1 , 2 , 5}
$A_6 =$ {1 , 3 , 4 , 5}
$A_7 =$ {2 , 4}
$A_8 =$ {3 , 5 , 8}

Let $A_i \subset \mathbb{N} (i = 1, 2, ..., n)$.
$\exists$ distinct natural numbers $k_i \in A_i$ iff
$|A_{i_1}\cup A_{i_2}\cup \dots \cup A_{i_k}| \ge k (k = 1, 2, ..., n)$ with $\{i_1, i_2, ..., i_k\} \subset \{1, 2, 3, ..., n\}$

$n = 1$，由何氏條件，知 $A_1$ 非空，即存在 $k_1 \in A_1$，即婚姻定理顯然成立。

（注：我知我係 poor presentation，應寫 for any natural number m, suppose P(m) is true…，但，都係 skip 好了。）

$I = \{i_1, i_2, ..., i_k\} \subset \{1, 2, 3, ..., m + 1\}$
$A(I) = A_{i_1}\cup A_{i_2}\cup ... \cup A_{i_k}$

（情況一）除 $I = \Phi$$I = \{1, 2, 3, ..., m + 1\}$ 外，均有 $|A(I)| > |I|$

（情況二）在 $\{1, 2, 3, ..., m + 1\}$ 中存在真子集 $I$，使 $|A(I)| = |I|$

$C(J) = C(I \cup J) \backslash C(I)$，故

$|C(J)| = |C(I \cup J)| - |C(I)| \ge |I \cup J| - |I| = |J|$

http://episte.math.ntu.edu.tw/articles/mm/mm_10_1_09/index.html