集合と関係

home > 数学の基礎

数学のあらゆる分野の土台になる、集合・関係・写像・数え上げ・数の集合の基本をまとめる。後のページで使う言葉と記号は、ここで定める。

用語

$A, B$ を集合とする。

集合の演算

$A, B$ を集合とする。

冪集合

集合 $U$ のすべての部分集合からなる集合を $U$ の冪集合といい、$\mathcal{P}(U)$ または $2^{U}$ と記す。すなわち、

$$2^{U} = \{S \mid S\subseteq U\}$$

例1 集合 $U=\{1,2,3\}$ の冪集合は

$$2^{U} = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$$

$\emptyset, U \subseteq U$ であるため、$\emptyset, U \in 2^{U}$ となる。したがって、冪集合は常に空ではない。

全体集合と補集合

通常、私たちが考える集合 $A, B, \dots$ などは、ある確定したより大きな集合 $U$ の部分集合である。このとき、$U$ を全体集合と呼ぶ。 $A$ が全体集合 $U$ の部分集合であるとき、$U\setminus A$ を $U$ における $A$ の補集合といい、$\complement_{U}(A)$ または単に $A^{c}$ と記す。

特に断りのない限り、本節で議論する集合の共通部分、和集合、補集合、差集合などの演算は、すべてある全体集合 $U$ の中での演算である。

例2 $A\setminus B = A\cap B^{c}$を示せ。

証明. 集合 $A\setminus B = A\cap B^{c}$ を証明するには、$A\setminus B \subseteq A\cap B^{c}$ かつ $A\cap B^{c} \subseteq A\setminus B$ を示せばよい。 まず $A\setminus B \subseteq A\cap B^{c}$ を証明する。すなわち、任意の $x\in A\setminus B$ に対して $x\in A\cap B^{c}$ となることを示す。 実際、任意の $x\in A\setminus B$ について、差集合の定義より $x\in A$ かつ $x\notin B$ である。$x\notin B$ であるため $x\in B^{c}$ となる。したがって $x\in A$ かつ $x\in B^{c}$ であり、共通部分の定義より $x\in A\cap B^{c}$ となる。さらに部分集合の定義から $A\setminus B \subseteq A\cap B^{c}$ がわかる。

同様の方法で $A\cap B^{c} \subseteq A\setminus B$ を証明できる。 最後に、集合が等しいことの定義から、$A\setminus B = A\cap B^{c}$ を得る。

∎

集合の演算則

以下に、共通部分・和集合・補集合の重要な演算法則を挙げる。$A, B, C$ を全体集合 $U$ の部分集合とするとき、次が成り立つ。

  1. 結合法則: $A\cup(B\cup C)=(A\cup B)\cup C$, $A\cap(B\cap C)=(A\cap B)\cap C$
  2. 交換法則: $A\cup B=B\cup A$, $A\cap B=B\cap A$
  3. 吸収法則: $A\cup(A\cap B)=A$, $A\cap(A\cup B)=A$
  4. 分配法則: $A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$, $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
  5. 補元法則: $A\cup A^{c}=U$, $A\cap A^{c}=\emptyset$
  6. 冪等法則: $A\cup A=A$, $A\cap A=A$
  7. 有界法則: $A\cup\emptyset=A$, $A\cup U=U$, $A\cap\emptyset=\emptyset$, $A\cap U=A$
  8. 0-1法則: $\emptyset^{c}=U$, $U^{c} = \emptyset$
  9. ド・モルガンの法則: $(A\cup B)^{c}=A^{c}\cap B^{c}$, $(A\cap B)^{c}=A^{c}\cup B^{c}$
  10. 対合法則: $(A^{c})^{c}=A$

証明. 明らかな (1) (2) (3) (4) (5) は証明しない。以下では、最初の5つの性質を用いて残りの性質を証明する。

(6) 冪等法則. 吸収法則より

$$A\cap(A\cup A) = A, \quad A\cup(A\cap(A\cup A))=A$$

したがって

$$A\cup A = A\cup(A\cap(A\cup A)) = A$$

同様に、

$$A\cap A = A\cap(A\cup(A\cap A)) = A$$

(7) 有界法則. 補元法則より $A\cap A^{c}=\emptyset$。吸収法則より、

$$A\cup\emptyset = A\cup(A\cap A^{c}) = A$$

同様に、

$$A\cup U = A\cup(A\cup A^{c}) = (A\cup A)\cup A^{c} = A\cup A^{c} = U$$

ここでは順に、補元法則、結合法則、冪等法則、補元法則を利用した。残りの2つの等式も同様である。

(8) 0-1法則. 順に吸収法則、交換法則、補元法則、交換法則、補元法則を利用すると、

$$\emptyset^{c} = \emptyset^{c}\cup(\emptyset^{c}\cap\emptyset) = \emptyset^{c}\cup(\emptyset\cap\emptyset^{c}) = \emptyset^{c}\cup\emptyset = \emptyset\cup\emptyset^{c} = U$$

2つ目の等式も同様である。

(9) ド・モルガンの法則. $S=A\cup B$, $T=A^{c}\cap B^{c}$ とおくと、

$$\begin{aligned}S\cup T &= (A\cup B)\cup(A^{c}\cap B^{c}) \\ &= ((A\cup B)\cup A^{c})\cap((A\cup B)\cup B^{c}) = U\cap U = U\end{aligned}$$
$$\begin{aligned}S\cap T &= (A\cup B)\cap(A^{c}\cap B^{c}) \\ &= (A\cap(A^{c}\cap B^{c}))\cup(B\cap(A^{c}\cap B^{c})) = \emptyset\cup\emptyset = \emptyset\end{aligned}$$

ゆえに、

$$\begin{aligned}S^{c} &= S^{c}\cup\emptyset = S^{c}\cup(S\cap T) = (S^{c}\cup S)\cap(S^{c}\cup T) \\ &= U\cap(S^{c}\cup T) = (S\cup T)\cap(S^{c}\cup T) \\ &= (S\cap S^{c})\cup T = T\end{aligned}$$

すなわち $(A\cup B)^{c} = A^{c}\cap B^{c}$ である。2つ目の等式も同様である。

(10) 対合法則. 補元法則より $A\cup A^{c}=U$, $A\cap A^{c}=\emptyset$ である。これら2つの等式の集合 $A$ を $A^{c}$ に置き換えると、

$$A^{c}\cup(A^{c})^{c}=U, \quad A^{c}\cap(A^{c})^{c}=\emptyset$$

となる。ゆえに、

$$\begin{aligned}(A^{c})^{c} &= (A^{c})^{c}\cup(A^{c}\cap A) \\ &= ((A^{c})^{c}\cup A^{c})\cap((A^{c})^{c}\cup A) \\ &= (A^{c}\cup A)\cap((A^{c})^{c}\cup A) \\ &= (A^{c}\cap(A^{c})^{c})\cup A = A\end{aligned}$$

∎

集合族の共通部分と和集合

$S_{\lambda} \ (\lambda\in\Lambda)$ をすべて集合とする（ここで $\Lambda$ は任意の添字集合であり、有限集合でも無限集合でもよい）。

例3 集合 $A, B, C$ の共通部分は簡単に $A\cap B\cap C$ と書くことができる。これは $(A\cap B)\cap C$ に等しいため、共通部分の演算を複数回適用して得られたものとみなすことができる。

例4 $(1-\frac{1}{n}, 2+\frac{1}{n})$ の形をしたすべての開区間（ここで $n$ は正の整数）を考える。それらの共通部分は

$$\bigcap_{n=1}^{\infty} \left(1-\frac{1}{n}, 2+\frac{1}{n}\right) = \left\{x \mathrel{\Big|} \text{任意の正の整数 } n \text{ に対して } x\in\left(1-\frac{1}{n}, 2+\frac{1}{n}\right)\right\} = [1, 2]$$

であり、それらの和集合は

$$\bigcup_{n=1}^{\infty} \left(1-\frac{1}{n}, 2+\frac{1}{n}\right) = \left\{x \mathrel{\Big|} \text{ある正の整数 } n \text{ が存在して } x\in\left(1-\frac{1}{n}, 2+\frac{1}{n}\right)\right\} = (0, 3)$$

である。

