集合論

ここでは数学を学ぶ上で最も基本的である論理学の基本について学ぶ。多くのことは既に知っていることであると思うが、それらを確認しておくということは大事である。勉強をしていて、何かが分からないときには、自分が何を理解していないのかを考えてみると良い。多くの場合、理解できていないのはそのとき勉強していることではなく、もっと前に段階にある。そして、それが実はここで学ぶ論理の部分であるということも少なくはないのである。

1.1 命題

それが真 (true) であるか偽 (false) であるかがはっきりとしている事柄を命題という。例えば以下は命題の例である。

もちろん (1), (3) は真で (2), (4) は偽である。 (2) にはやや注意が必要である。偶数のうちには $4$ の倍数も含まれているので (2) は真であったり、偽であったりするように思われる。しかし、実は (2) は

ということを主張していると理解されるのである。したがって一つでも $4$ の倍数でない偶数 (例えば $2$ ) があれば偽であるということになるのである。

どれも明確な基準が定められておらず、真か偽か判定できない。

とすると $n$ を定めれば $A$ , $B$ 共に真か偽かが定まり、これらは命題である。真であるか偽であるかが $n$ に依存するので、このような場合は単に $A$ , $B$ とは書かずに $A (n )$ , $B (n)$ などと書くこともある。

とおくと、これらも命題であり $C$ は偽、 $D$ は真である。 $C$ や $D$ は $n$ には依存しない命題である。ここで $A(n )$ や $B(n)$ は命題であり「 $A (n)$ ならば $B (n)$ である」というのも命題であることに注意する。

一般に「 $A$ ならば $B$ である」ということを $A ⇒ B$ または $B ⇐ A$ と書く。命題 $B ⇒ A$ を命題 $A ⇒ B$ の逆命題、または単に逆という。ある命題が真であっても、その逆が真であるとは限らない。命題 $A ⇒ B$ が真であるとき $A$ を $B$ の十分条件といい、 $B$ を $A$ の必要条件という。命題 $A ⇒ B$ と命題 $B ⇒ A$ が共に真であるとき $A$ を $B$ の必要十分条件といい $A ⇔ B$ と書く。明らかに、このとき $B$ は $A$ の必要十分条件でもある。 $A ⇔ B$ であるとき命題 $A$ と $B$ は同値であるともいう。同値な命題を同じ命題と考えることもある。

二つの命題 $A$ , $B$ が同時に真であるときに真であると定めた命題を $A ∧ B$ と書き $A$ かつ $B$ と読む。二つの命題 $A$ , $B$ の少なくとも一方が真であるときに真であると定めた命題を $A ∨ B$ と書き $A$ または $B$ と読む。 $A ∧ B$ を $A and B$ 、 $A ∨ B$ を $A or B$ などとも書く。

例1.1.1. 自然数 $n$ に対して

$A (n)$: : $n$ は $2$ の倍数である。
$B (n)$: : $n$ は $3$ の倍数である。

とすれば

$A (n) ∧ B(n)$: : $n$ は $2$ の倍数であり、かつ $3$ の倍数である。
$A (n) ∨ B(n)$: : $n$ は $2$ の倍数、または $3$ の倍数である。

などとなる。明らかに

: $n$ は $6$ の倍数である。

は $A(n ) ∧ B (n )$ であるための必要十分条件である。

命題 $A$ に対して、 $A$ が偽のときに真と定めた命題を $ｬA$ と書き $A$ の否定、または $A$ でないと読む。明らかに $ｬ (ｬA )$ は $A$ の必要十分条件である。

命題 $B ⇒ A$ が真であるとき、命題 $ｬA ⇒ ｬB$ は常に真となる。これを $B ⇒ A$ の対偶という。 $ｬA ⇒ ｬB$ の対偶は $B ⇒ A$ となるので、 $ｬA ⇒ ｬB$ であることは $B ⇒ A$ となることの必要十分条件である。

対偶が常に真であるということは次のように考えると理解しやすい。 $B ⇒ A$ ということは、 $B$ が $A$ よりも “強い” ということである。図で表すと Figure 1.1 のようになる。

よってこのとき $ｬA$ は $ｬB$ よりも “強く”、 $ｬA ⇒ ｬB$ が成り立つのである。

