現代の数学は殆どの場合,集合を用いて議論が展開される.集合とは「数学的対象の集まり」として定義されるものである.これを用いることで,数学の議論を整理することができる.例えば,整数は「 $n$ を整数とする」というように書いていた文は, $\mathbb{Z}$ を整数全体の集合と定めることで,「 $n \in \mathbb{Z}$ とする」と書くことができる.このように,集合を用いることで,自然言語で表されていた数学をより形式的なものにすることができるようになった.このような集合論を素朴集合論という.

集合は19世紀後半にCantorによって生み出された概念であり,発見されて以来多くの研究者によって集合の性質が調べられた.しかし, Cantorの集合論には致命的な矛盾を抱えることになる.例えば,こんにちRusselの逆理として知られる「パラドックス」がある.これは,

$R := \{ x \ | \ x \notin x \}$

という集合を考えると,

$R \in R \leftrightarrow R \notin R$

となってしまい,矛盾するというものである.このパラドックスが起こる理由は,集合を「ものの集まり」という曖昧な定義によって定めていることに起因している.その他, Cantorの逆理やBurali-Fortiの逆理など, Cantorの集合論には様々な矛盾を孕んでいることが当時から知られていた.

そこで,こうした集合論の逆理から解放されることが要請された.その中でも,ZFC公理系は20世紀初頭にZermeloによって考案され, Fraenkel(やVon Neimannら)によって修正されたことからZF公理系と呼ばれ,更に選択公理(The Axiom of Choice)を追加したものをZFC公理系という.この公理系は現在広く使用されており,大抵の場合,この公理系を特に意識することなく用いる.このように,公理に立脚して議論される集合論を公理的集合論という.

本シリーズ「現代数学の基礎・集合論入門」では, ZFC公理系に基づく公理的集合論について説明する.現在の大学数学科では学部3～4年次に学習する内容だが,全国的に見ても公理的集合論を取り扱っている大学は決して多くないらしい.しかし,現代数学を学ぶ上で,こうした背景があることを知っておくことは重要であるだろうから,これを機に知っていただけたら幸いである.

第1講目次

第1講目次
集合論言語
外延性公理と集合の存在
参考文献

集合論言語

この節は集合論を厳密に議論するのに必要な言語と論理について説明している.しかし,この節は読み飛ばしても今後の議論においてあまり支障はない.必要になったら戻って読み返す程度でよい.

集合論を述べる為には,それを記述する為の言語が必要になる.集合論における言語を集合論言語という.集合論言語は１階述語論理と呼ばれるものを用いて定義される.なお,この段階では集合そのものは定義していないことに注意.また,この段階ではそれぞれの記号は意味をもたない単なる記号であることに注意.

Def.1.1(集合論言語)

集合論言語とは,次を満たす体系をいう.

記号
- 論理記号： $\vee, \ \wedge, \ \rightarrow, \ \leftrightarrow, \ \neg, \ \forall, \ \exists, \ =$
- 変数： $x, y, z, u, v, w, \cdots$
- 2変数述語記号： $\in$
論理式の定義
- $x, y$ が変数ならば, $x = y$ と $x \in y$ は論理式である(この論理式を原子論理式という).
- $\varphi, \psi$ が論理式ならば, $\varphi \vee \psi, \ \varphi \wedge \psi, \ \varphi \rightarrow \psi, \ \varphi \leftrightarrow \psi, \ \neg \varphi$ は論理式である.
- $\varphi$ が論理式, $x$ が変数ならば, $\forall x \varphi, \ \exists x \varphi$ は論理式である.
- 以上によりつくられたもののみが論理式である.

Def.1.2(論理記号の解釈)

論理式 $\varphi, \psi$ と変数 $x$ に対して,

