\def\vector#1{\boldsymbol{#1}}

集合論

2023年6月24日 #集合論

概要

集合論は数学の基礎的な分野であり、数学的対象を扱う上での基本的な概念や枠組みを提供する。これは集合や要素の集まりを厳密に定義し、それらの性質や関係を明確にすることでそれらを形式的に表現したり操作を行うことができる。

概要
集合
写像
演算
同値関係
参考文献

集合

集合 (set) は様々なものの集まりである。集合を構成するものを元または要素 (element) と呼ぶ。例えば 3 つの元 $x$ , $y$ , $z$ で構成される集合 $S$ を式 ( $\ref{group}$ ) のように表記し、元 $x$ が集合 $S$ に含まれることを式 ( $\ref{in}$ ) のように表記する。 $\begin{eqnarray} S & = & \{x, y, z\} \label{group} \\ x & \in & S \label{in} \end{eqnarray}$

式 ( $\ref{group}$ ) のように集合を構成する元を個別に列挙する表記を外延的記法 (sets defined by enumeration, roster method) と呼ぶ。もう一つの方法として式 ( $\ref{by_predicate}$ ) のように集合の性質に基づく表記を内包的記法 (sets defined by a predicate) と呼ぶ。ここで $\Phi$ は規則や述語と呼ばれ、集合 $S$ は述語が成立する (真となる) $x$ で構成されていることを示している。 $\begin{equation} S = \{x\,|\,\Phi(x), x \in T\} \label{by_predicate} \end{equation}$

一部のプログラミング言語では集合の内包的表記に由来するリスト内包表記と呼ばれるリスト生成の記法がある。例えば Python では [x * 2 for x in range(1,11) if x % 3 == 0] は [6, 12, 18] という新しいリストを生成する。これは関数型言語では range(1,11).filter(_ % 3 == 0).map(_ * 2) のように filter 関数と map 関数の組み合わせで代用することができる。

クラス (class) または類とは、元が持つある共通の性質によって明確に定義できる集合またはそのようなクラスの集合の集まりである。

プログラミング言語における型は暗にその型を持つ値の集合を定義する。したがって型やクラスは集合論の観点で類と見なすことができる。

一般に集合は重複する元を持たず元の順序を定めないため $\{x,y,x,z,y\}$ という値の集まりは集合として $\{x,y,z\}$ と表記する。重複する元の存在を意図する集合は重複集合 (multi-set)、元が順序を持つ集合は順序集合と明示的に呼ぶ。

一般的な数の集合は自然数 (natural number) を $\mathbb{N}$ 、整数 (integer) を $\mathbb{Z}$ 、有理数 (rational number) を $\mathbb{Q}$ 、実数 (real number) を $\mathbb{R}$ 、複素数 (complex number) を $\mathbb{C}$ と表す。 $\begin{eqnarray*} \mathbb{N} & = & \{1,2,3,\ldots\} \\ \mathbb{Z} & = & \{\ldots,-2,-1,0,1,2,\ldots\} \\ \mathbb{Q} & = & \left\{ \frac{n}{m} \ | \ n \in \mathbb{Z}, m \in \mathbb{N} \right\} \end{eqnarray*}$

元の数が有限である集合を有限集合 (finite set)、無限となる集合を無限集合 (infinite set) と呼ぶ。また元を一つも含まない集合 $\{\}$ を空集合 (empty set) と呼び $\emptyset$ で表す。

集合 $S$ に含まれる元の数を濃度 (potency) または基数 (cardinality) と呼び $|S|$ と表す。例えば自然数 $\mathbb{N}$ や実数 $\mathbb{R}$ は無限集合で $|\mathbb{N}|=|\mathbb{R}|=\infty$ である。また $\{1,2,3\}$ は有限集合で $|\{1,2,3\}|=3$ となる。また、例えば自然数 $\mathbb{N}$ と実数 $\mathbb{R}$ では実数 $\mathbb{R}$ の方が濃度は高いというように、無限集合であっても濃度の違いを考慮することができる。

