暗号の数学

集合と写像

集合

集合 (Set)
ある物(対象)の集まりで，以下の性質を持つものを集合と言う．
- ある対象がその集合に属するかどうか判断できること
- 集合に属するある２つの対象が同一のものかどうか判断できること
対象が有限である集合を有限集合，対象が無限にある集合を無限集合と言う．
- 集合の要素(元)
  - 集合に属する対象
  - 元 a は集合 A に属する(含まれる)
    a ∈ A，A ∋ 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 < x < 1なる実数}
    S = {k | -10 < k < 10}
部分集合 (Subset)
- 集合 A のすべての元が B の元でもあるとき，A は B の部分集合と言う．
  - A は B に包含される(B は A を包含する)という．
  - A ⊂ B または B ⊃ A と表す．
  - A ⊂ B ⇔ (∀ a ∈ A → a ∈ B）
- A ⊂ B かつ B ⊂ A のとき，A と B は等しい．
  A = B ⇔ (A ⊂ B ∧ B ⊂ A)
- A ⊂ B かつ A ≠ B のとき，A は B の真部分集合(proper subset)と言う．
順序対と直積
- 順序対 (ordered pair)
  ( a, b) ：順序を持つ2つの成分の組(第1成分，第2成分)
- 集合 A，B の直積集合
  A × B = {(x,y) | x ∈ A, y ∈ B }
  | A × B| = |A| × |B|
- n 項組 (n-tuple)
  ( a₁, a₂, a₃,..., a_n)
- n 次の直積集合
  A₁ × A₂ × ・・・ × A_n = {(a₁, a₂,..., a_n) | a₁ ∈ A₁, a₂ ∈ A₂,・・・, a_n ∈ A_n }
関係 (relation)
- 2つの集合 A，B の直積集合 A × B の任意の部分集合を A から B への2項関係(関係)という．
- x ∈ A が y ∈ B と R なる関係にあるとき xRy (または，x ～ y)と書く．
- A = B のとき，A の上の関係
逆関係
- B から A への関係 R の逆の関係： R^-1
- xR^-1y ≡ yRx
- R^-1 = { (x, y) | (y, x) ∈ R }
同値関係
集合 A 上の関係 R について，以下の条件を満たす時，R を同値関係と呼ぶ．
- 反射律
  x ∈ A → (x, x) ∈ R
- 対称律
  ( x, y) ∈ R → (y, x) ∈ R
- 推移律
  ( x, y) ∈ R ∧ (y, z) ∈ R → (x, z) ∈ R
同値類
関係 R を集合 S についての同値関係とする．
x ∈ S に対して x と同値な元を集めた S の部分集合を S(x) と書く．
S(x) = { z ∈ S | z ～ x }
このとき，任意の元 x，y に対し，S(x) と S(y) は，S(x) = S(y) か S(x) ∩ S(y) = Φ のいずれかである． S(x) を同値類(equivalent class)と呼ぶ．同値類の集合 {S(x) | x ∈ S} を S の同値関係 R による商集合と呼び，S / R で表す．同値類を S(x) と書く時，x を代表元と呼ぶ．

(例) 整数の集合 Z における3を法とする合同関係
- xR₃y: x ≡ y (mod 3)
  [0]=[3]=[6]= ・・・：　3で割り切れる整数
  [1]=[4]=[7]= ・・・：　3で割って1余る数
  [2]=[5]=[8]= ・・・：　3で割って2余る数
  Z = [0]+[1]+[2] ：　3つの同値類の直和
  Z / R₃ = {[0], [1], [2]}

写像

写像 (Mapping)
集合 X から集合 Y への関係 M が，次の2条件を満足するとき，関係 M を写像という．
- X の任意の元 x は必ず Y のある元に関係する(任意の x ∈ X に対し，xMy となる y ∈ Y が存在する)．
- 1つの x が異なる2つ以上の y に関係しない (x₁,x₂ ∈ X, y₁,y₂ ∈ Y で，x₁My₁，x₂My₂ のとき， y₁ ≠ y₂ ならば x₁ ≠ x₂)．
X から Y への写像 φ
- φ ： X → Y
- φ(x) ： x ∈ X, φ(x) ∈ Y
写像の性質
- 全射
  Y の任意の y に対して X に原像が存在する．すなわち， X のすべての元 x を写像させたものが Y になる．
- 単射
  f (x₁) = f (x₂) ならば x₁ = x₂，x₁,x₂ ∈ X，f (x₁), f (x₂) ∈ Y
- 全単射
  写像が全射でかつ単射(上への1対1写像)
  全単射なる写像を同型写像と呼ぶ．

Page Top