━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
数理論理学 確認問題８
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問1

素数全体の集合を S，奇数全体の集合を T で表す．

(1) 命題「S は T の部分集合である (S⊆T)」は偽である．
    部分集合の定義をふまえて，この命題を反証せよ．反証の方針を明示すること．

(2) 命題「S と T は互いに素である (S∩T＝∅)」は偽である．
    共通部分や空集合の定義をふまえて，この命題を反証せよ．
    反証の方針を明示すること．

●問2

S, T を任意の集合とする．

(1) S＝S∩T ならば S⊆T を証明せよ．ただし，証明の方針
    (何を仮定して何を導くかなど)を明示すること．

(2) 証明中で使った証明法を，論理式に表れる論理記号と関連させて説明せよ．

──────────────────────────────────────

●答1 (集合の性質の反証，論理式の否定)

(1) 包含関係 S⊆T が成り立たないことを示す．
反証：
S に所属して T に所属しない要素が存在することを示す．
2 は素数なので S の要素であるが，奇数ではないので T の要素ではない．

(2) S と T が互いに素ではないこと (S∩T≠∅) を示す．
反証：
S と T の両方に所属する要素が存在することを示す．
3 は素数であり奇数でもあるので，S と T の両方に所属する．

［解説］

(1)
集合 S が集合 T に包含されることは，S⊆T ⇔ ∀x (x∈S ⇒ x∈T) で定義される．
   ¬S⊆T
⇔ ¬∀x (x∈S ⇒ x∈T)       (部分集合の定義)
⇔ ∃x ¬(x∈S ⇒ x∈T)       (全称の否定)
⇔ ∃x (x∈S ∧ ¬x∈T)       (含意の否定)
だから，S⊆T を反証するには，x∈S かつ ¬x∈T となる x があることを示せばよい．
解答の反証では，x＝2 の場合に x∈S かつ ¬x∈T となることを示した．
なお，背理法を使う反証も可能である．

(2)
集合 S と T の共通部分は，x∈S∩T ⇔ x∈S ∧ x∈T で定義され，
空集合 ∅ は，x∈∅ ⇔ ¬∃x x∈∅ で定義される．
   S∩T≠∅
⇔ ¬ S∩T＝∅              (等号否定≠の定義)
⇔ ¬¬∃x x∈S∩T    (空集合の定義)
⇔ ∃x x∈S∩T              (二重否定)
⇔ ∃x (x∈S ∧ x∈T)        (集合の共通部分の定義)
だから，S∩T≠∅ を反証するには，x∈S かつ x∈T となる x があることを示せばよい．
解答の反証では，x＝3 の場合に x∈S かつ x∈T となることを示した．
3 以外にも，奇数の素数であれば具体例として使える．
なお，背理法を使う反証も可能である．

●答2 (集合の性質の証明)

(教科書 p.110 確認問題2.6 の解答と解説を参照)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/