第5章：述語論理 (2)

第 5 章述語論理 (2)
5.1
5.1.1
集合を変域とする述語
記法
量化子を用いるとき、述語変数の変域を断って、「x の変域を実数とするとき、∀x(P (x)) 」のような使い方をしていた
が、使っていたが、以後、集合の記法を用いて表すことにする。
定義 5.1 命題関数 P (x) に対し、
(i) 変数 x の変域が集合 X 全体である全称命題を (∀x ∈ X)(P (x)) と表す。
(ii) 変数の変域が集合 X 全体である存在命題を (∃x ∈ X)(P (x)) と表す。
例 : (i) 命題関数 P (x) を「x は x2 ≥ 0 を満たす」としたとき、(∀x ∈ Q)(P (x)) は真の命題。(∀x ∈ C)(P (x)) は偽の
命題。
(ii) 命題関数 Q(x) を「x は x2 = −1 を満たす」としたとき、(∀x ∈ R)(Q(x)) は偽の命題。(∀x ∈ C)(Q(x)) は真の命
題。（例終）
5.1.2
量化子を見直す
述語変数 x の変域 X が有限集合で X = {x1 , x2 , · · · , xk } だったとする。このとき、「すべての xj で P (xj ) が成り立
つ」というのは、
P (x1 ) ∧ P (x2 ) ∧ · · · ∧ P (xk )
ということで、「ある xj で P (xj ) が成り立つ」というのは、どれかひとつで P (xj ) が成り立つことだから、
P (x1 ) ∨ P (x2 ) ∨ · · · ∨ P (xk )
ということになる。有限個の命題に関しては、結合法則を繰り返して使えば否定を取ることができるので、例えば、
¬((∀x ∈ X)(P (x))) ≡ ¬(P (x1 ) ∧ P (x2 ) ∧ · · · ∧ P (xk ))
≡ ¬P (x1 ) ∨ ¬P (x2 ) ∨ · · · ∨ ¬P (xk )
≡ (∃x ∈ X)(¬P (x))
¬((∃x ∈ X)(P (x))) ≡ ¬ (P (x1 ) ∨ P (x2 ) ∨ · · · ∨ P (xk ))
≡ ¬P (x1 ) ∧ ¬P (x2 ) ∧ · · · ∧ ¬P (xk )
≡ (∀x ∈ X)(¬P (x))
となる。無限集合を変数の変域とする述語論理の命題の否定も、この形式で定まる。
35
定義 5.2 変域 X の変数 x を持つ命題関数 P (x) に対し、
(i) ¬((∀x ∈ X)(P (x))) ≡ (∃x ∈ X)(¬P (x))
5.2
5.2.1
(ii) ¬((∃x ∈ X)(P (x))) ≡ (∀x ∈ X)(¬P (x))
無限成分の和集合・共通部分
和集合
x が有限個の集合 X1 、X2 、· · · 、Xk の和集合の要素であることを、「x ∈ X1 または x ∈ X2 · · · または x ∈ Xk 」、
「{1, 2, · · · k} のうちのある j について x ∈ Xj 」と言い換えることができる。添字の集合を K = {1, 2, · · · , k} として式
で表すと、
∪
x∈
Xj
⇐⇒
(x ∈ X1 ) ∨ (x ∈ X2 ) ∨ · · · ∨ (x ∈ Xk )
⇐⇒
(∃j ∈ K)(x ∈ Xj )
j∈K
となる。つまり、
∪
Xj = {x | (∃j ∈ K)(x ∈ Xj )}
j∈K
と言い換えることができた。無限個の集合 X1 、X2 、· · · に対し、X1 ∪ X2 ∪ · · · と書くとはっきりしないが、言い換え
た形を一般化して、
∪
def.
Xk := {x | (∃j ∈ N)(x ∈ Xj )}
j∈N
と定義するとはっきりする。より一般に、添字の集合が離散的でない場合も、この定義の仕方は使える。
定義 5.3 添字の集合を Λ とし、λ ∈ Λ に対して集合 Xλ が定まるとする。このとき、
∪
def.
Xλ := {x | (∃λ ∈ Λ)(x ∈ Xλ ) }
λ∈Λ
と定義する。
def.
def.
2
例
Vα :=
{ : 平面 R := {√(x, y) | x, y ∈}R } 上の長さ α （α ≥ 0 ）のベクトル全体の集合を Vα と書く。すなわち、
∪
2
2 2
2
(x, y) ∈ R
x + y = α とする。このとき、R≥0 を非負の実数全体の集合とすると、R =
Vα となる。
当たり前みたいだが、定義に則して、(i) ⃗
x∈R
2
⇒ ⃗x ∈
∪
Vα 、(ii) ⃗x ∈
Vα ⇒ ⃗x ∈ R を確かめておく。
2
α∈R≥0
α∈R≥0
(i) 任意の R2 のベクトル ⃗x = (x y) ∈ R2 に対し、α =
α∈R≥0
∪
√
x2 + y 2 とすると、α ∈ R≥0 で、⃗x ∈ Vα である。よって、⃗x を
要素にもつ Vα が存在するので、
⃗x ∈ R2
=⇒
(∃α ∈ R≥0 ) ( ⃗x ∈ Vα )
=⇒
∪
⃗x ∈
Vα
α∈R≥0
(ii) Vα の定義より、
∪
Vα に含まれる任意の ⃗x は R2 の要素なので、⃗x ∈
α∈R≥0
α∈R≥0
以上、(i)、(ii) より、R2 =
∪
∪
Vα がいえる。（例終）
α∈R≥0
36
Vα ⇒ ⃗x ∈ R2
共通部分
5.2.2
和集合と同様に、有限個の集合 X1 、· · · 、Xk に対し、K := {1, 2, · · · , k} とすると、
∩
x∈
Xj
⇐⇒
(x ∈ X1 ) ∧ (x ∈ X2 ) ∧ · · · ∧ (x ∈ Xk )
⇐⇒
(∀j ∈ K)(x ∈ Xj )
j∈K
がいえる。すなわち、
∩
Xj = {x | (∀j ∈ K)(x ∈ Xj )}
j∈K
と言い換えられる。こちらの記法を一般化して、添字の集合が一般の場合の共通部分を定義することができる。
定義 5.4 添字の集合を Λ とし、λ ∈ Λ に対して集合 Xλ が定まるとする。このとき、
∩
def.
Xλ := {x | (∀λ ∈ Λ)(x ∈ Xλ ) }
λ∈Λ
と定義する。
def.
例 : R の部分集合 Uε を Uε := (3 − ε, 3 + ε) = {x ∈ R | 3 − ε < x < 3 + ε } とし、R>0 を正の実数の集合とすると
∩
Uε = {3} である。これを示すには、
ε∈R>0
(i)
3∈
∩
Uε 、
(ii)
a ̸= 3 のとき a ∈
/
ε∈R>0
∩
Uε
ε∈R>0
をいえばよい。これらは次のように示せる。
(i) すべての ε ∈ R>0 に対して 3 − ε < 3 < 3 + ε なので 3 ∈ Uε 。よって、3 ∈
∩
Uε である。
ε∈R>0
|a − 3|
とする1 と、ε0 ∈ R>0 で、a > 3 ならば a = 3 + 2ε0 > 3 + ε0 となり、a < 3
(ii) 3 以外の数 a に関して、ε0 :=
2
ならば a = 3 − 2ε0 < 3 − ε0 となるので、どちらにしろ a ∈
/ Uε0 となる。すなわち、 a ∈
/ Uε となる ε ∈ R>0 が存在する
∩
ので、a ∈
/
Uε である。
ε∈R>0
よって、
∩
Uε は 3 のみを要素に持つので、主張は成立する。（例終）
ε∈R>0
5.2.3
同値類別
前節で集合を同値類に分けたが、その部分を、和集合の言葉を用いて書き直しておく。集合 X 上の同値関係 ∼ に関し
て、 a ∈ X を代表元とする同値類を C(a) とすると、
(i) すべての x ∈ X は同値類のいずれかに含まれる。
(ii) C(a) ∩ C(b) = ϕ か C(a) = C(b) のいずれか
がいえた。これを以下のようにまとめておく。
1a
∈
/ Uϵ となる ϵ をひとつ決めたいだけなので、2 で割っているのはそれほど大きな意味はない。ε0 が |a − 3| より小さな正の数であればよい。
37
定義 5.5 X の部分集合 A0 を適当にとり、
∪
(i)
C(a) = X
a∈A0
(ii) A0 の要素 a、a′ に対し、a ̸= a′ ⇒ C(a) ∩ C(a′ ) = ϕ （ただし、ϕ は空集合）
がなりたつとき、(i) の形の分解を同値類別という。A0 のことを代表系という。
注 : 同値類別については、代表系が有限のときがわかりや
X
すいかもしれない。代表系が A0 = {a1 , · · · , ak } のとき、
集合 X は、
X=
k
∪
a1
···
a2
ak
C(aj ) = C(a1 ) ∪ C(a2 ) ∪ · · · ∪ C(ak ),
j=1
ただし、C(ai ) ∩ C(aj ) = ϕ
···
(i ̸= j)
C(a1 ) C(a2 )
···
C(ak )
と分解できる。つまり、共通部分を持たない同値類の和集
合で書けるので、すべての X の要素が、班分けできたこと
になる。
def.
例 : 整数の集合 Z 上の同値関係 ≡ (mod n) に対し、代表系 A0 を A0 := {0, 1, · · · n − 1} ととると、Z の同値類別
Z=
∪
C(r) = C(0) ∪ C(1) ∪ · · · ∪ C(n − 1),
r∈A0
が得られる。証明は数論の講義で行う（？）（例終）
def.
例 : N × N 上の同値関係 (a1 , b1 ) ∼ (a2 , b2 ) ⇐⇒ a1 + b2 = a2 + b1 に対し、代表系 A0 を
def.
A0 := {(k + 1, 1) | k ∈ N} ∪ {(1, 1)} ∪ {(1, k + 1) | k ∈ N}
とすると、N × N の同値類別
N×N=
∪
C((a, b)) = · · · ∪ C((1, 3)) ∪ C((1, 2)) ∪ C((1, 1)) ∪ C((2, 1)) ∪ C((3, 1)) ∪ · · ·
(a,b)∈A0
が得られる。この分解が同値類別の条件を満たすことは、次のように示せる。
(i) (m, n) ∈ N × N とすると、m > n、m = n、m < n のいずれかだが、
(a) m > n のときは、m − n と等しい k ∈ N に対し (m.n) ∼ (k + 1, 1) なので、(m, n) ∈ C((k + 1, 1)) 、
(b) m = n のときは、(m.n) ∼ (1, 1) なので、(m, n) ∈ C((1, 1))、
(c) m < n のときは、n − m と等しい k ∈ N に対し (m.n) ∼ (1, k + 1) なので、(m, n) ∈ C((1, k + 1))
である。よって、すべての N × N の要素が、A0 を代表元とする同値類に含まれる。
(ii) A0 の互いに異なる２つの要素を代表元にする同値類が共通部分を持たないことをいう。
def.
A+
0 := {(k + 1, 1) | k ∈ N},
def.
A00 := {(1, 1)},
def.
A+
0 := {(k + 1, 1) | k ∈ N}
−
0
としたとき、A0 = A+
0 ∪ A0 ∪ A0 となるので、
(a) A+
(b) A−
0 の相異なる要素を代表元とする同値類、
0 の相異なる要素を代表元とする同値類、
+
−
0
(c) A0 と A0 の要素を代表元とする同値類、
(d) A0 と A00 の要素を代表元とする同値類、
38
−
(e) A+
0 と A0 の要素を代表元とする同値類
が共通部分を持たないことをいえばよい。
(a) k ̸= l のとき、k + 1 + 1 = l + 1 + 1 を満たす自然数 k 、l は存在しないので、(k + 1, 1) (l + 1, 1)。よって、
C((k + 1, 1)) ∩ C((l + 1, 1)) = ϕ。
(b) k ̸= l のとき、1 + k + 1 = 1 + l + 1 を満たす自然数 k 、l は存在しないので、(1, k + 1) (1, l + 1)。よって、
C((1, k + 1)) ∩ C((1, l + 1)) = ϕ。
(c) k + 1 + 1 = 1 + 1 を満たす自然数 k は存在しないので、(k + 1, 1) (1, 1)。よって、C((k + 1, 1)) ∩ C((1, 1)) = ϕ。
(d) 1 + 1 = 1 + k + 1 を満たす自然数 k は存在しないので、(1, k + 1) (1, 1)。よって、C((1, k + 1)) ∩ C((1, 1)) = ϕ。
(e) k + 1 + l + 1 = 1 + 1 を満たす自然数 k 、l は存在しないので、(k + 1, 1) (1, l + 1)。よって、
C((k + 1, 1)) ∩ C((1, l + 1)) = ϕ。
である。よって、A0 のどの相異なる２つの要素を代表元にする剰余類も共通部分をもたない。
このとき、C((k + 1, 1)) ↔ k 、C((1, k + 1)) ↔ −k 、C((1, 1)) ↔ 0 と思うと、N × N から Z を作ることができる。
（例終）
def.
例 : Z × Z× 上の同値関係 (a1 , b1 ) ∼ (a2 , b2 ) ⇐⇒ a1 b2 = a2 b1 に対し、代表系 A0 を
def.
A0 := {(a′ , b′ ) ∈ Z× × N | gcd(a′ , b′ ) = 1} ∪ {(0, 1)}
とすると、同値類別
Z × Z× =
∪
C((a, b))
(a,b)∈A0
が得られる。同値類別の条件を満たすことは以下のように示すことができる。
(i) (a, b) ∈ Z × Z× が A0 のどれかの要素を代表元とする同値類に含まれることをいえばよいが、
(a) a = 0 のとき、(a, b) ∼ (0, 1) だから (a, b) ∈ C((0, 1))
(b) a > 0 のとき、d = gcd(a, b)、a′ = a/d、b′ = b/d とすると、(a′ , b′ ) ∈ A0 で、(a, b) ∼ (a′ , b′ ) がいえるから、
(a, b) ∈ C((a′ , b′ ))。
(c) a < 0 のとき、d = gcd(a, b)、a′ = −a/d、b′ = −b/d とすると、(a′ , b′ ) ∈ A0 で、(a, b) ∼ (a′ , b′ ) がいえるから、
(a, b) ∈ C((a′ , b′ ))。
なので、これはなりたつ。
(ii) A0 の相異なる要素が共通部分を持たないことをいえばよいが、
(a) a′ ̸= 0 のとき、(a′ , b′ ) (0, 1) なので、C((a′ , b′ )) ∩ C((0, 1)) = ϕ
(b) a′ ̸= 0、a′′ ̸= 0 のとき、(a′ , b′ )、(a′′ , b′′ ) ∈ A0 に対し、(a′ , b′ ) ∼ (a′′ , b′′ ) 、すなわち、a′ b′′ = a′′ b′ とする。
gcd(a′ , b′ ) = 1 より、a′ は a′′ の約数、同様に、gcd(a′′ , b′′ ) = 1 より、a′ は a′′ の約数なので、a′ = a′′ となる。
同様に、b′ = b′′ がいえるので、(a′ , b′ ) = (a′′ , b′′ ) となる。対偶をとると、(a′ , b′ ) ̸= (a′′ , b′′ ) ⇒ (a′ , b′ ) (a′′ , b′′ )
となり、C((a′ , b′ )) ∩ C((a′′ , b′′ )) = ϕ
なので、これはなりたつ。
このとき、C((a, b)) ↔
a
とすると、Z × Z× から Q を作ることができる。（例終）
b
39

Download Report