集合 $T$ のすべての元が集合 $S$ の元であるとき、 $T$ は $S$ の部分集合 (subset) であると言い $T \subset S$ で表す。

交差と和集合

集合 $S$ と $T$ に共通する元の集合を交差 (intersection) または積集合、共通集合と呼び式 ( $\ref{intersection}$ ) のように表す。また $S$ または $T$ のいずれかに属する元の集合を和集合 (union set) または合併集合と呼び式 ( $\ref{union}$ ) のように表す。 $\begin{eqnarray} S \cap T & = & \{x \ | \ x \in S \ \land \ x \in T\} \label{intersection} \\ S \cup T & = & \{x \ | \ x \in S \ \lor \ x \in T\} \label{union} \end{eqnarray}$ $n$ 個の集合による交差や和集合は式 ( $\ref{bigcap}$ ) のように表すことができる。 $\begin{equation} \begin{array}{lcl} {\displaystyle \bigcap_{i=1}^n S_i} & = & S_1 \cap S_2 \cap \ldots \cap S_n \\ {\displaystyle \bigcup_{i=1}^n S_i} & = & S_1 \cup S_2 \cup \ldots \cup S_n \end{array} \label{bigcap} \end{equation}$ $\cap$ と $\cup$ は結合律と交換律を満たすため式 ( $\ref{bigcap}$ ) においてどのような位置に括弧を配置しても良い。

直積

2 つの集合 $S$ , $T$ それぞれの元のすべての組み合わせからなる集合を $S$ と $T$ の直積 (Cartesian product, direct product) と呼び式 ( $\ref{cartesian_prod}$ ) のように表す。 $\begin{equation} S \times T = \left\{ (s, t) \ | \ s \in S, \ t \in T \right\} \label{cartesian_prod} \end{equation}$ 例えば集合 $\{x,y,z\}$ と $\{1,2\}$ の直積は式 ( $\ref{prod_ex}$ ) のようなペアの集合である。 $\begin{equation} \{x,y,z\} \times \{1,2\} = \left\{ \begin{array}{cc} (x,1) & (x,2) \\ (y,1) & (y,2) \\ (z,1) & (z,2) \end{array} \right\} \label{prod_ex} \end{equation}$ 集合 $S$ における $n$ 回の直積は式 ( $\ref{n_prod}$ ) のように表すことができる。ここで $S^0=\{()\}$ である。 $\begin{equation} S^n = S \times S \times \ldots \times S \label{n_prod} \end{equation}$

直和

交差が空集合となるような 2 つの集合 (つまり共通の元を持たない集合) を互いに疎であるという。互いに疎な 2 つの集合 $S \cap T = \emptyset$ の和集合 $S \cup T$ を直和 (direct sum) または分離和、非交和 (disjoint union) と呼び式 ( $\ref{directsum}$ ) のように表す。直和 $\oplus$ (または $\amalg$ ) は和集合 $\cup$ とほぼ同じ意味だが左右の集合が互いに疎であることを示唆している。 $\begin{equation} S \oplus T = \{x\,|\,x \in S \ \lor \ x \in T,\ S \cap T = \emptyset\} \label{directsum} \end{equation}$

$n$ 個の集合による直和は式 ( $\ref{n_directsum}$ ) のように表すことができる。 $\begin{equation} \coprod_{i=1}^n S_i = S_1 \oplus S_2 \oplus \ldots \oplus S_n \label{n_directsum} \end{equation}$

例えば奇数の集合 $S=\{2n+1\,|\,n\in\mathbb{Z}\}$ と偶数の集合 $T=\{2n\,|\,n\in\mathbb{Z}\}$ は互いに疎であり、 $S$ と $T$ の直和 $S \oplus T$ は整数 $\mathbb{Z}$ である。

互いに疎ではない集合で直和という言葉を使うときは、それぞれの元に出自情報を追加した上での和集合を意味する。例えば $S=\{x,y\}$ と $T=\{x,y,z\}$ に対する直和は $S \oplus T = \{x_S,y_S,x_T,y_T,z_T\}$ のようになる。