定理2 $A$、$S_{\lambda} \ (\lambda\in\Lambda)$ を集合とする（ここで $\Lambda$ は任意の添字集合）。このとき、次が成り立つ。

  1. 分配法則:
    $$A\cap \left(\bigcup_{\lambda\in\Lambda}S_{\lambda}\right)=\bigcup_{\lambda\in\Lambda}(A\cap S_{\lambda}), \quad A\cup\left(\bigcap_{\lambda\in\Lambda}S_{\lambda}\right)=\bigcap_{\lambda\in\Lambda}(A\cup S_{\lambda})$$
  2. ド・モルガンの法則:
    $$\left(\bigcup_{\lambda\in\Lambda}S_{\lambda}\right)^{c}=\bigcap_{\lambda\in\Lambda}({S_{\lambda}}^{c}), \quad \left(\bigcap_{\lambda\in\Lambda}S_{\lambda}\right)^{c}=\bigcup_{\lambda\in\Lambda}({S_{\lambda}}^{c})$$

関係

定義1（順序対） $A, B$ を集合とする。$a\in A, b\in B$ であるとき、集合

$$\{\{a\}, \{a,b\}\}$$

を要素 $a$ と $b$ からなる順序対といい、$(a,b)$ と記す。

例1 定義より $(1,2)=\{\{1\},\{1,2\}\}, (2,1)=\{\{2\},\{1,2\}\}$ である。したがって $(1,2)\ne(2,1)$ となる。

$$(1,1)=\{\{1\},\{1,1\}\}=\{\{1\},\{1\}\}=\{\{1\}\}$$

定理1 $(a,b)=(c,d)$ となるための必要十分条件は、$a=c$ かつ $b=d$ である。

証明

(十分性) $a=c$ かつ $b=d$ であれば、$\{a\}=\{c\}, \{a,b\}=\{c,d\}$ となる。したがって、

$$\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$$

すなわち $(a,b)=(c,d)$ である。

(必要性) $(a,b)=(c,d)$、すなわち $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$ と仮定する。このとき、

$$\{a\}=\{a\}\cap\{a,b\}=\{c\}\cap\{c,d\}=\{c\}$$

よって $a=c$ である。したがって $\{\{a\},\{a,b\}\}=\{\{a\},\{a,d\}\}$ となり、さらに

$$\{a,b\}=\{a\}\cup\{a,b\}=\{a\}\cup\{a,d\}=\{a,d\}$$

となる。以下、2つの場合に分けて考える。

  1. $a=b$ の場合、$d\in\{a,d\}$ および $\{a,d\}=\{a,b\}=\{b,b\}=\{b\}$ より $b=d$ が導かれる。
  2. $a\ne b$ の場合、$b\in\{a,b\}$ および $\{a,b\}=\{a,d\}$ より $b\in\{a,d\}$ を得る。$a\ne b$ であるため $b=d$ となる。

問題1 「順序$n$組」$(a_1,a_2,\dots,a_n)$ をどのように定義すれば、 $(a_1,a_2,\dots,a_n)=(b_1,b_2,\dots,b_n)$ であることと、各 $k\in\{1,2,\dots,n\}$ に対して $a_k=b_k$ であることが同値になるか？

解答

帰納的に、順序対を使って

$$(a_1, a_2, \dots, a_n) := \bigl((a_1, \dots, a_{n-1}),\, a_n\bigr)$$

と定義する（$n = 2$ は定義 1 の順序対）。定理 1 より、$(a_1,\dots,a_n) = (b_1,\dots,b_n)$ は $(a_1,\dots,a_{n-1}) = (b_1,\dots,b_{n-1})$ かつ $a_n = b_n$ と同値で、これを $n$ について帰納的にたどれば、すべての $k$ で $a_k = b_k$ となることと同値になる。

定義2（直積、デカルト積） $X, Y$ を集合とする。集合 $\{(x,y)\mid x\in X \text{ かつ } y\in Y\}$ を $X$ と $Y$ の直積といい、$X\times Y$ と記す。

例2 $X = \{A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2\}$, $Y = \{\spadesuit, \heartsuit, \diamondsuit, \clubsuit\}$ とすると、それらの直積は

$$\begin{aligned}X \times Y = \{ & (A,\spadesuit), (K,\spadesuit), (Q,\spadesuit), (J,\spadesuit), (10,\spadesuit), \dots, (3,\spadesuit), (2,\spadesuit), \\ & (A,\heartsuit), (K,\heartsuit), (Q,\heartsuit), (J,\heartsuit), (10,\heartsuit), \dots, (3,\heartsuit), (2,\heartsuit), \\ & (A,\diamondsuit), (K,\diamondsuit), (Q,\diamondsuit), (J,\diamondsuit), (10,\diamondsuit), \dots, (3,\diamondsuit), (2,\diamondsuit), \\ & (A,\clubsuit), (K,\clubsuit), (Q,\clubsuit), (J,\clubsuit), (10,\clubsuit), \dots, (3,\clubsuit), (2,\clubsuit) \}\end{aligned}$$

となる。直積は、$X$ の要素と $Y$ の要素から構成される順序対の全体がなす集合である。

一般に、集合 $X_1, X_2, \dots, X_n$ があるとき、それらの直積は次のように定義される。

$$X_1\times X_2\times\dots\times X_n := \{(x_1,x_2,\dots,x_n)\mid x_i\in X_i, i=1,2,\dots,n\}$$

定義3（二項関係） $X, Y$ を空でない集合とする。$R$ が $X\times Y$ の部分集合であるとき、$R$ を $X$ から $Y$ への二項関係と呼ぶ。 $x\in X, y\in Y$ とし、$(x,y)\in R$ であるとき、$x$ は $y$ と関係 $R$ があるといい、$xRy$ と記す。 特に、$X$ から $X$ への二項関係を、$X$ 上の二項関係と呼ぶ。

例3 $R=\{(x,y)\in\mathbb{R}\times\mathbb{R} \mid x^2+4y^2\le1\}$ とすると、$R$ は $\mathbb{R}$ から $\mathbb{R}$ への二項関係である。

例4 $R=\{(x,y)\in\mathbb{Z}\times\mathbb{Z} \mid \text{ある整数 } k \text{ が存在して } x-y=3k\}$ とすると、$R$ は $\mathbb{Z}$ から $\mathbb{Z}$ への二項関係（すなわち $\mathbb{Z}$ 上の二項関係）である。

例5 $R=\{(x,y)\in\mathbb{Q}\times\mathbb{Q} \mid \text{ある整数 } r \text{ が存在して } y-x=r\}$ とすると、$R$ は $\mathbb{Q}$ 上の二項関係である。

定義4（合成関係） $R$ を $X$ から $Y$ への二項関係、$S$ を $Y$ から $Z$ への二項関係とする。

$$S\circ R := \{(x,z)\in X\times Z \mid \text{ある } y\in Y \text{ が存在して } (x,y)\in R \text{ かつ } (y,z)\in S\}$$

とし、この $X$ から $Z$ への二項関係 $S\circ R$ を $R$ と $S$ の合成関係と呼ぶ。

例6 任意の空でない集合 $X$ に対し、$X$ 上の二項関係 $\{(x,y)\in X\times X \mid x=y\}$ を $X$ 上の恒等写像といい、$I_X$ と記す。すなわち $I_X=\{(x,x)\mid x\in X\}$ である。 空でない集合 $X, Y$ と、$X$ から $Y$ への二項関係 $R$ に対し、$R\circ I_X = R$ および $I_Y\circ R = R$ となることを証明せよ。

解答. 任意の $(x,y)\in R$ に対し、$(x,x)\in I_X$ であるため $(x,y)\in R\circ I_X$ となる。したがって $R\subseteq R\circ I_X$。 一方で、任意の $(x,y)\in R\circ I_X$ に対し、ある $t\in X$ が存在して $(x,t)\in I_X$ かつ $(t,y)\in R$ となる。$(x,t)\in I_X$ より $x=t$ であるため、$(x,y)=(t,y)\in R$。したがって $R\circ I_X\subseteq R$。 以上より $R\circ I_X = R$。2つ目の式も同様である。∎

例7 $R = \{(x,y)\in\mathbb{R}\times\mathbb{R} \mid x^2+4y^2\le1\}$, $S = \{(x,y)\in\mathbb{R}\times\mathbb{R} \mid x-y>1\}$ とする。$S\circ R$ を求めよ。