例1.1.2. 「 $B (n)$ ならば $A (n)$ である」という命題の否定は「 $B(n )$ であっても $A (n)$ でないことがある」である。「 $B(n )$ ならば $A (n )$ でない」とはならないことに注意する。これについては後で詳しく学ぶ。

命題 $B ⇒ A$ を考える。 $A$ が真であれば、この命題は常に真である。例えば

という命題は $B$ が真であるか偽であるかにかかわらず、常に真である。この対偶を考えると $ｬA ⇒ ｬB$ は $A$ が真、すなわち $ｬA$ が偽であれば常に真となる。よって命題 $B ⇒ A$ は $B$ が偽であれば $A$ が真であるか偽であるかにかかわらず、常に真である。

論理についての基本的な事柄をまとめておく。証明は与えない。同様のことが後に学ぶ集合に対しても成り立つ。

定理1.1.3.

$A ∧ (ｬA )$ は常に偽である。
$A ∨ (ｬA )$ は常に真である。
$A = ⇒ A$ は常に真である。
$A ∧ B ⇐ ⇒ B ∧ A$
$A ∨ B ⇐ ⇒ B ∨ A$
$A ∧ (B ∧ C ) ⇐ ⇒ (A ∧ B ) ∧ C$
$A ∨ (B ∨ C ) ⇐ ⇒ (A ∨ B ) ∨ C$
$ｬ(ｬA ) ⇐ ⇒ A$
(ド・モルガンの公式) $ｬ (A ∧ B ) ⇐ ⇒ (ｬA ) ∨ (ｬB )$
(ド・モルガンの公式) $ｬ (A ∨ B ) ⇐ ⇒ (ｬA ) ∧ (ｬB )$
$A ∧ (A ∧ B ) ⇐ ⇒ A ∧ B$
$A ∨ (A ∨ B ) ⇐ ⇒ A ∨ B$
$A ∨ (A ∧ B ) ⇐ ⇒ A$
$A ∧ (A ∨ B ) ⇐ ⇒ A$

例1.1.4. $(ｬA ) =⇒ A$ は常に偽であるように思われるが、先に述べたように $A$ が真であればこれは真である。

注意. $A$ が偽であれば、任意の命題 $B$ に対して $A =⇒ B$ は真になるのだが、これが感覚的に受け入れがたいという学生も少なくはない。先の説明では $A =⇒ B$ を感覚的に理解したが、正確には $A = ⇒ B$ の定義が $(ｬA ) ∨ B$ であり、認めてもらうしかない。

1.2 真理表

前の節で述べたことを理解するには真理表と呼ばれる表を用いるとよい。ある命題が真であることを $1$ , 偽であることを $0$ と表すことにする。二つの命題 $A$ , $B$ を考えるとき、それが真であるか偽であるかの可能性は 4 通りある。 $A, B$ によって定まる基本的な命題については以下の通りである。

例1.2.1. 真理表を用いて、ド・モルガンの公式を示してみよう。

-----------------------------------------------------------A--B---ｬ(A-∧-B-)--(ｬA-) ∨-(ｬB-)-ｬ(A--∨-B)--(ｬA-) ∧-(ｬB-)-1 1 0 0 0 01 0 1 1 0 00 1 1 1 0 0-0--0-------1-----------1------------1------------1-------

$ｬ(A ∧ B )$ を表す列と $(ｬA ) ∨ (ｬB )$ を表す列が等しいことから $ｬ (A ∧ B) ⇐ ⇒ (ｬA ) ∨ (ｬB )$ が分かる。 $ｬ (A ∨ B ) ⇐ ⇒ (ｬA ) ∧ (ｬB )$ も同様である。

例1.2.2. 真理表を用いて、ある命題と、その対偶が同値であることを示してみよう。

------------------------------------------A B A ⇒ B ｬA ｬB (ｬB ) ⇒ (ｬA )------------------------------------------1 1 1 0 0 11 0 0 0 1 00 1 1 1 0 10 0 1 1 1 1------------------------------------------

これによって命題とその対偶の同値性が分かる。

例1.2.3. 命題 $A ⇒ B$ と $B ⇒ C$ が共に真であるとき、 $A ⇒ C$ も真である。これを真理表を用いて示してみよう。

