可算個の有限集合の和

（命題） 可算個の有限集合の和は可算である
（証明）

可算個の有限集合を A₁, A₂, ... とし， その和集合を S = ∪_i A_i とする．

1. S が有限集合のとき
明らかに可算である．


2. S が無限集合のとき
B_i ∩ B_j = ∅ (i ≠ j) となるように
以下の規則で新たな集合B_iをつくる．
• B₁ = A₁
• B_i = A_i - (A₁ ∪ A₂ ∪ ... ∪ A_{i - 1})
有限集合 B_i の基数を |B_i| = m_i ， b_ij ∈ B_iとすれば，
B_i を以下のように書き並べることができる．
• B₁ = {b₁₁, b₁₂, ... , b_1m1}
• B₂ = {b₂₁, b₂₂, ... , b_2m2}
• :
• B_i = {b_i1, b_i2, ... , b_ij, ... , b_imi}
• :
ここで，f: S → N を，
• f(b_ij) = m₁ + m₂ + ... + m_{i - 1} + j
と定義すると，f は S と N の一対一対応を表す．
よって，S は可算である．■