解答. 合成関係の定義に従い直接計算する。

$$\begin{aligned}S\circ R &= \{(x,y)\in\mathbb{R}\times\mathbb{R} \mid \text{ある } t \text{ が存在して } (x,t)\in R \text{ かつ } (t,y)\in S\} \\ &= \{(x,y)\in\mathbb{R}\times\mathbb{R} \mid \text{ある } t \text{ が存在して } x^2+4t^2\le1 \text{ かつ } t-y>1\} \\ &= \left\{(x,y)\in\mathbb{R}\times\mathbb{R} \mathrel{\Big|} \text{ある } t \text{ が存在して } -\frac{\sqrt{1-x^2}}{2}\le t\le\frac{\sqrt{1-x^2}}{2} \text{ かつ } t>y+1\right\} \\ &= \left\{(x,y)\in\mathbb{R}\times\mathbb{R} \mathrel{\Big|} \text{ある } t \text{ が存在して } t\in\left[-\frac{\sqrt{1-x^2}}{2},\frac{\sqrt{1-x^2}}{2}\right]\cap(y+1,+\infty)\right\} \\ &= \left\{(x,y)\in\mathbb{R}\times\mathbb{R} \mathrel{\Big|} \left[-\frac{\sqrt{1-x^2}}{2},\frac{\sqrt{1-x^2}}{2}\right]\cap(y+1,+\infty)\ne\emptyset\right\} \\ &= \left\{(x,y)\in\mathbb{R}\times\mathbb{R} \mathrel{\Big|} \frac{\sqrt{1-x^2}}{2}\in(y+1,+\infty)\right\} \\ &= \{(x,y)\in\mathbb{R}\times\mathbb{R} \mid |x|\le1 \text{ かつ } \sqrt{1-x^2}>2y+2\}\end{aligned}$$

定理2（結合法則） $R$ が $X$ から $Y$、$S$ が $Y$ から $Z$、$T$ が $Z$ から $W$ への二項関係であるとき、

$$T\circ(S\circ R) = (T\circ S)\circ R$$

が成り立つ。

証明. $S\circ R$ は $X$ から $Z$ への関係であるため、$T\circ(S\circ R)$ は $X$ から $W$ への関係となる。同様に $T\circ S$ は $Y$ から $W$ への関係であるため、$(T\circ S)\circ R$ は $X$ から $W$ への関係となる。 任意の $(x,w)\in X\times W$ について、$(x,w)\in T\circ(S\circ R) \iff (x,w)\in (T\circ S)\circ R$ を示せばよい。実際、

$$\begin{aligned}(x,w)\in T\circ(S\circ R) &\iff \text{ある } z\in Z \text{ が存在して } (x,z)\in S\circ R \text{ かつ } (z,w)\in T \\ &\iff \text{ある } z\in Z \text{ とある } y\in Y \text{ が存在して } (x,y)\in R \text{ かつ } (y,z)\in S \text{ かつ } (z,w)\in T \\ &\iff \text{ある } y\in Y \text{ とある } z\in Z \text{ が存在して } (x,y)\in R \text{ かつ } (y,z)\in S \text{ かつ } (z,w)\in T \\ &\iff \text{ある } y\in Y \text{ が存在して } (x,y)\in R \text{ かつ } (y,w)\in T\circ S \\ &\iff (x,w)\in(T\circ S)\circ R\end{aligned}$$

∎

定義5（逆関係） $R$ を $X$ から $Y$ への二項関係とする。

$$R^{-1} := \{(y,x)\in Y\times X \mid (x,y)\in R\}$$

とし、この $Y$ から $X$ への二項関係 $R^{-1}$ を、関係 $R$ の逆関係と呼ぶ。

例8 $\mathbb{R}$ 上の関係 $S=\{(x,y)\in\mathbb{R}\times\mathbb{R} \mid y\ge x^2\}$ を考える。$S$ の逆関係 $S^{-1}$ も $\mathbb{R}$ 上の関係であり、

$$S^{-1} = \{(y,x)\in\mathbb{R}\times\mathbb{R} \mid y\ge x^2\} = \{(x,y)\in\mathbb{R}\times\mathbb{R} \mid x\ge y^2\}$$

となる。

定理3 $R$ が $X$ から $Y$ への二項関係ならば、$(R^{-1})^{-1}=R$ である。

証明. 任意の $(x,y)\in X\times Y$ に対し、

$$(x,y)\in (R^{-1})^{-1} \iff (y,x)\in R^{-1} \iff (x,y)\in R$$

したがって $(R^{-1})^{-1}=R$ である。∎

定理4 $R$ が $X$ から $Y$ への関係、$S$ が $Y$ から $Z$ への関係であるとき、次が成り立つ。

$$(S\circ R)^{-1} = R^{-1}\circ S^{-1}$$

証明. 任意の $(z,x)\in Z\times X$ に対し、

$$\begin{aligned}(z,x)\in(S\circ R)^{-1} &\iff (x,z)\in S\circ R \\ &\iff \text{ある } y\in Y \text{ が存在して } (x,y)\in R \text{ かつ } (y,z)\in S \\ &\iff \text{ある } y\in Y \text{ が存在して } (y,x)\in R^{-1} \text{ かつ } (z,y)\in S^{-1} \\ &\iff (z,x)\in R^{-1}\circ S^{-1}\end{aligned}$$

したがって $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$ となる。∎

定義6（同値関係） $R$ を空でない集合 $X$ 上の二項関係とする。$R$ が次の条件を満たすとき、$R$ は $X$ 上の同値関係であるという。

  1. 反射律: 任意の $x\in X$ に対して $xRx$ が成り立つ。
  2. 対称律: 任意の $x,y\in X$ に対して、$xRy$ ならば $yRx$ が成り立つ。
  3. 推移律: 任意の $x,y,z\in X$ に対して、$xRy$ かつ $yRz$ ならば $xRz$ が成り立つ。

与えられた同値関係 $R$ において、$xRy$ のとき、$x$ と $y$ は同値であるといい、$x\sim y$ と記す。

例9 任意の空でない集合 $X$ に対し、$I_X=\{(x,x)\mid x\in X\}$ は $X$ 上の同値関係である。$X\times X$ も $X$ 上の同値関係である。集合の包含関係の観点からは、$I_X$ は $X$ 上の最小の同値関係であり、$X\times X$ は最大の同値関係である。

例10 $\{(x,y)\in\mathbb{R}\times\mathbb{R}\mid x-y\in\mathbb{Z}\}$、$\{(x,y)\in\mathbb{R}\times\mathbb{R}\mid x-y\in\mathbb{Q}\}$ はともに $\mathbb{R}$ 上の同値関係であるが、$\{(x,y)\in\mathbb{R}\times\mathbb{R}\mid x-y\in\mathbb{N}\}$ は対称律を満たさないため同値関係ではない。 $m\in\mathbb{N}^+$ とすると、$\{(x,y)\in\mathbb{Z}\times\mathbb{Z}\mid \text{ある } k\in\mathbb{Z} \text{ が存在して } x-y=km\}$ は $\mathbb{Z}$ 上の同値関係である。この同値関係の下で、互いに同値な要素 $x, y$ は法 $m$ に関して合同であるといい、$x\equiv y \pmod m$ と記す。

定義7 $R$ を $X$ 上の同値関係とする。任意の $x\in X$ に対し、$[x]_R := \{y\in X\mid yRx\}$ を $R$ の同値類と呼ぶ。集合 $X/R := \{[x]_R\mid x\in X\}$ を $R$ に関する $X$ の商集合と呼ぶ。

定理5 $R$ が空でない集合 $X$ 上の同値関係であるとき、$R$ の各同値類は空でなく、異なる同値類は互いに素（交わらない）であり、次が成り立つ。

$$X = \bigcup_{x\in X}[x]_R$$

写像

定義1（写像、関数） $X$ を空でない集合とし、$R$ を $X$ から $Y$ への二項関係とする。$R$ が以下の条件を満たすとき、

  1. $R$ は右一意的である：$xRy_1$ かつ $xRy_2$ ならば $y_1=y_2$。
  2. $R$ は左全域的である：任意の $x\in X$ に対し、ある $y\in Y$ が存在して $xRy$ となる。