----------------------------------------------------------------------------------A--B--C---A-⇒-B--B-⇒--C--(A-⇒-B)-∧(B-⇒-C-)-A-⇒--C--(A-⇒-B)-∧(B-⇒-C-) =⇒-(A-⇒--C)-1 1 1 1 1 1 1 11 1 0 1 0 0 0 11 0 1 0 1 0 1 11 0 0 0 1 0 0 10 1 1 1 1 1 1 10 1 0 1 0 0 1 10 0 1 1 1 1 1 1-0--0---0----1-------1------------1------------1-----------------1---------------

問1.2.4. $ｬ(A ⇒ B)$ と $A ∧ (ｬB )$ が同値な命題であることを真理表を用いて示せ。

注意. 先に述べたように $A ⇒ B$ の定義は $(ｬA ) ∨ B$ である。

1.3 「任意の...」と「ある...」

数学では「任意の $⋅⋅⋅$ に対して $⋅⋅⋅$ である」とか「ある $⋅⋅⋅$ が存在して $⋅⋅⋅$ である」などという言い方がよく使われる。これらの意味をきちんと理解していないと、証明などが理解できない。まずは例を見てみよう。

A の否定は何であろうか。 A が偽であるということは、一つでも $2x ≥ 0$ が成り立たない実数 $x$ が存在すればよい。したがって

となる。より自然にいえば「 $x2 < 0$ となる実数 $x$ が存在する」ということになる。次に実数列 $S = {a ,a ,⋅⋅⋅}1 2$ に対して次の命題を考える。

この否定は何であろうか。一つでも $an < 0$ となる自然数 $n$ が存在すれば $B (S)$ は真になるので、 $B (S )$ が偽になるためには、すべての自然数 $n$ に対して $an ≥ 0$ でなければならない。よって

以上のように「任意の $⋅⋅⋅$ に対して $⋅⋅⋅$ である」と「ある $⋅⋅⋅$ が存在して $⋅⋅⋅$ である」ということは、否定によって互いに移り会うものなのである。しっかりと覚えておこう。

数学の教科書などでは、先の例のように命題をきちんと文章で表している場合がほとんどであるが、講義などでは適当に省略した記号を用いる場合が多い。この記号が理解できないことも講義が分からなくなる一つの要因である。ここできちんと理解しておこう。

非負整数全体を $ℤ ≥0$ , 負の整数全体を $ℤ <0$ などと書くこともある。 $:=$ の記号は左辺を右辺で定めるという意味であるが、人によって違う記号を用いる場合もある。また集合という言葉は後できちんと説明するが、ここでは単に「自然数全体の集まり」のように理解すればよい。 $n$ が自然数であるということを $n ∈ ℕ$ と表す。他の記号についても同様である。

さて「任意の自然数 $n$ に対して $⋅⋅⋅$ 」ということを記号で「 $∀n ∈ ℕ$ に対して $⋅⋅⋅$ 」などと書く。「ある自然数 $n$ に対して $⋅⋅⋅$ 」ということは記号で「 $∃n ∈ ℕ$ に対して $⋅⋅⋅$ 」などと書く。 $∀$ は All の A を引っくり返したもの、 $∃$ は Exists の E を引っくり返したものである。次の命題はすべて同じことを言っている。

all, any, every は英語としては、その与えるニュアンスが異なるが、論理的には同じと思ってよい。同様に次も同じことである。

「 $∃x$ such that $B$ 」というのは「 $B$ であるような $x$ が存在する」ということを英語で言っているだけである。「such that」を省略して「s.t.」と書くことも多い。次の二つの命題を考えよう。

この二つは記述してある順番が違うだけである。同じ意味だろうか。実はこれは全く違う意味なのである。それは文章にして読んでみれば分かる。

$C$ は与えられた $r ∈ ℝ$ に対して $n ∈ ℕ$ を決めればよいので真である。一方 $D$ は $r ∈ ℝ$ に関係なく $n ∈ ℕ$ が存在しなければならず偽である。このように省略した記号は便利ではあるが、間違えをおかしやすいものである。試験の答案などにはきちんとした文章を書くことを勧める。

注意. 上の命題 $C$ をより自然な言葉で「任意の $r ∈ ℝ$ に対して $r < n$ となるような $n ∈ ℕ$ が存在する」と読むこともできる。しかしこの場合、

任意の $r ∈ ℝ$ に対して、 $r < n$ となるような $n ∈ ℕ$ が存在する
任意の $r ∈ ℝ$ に対して $r < n$ 、となるような $n ∈ ℕ$ が存在する

