証明法 (演習問題の解答)

数理論理学配布資料 (山田)
証明法
(演習問題の解答)
演習の実施後に読むことを推奨！
●演習問題（集合論に関する性質の証明）
(1) A ∪ B ⊆ C ⇔ A ⊆ C ∧ B ⊆ C
［証明］(⇒) A ∪ B ⊆ C を仮定して，A ⊆ C と B ⊆ C を示す．A ⊆ C を証明するため，x ∈ A を
仮定して x ∈ C を導く．x ∈ A と和集合の定義より x ∈ A ∪ B ．これと仮定 A ∪ B ⊆ C より x ∈ C ．
B ⊆ C の証明も同様である．(⇐) A ⊆ C と B ⊆ C を仮定して，A ∪ B ⊆ C を示す．A ∪ B ⊆ C を
証明するため，x ∈ A ∪ B を仮定して x ∈ C を導く．仮定 x ∈ A ∪ B と和集合の定義より，(a) x ∈ A
または (b) x ∈ B だから，この二つの場合分けにより x ∈ C を導く．(a) の場合は仮定 A ⊆ C より
x ∈ C ．(b) の場合は仮定 B ⊆ C より x ∈ C ．
(2) A × B ⊆ C × D ⇒ A ⊆ C ∧ B ⊆ D
［反証］A = ∅, B = {1, 2}, C = {0}, D = {1} とおけば，A × B = ∅ と C × D = {(0, 1)} が成り
立つから，A × B ⊆ C × D だが，B ⊆ D が成り立たない．
なお，次のように前提を強めれば，含意が成立するようになる．
A=∅ ∧ B =∅ ∧ A×B ⊆C×D ⇒ A⊆C ∧ B ⊆D
［証明］A = ∅ と B = ∅ と A × B ⊆ C × D を仮定して，二つの包含関係 A ⊆ C と B ⊆ D を示
す．まず，包含関係 A ⊆ C を証明するため，x ∈ A を仮定して x ∈ C を導く．仮定 B = ∅ より，
B には少なくとも 1 つの要素 y が存在するので，直積集合の定義より (x, y) ∈ A × B ．これと仮
定 A × B ⊆ C × D より (x, y) ∈ C × D．これと直積集合の定義より x ∈ C ．もう一つの包含関係
B ⊆ D も，仮定 A = ∅ を使えば同様に証明できる．
(3) ∃A ⊆ N ∀B ⊆ N (A ∩ B = B ∧ B ∩ A = B)
［証明］A = N とおけば，任意の自然数集合 B について，A∩B = N∩B = B かつ B∩A = B∩N = B ．
(4) 自然数上の演算 f を，n が偶数のとき f (n) = n div 2，n が奇数のとき f (n) = 2 × (n div 2) + 1，と
定めると，∀m ∈ N ∃n ∈ N f (n) = m
［証明］任意の自然数 m について，n = 2m とおく．n は偶数だから，f の定義より f (n) = f (2m) =
(2m) div 2 = m．
(5) 関係 R′ を xR′ y ⇔ xRy ∧ ¬ yRx と定めると，R が推移的ならば R′ も推移的．
［証明］R が推移的であると仮定する．R′ が推移的であることを示すため，任意の要素 x, y, z につ
いて，xR′ y と yR′ z を仮定して xR′ z を証明する．xR′ z を示すには，R′ の定義より，(a) xRz が成
立する，(b) zR′ x が成立しない，の二つを示す必要がある．まず，(a) を証明する．仮定 xR′ y と
仮定 yR′ z と R′ の定義より，xRy かつ yRz だから，R の推移性より xRz ．次に，(b) を背理法に
より示すため，zR′ x を仮定して矛盾を導く．仮定 zR′ x と仮定 xR′ y と R′ の定義より，zRx かつ
xRy だから，R の推移性より zRy ．一方，仮定 yR′ z と R′ の定義より zRy は成立しないが，これ
は zRy に矛盾する．
山田俊行
http://www.cs.info.mie-u.ac.jp/~toshi/
1

Download Report