$R$ は $X$ から $Y$ への写像または関数であるといい、$R:X\to Y$ と記す。

与えられた写像 $R:X\to Y$ について、以下の関連概念が重要である。

定理1（合成写像） $f:X\to Y, g:Y\to Z$ ならば、$g\circ f:X\to Z$ は写像である。

証明. $f:X\to Y$ は写像であるため、任意の $x\in X$ に対し、ある $y\in Y$ が存在して $xfy$ となる。 $g:Y\to Z$ も写像であるため、ある $z\in Z$ が存在して $ygz$ となる。 合成関係の定義より $x(g\circ f)z$ が成り立つ。したがって $g\circ f$ は左全域的である。

任意の $x\in X$、$z_1, z_2\in Z$ について、$x(g\circ f)z_1$ かつ $x(g\circ f)z_2$ であるとすると、ある $y_1\in Y$ が存在して $xfy_1$ かつ $y_1gz_1$ となり、またある $y_2\in Y$ が存在して $xfy_2$ かつ $y_2gz_2$ となる。 $f$ が右一意的であることから $y_1=y_2$ であり、ゆえに $y_1gz_1, y_1gz_2$ となる。さらに $g$ が右一意的であることから $z_1=z_2$ が導かれる。したがって $g\circ f$ は右一意的である。 よって、$g\circ f$ は写像である。∎

注. 写像 $g\circ f:X\to Z$ を、写像 $f$ と $g$ の合成写像と呼ぶ。

例1 $X=\mathbb{R}, Y=\mathbb{R}$ とすると、$X$ から $Y$ への二項関係

$$f=\{(x,y)\mid x,y\in\mathbb{R}, y=x^2\}$$

は $X$ から $Y$ への写像であり、通常は

$$f:X\to Y, x\mapsto x^2, \quad \text{または} \quad f(x)=x^2 \ (x\in\mathbb{R})$$

と記される。 ここで $f$ の定義域と終域はともに $\mathbb{R}$ であり、値域は $f(\mathbb{R})=\{z\in\mathbb{R}\mid z\ge0\}$ である。 もし $Z=\{z\in\mathbb{R}\mid z\ge0\}$ とすれば、$X$ から $Z$ への二項関係

$$g = \{(x,z)\mid x\in\mathbb{R}, z\in Z, z=x^2\}$$

は $X$ から $Z$ への写像（すなわち $g:X\to Z, x\mapsto x^2$）であり、その値域は $g(\mathbb{R})=Z$ となる。 $f$ と $g$ の定義域は同じであり、任意の $x\in X$ に対して $f(x)=g(x)$ となることに注意せよ。通常、これら2つの関数は同一であるとみなされる。実際、$f$ と $g$ を単なる二項関係として考えれば、これら2つの順序対の集合（平面座標系における関数のグラフに相当）は完全に一致する。

定義2（単射、全射、全単射） $f:X\to Y$ とする。

  1. $f(x_1)=f(x_2)$ を満たす任意の $x_1, x_2\in X$ に対して常に $x_1=x_2$ が成り立つとき、$f$ は単射であるという。
  2. 任意の $y\in Y$ に対して、ある $x\in X$ が存在して $y=f(x)$ となるとき、$f$ は全射であるという。
  3. $f$ が単射でありかつ全射であるとき、$f$ を全単射であるという。

例2 例1に引き続き考える。上記の定義によれば、$f$ も $g$ も単射ではなく、したがって全単射でもない。$f$ は全射ではないが、$g$ は全射である。一般に、任意の写像 $f:X\to Y$ について、関数のグラフが同一であるという観点から、これを $X$ から $f(X)$ への全射とみなすことができる。さらに、写像 $f:X\to Y$ が単射であれば、上記の意味で $X$ から $f(X)$ への全単射とみなすことができる。

例3（恒等写像） $X$ を空でない集合とする。前節では恒等写像 $I_X=\{(x,x)\mid x\in X\}$ を二項関係として論じたが、実際には $I_X$ は写像（すなわち $I_X:X\to X, x\mapsto x$ または $I_X(x)=x \ (x\in X)$）である。これは全単射であるだけでなく、任意の写像 $f:X\to Y$ に対して $f\circ I_X=f, I_Y\circ f=f$ を満たす。

定理2 写像 $f:X\to Y$ の逆関係 $f^{-1}:Y\to X$ が写像となるための必要十分条件は、$f$ が全単射であることである。

証明. 二項関係 $f^{-1}:Y\to X$ が右一意的である

$$\begin{aligned}&\iff \text{任意の } y\in Y, x_1, x_2\in X \text{ について、} yf^{-1}x_1 \text{ かつ } yf^{-1}x_2 \text{ ならば } x_1=x_2 \\ &\iff \text{任意の } y\in Y, x_1, x_2\in X \text{ について、} x_1fy \text{ かつ } x_2fy \text{ ならば } x_1=x_2 \\ &\iff f \text{ は単射である。}\end{aligned}$$

二項関係 $f^{-1}:Y\to X$ が左全域的である

$$\begin{aligned}&\iff \text{任意の } y\in Y \text{ に対し、ある } x\in X \text{ が存在して } yf^{-1}x \\ &\iff \text{任意の } y\in Y \text{ に対し、ある } x\in X \text{ が存在して } xfy \\ &\iff f \text{ は全射である。}\end{aligned}$$

∎

注. 写像 $f:X\to Y$ の逆関係 $f^{-1}:Y\to X$ も写像であるとき、$f^{-1}$ を $f$ の逆写像と呼ぶ。

定理3 $f:X\to Y$ が全単射であれば、その逆写像 $f^{-1}$ も全単射であり、次が成り立つ。

$$(f^{-1})^{-1}=f, \quad f^{-1}\circ f=I_X, \quad f\circ f^{-1}=I_Y$$

証明. $f$ が写像であることから $f$ は右一意的であり、ゆえに $f^{-1}$ は単射である。また $f$ は左全域的であるため、$f^{-1}$ は全射である。よって $f^{-1}$ は全単射である。さらに、前節の定理3より $(f^{-1})^{-1}=f$ となる。

次に $f^{-1}\circ f=I_X$ を証明する。一方で、任意の $(x_1, x_2)\in X\times X$ について、

$$\begin{aligned}(x_1, x_2)\in f^{-1}\circ f &\iff \text{ある } y\in Y \text{ が存在して } (x_1, y)\in f \text{ かつ } (y, x_2)\in f^{-1} \\ &\iff \text{ある } y\in Y \text{ が存在して } (x_1, y)\in f \text{ かつ } (x_2, y)\in f \\ &\iff \text{ある } y\in Y \text{ が存在して } y=f(x_1) \text{ かつ } y=f(x_2)\end{aligned}$$

$f$ は単射であるため $x_1=x_2$ となり、したがって $(x_1, x_2)\in I_X$ である。これは $f^{-1}\circ f\subseteq I_X$ を示している。 他方で、任意の $(x,x)\in I_X$ に対し、$f$ が写像であるためある $y\in Y$ が存在して $(x,y)\in f$ となり、このとき $(y,x)\in f^{-1}$ も成り立つ。ゆえに $(x,x)\in f^{-1}\circ f$ である。これは $I_X\subseteq f^{-1}\circ f$ を示している。 以上より $f^{-1}\circ f=I_X$ である。これまでの論証から、任意の全単射 $g:Y\to X$ に対して $g^{-1}\circ g=I_Y$ が成り立つ。 ここで $f^{-1}:Y\to X$ は全単射であり、$(f^{-1})^{-1}=f$ であるため、$f\circ f^{-1}=(f^{-1})^{-1}\circ f^{-1}=I_Y$ となる。∎

定理4 任意の写像 $f:X\to Y$ に対して、

  1. $f$ が単射 $\iff$ ある写像 $g:Y\to X$ が存在して $g\circ f=I_X$ （$g$ を $f$ の左逆写像と呼ぶ）。
  2. $f$ が全射 $\iff$ ある写像 $h:Y\to X$ が存在して $f\circ h=I_Y$ （$h$ を $f$ の右逆写像と呼ぶ）。
  3. $f$ が全単射 $\iff$ ある写像 $g, h:Y\to X$ が存在して $g\circ f=I_X$, $f\circ h=I_Y$。
  4. $f$ が全単射 $\iff$ ある写像 $g:Y\to X$ が存在して $g\circ f=I_X$, $f\circ g=I_Y$。