一般的なプログラミング言語の列挙型 (enum) は列挙した識別子に定数を割り当てているだけのことが多いが、Rust の列挙型は複数の型 (集合) を統合した直和型データ構造を定義することができる。例えば上記の例は次の DirectSum 型のように定義できる。
enum S { x, y }
enum T { x, y, z }
enum DirectSum { S(S), T(T) }

写像

集合 $S$ 上の全ての要素を集合 $T$ 上の特定の要素と対応づける規則を写像 (map) または関数 (function) と言い式 ( $\ref{map}$ ) のように表す。このとき集合 $S$ を写像 $f$ の定義域 (domain) または始集合、 $T$ を $f$ の値域 (codomain) または終集合と呼ぶ。 $\begin{equation} f: S \to T \label{map} \end{equation}$ 集合 $S$ に含まれる個別の元 $x \in S$ の像を表すには式 ( $\ref{mapsto}$ ) のような矢印を使用する。 $\begin{equation} x \mapsto f(x) \label{mapsto} \end{equation}$ 例えば $f(r)=\pi r^2$ に対しては集合として $f:\mathbb{R} \to \mathbb{R}$ であり、元として $2 \mapsto 4 \pi$ である。

集合 $S$ から $T$ への写像全体の集合を式 ( $\ref{mapset}$ ) のように表す。 $\begin{equation} {\rm Map}(S,T) = \{f \ | \ f: S \to T\} \label{mapset} \end{equation}$

直積 $S \times T$ に対する写像 $f: S \times T \to U$ は $x \in S$ , $y \in T$ に対して $f(x,y) \in U$ を定める。ここで $x_0 \in S$ を固定することで写像 $y \mapsto f(x_0,y)$ は $T \to U$ となる。つまり $f(x_0,y)=f_{x_0}(y)$ と置けば $f_{x_0}$ は ${\rm Map}(T,U)$ の元であると言える。すなはち $x_0 \mapsto f_{x_0}$ は $S \to {\rm Map}(T,U)$ となる写像を導く。したがって式 ( $\ref{prodmap}$ ) のような全単射が得られる。 $\begin{equation} {\rm Map}(S \times T, U) \to {\rm Map}(S, {\rm Map}(T, U)) \label{prodmap} \end{equation}$

射

写像 $f:S \to T$ に関して、集合 $S$ 上で異なる要素の像が必ず $T$ 上の異なる要素に対応する写像は単射 (injection) である。このため集合 $T$ の元の数は $S$ と同じかそれより大きくなければならず $f$ の像は $T$ の部分集合となる。

写像 $f:S \to T$ による像が $T$ のすべての要素に対応する (つまり像が $T$ と等しい) 写像は全射 (surjection) である。全射のケースでは集合 $T$ の元の数は $S$ と同じかそれより小さくなければならない。

単射であり全射でもある写像を全単射 (bijection) と呼ぶ。全単射では集合 $S$ と $T$ の元の数は等しく、逆写像 $f^{-1}$ が存在する。

合成写像

2 つの写像 $f:S \to T$ と $g:T \to U$ が与えられたとき、式 ( $\ref{composite_func}$ ) で表されるような写像 $g \circ f$ を合成写像 (composite function) と呼ぶ。 $\begin{equation} (g \circ f)(s) = g(f(s)) \label{composite_func} \end{equation}$ 写像の合成は結合律が成立する。つまり $h \circ (g \circ f) = (h \circ g) \circ f$ である。

恒等写像

任意の $x \in S$ に対して式 ( $\ref{identity_map}$ ) が成り立つ写像 ${\rm id}_S$ を恒等写像 (identity map) と呼ぶ。 $\begin{equation} \forall x \in S, \ {\rm id}_S(x) = x \label{identity_map} \end{equation}$ $f:S \to T$ , $g:T \to S$ に対する恒等写像の合成写像は式 ( $\ref{identity_comp}$ ) に示すように元の写像と等しい。 $\begin{equation} \begin{array}{lcl} f \circ {\rm id}_S & = & f \\ {\rm id}_S \circ g & = & g \end{array} \label{identity_comp} \end{equation}$

