[開設 07/03/23=MM/DD/YY]

集合族の演算法則

(1): Λ≠∅のとき， (∪_λ∊ΛA_λ)∪B = ∪_λ∊Λ(A_λ∪B), (∩_λ∊ΛA_λ)∩B = ∩_λ∊Λ(A_λ∩B).
(2): ∪_λ∊Λ (A_λ∪B_λ) = (∪_λ∊Λ A_λ) ∪ (∪_λ∊Λ B_λ), ∩_λ∊Λ (A_λ∩B_λ) = (∩_λ∊Λ A_λ) ∩ (∩_λ∊Λ B_λ).
(3): ∪_λ∊Λ ∪_μ∊Μ A_λ,μ = ∪_μ∊Μ ∪_λ∊Λ A_λ,μ, ∩_λ∊Λ ∩_μ∊Μ A_λ,μ = ∩_μ∊Μ ∩_λ∊Λ A_λ,μ.
(4): (∪_λ∊ΛA_λ)∩B = ∪_λ∊Λ(A_λ∩B), (∩_λ∊ΛA_λ)∪B = ∩_λ∊Λ(A_λ∪B).
(5): (∪_λ∊ΛA_λ)^c = ∩_λ∊Λ A_λ^c, (∩_λ∊ΛA_λ)^c = ∪_λ∊Λ A_λ^c.
(6): ∀λ'∊Λ ( A_λ' ⊆ ∪_λ∊ΛA_λ ), ∀λ'∊Λ ( ∩_λ∊ΛA_λ ⊆ A_λ' ).
(7): ∀λ∊Λ ( A_λ ⊆ B ) ⇒ ∪_λ∊ΛA_λ ⊆ B, ∀λ∊Λ ( B ⊆ A_λ ) ⇒ B ⊆ ∩_λ∊ΛA_λ.
(8): A ⊆ B ⇒ ∪A ⊆ ∪B, A ⊆ B ⇒ ∩B ⊆ ∩A.

証明のための準備．次の論理法則 (a)–(h) が成り立つ．なお，P は x の現れない論理式である．（これらの論理法則については，「付帯条件つき限定命題に関する論理法則」を参照．）

(a): [ ∀x ∊A ; F(x) ]∧P 　⇔　 ∀x ∊A [ F(x)∧P ] 　　　（A≠ ∅ のとき）
(b): [ ∃x ∊A ; F(x) ]∧P 　⇔　 ∃x ∊A [ F(x)∧P ]
(c): [ ∀x ∊A ; F(x) ]∨P 　⇔　 ∀x ∊A [ F(x)∨P ]
(d): [ ∃x ∊A ; F(x) ]∨P 　⇔　 ∃x ∊A [ F(x)∨P ] 　　　（A≠ ∅ のとき）
(e): ∀x ∊A, ∀y ∊B ; F(x,y) 　⇔　 ∀y ∊B, ∀x ∊A ; F(x,y)
(f): ∃x ∊A, ∃y ∊B ; F(x,y) 　⇔　 ∃y ∊B, ∃x ∊A ; F(x,y)
(g): ∀x ∊A [ F(x) ∧ G(x) ] 　⇔　 [ ∀x ∊A ; F(x) ] ∧ [ ∀x ∊A ; G(x) ]
(h): ∃x ∊A [ F(x) ∨ G(x) ] 　⇔　 [∃x ∊A ; F(x) ] ∨ [∃x ∊A ; G(x) ]

下の証明中の「任意に固定する」については，資料「「任意に固定する」とはどういうことか」を参照してください．

(1)

(∪_λ∊ΛA_λ)∪B = ∪_λ∊Λ(A_λ∪B)

証明

x ∊(∪_λ∊ΛA_λ)∪B
	⇔	x ∊∪_λ∊ΛA_λ ∨x ∊B	（∵ 合併集合の定義）
	⇔	(∃λ∊Λ (x ∊A_λ) ) ∨ x ∊B	（∵ 集合族の合併集合の定義）
	⇔	∃λ∊Λ (x ∊A_λ ∨ x ∊B)	（∵ 上記 (d) ）
	⇔	∃λ∊Λ (x ∊A_λ∪B)	（∵ 合併集合の定義）
	⇔	x ∊∪_λ∊Λ(A_λ∪B) .	（∵ 集合族の合併集合の定義）

(∩_λ∊ΛA_λ)∩B = ∩_λ∊Λ(A_λ∩B)

証明

x ∊(∩_λ∊ΛA_λ)∩B
	⇔	x ∊∩_λ∊ΛA_λ ∧x ∊B	（∵ 共通集合の定義）
	⇔	(∀λ∊Λ (x ∊A_λ) ) ∧ x ∊B	（∵ 集合族の共通集合の定義）
	⇔	∀λ∊Λ (x ∊A_λ ∧ x ∊B)	（∵ 上記 (a) ）
	⇔	∀λ∊Λ (x ∊A_λ∩B)	（∵ 共通集合の定義）
	⇔	x ∊∩_λ∊Λ(A_λ∩B) .	（∵ 集合族の共通集合の定義）