この定理の証明は以下の4つの補題から得られる。

補題5 $f:X\to Y$ が単射ならば、$f$ は左逆写像を持つ。

証明. $h:X\to f(X), x\mapsto f(x)$ とすると、$h$ は全射である。$f$ が単射であるため $h$ も単射となり、したがって $h$ は全単射となる。よって逆写像 $h^{-1}:f(X)\to X$ が存在する。 $X$ は空でないため、$a\in X$ を1つ選んで固定する。$g=h^{-1}\cup ((Y\setminus f(X))\times\{a\})$ と置く。すなわち、

$$g=h^{-1}\cup \{(t,a) \mid t\in Y\setminus f(X)\}$$

とすると、$g$ は $Y$ から $X$ への写像となる。任意の $x\in X$ に対し、$f(x)\in f(X)$ であるため

$$g(f(x))=h^{-1}(f(x))=h^{-1}(h(x))=x$$

となる。したがって $g\circ f=I_X$ である。∎

補題6 $f:X\to Y$ が全射ならば、$f$ は右逆写像を持つ。
（範囲外のため証明略）

補題7 $f:X\to Y, g:Y\to Z$ とする。合成写像 $g\circ f$ が単射ならば、$f$ は単射である。合成写像 $g\circ f$ が全射ならば、$g$ は全射である。

証明. (1) $g\circ f$ が単射であるとする。$x_1, x_2\in X$ で $f(x_1)=f(x_2)$ ならば、$g(f(x_1))=g(f(x_2))$、すなわち $(g\circ f)(x_1)=(g\circ f)(x_2)$ となる。$g\circ f$ が単射であることから $x_1=x_2$ となる。ゆえに $f$ は単射である。 (2) $g\circ f$ が全射であるとする。任意の $z\in Z$ に対し、ある $x\in X$ が存在して $g(f(x))=z$ となる。$f(x)\in Y$ であるため、ある $y\in Y$ が存在して $g(y)=z$ となる。ゆえに $g$ は全射である。∎

補題8 $f:X\to Y, g, h:Y\to X$ とする。$g\circ f=I_X, f\circ h=I_Y$ ならば、$g=h$ である。

証明. $g\circ f=I_X, f\circ h=I_Y$ であり、写像の合成は二項関係の合成として結合法則を満たすため、

$$g = g\circ I_Y = g\circ(f\circ h) = (g\circ f)\circ h = I_X\circ h = h$$

となる。∎

定理9 $f:X\to Y, g:Y\to X$ とする。$g\circ f=I_X, f\circ g=I_Y$ ならば、$f, g$ はともに全単射であり、互いに逆写像である。

例4 $f:X\to Y$ とする。$V=\{(x_1,x_2)\mid x_1, x_2\in X, f(x_1)=f(x_2)\}$ と定義すると、$V$ は集合 $X$ 上の同値関係である。この同値関係において、$x_1\sim x_2$ となるための必要十分条件は $f(x_1)=f(x_2)$ となることである。

有限集合と数え上げ

例1 集合 $A=\{2k \mid k\in\mathbb{N}\}$ は $\mathbb{N}$ の真部分集合であり、$f:\mathbb{N}\to A, k\mapsto 2k$ は全単射である。しかし、すべての空でない集合が、自身の真部分集合への全単射を持つわけではない。

$S$ を空でない集合とする。ある正の整数 $n$ と、全単射 $f:\{1,2,\dots,n\}\to S$ が存在するとき、$S$ は有限集合であるといい、$|S|=n$ と記す。空集合 $\emptyset$ も有限集合であると約束し、$|\emptyset|=0$ と記す。

命題1 $A, B$ を有限集合とする。

  1. 単射 $f:A\to B$ が存在するならば、$|A|\le|B|$。
  2. 全射 $f:A\to B$ が存在するならば、$|A|\ge|B|$。
  3. 全単射 $f:A\to B$ が存在するならば、$|A|=|B|$。

例2 空でない集合 $S_1, S_2$ がともに有限集合であるならば、$|S_1\times S_2| = |S_1|\cdot|S_2|$ である。

証明. $|S_1|=n$ とし、$S_1=\{x_1, x_2, \dots, x_n\}$ とおく。 任意の $x_j\in S_1$ に対し、集合 $P_j=\{(x_j, y)\mid y\in S_2\}$ を考える。写像 $f_j:S_2\to P_j, y\mapsto(x_j,y)$ は全単射であるため、$|P_j|=|S_2|$ となる。 $P_1, P_2, \dots, P_n$ は互いに素（交わらない）な空でない集合であり、$\bigcup_{j=1}^{n}P_j = S_1\times S_2$ であるため、和の法則（加法原理）より

$$|S_1\times S_2| = |P_1| + |P_2| + \dots + |P_n| = n|S_2| = |S_1|\times|S_2|$$

を得る。∎

定義1 全体集合 $X$ の任意のサブセット $S$ に対し、関数 $\chi_S:X\to\{0,1\}$ を次のように定義する。

$$\chi_S(x) = \begin{cases} 1, & x\in S; \\ 0, & x\notin S. \end{cases}$$

$\chi_S$ を $S$ の指示関数（または特性関数）と呼ぶ。

性質2 $X$ を全体集合とし、$A, B\subseteq X$ とする。

  1. $A\cap B=\emptyset$ ならば、$\chi_A \cdot \chi_B = 0$。
  2. $B = A^c$ ならば、$\chi_A + \chi_B = 1$。
  3. $\chi_{A\cap B} = \min(\chi_A, \chi_B) = \chi_A \cdot \chi_B$。
  4. $\chi_{A\cup B} = \max(\chi_A, \chi_B) = 1 - (1-\chi_A)\cdot(1-\chi_B)$。
  5. $\chi_{A\cup B} + \chi_{A\cap B} = \chi_A + \chi_B$。

記法. 空でない集合 $X, Y$ に対し、$Y^X=\{f \mid f:X\to Y\}$ と記す。 空でない集合 $X, Y$ がともに有限集合であれば、積の法則（乗法原理）より直ちに $|Y^X| = |Y|^{|X|}$ がわかる。

性質3 $X$ が空でない集合ならば、全単射 $\varphi:\mathcal{P}(X)\to \{0,1\}^X$ が存在する。

証明. 任意の $S\subseteq X$ に対して、明らかに $\chi_S\in\{0,1\}^X$ である。$\varphi:\mathcal{P}(X)\to \{0,1\}^X, S\mapsto \chi_S$ と定義する。 任意の $f\in\{0,1\}^X$ に対し、$S=\{x\in X\mid f(x)=1\}$ とおくと、$f=\chi_S$、すなわち $f=\varphi(S)$ となる。したがって $\varphi$ は全射である。また、$\varphi$ が単射であることも容易にわかるため、$\varphi$ は全単射である。∎

系4 $X$ が有限集合ならば、$|\mathcal{P}(X)| = 2^{|X|}$ である。

例3 集合 $S=\{1,2,\dots,n\}$ から、$A\subseteq B$ となるような部分集合の対 $(A, B)$ を取り出す方法はいくつあるか？

解答. $U=\{(A,B)\mid A\subseteq B\subseteq S\}$, $V=\{f\mid f:S\to\{0,1,2\}\}$ とおくと、$|V|=3^n$ である。 任意の $(A,B)\in U$ に対し、$g_{(A,B)}:S\to\{0,1,2\}$ を次のように定義する。

$$g_{(A,B)}(x) = \begin{cases} 0, & x\notin B \\ 1, & x\in B\setminus A \\ 2, & x\in A \end{cases}$$

このとき $g_{(A,B)}\in V$ である。さらに $\varphi:U\to V, \varphi(A,B)=g_{(A,B)}$ と定義すると、これは全単射となる。したがって、$|U|=|V|=3^n$ である。

定理5（包除原理） $A, B$ が有限集合ならば、次が成り立つ。

$$|A\cup B| = |A| + |B| - |A\cap B|$$

一般に、$S_1, S_2, \dots, S_n$ がすべて有限集合ならば、

$$\left|\bigcup_{1\le i\le n}S_i\right| = \sum_{1\le k\le n}(-1)^{k-1}\sum_{1\le i_1<i_2<\dots<i_k\le n}\left|\bigcap_{1\le s\le k}S_{i_s}\right|$$

