私的数学日誌

29日目「和集合の要素を数える」

|・|を集合の要素数とする。

最終的に示したいのは。

定理

A、Bを有限な集合としたとき、

|A∪B|=|A|+|B|-|A∩B|

である。

まず、次の定理を示そう。

和の法則

A、Bを有限な集合として、A∩B=∅のとき

|A∪B|=|A|+|B|が成り立つ。

[証明]

ある自然数m、nが存在して、f:[1,m]→A、g:[1,n]→Bとなる全単射写像が仮定より存在する。ここで示すのは、全単射写像h:[1,m+n]→A∪Bの存在である。

ここでs:[1,n]→[m+1,m+n]となる写像、s(n)=m+nをとると、sは全単射より、

|[1,n]|=|[m+1,m+n]|つまり、G:[m+1,m+n]→Bとなる写像が再びとれる。

hを次のように構成する。

x∈[1,m]のとき、h(x)=f(x)

x∈[m+1,m+n]のとき、h(x)=G(x)

これが全単射であることを示す。

まずは全射性を示す。

f(x)とG(x)の全射性と単射性より明らかである。

次に単射性を示す。

h(x)=h(y)→x=yを示す。

ｘ、yが[1,m]と[m+1,m+n]のどちらに入るかで場合分けする。

両方同じ集合に入った場合、hはfかGに等しくなるため、f、Gの単射性より明らか。

x∈[1,m]、y∈[m+1,m+n]の場合、f(x)=G(y)が成り立つ。f(x)∈B∩Aが成り立つが、A∩B=∅よりf(x)が存在することに矛盾する。よって、このような場合は存在しない。対称性より、y∈[1,m]、x∈[m+1,m+n]も同様。よって、h:[1,m+n]→A∪Bは全単射である。

これにより、交叉のない2つの有限集合の和集合の要素数は2つの集合の要素数に分解することができることがわかった。

ここで、次の補題達を証明する。

和の法則

有限集合A、B、Cがどの2つを取っても互いに素であれば、

|A∪B∪C|=|A|+|B|+|C|

[証明]

A∪B∪Cについて、集合の分配法則を使うと、(A∪B)∩C=(A∩C)∪(B∩C)=∅

よって、|A∪B∪C|=|(A∪B)∪C|=|A∪B|+|C|

A∩B=∅より、|A∪B|+|C|=|A|+|B|+|C|。

補集合の法則

有限集合A、Bについて、B⊆Aのとき、|A\B|=|A|-|B|

[証明]

|A|=|B∪(A\B)|=|B|+|A\B|より。

和集合の分解補題

A∪B=(A\A∩B)∪(B\A∩B)∪(A∩B)

[証明]

右辺をXとおく。a∈A∪B→a∈Xを示す。

a∈A、a∉Bのとき、a∈A\A∩B

a∉A、a∈Bのとき、a∈B\A∩B

a∈A、a∈Bのとき、a∈A∩B

逆を示す。a∈Xのとき、

a∈A\A∩Bのとき、a∈Aより。

a∈B\A∩Bのとき、a∈Bより。

a∈A∩Bのとき、a∈Aより。

よって、左辺=右辺。右辺の集合同士がどの2つも互いに素であることを示す。

(A\A∩B)∩(B\A∩B)=∅だけ示せばよい。（残り2つの場合は明らか。）

a∈A\A∩Bのとき、a∈Aかつ、a∉Bが成り立つためa∉B\A∩B。

a∈B\A∩Bのとき、a∈Bかつ、a∉Aより、a∉A\A∩B。

よって、右辺が実際に分解になっていることを示せた。

定理の証明

ここまで来たらとても簡単。

[証明]

|A∪B|=|(A\A∩B)∪(B\A∩B)∪(A∩B)|=|A\A∩B|+|B\A∩B|+|A∩B|=|A|+|B|-|A∩B|より。

そうして、一番最初に述べた定理が証明された。