集合論、代数学、解析学で使う基本的な定義をまとめる。
1. 集合
集合とは、互いに区別できる対象を集めたものであり、その対象を元という。$x\in X$は、$x$が集合$X$の元であることを表す。
2. 外延的定義と内包的定義
集合は、元を列挙する外延的定義、または元が満たす性質を示す内包的定義によって表せる。例えば、英小文字全体の集合は
\[\{a,b,c,\ldots,z\}\]と書ける。
3. 部分集合
$X$のすべての元が$Y$にも属するとき、$X$は$Y$の部分集合であるといい、$X\subseteq Y$と書く。
\[X \subseteq Y \iff \forall x\,(x \in X \Rightarrow x \in Y).\]4. 和集合
和集合$X\cup Y$は、$X$または$Y$の少なくとも一方に属する元からなる。
\[X \cup Y = \{x \mid x \in X \lor x \in Y\}.\]5. 共通部分
共通部分$X\cap Y$は、$X$と$Y$の両方に属する元からなる。
\[X \cap Y = \{x \mid x \in X \land x \in Y\}.\]6. 差集合
差集合$X\setminus Y$は、$X$には属するが$Y$には属さない元からなる。
\[X \setminus Y = \{x \in X \mid x \notin Y\}.\]7. 補集合
全体集合$U$を固定し、$X\subseteq U$とする。$X$の補集合は
\[X^c = U \setminus X\]である。
8. 空集合
空集合$\emptyset$は元を持たない集合であり、あらゆる集合の部分集合である。
9. 冪集合
$X$の冪集合は、$X$のすべての部分集合からなる集合である。
\[\mathcal{P}(X) = \{A \mid A \subseteq X\}.\]| $2^X$とも書く。$X$が有限集合なら、$ | \mathcal{P}(X) | =2^{ | X | }$である。 |
10. 直積
$A$と$B$の直積は順序対からなる。
\[A \times B = \{(a,b) \mid a \in A,\ b \in B\}.\]集合$X_1,\ldots,X_n$の直積は
\[X_1 \times \cdots \times X_n = \{(x_1,\ldots,x_n) \mid \forall i,\ x_i \in X_i\}\]である。すべての$X_i$が同じ集合$X$なら、$X^n$と書く。
11. 対称差
対称差$A\triangle B$は、$A$と$B$のちょうど一方に属する元からなる。
\[A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B).\]12. 群と位数
群とは、空でない集合$G$と二項演算$\cdot:G\times G\to G$の組であり、結合法則、単位元の存在、各元の逆元の存在を満たすものをいう。すべての$x,y,z\in G$について、
- $(x\cdot y)\cdot z=x\cdot(y\cdot z)$;
- $e\cdot x=x\cdot e=x$となる単位元$e\in G$が存在する;
- 各$x\in G$に対し、$x\cdot x^{-1}=x^{-1}\cdot x=e$となる逆元$x^{-1}\in G$が存在する。
演算が結合的な集合は半群、さらに単位元を持つものはモノイドである。演算が可換な群をアーベル群という。有限群の位数はその元の個数である。
13. 代数的数と超越数
複素数が有理数係数の0でない多項式の根であるとき、その数を代数的数という。代数的でない複素数を超越数という。
14. 写像
写像$f:X\to Y$は、$X$の各元に$Y$のただ一つの元を対応させる。$X$を定義域、$Y$を終域という。像（値域）は
\[f(X)=\{f(x)\mid x\in X\}\subseteq Y\]である。対応を$x\mapsto f(x)$と表す。
15. 単射、全射、全単射
写像$f:X\to Y$について、
- $f(x_1)=f(x_2)$ならば$x_1=x_2$が成り立つとき単射;
- 任意の$y\in Y$に対して$f(x)=y$となる$x\in X$が存在するとき全射;
- 単射かつ全射であるとき全単射という。
16. 逆写像
$f:X\to Y$が全単射であるときに限り、逆写像$f^{-1}:Y\to X$が存在し、$f^{-1}(f(x))=x$および$f(f^{-1}(y))=y$を満たす。
17. 対等な集合
$A$から$B$への全単射が存在するとき、$A$と$B$は対等であるといい、$A\sim B$と書く。
18. 濃度と可算性
| 集合$A$の濃度$ | A | $は、その集合の大きさを表す。有限集合の濃度は元の個数である。自然数全体$\mathbb{N}$と全単射を持つ無限集合を可算無限という。「可算」は有限集合と可算無限集合の両方を指す場合が多い。 |
19. 濃度の比較
| $A$から$B$への単射が存在すれば、$ | A | \leq | B | $である。濃度が等しいのは両者の間に全単射がある場合に限る。通常の濃度の比較では、$ | A | < | B | $は$ | A | \leq | B | $かつ$ | A | \ne | B | $を意味する。 |