証明. $S_1, S_2, \dots, S_n$ をすべて有限集合 $X$ の部分集合とし、$B=(S_1\cup S_2\cup\dots\cup S_n)^c$ とおく。このとき、

$$\prod_{1\le i\le n}(1-\chi_{S_i}) = \prod_{1\le i\le n}\chi_{S_i^c} = \chi_{S_1^c\cap S_2^c\cap\dots\cap S_n^c} = \chi_B = 1 - \chi_{S_1\cup S_2\cup\dots\cup S_n}$$

ゆえに、

$$\begin{aligned}\chi_{S_1\cup S_2\cup\dots\cup S_n} &= 1 - \prod_{1\le i\le n}(1-\chi_{S_i}) \\ &= 1 - \left(1 + \sum_{S\subseteq\{1,2,\dots,n\}, S\ne\emptyset}(-1)^{|S|}\prod_{i\in S}\chi_{S_i}\right) \\ &= 1 - \left(1 + \sum_{S\subseteq\{1,2,\dots,n\}, S\ne\emptyset}(-1)^{|S|}\chi_{\bigcap_{i\in S}S_i}\right) \\ &= \sum_{S\subseteq\{1,2,\dots,n\}, S\ne\emptyset}(-1)^{|S|-1}\chi_{\bigcap_{i\in S}S_i}\end{aligned}$$

任意の $S\subseteq X$ に対して $|S| = \sum_{x\in X}\chi_S(x)$ が成り立つため、上の等式の両辺を $x\in X$ について和をとることで、

$$\left|\bigcup_{1\le i\le n}S_i\right| = \sum_{S\subseteq\{1,2,\dots,n\}, S\ne\emptyset}(-1)^{|S|-1}\left|\bigcap_{i\in S}S_i\right|$$

を得る。∎

例4 集合 $S=\{1,2,\dots,n\}$ から部分集合の対 $(A, B)$ を取り出す。$A$ が $B$ の部分集合でなく、かつ $B$ も $A$ の部分集合ではないような取り出し方は何通りあるか？

解答. $X=\{(A,B)\mid A, B\subseteq S\}$ とする。積の法則より $|X|=|2^S\times 2^S|=2^n\cdot 2^n=4^n$ である。 また、$U=\{(A,B)\mid A\subseteq B\subseteq S\}, V=\{(A,B)\mid B\subseteq A\subseteq S\}$ とおく。 例3の結果から、$|U|=|V|=3^n$ であり、さらに

$$|U\cap V| = |\{(A,B)\mid A=B\subseteq S\}| = |\{A\mid A\subseteq S\}| = |2^S| = 2^n$$

最後に、包除原理より

$$\begin{aligned}|U^c\cap V^c| &= |(U\cup V)^c| = |X| - |U\cup V| \\ &= |X| - (|U| + |V| - |U\cap V|) \\ &= 2^n\cdot 2^n - 2\cdot 3^n + 2^n = 4^n - 2\cdot 3^n + 2^n\end{aligned}$$

順列

以下、常に $M=\{1,2,\dots,m\}$ とし、空でない集合 $S$ は有限集合で $|S|=n$ とする。

定義2（重複のない順列） $f:M\to S$ が単射であるとき、$f$ を $S$ から $m$ 個の要素を取り出して並べる（重複のない）順列と呼ぶ。特に $m=n$ のとき、$f$ を $S$ の要素の完全順列（すべての要素の順列）と呼ぶ。 $F=\{f\mid f:M\to S \text{ は単射}\}$ とおくとき、$|F|$ を $S$ から $m$ 個の要素を取り出して並べる順列の数と呼ぶ。 順列 $f$ は $f(1), f(2), \dots, f(m)$、あるいは $(f(1), f(2), \dots, f(m))$ のように表すことができる。

定理6 $n$ 個の要素の集合 $S$ から $m$ 個の要素を取り出して並べる順列の数は

$$P(n,m) = n\cdot(n-1)\cdot\dots\cdot(n-m+2)\cdot(n-m+1) = \frac{n!}{(n-m)!}$$

である。特に、$n$ 個の要素の集合 $S$ の要素すべての順列の数は $n!$ である。

定義3（重複順列） 写像 $f:M\to S$ を $S$ から $m$ 個の要素を取り出す重複順列と呼ぶ。 $F=\{f\mid f:M\to S\}$ とおくとき、$|F|$ を $S$ から $m$ 個の要素を取り出す重複順列の数と呼ぶ。

定理7 $n$ 個の要素の集合 $S$ から $m$ 個の要素を取り出す重複順列の数は $n^m$ である。

問題2 「順序$n$組」を写像を用いてどのように記述するか？ 「無限数列」を写像を用いてどのように記述するか？

解答

順序 $n$ 組 $(a_1, \dots, a_n)$ は、写像 $a: \{1, 2, \dots, n\} \to A$、$k \mapsto a_k$ と同じものとみなせる。二つの写像が等しいことは、すべての $k$ で値が等しいことだから、問題 1 の同値性がそのまま成り立つ。 無限数列 $(a_k)_{k \ge 1}$ は、写像 $a: \mathbb{N}^* \to \mathbb{R}$、$k \mapsto a_k$ である（項が実数の場合）。

例5 $n$ 元集合 $S=\{x_1, x_2, \dots, x_n\}$、$M=\{1,2,\dots,m\}$ とし、正の整数 $m_1, m_2, \dots, m_n$ は $\sum_{j=1}^{n}m_j=m$ を満たすとする。 $F=\{f\mid f:M\to S, \text{任意の } x_i\in S \text{ に対して } |f^{-1}(x_i)|=m_i\}$ とするとき、$|F|$ を求めよ。

解答. $G=\{(x_i, k)\mid x_i\in S, k\in\mathbb{N}^*, 1\le k\le m_i\}$ とおくと、$|G|=m$ である。 $U=\{g\mid g:M\to G \text{ は全単射}\}$ とおくと、$|U|=m!$ である。 $U$ 上の関係 $R$ を次のように定義する：$gRh \iff \pi\circ g = \pi\circ h$ （ここで $\pi:G\to S, (x_i, k)\mapsto x_i$）。このとき、

  1. $R$ は $U$ 上の同値関係であり、任意の $g\in U$ に対して $\pi\circ g\in F$ となる。
  2. $R$ の各同値類にはちょうど $r := m_1!m_2!\dots m_n!$ 個の要素が含まれる。
  3. 写像 $\varphi:U/R\to F, [g]_R\mapsto \pi\circ g$ は全単射である。

したがって、$m! = |U| = |U/R|\cdot r = |F|\cdot r$ となる。よって、$|F| = \frac{m!}{m_1!m_2!\dots m_n!}$ である。

組合せ

以下、$S$ を要素数が $n$ の有限集合とし、$m\in\mathbb{N}$ とする。

定義4（組合せ） $X$ が $S$ の部分集合であり $|X|=m$ であるとき、$X$ を $S$ から $m$ 個の要素を取り出す組合せ（または $S$ の $m$-部分集合）と呼ぶ。 $S$ のすべての $m$-部分集合の個数を、$S$ から $m$ 個の要素を取り出す組合せの数と呼ぶ。

定理8 $n$ 個の要素の集合 $S$ から $m$ 個の要素を取り出す組合せの数は

$$C(n,m) = \frac{P(n,m)}{m!} = \frac{n!}{m!(n-m)!}$$

性質9 $C(n,m) = C(n, n-m)$、$C(n+1, m+1) = C(n, m+1) + C(n, m)$。

証明. (1) $S$ を $n$ 元集合とし、$A=\{X\mid X\subseteq S, |X|=m\}, B=\{X\mid X\subseteq S, |X|=n-m\}$ とおく。$\varphi:A\to B, X\mapsto S\setminus X$ と定義すると、これは全単射である。
(2) 全体集合 $S$ を $n+1$ 元集合とし、$a\in S$ を1つ固定する。$T=S\setminus\{a\}$ とおくと $|T|=n$ であり、

$$\{X\mid X\subseteq S, |X|=m+1\} = \{X\mid X\subseteq T, |X|=m+1\} \cup \{Y\cup\{a\}\mid Y\subseteq T, |Y|=m\}$$