(2)

∪_λ∊Λ (A_λ∪B_λ) = (∪_λ∊Λ A_λ) ∪ (∪_λ∊Λ B_λ)

証明

x ∊ ∪_λ∊Λ (A_λ∪B_λ)
	⇔	∃λ∊Λ ( x ∊ A_λ∪B_λ )	（∵ 集合族の合併集合の定義）
	⇔	∃λ∊Λ ( x ∊ A_λ ∨ x ∊ B_λ )	（∵ 合併集合の定義）
	⇔	[ ∃λ∊Λ ; x ∊ A_λ ]
		∨ [ ∃λ∊Λ ; x ∊ B_λ ]	（∵ 上記 (h)）
	⇔	x ∊ ∪_λ∊Λ A_λ ∨ x ∊ ∪_λ∊Λ B_λ	（∵ 集合族の合併集合の定義）
	⇔	x ∊ (∪_λ∊Λ A_λ) ∪ (∪_λ∊Λ B_λ) .	（∵ 合併集合の定義）

∩_λ∊Λ (A_λ∩B_λ) = (∩_λ∊Λ A_λ) ∩ (∩_λ∊Λ B_λ)

証明

x ∊ ∩_λ∊Λ (A_λ∩B_λ)
	⇔	∀λ∊Λ ( x ∊ A_λ∩B_λ )	（∵ 集合族の共通集合の定義）
	⇔	∀λ∊Λ ( x ∊ A_λ ∧ x ∊ B_λ )	（∵ 共通集合の定義）
	⇔	[ ∀λ∊Λ ; x ∊ A_λ ]
		∧ [ ∀λ∊Λ ; x ∊ B_λ ]	（∵ 上記 (g)）
	⇔	x ∊ ∩_λ∊Λ A_λ ∧ x ∊ ∩_λ∊Λ B_λ	（∵ 集合族の共通集合の定義）
	⇔	x ∊ (∩_λ∊Λ A_λ) ∩ (∩_λ∊Λ B_λ) .	（∵ 共通集合の定義）

(3)

∪_λ∊Λ ∪_μ∊Μ A_λ,μ = ∪_μ∊Μ ∪_λ∊Λ A_λ,μ

証明

x ∊∪_λ∊Λ ∪_μ∊Μ A_λ,μ
	⇔	∃λ∊Λ (x ∊∪_μ∊ΜA_λ,μ)	（∵ 集合族の合併集合の定義）
	⇔	∃λ∊Λ, ∃μ∊Μ (x ∊A_λ,μ)	（∵ 集合族の合併集合の定義）
	⇔	∃μ∊Μ, ∃λ∊Λ (x ∊A_λ,μ)	（∵ 2 重限定命題に関する法則）
	⇔	∃μ∊Μ (x ∊∪_λ∊ΛA_λ,μ)	（∵ 集合族の合併集合の定義）
	⇔	x ∊∪_μ∊Μ ∪_λ∊Λ A_λ,μ .	（∵ 集合族の合併集合の定義）

∩_λ∊Λ ∩_μ∊Μ A_λ,μ = ∩_μ∊Μ ∩_λ∊Λ A_λ,μ

証明

x ∊∩_λ∊Λ ∩_μ∊Μ A_λ,μ
	⇔	∀λ∊Λ (x ∊∩_μ∊ΜA_λ,μ)	（∵ 集合族の共通集合の定義）
	⇔	∀λ∊Λ, ∀μ∊Μ (x ∊A_λ,μ)	（∵ 集合族の共通集合の定義）
	⇔	∀μ∊Μ, ∀λ∊Λ (x ∊A_λ,μ)	（∵ 2 重限定命題に関する法則）
	⇔	∀μ∊Μ (x ∊∩_λ∊ΛA_λ,μ)	（∵ 集合族の共通集合の定義）
	⇔	x ∊∩_μ∊Μ ∩_λ∊Λ A_λ,μ .	（∵ 集合族の共通集合の定義）

(4)

(∪_λ∊ΛA_λ)∩B = ∪_λ∊Λ(A_λ∩B)

証明

x ∊(∪_λ∊ΛA_λ)∩B
	⇔	x ∊∪_λ∊ΛA_λ ∧x ∊B	（∵ 共通集合の定義）
	⇔	(∃λ∊Λ (x ∊A_λ) ) ∧ x ∊B	（∵ 集合族の合併集合の定義）
	⇔	∃λ∊Λ (x ∊A_λ ∧ x ∊B)	（∵ 上記 (b) ）
	⇔	∃λ∊Λ (x ∊A_λ∩B)	（∵ 共通集合の定義）
	⇔	x ∊∪_λ∊Λ(A_λ∩B) .	（∵ 集合族の合併集合の定義）

(∩_λ∊ΛA_λ)∪B = ∩_λ∊Λ(A_λ∪B)

証明

