集合・関係・関数

講座の言語

次の課では、ある関数、すなわち後者関数によって自然数を定義する。この関数は単射であり、$1$ をとらない。次の単元では整数と有理数を同値関係の同値類として構成する。組合せ論の課では元の個数を全単射によって定義する。自然数の順序は順序関係であり、第三単元では実関数を合成し、その逆を求める。これらの語はすべて同じ言語に属しており、講座が以後引用する最初の定理とともに、使う前に定めておくのがよい。

何を先取りしているかを明らかにしておく必要がある。例では、小さな自然数とその順序、加法、乗法、整除性、割り算の余りを、学校で学んだとおりに用いる。次の課はペアノの公理によって自然数を定義し、この単元の課はこれらの演算を定義してその性質を証明するが、この課の例はどれも用いないので、循環はない。この課のどの定理も例に依存しない。数は定理がどのように働くかを見るためだけに使われる。

認めること

集合とは対象の集まりであり、その対象を元という。$a \in A$ と書いて $a$ が $A$ に属することを表し、$a \notin A$ と書いてそれを否定する。集合と所属は定義しない。それらは算術における $1$ と後者のように、原始的な概念である。しかし、すべての性質が集合を定めるわけではない。自分自身に属さない集合全体からなる集合 $R$ が存在するとすると、「$R$ は $R$ に属するか」という問いには答えがない。$R$ の定義から $R \in R \leftrightarrow R \notin R$ が得られるからである。この矛盾はラッセルが 1901 年に発見したもので、集合の作り方を制限することを強いる。性質は、すでに与えられた集合から元を選び出すことしかできない。

証明なしに認める事実（素朴集合論の規則）。この課で用いる素朴集合論の規則を、証明なしに認める。同じ元をもつ二つの集合は等しい。与えられた集合 $A$ と性質 $P$ から、$\{ x \in A : P(x) \}$ という集合、すなわち $A$ の元のうちその性質を満たすものからなる集合を作ることができる。さらに、空集合、集合 $\{a, b\}$（その元は $a$ と $b$ だけ）、集合からなる集合の元の和集合、そして集合の部分集合全体からなる集合が存在する。自然数の集合の性質をもつ集合の存在は、次の課で認める。

これらの規則はツェルメロとフレンケルの公理に属し、その研究は集合論の分野であって、この講座の範囲を超える。そのためここでは認めることにし、何を使っているかが正確にわかるように明示しておく。

量化子の論理

証明は結合子 $\neg$、$\wedge$、$\vee$、$\rightarrow$、$\leftrightarrow$ によって言明を組み合わせる。これらの結合子の法則は補助講座数理論理学 I：命題論理で、その言語から学ぶ。ここでは次のことを思い出せば十分である。含意 $p \rightarrow q$ は、$p$ が真で $q$ が偽のときに限り偽であり、その対偶 $\neg q \rightarrow \neg p$ と同値である。そしてド・モルガンの法則は連言と選言の否定を与える。

しかし、集合について語るには、すべての元について、あるいはある元についての言明も必要である。$P(x)$ が $A$ の元の性質であるとき、言明 $(\forall x \in A)\,P(x)$ は「すべての $x$（$A$ の元）について $P(x)$」と読み、$A$ のすべての元がその性質を満たすと主張する。言明 $(\exists x \in A)\,P(x)$ は「ある $x$（$A$ の元）が存在して $P(x)$」と読み、少なくとも一つの元がその性質を満たすと主張する。そして $(\exists! x \in A)\,P(x)$ は、その性質を満たす元がちょうど一つあると主張する。記号 $\forall$ と $\exists$ は量化子と呼ばれ、それぞれ全称量化子、存在量化子である。

証明なしに認める事実（量化子の否定）。すべての元が性質を満たすことを否定するのは、ある元がそれを満たさないと主張することであり、ある元がそれを満たすことを否定するのは、どの元もそれを満たさないと主張することである。

これらの規則は一階論理に属し、ここでは認める。これらはド・モルガンの法則を一般化している。$A = \{a, b\}$ ならば、全称言明は $P(a) \wedge P(b)$ であり、存在言明は $P(a) \vee P(b)$ だからである。量化子の順序は重要である。言明 $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ は、どの自然数にもそれより大きい別の自然数があることを述べており、真である。言明 $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ は、すべての自然数より、それ自身よりも大きい自然数があることを述べており、偽である。