$\varphi \vee \psi$ を「 $\varphi$ または $\psi$ 」と解釈する.
$\varphi \wedge \psi$ を「 $\varphi$ かつ $\psi$ 」と解釈する.
$\varphi \rightarrow \psi$ を「 $\varphi$ ならば $\psi$ 」と解釈する.
$\varphi \leftrightarrow \psi$ を「 $\varphi$ と $\psi$ は同値である」と解釈する.
$\neg \varphi$ を「 $\varphi$ でない」と解釈する.
$\forall x \varphi$ を「すべての $x$ に対して, $\varphi$ が成り立つ」と解釈する.
$\exists x \varphi$ を「 $\varphi$ を満たすような $x$ が存在する」と解釈する.

Def.1.3(集合とその元)

集合論言語の変数を集合という.集合 $x, y$ に対し, $x \in y$ を $x$ は $y$ の元(要素)である,または $x$ は $y$ に属するという.

$\neg ( x \in y ), \ \neg ( x = y )$ をそれぞれ $x \notin y, \ x \neq y$ とかく.

Def.1.4(束縛変数,自由変数)

論理式 $\varphi$ と変数 $x$ に対し, $\forall x \varphi, \ \exists x \varphi$ における $\varphi$ をそれぞれ $\forall x, \ \exists x$ のスコープという. $x$ が $\varphi$ の中にある $\forall x, \ \exists x$ のスコープの中に現れているとき, $x$ は $\varphi$ の束縛変数であるという.そうでないとき, $x$ は $\varphi$ の自由変数であるという.

$x$ が $\varphi$ の自由変数であるとき, $\varphi(x)$ とかく.変数 $y$ が論理式 $\varphi$ の中の $\forall y, \ \exists y$ のスコープの中に $x$ が自由に現れないとき, $y$ は $\varphi$ において $x$ について自由であるという.自由変数 $x$ をもつ論理式 $\varphi(x)$ に対し,変数 $y$ が $\varphi(x)$ において $x$ について自由であるとき, $x$ を $y$ に置き換えて得られる論理式を $\varphi(x/y), \ \varphi(y)$ などとかく.

論理式 $\varphi$ が自由変数をもたないとき, $\varphi$ を文(閉論理式)という.論理式 $\varphi$ に含まれる自由変数をすべて $\forall$ で束縛して得られる論理式を $\varphi$ の全称閉包という.

Ex.1.5

(1) $\varphi \stackrel{def.}{\equiv} \forall x ( x = x )$

という論理式を考えると, $x$ は $\forall x$ のスコープの中に現れているので, $x$ は $\varphi$ の束縛変数である.

(2) $\varphi \stackrel{def.}{\equiv} \forall y ( y \in x )$

という論理式を考えると, $x$ は $\forall x, \ \exists x$ のスコープの中に現れていないので, $x$ は $\varphi$ の自由変数である.よって, $\varphi$ は $\varphi(x)$ とかける.

(3) $y$ が $\varphi$ において $x$ について自由であるとは, $\varphi(x)$ を $\varphi(y)$ としたときに衝突を起こさないという意味である.例えば,

$\varphi(x) \stackrel{def.}{\equiv} \exists y ( x \in y )$

と定めるとき, $y$ は $\varphi$ において $x$ について自由でない.このとき, $\varphi(y)$ は

$\varphi(y) \equiv \exists y ( y \in y )$

となってしまい, $\exists y$ の中のスコープ $x \in y$ の中にある $x$ と衝突を起こしてしまう.しかし,変数 $z$ は $\varphi$ において $x$ について自由である.このとき,

$\varphi(z) \equiv \exists y ( z \in y )$

とかける.

(4) $\varphi \stackrel{def.}{\equiv} \exists y \forall x ( x \notin y )$

は文である.

Def.1.6(論理式の略記法)

論理式 $\varphi$ と変数 $x, y$ に対し,次の略記を導入する.