x ∊(∩_λ∊ΛA_λ)∪B
	⇔	x ∊∪_λ∊ΛA_λ ∨x ∊B	（∵ 合併集合の定義）
	⇔	(∀λ∊Λ (x ∊A_λ) ) ∨ x ∊B	（∵ 集合族の共通集合の定義）
	⇔	∀λ∊Λ (x ∊A_λ ∨ x ∊B)	（∵ 上記 (c) ）
	⇔	∀λ∊Λ (x ∊A_λ∪B)	（∵ 合併集合の定義）
	⇔	x ∊∩_λ∊Λ(A_λ∪B) .	（∵ 集合族の共通集合の定義）

(5)

(∪_λ∊ΛA_λ)^c = ∩_λ∊Λ A_λ^c

証明

x ∊(∪_λ∊ΛA_λ)^c
	⇔	¬(x ∊∪_λ∊ΛA_λ)	（∵ 補集合の定義）
	⇔	¬(∃λ∊Λ (x ∊A_λ) )	（∵ 集合族の合併集合の定義）
	⇔	∀λ∊Λ (x∉A_λ)	（∵ de Morgan 律）
	⇔	∀λ∊Λ (x ∊A_λ^c)	（∵ 補集合の定義）
	⇔	x ∊∩_λ∊ΛA_λ^c .	（∵ 集合族の共通集合の定義）

(∩_λ∊ΛA_λ)^c = ∪_λ∊Λ A_λ^c

証明

x ∊(∩_λ∊ΛA_λ)^c
	⇔	¬∀λ∊Λ (x ∊A_λ)	（∵ 集合族の共通集合の定義）
	⇔	∃λ∊Λ (x∉A_λ)	（∵ de Morgan 律）
	⇔	∃λ∊Λ (x ∊A_λ^c)	（∵ 補集合の定義）
	⇔	x ∊∪_λ∊ΛA_λ^c .	（∵ 集合族の合併集合の定義）

(6)

∀λ'∊Λ ( A_λ' ⊆ ∪_λ∊ΛA_λ )

証明: 任意に λ'∊Λ を固定する． x ∊A_λ' とすると，明らかに少なくとも１つの λ∊Λ に対して x ∊A_λ となっているから，集合族の合併集合の定義より x ∊∪_λ∊ΛA_λ である．よって，包含関係の定義より A_λ' ⊆ ∪_λ∊ΛA_λ．

∀λ'∊Λ ( ∩_λ∊ΛA_λ ⊆ A_λ' )

証明: 任意に λ'∊Λ を固定する． x ∊∩_λ∊ΛA_λ とすると，集合族の共通集合の定義よりすべての λ∊Λ に対して x ∊A_λ である．したがって， λ'∊Λ に対しても x ∊A_λ' である．よって，包含関係の定義より ∩_λ∊ΛA_λ ⊆ A_λ' ．

(7)

∀λ∊Λ ( A_λ ⊆ B ) ⇒ ∪_λ∊ΛA_λ ⊆ B．

証明: 任意に x ∊∪_λ∊ΛA_λ を固定する．集合族の合併集合の定義より， x ∊A_λ なる λ∊Λ が存在する．仮定より，この λ∊Λ についても A_λ ⊆ B であるから，包含関係の定義より x ∊B となる．したがって，包含関係の定義より ∪_λ∊ΛA_λ ⊆ B．

∀λ∊Λ ( B ⊆ A_λ ) ⇒ B ⊆ ∩_λ∊ΛA_λ．

証明: 任意に x ∊B を固定する．任意の λ∊Λ に対して，仮定 B ⊆ A_λ と包含関係の定義より x ∊A_λ となるから，集合族の共通集合の定義より x ∊∩_λ∊ΛA_λ である．したがって，包含関係の定義より B ⊆ ∩_λ∊ΛA_λ．

(8)

A ⊆ B ⇒ ∪A ⊆ ∪B

証明: 任意に x を固定し， x ∊∪A とする．すると集合族の合併集合の定義から，ある A ∊A が存在して x ∊A である．この A ∊A に，仮定 A ⊆ B と包含関係の定義を適用すると A ∊B となる．よって x ∊A であるような A ∊B が存在したので，集合族の合併集合の定義から x ∊∪B である．以上で，「任意の x について， x ∊∪A ならば x ∊∪B」が言えたので，包含関係の定義から ∪A ⊆ ∪B である．

A ⊆ B ⇒ ∩B ⊆ ∩A

証明: 任意に x を固定し， x ∊∩B とする．また，任意に A ∊A を固定する．すると，仮定 A ⊆ B と包含関係の定義から A ∊B である． x ∊∩B と集合族の共通集合の定義から，任意の B ∊B に対して x ∊B であり，今 A ∊B なので， x ∊A である．これで，任意の A ∊A に対して x ∊A であることが言えたので，集合族の共通集合の定義から x ∊∩A である．以上で，「任意の x について， x ∊∩B ならば x ∊∩A」が言えたので，包含関係の定義から ∩B ⊆ ∩A である．

離散構造（室伏）のホーム

murofusi "at mark" c "dot" titech "dot" ac "dot" jp ("at mark" -> @ / "dot" -> .)