逆写像

2 つの写像 $f:S \to T$ と $g:T \to S$ に対して式 ( $\ref{inverse_map}$ ) が成り立つとき、 $g$ は $f$ の逆写像 (inverse map) であると言い $g=f^{-1}$ と表すことができる。このとき集合 $S$ と $T$ の元の数は等しく、 $f$ も $g$ も全単射である。 $\begin{equation} \begin{array}{lcl} g \circ f & = & {\rm id}_S \\ f \circ g & = & {\rm id}_T \label{inverse_map} \end{array} \end{equation}$

演算

集合 $S$ に対して $f:S \to S$ となる写像 $f$ を  $S$ 上の単項演算 (unary operation over $S$ ) と呼ぶ。例えば整数 $x \in \mathbb{Z}$ に対する写像 $x \mapsto -x \in \mathbb{Z}$ は $Z$ 上の単項演算である。

集合 $S$ に対して $S \times S \to S$ となる写像を  $S$ 上の二項演算 (binary operation over $S$ ) と呼ぶ。例えば写像 $f(x,y)=x+y$ は実数 $\mathbb{R}$ に対して $f:\mathbb{R} \times \mathbb{R} \to \mathbb{R}$ であるため $\mathbb{R}$ 上の二項演算である。一方で $f(x,y)=x^y$ は整数 $\mathbb{Z}$ に対して $f:\mathbb{Z} \times \mathbb{Z} \to \mathbb{Q}$ であるため  $\mathbb{N}$ に閉じていない。

より一般化すると、集合 $S$ の $n$ 個の直積から $S$ への写像 $f:S^n \to S$ を  $S$ 上の $n$ 項演算 ( $n$ -ary operation over $S$ ) と呼ぶ。つまり、 $S$ 上の $n$ 項演算とは $S$ に含まれる $n$ 個の元をとり $S$ の元を一つ定める写像を意味する。

この考えに基づくと $S^0=\{()\}$ に対しては  $S$ 上の 0 項演算 (nullary operation over $S$ ) が成立し、これは写像 $f:\{()\}\to S$ 、すなはち $f(())=x\in S$ となる値 $x$ を定めることを意味する。

$f:T \times S \to S$ となるような写像 $f$ を  $T$ の $S$ への作用という。

同値関係

ある集合 $S$ における 2 つの元 $x,y\in S$ の間に何らかの関係 (relation) $R$ が成立するとき、 $x$ と $y$ は関係がある。集合の 2 つの元の間に定める関係を二項関係 (binary relation) と呼ぶ。二項関係 $R$ が成立する集合 $\mathcal{R}$ は式 ( $\ref{bin_relation}$ ) に示すような直積集合の条件付き部分集合で表すことができる。 $\begin{equation} \mathcal{R} = \{(x, y) \in S^2 \ | \ x R y\} \label{bin_relation} \end{equation}$ 例えば 2 つの整数 $x,y\in\mathbb{Z}$ の「小なり」関係 $x \lt y$ が成立するペアの集合は $\mathcal{R} = \{(x,y) \in \mathbb{Z}^2\,|\,x\lt y\}$ と表すことができる。この場合 $(1,8)$ や $(-5,-4)$ は $\mathcal{R}$ に含まれるが $(2,2)$ や $(3,-2)$ は $\mathcal{R}$ に含まれない。

集合 $S$ 上の二項関係 $R$ が $x,y\in S$ 対して次の 3 つの条件を満たすとき $R$ は同値関係 (equivalence relation) である。

推移律: $xRy \, \land \, yRz \Rightarrow xRz$
反射律: $xRx$
対称律: $xRy \Rightarrow yRx$

$x$ と $y$ が同値関係であることを $x \sim y$ または $x \equiv y$ と表す。

参考文献

新井敏康, 基幹講座数学集合・論理と位相, 東京図書 (2022)

集合論

概要

Table of Contents

集合

交差と和集合

直積

直和

写像

射

合成写像

恒等写像

逆写像

演算

同値関係

参考文献