$\exists ! y \varphi(y)$ とは $\exists y \varphi(y) \wedge \forall x \forall y ( \varphi(x) \wedge \varphi(y) \rightarrow x = y )$ のことをいう.
$\exists x \in y \varphi(x)$ とは $\exists x ( x \in y \wedge \varphi(x) )$ のことをいう.
$\forall x \in y \varphi(x)$ とは $\exists x ( x \in y \rightarrow \varphi(x) )$ のことをいう.

Def.1.7(論理公理)

次の論理式を集合論言語上の論理公理という.

$\varphi \rightarrow ( \psi \rightarrow \varphi )$ .
$( \varphi \rightarrow \psi ) \rightarrow ( ( \varphi \rightarrow ( \psi \rightarrow \theta ) ) \rightarrow ( \varphi \rightarrow \theta ) )$ .
$( \varphi \wedge \psi ) \rightarrow \varphi, \ ( \varphi \wedge \psi ) \rightarrow \psi$ .
$\varphi \rightarrow ( \psi \rightarrow ( \varphi \wedge \psi ) )$ .
$\varphi \rightarrow ( \varphi \vee \psi ), \ \psi \rightarrow ( \varphi \vee \psi )$ .
$( \varphi \rightarrow \theta ) \rightarrow ( ( \psi \rightarrow \theta ) \rightarrow ( ( \varphi \vee \psi ) \rightarrow \theta ) )$ .
$( \varphi \rightarrow \psi ) \rightarrow ( ( \varphi \rightarrow \neg \psi ) \rightarrow \neg \varphi )$ .
$\neg ( \neg \varphi ) \rightarrow \varphi$ .
$\varphi(y) \rightarrow \exists x \varphi(x)$ .ここで, $y$ は $\varphi(x)$ において $x$ について自由である.
$\forall x \varphi(x) \rightarrow \varphi(y)$ .ここで, $y$ は $\varphi(x)$ において $x$ について自由である.
$\forall x ( \varphi \rightarrow \psi ) \rightarrow ( \forall x \varphi \rightarrow \forall x \psi )$ .
$\forall x \neg \varphi \leftrightarrow \neg \exists x \varphi$ .

Def.1.8(等号公理)

次の論理式を集合論言語上の等号公理という.

$\forall x ( x = x )$ . (反射律)
$\forall x \forall y ( x = y \leftrightarrow y = x )$ . (対称律)
$\forall x \forall y \forall z ( x = y \wedge y = z \rightarrow x = z )$ . (推移律)
$\forall x \forall y \forall x' \forall y' ( x = y \wedge x' = y' \rightarrow ( x \in x' \leftrightarrow y \in y' ) )$ .

Def.1.9(モーダス・ポーネンス)

次の推論規則をモーダス・ポーネンスという.

$\varphi, \ \varphi \rightarrow \psi \Longrightarrow \psi$ .

即ち, $\varphi$ と $\varphi \rightarrow \psi$ が成り立てば, $\psi$ も成り立つという推論をいう.

Def.1.10(証明)

$\Sigma$ を文の族, $\varphi$ を文とする.このとき, $\Sigma$ から $\varphi$ の証明(演繹)とは,文の有限列 $\varphi_0, \cdots, \varphi_n$ が存在して, $\varphi$ は $\varphi_n$ であって,各 $i = 0, \cdots n$ に対して $\varphi_i$ は次のいずれかであることをいう.

$\varphi_i$ は $\Sigma$ の文である.
$\varphi_i$ は論理公理または等号公理である.
ある $j, k \lt i$ が存在して, $\varphi_i$ は $\varphi_j, \varphi_k$ からのモーダス・ポーネンスによって導かれる.即ち, $\varphi_k$ は $\varphi_j \rightarrow \varphi_i$ である.

$\Sigma$ から $\varphi$ の証明が存在するとき, $\varphi$ は $\Sigma$ から証明可能であるといい, $\Sigma \vdash \varphi$ とかく.特に, $\varphi$ が $\emptyset$ から証明可能であるとき, $\varphi$ は単に証明可能であるといい, $\vdash \varphi$ とかく.