と句点を入れてみると (1) は $C$ を、 (2) は $D$ を表している。このように命題を記述する場合には、その意味が明らかとなるように細心の注意が必要となる。通常は、句点がない場合にもその文脈からどちらの意味であるかが読み取れることが多いが、少なくとも試験ではきちんと区別しなくてはならない。

上の $C$ , $D$ の否定を求めておく。文章から否定を考えるのはやや難しいが、記号を用いた場合には簡単であることが分かるだろう。

これをもう少し詳しく説明しよう。命題 $C$ は丁寧に書くと以下のようになる。

ここで ( $r < n$ ) は $r$ と $n$ に関する命題である。 ( $∃n ∈ ℕ$ ( $r < n$ )) は $r$ のみに関する命題である。なぜならば $n$ はこの中で定義されているので、これは特定の $n$ に関することをいっている訳ではないからである。同様に考えて命題 $C$ はどの変数にも依存しない命題である。 $ｬC$ は以下のように解釈される。

例1.3.1 ( $ε$ - $δ$ 論法). 関数 $y = f(x)$ が $x = a$ で連続であるとは、以下の条件を満たすこととして定義される。

[定義] 任意の正の数 $ε$ に対して、ある正の数 $δ$ があって $|x - a | < δ$ ならば $|f (x) - f (a)| < ε$ が成り立つ。

例えば $y = f(x ) = 2x$ という関数は任意の $x = a$ において連続であるが、それは以下のように証明される。

証明. $ε$ を任意の正の数とする。 $δ = ε∕2$ とする。このとき $|x - a| < δ$ ならば

|f (x) - f(a)| = |2x - 2a | = 2|x - a| < 2δ = ε

である。 (証明終り)

ここで重要なのは「ある正の数 $δ$ があって」といっているので本当に $δ$ を決めてやる必要があるということである。 $δ = ε∕2$ というのは本質的ではなく、例えば $δ = ε∕3$ でも構わない。存在することをいいたいのだから、少なくとも一つの例を見せればいいのである。

さて、次に連続でないことを証明してみよう。 $y = f(x)$ は $x < 0$ のとき $0$ で $x ≥ 0$ のとき $1$ で定めるとする。このとき、この関数は $x = 0$ で連続でないことは分かるだろう。これを上の定義にしたがって証明する。連続でないことを示したいので定義を否定すればよい。このままで考えるとやや難しいので、連続の定義を記号を用いて書き直してみる。

[定義] $∀ε > 0$ , $∃ δ > 0$ , $∀x ∈ ℝ$ ( $|x - a | < δ$ $= ⇒$ $|f(x) - f(a)| < ε$ ).

これを否定するので、連続でないということは

$∃ε > 0$ , $∀δ > 0$ $∃x ∈ ℝ$ $ｬ$ ( $|x - a| < δ$ $= ⇒$ $|f(x) - f(a )| < ε$ ).

$ｬ$ ( $|x - a | < δ$ $= ⇒$ $|f(x) - f(a)| < ε$ ) は「 $|x - a| < δ$ and $|f(x) - f(a)| ≥ ε$ 」ということである (問 1.2.4 )。したがって、いいたいことは

$∃ε > 0$ , $∀δ > 0$ , $∃x ∈ ℝ$ (( $|x - a| < δ$ ) $∧$ ( $|f (x) - f(a)| ≥ ε$ )).

ということになる。さて証明をしてみよう。 $∃ε > 0$ となっているので $ε$ をきちんと決めてやらなくてはならないことに注意する。 $x ∈ ℝ$ も同様に決めてやる必要がある。

証明. $ε = 1∕2$ とする。任意の $δ > 0$ に対して $x = - δ∕2$ とすれば $|x - 0| = δ∕2 < δ$ であって $|f(x ) - f (0 )| = |0 - 1| = 1 ≥ 1∕2 = ε$ である。 (証明終り)

この証明で $x$ は $δ$ によって決まっていることに注意しよう。このような場合「 $x$ の取り方は $δ$ に依存する」などという言い方をする。またこの場合も $ε$ や $x$ はこのように決めなくてはならないわけではなく、例えば $ε = 1∕4$ , $x = - δ∕5$ などでも構わない。 $ε$ をどのように決めるかは問題によって異なり、自分で考えるしかない。