言明の論理形式が、その証明の仕方を決める。この課で用いる方針は次のとおりであり、その論理的な根拠は演繹の技法の課で学ぶ。

• $(\forall x \in A)\,P(x)$ を証明するには、任意の元 $x$（$A$ の元）をとり、$A$ に属すること以外は何も仮定せずに、$P(x)$ を証明する。
• $(\exists x \in A)\,P(x)$ を証明するには、$A$ の具体的な元で $P$ を満たすものを示す。$(\forall x \in A)\,P(x)$ を否定するには反例、すなわちそれを満たさない元が一つあれば十分である。
• $p \rightarrow q$ を証明するには、$p$ を仮定して $q$ を導くか、対偶 $\neg q \rightarrow \neg p$ を証明するか、$p \wedge \neg q$ を仮定して矛盾を導く。
• $p \leftrightarrow q$ を証明するには、二つの含意 $p \rightarrow q$ と $q \rightarrow p$ を証明する。

集合

所属、相等、包含

集合は、中括弧の中にその元を並べる外延的記法、たとえば $\{1, 2, 3\}$ で記述することも、性質による内包的記法、たとえば $\{ n \in \mathbb{N} : n \leq 3 \}$（同じ集合である）で記述することもできる。外延性の規則は、集合がその元によって決まることを述べる。

ここから、外延的記法では順序も重複も関係ないことがわかる。$\{1, 2, 2\}$ と $\{2, 1\}$ は同じ元をもつので同じ集合である。また、元をもたない集合はただ一つ、空集合 $\emptyset$ であることもわかる。元をもたない二つの集合は同じ元をもつ、すなわちどちらも元をもたないからである。

定義（包含）。集合 $A$ が集合 $B$ に含まれる、あるいは $B$ の部分集合であるとは、$A$ のすべての元が $B$ の元であることをいう。

さらに $A \neq B$ であるとき、$A$ は $B$ の真部分集合であるという。

空集合はすべての集合 $A$ に含まれる。含意 $x \in \emptyset \rightarrow x \in A$ は前件がつねに偽なので真だからである。所属と包含は区別しなければならない。$1 \in \{1, 2\}$ と $\{1\} \subseteq \{1, 2\}$ は真だが、$\{1\} \in \{1, 2\}$ は偽である。$\{1, 2\}$ の元は $1$ と $2$ だけであり、集合 $\{1\}$ はそのどちらとも等しくないからである。$\{1\} \neq 1$ である。$1$ をただ一つの元とする集合は $1$ と異なるからであり、また $\{1\} \neq 2$ である。

和集合、共通部分、差集合

定義（集合の演算）。$A$ と $B$ の和集合は、少なくとも一方に属する元の集合であり、共通部分は両方に属する元の集合であり、差集合 $A \setminus B$ は $A$ に属し $B$ に属さない元の集合である。

$B \subseteq A$ のとき、差集合 $A \setminus B$ を $B$ の $A$ に関する補集合という。二つの集合は、共通部分が空であるとき共通部分をもたないという。

各演算は一つの結合子に対応する。和集合は選言に、共通部分は連言に、差集合は連言と否定に対応する。そうであれば、論理の各法則は集合の法則を生む。和集合と共通部分は交換的かつ結合的であり、互いに分配的である。結合子がそうだからである。これらはすべて次の定理のように証明される。補集合はつねにある基準の集合に関してとる。$B$ にないものすべての集合は、ラッセルの逆理を再び生むからである。

冪集合

集合の部分集合はそれ自身また集合をなし、その存在ははじめに認めた。$A$ の冪集合は $\mathcal{P}(A)$ と書き、$A$ の部分集合を元とする集合である。

たとえば、$\{1, 2, 3\}$ の冪集合は八つの元をもつ。空集合、三つの一元集合、三つの二元集合、そして $\{1, 2, 3\}$ そのものである。

