暗号の数学
集合と写像
集合
- 集合 (Set)
ある物(対象)の集まりで，以下の性質を持つものを集合と言う．- ある対象がその集合に属するかどうか判断できること
- 集合に属するある２つの対象が同一のものかどうか判断できること
- 集合の要素(元)
- 集合に属する対象
- 元 $a$ は集合 $A$ に属する(含まれる)
$a \in A$，$A \ni a$
- 集合の大きさ
有限集合の元の数 ： $|A|$
- 外延的記法
$K = \{1,2,3,4,5,6,7,8,9\}$
$K = \{1桁の自然数\}$
- 内包的記法
- $K = \{n\ |\ nは1桁の自然数 \}$
- $A = \{x\ |\ P(x) \}$
$P(x)$ は $x$ についての条件
例)：
$N = \{x\ |\ xは自然数\}$
$P = \{x\ |\ x は 0 \lt x \lt 1 なる実数\}$
$S = \{k\ |\ -10 \lt k \lt 10 \}$
- 部分集合 (Subset)
- 集合 $A$ のすべての元が $B$ の元でもあるとき，$A$ は $B$ の部分集合と言う．
- $A$ は $B$ に包含される($B$ は $A$ を包含する)という．
- $A \subset B$ または $B \supset A$ と表す．
- $A \subset B$ $\Leftrightarrow$ ($\forall a \in A \Rightarrow a \in B$）
- $A \subset B$ かつ $B \subset A$ のとき，$A$ と $B$ は等しい．
$A=B$ $\Leftrightarrow$ ($A \subset B \wedge B \subset A$) - $A \subset B$ かつ $A \ne B$ のとき，$A$ は $B$ の真部分集合(proper subset)と言う．
- 順序対 (ordered pair)
$(a, b)$ ： 順序を持つ2つの成分の組(第1成分，第2成分) - 集合 $A$，$B$ の直積集合
$A \times B = \{(x, y)\ |\ x \in A, y \in B \}$
$ |A \times B| = |A| \times |B|$ - $n$ 項組 ($n$-tuple)
$(a_1,a_2,a_3,\ldots, a_n)$ - $n$ 次の直積集合
$A_1 \times A_2 \times \cdots \times A_n = \{(a_1,a_2,\ldots, a_n)\ |\ a_1 \in A_1, a_2 \in A_2,\cdots, a_n \in A_n \}$
- 2つの集合 $A$，$B$ の直積集合 $A \times B$ の任意の部分集合を $A$ から $B$ への2項関係(関係)という．
- $x \in A$ が $y \in B$ と $R$ なる関係にあるとき $xRy$ (または，$x \sim y$)と書く．
- $A = B$ のとき，$A$ の上の関係
- $B$ から $A$ への関係 $R$ の逆の関係： $R^{-1}$
- $xR^{-1}y \equiv yRx$
- $R^{-1} = \{ (x,y)\ |\ (y,x) \in R \}$
集合 $A$ 上の関係 $R$ について，以下の条件を満たす時，$R$ を同値関係と呼ぶ．- 反射律
$x \in A \longrightarrow (x,x) \in R$ - 対称律
$(x,y) \in R \longrightarrow (y,x) \in R$ - 推移律
$(x,y) \in R \wedge (y,z) \in R \longrightarrow (x,z) \in R$
関係 $R$ を集合 $S$ についての同値関係とする．
$x \in S$ に対して $x$ と同値な元を集めた $S$ の部分集合を $S(x)$ と書く． \[ S(x) = \{ z \in S\ |\ z \sim x \} \] このとき，任意の元 $x$，$y$ に対し，$S(x)$ と $S(y)$ は，$S(x)=S(y)$ か $S(x) \cap S(y) = \phi$ のいずれかである． $S(x)$ を同値類(equivalent class)と呼ぶ． 同値類の集合 $\{S(x)\ |\ x \in S\}$ を $S$ の同値関係 $R$ による商集合と呼び，$S/R$ で表す． 同値類を $S(x)$ と書く時，$x$ を代表元と呼ぶ．
(例) 整数の集合 $Z$ における3を法とする合同関係- $xR_3y: x \equiv y \pmod{3}$
$[0]=[3]=[6]= \cdots$： $3$ で割り切れる整数
$[1]=[4]=[7]= \cdots$： $3$ で割って $1$ 余る数
$[2]=[5]=[8]= \cdots$： $3$ で割って $2$ 余る数
$Z = [0]+[1]+[2] $ ： 3つの同値類の直和
$Z/R_3 = \{[0],\ [1],\ [2]\}$
- 集合 $A$ のすべての元が $B$ の元でもあるとき，$A$ は $B$ の部分集合と言う．
写像
- 写像 (Mapping)
集合 $X$ から集合 $Y$ への関係 $M$ が，次の2条件を満足するとき，関係 $M$ を写像という．- $X$ の任意の元 $x$ は必ず $Y$ のある元に関係する(任意の $x \in X$ に対し，$xMy$ となる $y \in Y$ が存在する)．
- 1つの $x$ が異なる2つ以上の $y$ に関係しない ($x_1,x_2 \in X,\ y_1,y_2 \in Y$ で，$x_1My_1$，$x_2My_2$ のとき，$y_1 \ne y_2$ ならば $x_1 \ne x_2$)．
- $\varphi$ ： $X \rightarrow Y$
- $\varphi(x)$ ： $x \in X,\ \varphi(x) \in Y$
- 写像の性質
- 全射
$Y$ の任意の $y$ に対して $X$ に原像が存在する．すなわち，$X$ のすべての元 $x$ を写像させたものが $Y$ になる． - 単射
$f(x_1) = f(x_2)$ ならば $x_1=x_2$，$x_1,x_2 \in X$，$f(x_1),f(x_2) \in Y$ - 全単射
写像が全射でかつ単射(上への1対1写像)
全単射なる写像を同型写像と呼ぶ．
- 全射
／