右辺の2つの集合は交わらない（互いに素である）ことに注意すれば、結論が得られる。∎

数の集合

自然数（すなわち非負の整数）全体の集合を $\mathbb{N}$ で表し、自然数の集合と呼ぶ。整数全体の集合を $\mathbb{Z}$ で表し、整数の集合と呼ぶ。有理数全体の集合を $\mathbb{Q}$ で表し、有理数の集合と呼ぶ。実数全体の集合を $\mathbb{R}$ で表し、実数の集合と呼ぶ。複素数全体の集合を $\mathbb{C}$ で表し、複素数の集合と呼ぶ。

$\mathbb{N}^* = \{n\in\mathbb{Z}\mid n>0\}$ と記し、正の整数の集合と呼ぶ（$\mathbb{N}^+$, $\mathbb{N}_+$ と記すこともある）。同様に、$\mathbb{Q}^+ = \{q\in\mathbb{Q}\mid q>0\}$、$\mathbb{R}^+ = \{r\in\mathbb{R}\mid r>0\}$ などと記す。

自然数の集合 $\mathbb{N}$

ここでは自然数の定義は与えず、3つの基本的な命題を述べた後に議論を展開する。命題1は「ペアノの公理」の1つであり、命題2と命題3は（加法と乗法、および大小関係などの一連の複雑な操作を定義した後の）ペアノの公理からの帰結である。

命題1（帰納法の公理） $S\subseteq\mathbb{N}$ とする。もし

  1. $0\in S$ であり、かつ
  2. 任意の $k\in S$ に対して $k+1\in S$ であるならば、

$S=\mathbb{N}$ である。

命題2（離散性） 任意の $a\in\mathbb{N}$ に対して、$a < b < a+1$ となるような $b\in\mathbb{N}$ は存在しない。

命題3（アルキメデスの性質） 任意の $a,b\in\mathbb{N}$ について、$a>0$ ならば、ある正の整数 $n$ が存在して $na>b$ となる。

定理4（数学的帰納法の原理） $P(n)$ を自然数 $n$ に関する命題とする。もし

  1. $P(0)$ が成り立ち、かつ
  2. $P(n)$ が成り立つことから $P(n+1)$ が成り立つことが導かれるならば、

すべての自然数 $n$ について $P(n)$ が成り立つ。

証明. 集合 $S=\{n\in\mathbb{N}\mid P(n)\text{ が成り立つ}\}$ を考える。(1)より $0\in S$ である。(2)より $n\in S$ ならば $n+1\in S$ である。帰納法の公理より $S=\mathbb{N}$、すなわちすべての自然数 $n$ について $P(n)$ が成り立つ。∎

例1 $f:\mathbb{N}\to\mathbb{R}^+$ が $f(0)=1$ を満たし、任意の $n\in\mathbb{N}$ に対して $f(n+1) = \frac{1}{2}f(n)(4-f(n))$ を満たすとする。任意の $n\in\mathbb{N}$ に対して $f(n)<f(n+1)<2$ であることを証明せよ。

解答. 命題 $P(n)$ を「$f(n)<f(n+1)<2$」とする。 $f(0)=1$、$f(1)=\frac{1}{2}\cdot 1\cdot (4-1)=\frac{3}{2}$ であるため、$f(0)<f(1)<2$、すなわち $P(0)$ は成り立つ。 $P(k)$ が成り立つ、すなわち $f(k)<f(k+1)<2$ と仮定すると、

$$f(k+2) - f(k+1) = \frac{1}{2}f(k+1)(4-f(k+1)) - f(k+1) = \frac{1}{2}(2-f(k+1))f(k+1)$$

$f(k+1)<2$ より $2-f(k+1)>0$ であり、$f(k+1)>0$ であるため、この差は正となる。ゆえに $f(k+1)<f(k+2)$。 さらに、

$$f(k+2) = \frac{1}{2}f(k+1)(4-f(k+1)) = \frac{1}{2}(4 - (2-f(k+1))^2) < 2$$

したがって $P(k+1)$ も成り立つ。数学的帰納法の原理により、任意の $n\in\mathbb{N}$ に対して $f(n)<f(n+1)<2$ が成り立つ。∎

定理5（最小値の原理） $S\subseteq\mathbb{N}$ かつ $S\ne\emptyset$ ならば、$S$ には最小の要素が存在する。すなわち、ある $m\in S$ が存在して、任意の $s\in S$ に対して $m\le s$ となる。

証明. $T=\{t\in\mathbb{N} \mid \text{任意の } s\in S \text{ に対して } t\le s\}$ とおく。明らかに $0\in T$ である。 もし仮に「任意の $t\in T$ に対して $t+1\in T$」であるとすれば、帰納法の公理より $T=\mathbb{N}$ となる。しかし $S$ は空でないため、ある $a\in S$ が存在する。$a<a+1$ であり、$T$ の定義より $a+1\notin T$ となるが、これは $T=\mathbb{N}$ に矛盾する。したがって、ある $m\in T$ が存在して $m+1\notin T$ となる。 $m+1\notin T$ であるため、ある $b\in S$ が存在して $b < m+1$ となる。離散性より $b\le m$ である。一方で $m\in T$ であるため $m\le b$ も成り立つ。よって $m=b$ であり、したがって $m\in S$ となる。最後に、$m\in T$ であることから、$m$ は $S$ の最小の数であることがわかる。∎

系6（最大値の原理） $S\subseteq\mathbb{N}, S\ne\emptyset$ であり、ある $\beta\in\mathbb{N}$ が存在して任意の $s\in S$ に対して $s\le \beta$ となるならば、$S$ には最大の要素が存在する。すなわち、ある $m\in S$ が存在して、任意の $s\in S$ に対して $s\le m$ となる。

整数の集合 $\mathbb{Z}$

性質7（離散性とアルキメデスの性質）

  1. 任意の $a\in\mathbb{Z}$ に対して、$a<b<a+1$ となるような $b\in\mathbb{Z}$ は存在しない。
  2. 任意の $a,b\in\mathbb{Z}$ について、$a>0$ ならば、ある正の整数 $n$ が存在して $na>b$ となる。

性質8 $S\subseteq\mathbb{Z}, S\ne\emptyset$ とする。

  1. ある $\alpha\in\mathbb{Z}$ が存在して、任意の $s\in S$ に対して $s\ge\alpha$ となるならば、$S$ には最小の要素が存在する。
  2. ある $\beta\in\mathbb{Z}$ が存在して、任意の $s\in S$ に対して $s\le\beta$ となるならば、$S$ には最大の要素が存在する。

問題3 全単射 $\mathbb{N}^*\to\mathbb{Z}$ は存在するか？

解答

存在する。たとえば

$$f(n) = \begin{cases} n/2, & n \text{ が偶数のとき} \\ -(n-1)/2, & n \text{ が奇数のとき} \end{cases}$$

とおくと、$f(1), f(2), f(3), f(4), \dots = 0, 1, -1, 2, \dots$ となり、すべての整数をちょうど一度ずつとる。偶数 $n$ は正の整数に、奇数 $n$ は $0$ 以下の整数に一対一に対応するから、$f$ は全単射である。

有理数の集合 $\mathbb{Q}$

性質9（アルキメデスの性質） 任意の $a,b\in\mathbb{Q}$ について、$a>0$ ならば、ある正の整数 $n$ が存在して $na>b$ となる。

定理10（稠密性） 任意の $a,b\in\mathbb{Q}$ について、$a<b$ ならば、ある $r\in\mathbb{Q}$ が存在して $a<r<b$ となる。

例2 $A=\{x\in\mathbb{Q} \mid x>0, x^2<2\}$、$B=\{x\in\mathbb{Q} \mid x>0, x^2>2\}$ とする。$A$ には最大の数がなく、$B$ には最小の数がないことを証明せよ。

解答. 正の有理数 $p$ に対し、$q = p - \frac{p^2-2}{p+2}$とすると、$q = \frac{2p+2}{p+2} > 0$ であり、$q^2-2 = \frac{2(p^2-2)}{(p+2)^2}$ となる。 したがって、$p\in A$（すなわち $p^2<2$）のときは $q\in A$ となり、かつ $q>p$ である。これは $A$ に最大の数がないことを示している。 $p\in B$ のときは $q\in B$ となり、かつ $q<p$ である。これは $B$ に最小の数がないことを示している。∎