任意の集合 $A$ について、空集合と $A$ 自身は $\mathcal{P}(A)$ の元であり、各 $a$（$A$ の元）について $\{a\} \in \mathcal{P}(A)$ であるが、$a$ は一般に $\mathcal{P}(A)$ の元ではない。組合せ論の課では、$n$ 個の元をもつ集合が $2^n$ 個の部分集合をもつことを証明する。

順序対と直積

平面の点、分数、まだ実行していない引き算は、決まった順序に並べた二つの対象で記述される。対 $(3, 5)$ は対 $(5, 3)$ ではない。集合 $\{3, 5\}$ はこれを表すのに役立たない。$\{5, 3\}$ と等しいからである。順序対に求めるのはただ一つ、その特徴的性質である。二つの対が等しいのは、第一成分が一致し、第二成分が一致するとき、かつそのときに限る。クラトフスキは 1921 年に、この性質をもつ対象を構成するには集合の概念だけで足りることを示した。

定義（順序対）。第一成分 $a$、第二成分 $b$ の順序対とは、集合

特徴的性質が証明されれば、クラトフスキの構成は忘れてよい。講座が対について述べることはすべてこの性質から導かれる。

定義（直積）。$A$ と $B$ の直積とは、第一成分が $A$ に属し、第二成分が $B$ に属する対の集合である。

記法 $\{ (a, b) : a \in A \wedge b \in B \}$ そのものは認めた規則の一つではない。それらの規則は、すでに作られた集合から元を分離することしか許さない。しかし、この集合は存在する。$a \in A$ かつ $b \in B$ ならば、集合 $\{a\}$ と $\{a, b\}$ は $A \cup B$ に含まれ、したがって $\mathcal{P}(A \cup B)$ の元である。ここから対 $(a, b) = \{ \{a\}, \{a, b\} \}$ が $\mathcal{P}(A \cup B)$ に含まれること、すなわち $\mathcal{P}(\mathcal{P}(A \cup B))$ の元であることがわかる。したがって直積は、認めた規則によって存在が保証される集合の中で分離によって作られる。$A \cup B$ は $\{A, B\}$ の元の和集合であり、そこで冪集合を二回とる。

この名前はデカルトを思い起こさせる。解析幾何の平面は $\mathbb{R} \times \mathbb{R}$ である。積は交換的ではない。$\{1\} \times \{2\}$ は $(1, 2)$ だけを含み、$\{2\} \times \{1\}$ は $(2, 1)$ だけを含むが、特徴的性質により、後者は前者と異なる。

関係

$2$ が $6$ を割り切る、$3$ が $5$ より小さい、あるいは二つの日付が同じ曜日であると言うことは、ある対象の対が関係していると主張することである。そうであれば、関係はそれが結びつける対によって決まり、対の集合として定義できる。

定義（関係）。$A$ から $B$ への関係とは、部分集合 $R$（積 $A \times B$ に含まれるもの）のことである。$A$ 上の関係とは、$A$ から $A$ への関係である。$(a, b) \in R$ のとき、$a$ と $b$ は $R$ によって関係しているという。

たとえば、$\{1, 2, 3\}$ 上の関係「以下」は、対の集合 $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$ である。よく使う関係では、二つの項の間に $a \leq b$ や $a \mid b$ のような記号を書き、$(a, b) \in R$ とは書かない。集合上の関係の四つの性質が講座全体を通じて現れる。

定義（関係の性質）。関係 $R$（$A$ 上の）は、それぞれ次の条件を満たすとき、反射的、対称的、反対称的、推移的であるという。

