ホーム
情報セキュリティ
暗号技術
暗号の数学
集合と写像
集合
集合 (Set)
ある物(対象)の集まりで,以下の性質を持つものを集合と言う.
ある対象がその集合に属するかどうか判断できること
集合に属するある2つの対象が同一のものかどうか判断できること
対象が有限である集合を有限集合,対象が無限にある集合を無限集合と言う.
集合の要素(元)
集合に属する対象
元 $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 \}$
関係 (relation)
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]\}$
写像
写像 (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$).
$X$ から $Y$ への写像 $\varphi$
$\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写像)
全単射なる写像を同型写像と呼ぶ.
Prev
Page Top
Next