文の族 $\Sigma$ と文 $\varphi$ に対して, $\Sigma \vdash \varphi$ を満たすとき, $\Sigma$ を公理系, $\Sigma$ の文を公理, $\varphi$ を $\Sigma$ の定理という.

Rem.1.11(自然言語と集合論言語)

ここまで,集合論言語とその上の1階述語論理体系について説明した.このとき,論理公理と推論規則から,これまで常識的に行われていた推論は可能である.例えば,ド・モルガンの法則 $\neg ( \varphi \wedge \psi ) \leftrightarrow \neg \varphi \vee \neg \psi$ と $\neg ( \varphi \vee \psi ) \leftrightarrow \neg \varphi \wedge \neg \psi$ は証明可能であり,対偶 $( \varphi \rightarrow \psi ) \leftrightarrow ( \neg \psi \rightarrow \neg \varphi )$ も証明可能であり,背理法(帰謬法) $( \varphi \rightarrow ( \psi \wedge \neg \psi ) ) \rightarrow \neg \varphi$ も証明可能である.従って,以上の集合論言語とその上の1階述語論理体系は自然言語を形式的に書き表す手法,つまり「常識的な推論の為の言語」とみて差し支えない.

外延性公理と集合の存在

以後,すべての議論は集合論言語とその上の1階述語論理体系の下で行う.

Def.1.12(集合の存在公理)

次の文を集合の存在公理という.

$\exists x ( x = x )$

以後,集合の存在公理を仮定する.

集合の存在公理は公理の名前の通りで,集合は何かはわからないが確かに存在することを主張している.通常,集合論を議論する際はこの公理をわざわざ主張しない.というのも,集合論言語上で議論する以上,何か1つは集合が存在しないと議論にならないからである.しかし,ここではそれを明文化することで集合の存在をはっきりとさせ,わかりやすくする.

Def.1.13(外延性公理)

次の文を外延性公理という.

$\forall x \forall y ( x = y \leftrightarrow \forall z ( z \in x \leftrightarrow z \in y ) )$

以後,外延性公理を仮定する.

外延性公理は「集合が等しいことの特徴付け」である.集合が等しいことを言うには,集合の元を調べればいい.つまり,集合 $X$ のすべての元が集合 $Y$ に属していて,逆に $Y$ のすべての元が $X$ に属していれば, $X$ と $Y$ は同じ集合であることを主張している.素朴集合論では集合が等しいことは定義だったが,ここではルールとして規定する.

Def.1.14(部分集合)

$x \subset y \stackrel{def.}{\Longleftrightarrow} \forall z ( z \in x \rightarrow z \in y )$ .

$x \subset y$ のとき, $x$ は $y$ の部分集合である,または $x$ は $y$ に含まれるという.

$x \subsetneq y \stackrel{def.}{\Longleftrightarrow} x \subset y \wedge x \neq y$ .

$x \subsetneq y$ のとき, $x$ は $y$ の真部分集合という.

Thm.1.15

$x \subset x$ .
$x \subset y \wedge y \subset x \rightarrow x = y$ .
$x \subset y \wedge y \subset z \rightarrow x \subset z$ .

証明

外延性公理と部分集合の定義より明らかであろう.しかし,はじめての定理であるから,念のため証明を書いておこう.

(1) $z$ をとり, $z \in x$ とすると,この仮定から確かに $x \subset x$ である.

(2) $x \subset y$ かつ $y \subset x$ とする. $z$ をとる. $z \in x$ とすると, $x \subset y$ より $z \in y$ である.また, $z \in y$ とすると, $y \subset x$ より $z \in x$ である.従って,外延性公理より $x = y$ である.

(3) $x \subset y$ かつ $y \subset z$ とする. $a$ をとり, $a \in x$ とする.このとき, $x \subset y$ より $a \in y$ である.これと $y \subset z$ より $a \in z$ である.よって, $x \subset z$ である. $\square$