• 各元が自分自身と関係しているとき反射的である：$(\forall a \in A)\,((a, a) \in R)$。
• $a$ が $b$ と関係していることから $b$ が $a$ と関係していることが従うとき対称的である：$(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$。
• 両方向に関係している二つの元が等しいとき反対称的である：$(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$。
• $a$ が $b$ と関係し、$b$ が $c$ と関係していることから、$a$ が $c$ と関係していることが従うとき推移的である：$(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$。

$A \times A$ の格子では、関係は点の集合である。対 $(a, a)$ からなる対角線全体を含むとき反射的であり、その図形が対角線に関して対称であるとき対称的であり、対角線の外のどの点も、その対称な点が関係に入っていないとき反対称的である。反対称は「対称でない」という意味ではない。相等関係は両方の性質をもち、演習問題 1 ではどちらももたない関係を求める。

同値関係

関係「偶奇が同じ」は部分的な相等のようにふるまう。ある一つの側面、すなわち偶奇で一致する数を同一視し、他の側面は無視する。このようにふるまわせる三つの性質には名前がある。

定義（同値関係）。$A$ 上の関係が反射的、対称的、推移的であるとき、同値関係という。このとき $a \sim b$ と書き、$a$ は $b$ と同値であるという。$a$ の同値類とは、$a$ と同値な元の集合であり、その各元はその類の代表元である。

同値類全体の集合を商集合といい、$A/{\sim}$ と書く。

同値関係の例としては、各同値類が一つの元だけをもつ相等関係、同値類が二つの「偶奇が同じ」、同値類が三つの「$3$ で割った余りが同じ」、そして例題 3 で扱う、同値類が七つの「同じ曜日である」がある。一般に、$g$ が $A$ 上で定義された関数ならば、関係 $g(x) = g(y)$ は相等関係から三つの性質を受け継ぐ。例題 5 は、すべての同値関係がこの形であることを示す。

したがって、同値類は集合を重なりのないブロックに分ける。この集合の分け方は、それ自体として定義する価値がある。

定義（分割）。集合 $A$ の分割とは、$A$ の部分集合からなる集合であって、それらの部分集合（ブロックという）が空でなく、どの二つも共通部分をもたず、その和集合が $A$ であるものをいう。同値な言い方をすれば、$A$ の各元がちょうど一つのブロックに属する。

したがって、$A$ 上の同値関係を与えることと、$A$ の分割を与えることは、同じことを言う二つの方法である。例題 4 はこれを利用して同値関係を数える。商集合は、新しい集合として見た分割である。$A$ から $A/{\sim}$ へ移ると、同値な元は一つに融合する。

同様に、有理数の課では、二つの分数 $(p, q)$ と $(r, s)$ は $ps = qr$ のとき同値であり、有理数は一つの同値類である。合同式の課では、$n$ を法とする剰余類は整数の間の同値関係の同値類である。

順序関係

前の例の整除関係は対称的ではなく反対称的であった。元を同一視するのではなく、順序づける。この種の関係には固有の名前がある。

定義（順序）。$A$ 上の関係が反射的、反対称的、推移的であるとき、順序関係または半順序という。このとき $a \preceq b$ と書き、$a$ は $b$ に先行するという。二つの元がいつも比較可能であるとき、すなわち任意の $a$ と $b$ について $a \preceq b$ または $b \preceq a$ であるとき、その順序は全順序である。

順序の例としては、自然数の間の関係 $\leq$（自然数の演算の課で証明する三分律により全順序である）、包含関係（その性質の定理により順序であるが、$\{1\}$ と $\{2\}$ が比較可能でないので全順序ではない）、そして自然数の間の整除関係（その反対称性は整除性の課で証明し、$2 \mid 3$ も $3 \mid 2$ も成り立たないので全順序ではない）がある。有限の順序はハッセ図で描く。各元に一つの点を置き、$b$ を $a$ より上に置くのは $a$ が $b$ に先行するときで、両者の間に他の元がないときに線分で結ぶ。推移性により、残りの線分は省略できる。

定義（界と極端な元）。$\preceq$ を $A$ 上の順序、$X$ を $A$ の部分集合とする。$X$ の界と極端な元を次のように定義する。

• 元 $c$（$A$ の元）が $X$ の下界であるとは、$X$ のすべての元に先行することであり、上界であるとは、$X$ のすべての元がそれに先行することである。
• $X$ の最小元とは、$X$ の下界であって $X$ に属するものであり、最大元とは、上界であって $X$ に属するものである。
• 元 $m$（$X$ の元）は、$X$ の元でそれと異なるものがそれに先行しないとき極小元であり、それが $X$ の元でそれ自身と異なるものに先行しないとき極大元である。
• $X$ の下限とは、その下界の集合の最大元であり、上限とは、その上界の集合の最小元である。ただし存在する場合に限る。