問題4 上記の $q$ はどのように見つけたのか？ $x^2=2$ となる正の有理数が存在しないことを証明せよ。

解答

$p$ の値を、$p^2$ と $2$ の差に比例する量だけ動かして $\sqrt{2}$ に近づけたい。$q = p - \dfrac{p^2-2}{m}$ とおくと、

$$q^2 - 2 = (p^2-2)\cdot\frac{(m-p)^2 - 2}{m^2}.$$

$(m-p)^2 > 2$ なら $q^2 - 2$ は $p^2 - 2$ と同じ符号になる（$p$ が $\sqrt{2}$ をまたがない）。$p$ に依らない簡単な選び方として $m = p + 2$ をとると $(m-p)^2 - 2 = 2$ で、$q = \dfrac{2p+2}{p+2}$、$q^2 - 2 = \dfrac{2(p^2-2)}{(p+2)^2}$ となる。

$x^2 = 2$ をみたす正の有理数 $x = a/b$（$a, b$ は互いに素な正の整数）があるとする。$a^2 = 2b^2$ より $a^2$ は偶数だから $a$ も偶数で、$a = 2c$ と書ける。すると $4c^2 = 2b^2$、$b^2 = 2c^2$ より $b$ も偶数となり、$a, b$ が互いに素であることに矛盾する。よって存在しない。

問題5 全単射 $\mathbb{N}^*\to\mathbb{Q}$ は存在するか？

解答

存在する。有理数を既約分数 $p/q$（$q \ge 1$）で表し、「高さ」$h = |p| + q$ を決める。各 $h \ge 1$ について、高さ $h$ の有理数は有限個（$|p| \le h-1$、$q \le h$ の範囲）である。 そこで、$0$ を最初に置き、高さが小さい順に、同じ高さの中は適当な順（たとえば $p$ の小さい順）に並べて番号を $1, 2, 3, \dots$ とつける。どの有理数もちょうど一つの高さをもち、その高さの有限個の並びの中に現れるから、この対応は $\mathbb{N}^*$ から $\mathbb{Q}$ への全単射である。

実数の集合 $\mathbb{R}$

性質11（アルキメデスの性質） 任意の $a,b\in\mathbb{R}$ について、$a>0$ ならば、ある正の整数 $n$ が存在して $na>b$ となる。

系12 任意の実数 $x$ に対し、必ずある正の整数 $n$ が存在して $-n<x<n$ となる。（証明略）

系13 任意の実数 $x$ に対し、$x$ を超えない最大の整数が必ず存在し、また $x$ を下回らない最小の整数も存在する。 注. 通常、$x$ を超えない最大の整数を $[x]$ または $\lfloor x\rfloor$ と記し、$x$ を下回らない最小の整数を $\lceil x\rceil$ と記す。

定理14（$\mathbb{R}$ における $\mathbb{Q}$ の稠密性） 任意の $a,b\in\mathbb{R}$ について、$a<b$ ならば、ある $r\in\mathbb{Q}$ が存在して $a<r<b$ となる。

証明. $\mathbb{R}$ のアルキメデスの性質より、ある正の整数 $k$ が存在して $k>-a$、すなわち $k+a>0$ となる。 $a<b$ より $b-a>0$ であるから、$\mathbb{R}$ のアルキメデスの性質より、ある正の整数 $n$ が存在して

$$n(b-a) > 1$$

となる。 $S=\{x\in\mathbb{N} \mid x>n(k+a)\}$ を考える。アルキメデスの性質より $l>n(k+a)$ となる正の整数 $l$ が存在するため $S$ は空ではない。最小値の原理より、$S$ には最小の要素 $m$ が存在する。 $m\in S$ より $m>n(k+a)$ である。 $m$ は $S$ の最小要素であるため、$m-1\notin S$、すなわち $m-1\le n(k+a)$ となる。したがって

$$m \le n(k+a)+1 < n(k+a) + n(b-a) = n(k+b)$$

ゆえに $n(k+a) < m < n(k+b)$ である。$r = \frac{m}{n}-k$ とおくと、$r\in\mathbb{Q}$ かつ $a<r<b$ となる。∎

系15 $x$ を実数とする。任意の正の有理数 $r$ に対して $x<r$ であるならば、$x\le0$ である。

問題6 $\mathbb{R}\setminus\mathbb{Q}$ を無理数の集合と呼び、これはすべての無理数からなる集合である。例えば $\sqrt{2}\in\mathbb{R}\setminus\mathbb{Q}$ である。無理数の集合も $\mathbb{R}$ において稠密であろうか？

解答

稠密である。実数 $a < b$ をとる。$a/\sqrt{2} < b/\sqrt{2}$ だから、$\mathbb{Q}$ の稠密性（定理 14）より有理数 $r$ で $a/\sqrt{2} < r < b/\sqrt{2}$ をみたすものがある。$r = 0$ のときは、$0 < r' < b/\sqrt{2}$ をみたす別の有理数 $r'$ をとり直せば $r \neq 0$ にできる。 このとき $r\sqrt{2}$ は $a < r\sqrt{2} < b$ をみたす。しかも $r\sqrt{2}$ は無理数である（有理数であれば $\sqrt{2} = (r\sqrt{2})/r$ も有理数になってしまう）。よって、任意の二つの実数の間に無理数がある。

定義1 $S\subseteq\mathbb{R}, S\ne\emptyset$ とする。

  1. ある $a\in\mathbb{R}$ が存在して、任意の $x\in S$ に対して $a\le x$ となるならば、$S$ は下に有界である（あるいは下界を持つ）といい、$a$ を $S$ の下界と呼ぶ。
  2. ある $b\in\mathbb{R}$ が存在して、任意の $x\in S$ に対して $x\le b$ となるならば、$S$ は上に有界である（あるいは上界を持つ）といい、$b$ を $S$ の上界と呼ぶ。
  3. $S$ が下に有界かつ上に有界であるとき、$S$ は有界であるという。
  4. $\alpha$ が $S$ の下界であり、$\alpha$ より大きい実数がどれも $S$ の下界とならないとき、$\alpha$ を $S$ の最大下界または下限と呼び、$\inf S$ と記す。
  5. $\beta$ が $S$ の上界であり、$\beta$ より小さい実数がどれも $S$ の上界とならないとき、$\beta$ を $S$ の最小上界または上限と呼び、$\sup S$ と記す。

問題7 $f(n)=\sqrt{1+\sqrt{2+\sqrt{3+\dots+\sqrt{n+\sqrt{n+1}}}}} \ (n\in\mathbb{N}^*)$ の値域には上界があるか？

解答

上界をもつ。$T_k = \sqrt{k + \sqrt{(k+1) + \cdots + \sqrt{n + \sqrt{n+1}}}}$（$1 \le k \le n$）とおくと $f(n) = T_1$ で、$T_k = \sqrt{k + T_{k+1}}$（$T_n = \sqrt{n + \sqrt{n+1}}$）である。すべての $k$ で $T_k < k+1$ となることを、$k$ の大きい方から帰納法で示す。

$k = n$：$n + \sqrt{n+1} < n + (n+1) = 2n + 1 \le (n+1)^2$ だから $T_n < n+1$。
$k+1$ で成り立つと仮定する。$T_{k+1} < k+2$ だから $T_k^2 = k + T_{k+1} < 2k + 2 \le (k+1)^2$（$k \ge 1$ で $k^2 \ge 1$ より成り立つ）。よって $T_k < k+1$。

特に $k = 1$ で $f(n) = T_1 < 2$。したがって値域は $2$ を上界にもつ（$n$ によらない）。

定理16（上限・下限の原理 / 連続性公理） $\mathbb{R}$ において、上に有界な空でない集合は必ず上限を持ち、下に有界な空でない集合は必ず下限を持つ。
（範囲外のため証明略）

注. この定理は実数の集合の「完備性（連続性）」を記述するものであり、数学における重要な定理の1つである。

例3 $\sup[0,1]=1$, $\sup(0,1)=1$。$\inf\{\frac{n+1}{n}\mid n\in\mathbb{N}^*\} = 1$。例2の $A, B$ については、$\sup A = \inf B = \sqrt{2}$ である。$\inf\{n\mid n\in\mathbb{Z}, n\ge2\} = 2$。

無限 »