集合と写像

集合と写像#

関係データベースのデータモデルである関係データモデルは，代数学，特に集合と写像に関する数学理論に支えられている．関係データモデルを理解するためにはこれらの知識が必要となるため，以下，最低限必要となる集合と写像の知識を説明する．

以下の説明はかなり形式的である．当たり前のことを記号をふんだんに使って説明しているが，物事を抽象化して捉えるためには記号的（数学的）な道具が必要になるので，嫌がらず読んでほしい（ただし気負いすぎないこと）．なお，集合と写像について知識がある読者は，本節を読み飛ばしても問題ない．

集合#

数学における集合（set） とは，何かを集めたものである．集合を構成する個々の「何か」は 要素（あるいは元; element） と呼ばれる．

例えば，以下は集合の例である．

${1, 2, 3}$

上記集合は整数1，2，3を要素として集めたものである． 1，2，3はそれぞれ集合{1, 2, 3}の要素である．一般に，集合は波カッコの中に要素を並べて表現する．

集合には名前がつけられる．例えば，上記集合について

$A = {1, 2, 3}$

とすれば，集合 ${1, 2, 3}$ を集合Aと呼ぶことができる．なお，慣習上，集合をアルファベットで表すときは大文字アルファベット1文字，集合の要素をアルファベットで表すときは小文字アルファベット1文字を使う（例外ケースもある）．

ある要素がある集合に属していることは，記号 $\in$ を用いて表現する．例えば，整数1が集合Aに属していること（つまり集合Aの要素であること）は

$1 \in A$

と書ける．一方，ある要素がある集合に属して「いない」ことは，記号 $\notin$ を用いて表現する．例えば，整数7が集合Aに属していないことは

$7 \notin A$

と書ける．

集合の要素は数に限らない．例えば，以下の平仮名集合Hのように文字の集合もありうる．

$H = {あ, い, う, え, お, . . . ., わ, を, ん}$

なお，集合の要素間の順序関係は無視される[1]．それゆえ，集合 $A = {1, 2, 3, 4, 5}$ と $B = {5, 4, 3, 2, 1}$ はまったく同じ集合となる．つまり，

$A = B$

となる．また，（数学的な定義の）集合の要素は重複してはならない[2]．重複する要素があった場合は，重複は無視して扱われる．例えば， $A = {1, 3, 5, 7, 7}$ は $A = {1, 3, 5, 7}$ として扱われることになる．

集合の外延的定義と内包的定義#

集合の定義（表記）方法には2種類ある．

1つは外延的定義である．これは，集合の要素を具体的に列挙することで集合を定義する方法である．例えば，

$A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}$

は「20以下の偶数」である集合Aを外延的定義によって定義したものである．外延的定義では集合の要素をすべて列挙するのが大変なため，以下のように途中の要素をテンテンで省略して書く場合もある．

$A = {2, 4, 6, . . ., 18, 20}$

2つめの定義方法は内包的定義である．外延的定義では要素を具体的に列挙するのに対して，内包的定義では集合の要素が満たすべき条件（性質）を示すことで集合を定義する．例えば，前述の集合Aであれば，

$A = {2 n | n は整数かつ 0 \leq n \leq 10}$

と書ける．内包的定義では波カッコの中を縦棒（|）で区切り，左側に集合の要素を表す文字を書き，右側には要素に関する条件を書く．なお，条件のAND（「かつ」）は以下のようにカンマで書くこともある．

$A = {2 n | n は整数, 0 \leq n \leq 10}$

よく使われる数の集合#

整数，自然数のように，よく使われる数の集合には特別な集合名が付けられている．以下，代表的な数の集合を列挙しておく．

$Z$ は，整数全体をあらわす集合である．すなわち，

$Z = {. . ., - 2, - 1, 0, 1, 2, . . .}$ .

例えば， $- 7 \in Z$ であり， $0.3 \notin Z$ である．

$N$ は，自然数全体をあらわす集合である．すなわち，

$N = {1, 2, 3, . . .} = {n | n \in Z, n \geq 1}$ .

$R$ は，実数全体をあらわす集合である．例えば， $\sqrt{3} \in R$ ， $π \in R$ ， $e \in R$ であり， $1 + 1 i \notin R$ ， $文字 \notin R$ である（★Quiz1★，★Quiz2★）．

空集合#

要素を持たない集合も集合である．そのような集合を空集合と呼ぶ．空集合は $ϕ$ で表す．すなわち，

$ϕ = {}$ ．

集合の要素数#

集合Xの要素数は， $| X |$ と表記する．例えば $A = {1, 2, 3, 4, 5}$ のとき， $| A | = 5$ である．また，

$Z_{n} = {0, 1, 2, 3, . . . ., n - 1} = {x | x \in Z, 0 \leq x \leq n}$

のとき， $| Z_{n} | = n$ となる．

要素を持たない集合も集合である．そのような集合を空集合と呼ぶ．空集合は $ϕ$ で表す．すなわち，

$ϕ = {}$ ．

積集合（集合の共通部分）#

2つの集合A，Bが与えられたとき，集合A，Bに共通の要素を集めた集合を積集合（あるいは共通集合; intersection） と呼ぶ．集合Aと集合Bの積集合は $A \cap B$ と記す．積集合 $A \cap B$ の内包的定義は以下の通り：

$A \cap B = {x | x \in A かつ x \in B}$

以下の図は，集合 $A = {2, 4, 6, 8, 10}$ と集合 $B = {4, 8, 12, 16, 20}$ の積集合 $A \cap B$ をベン図で表している．このケースでは $A \cap B = {4, 8}$ となる．

積集合

和集合#

2つの集合A，Bが与えられたとき，集合A，Bのいずれかに属する要素を集めた集合を和集合（union） と呼ぶ．集合Aと集合Bの和集合は $A \cup B$ と記す．和集合 $A \cup B$ の内包的定義は以下の通り：

$A \cup B = {x | x \in A または x \in B}$

以下の図は，集合 $A = {2, 4, 6, 8, 10}$ と集合 $B = {4, 8, 12, 16, 20}$ の和集合 $A \cup B$ をベン図で表している．このケースでは $A \cup B = {2, 4, 6, 8, 10, 12, 16, 20}$ となる．

和集合

差集合#

2つの集合A，Bが与えられたとき，集合Aには属しているが集合Bには属していない要素を集めた集合をBからAを引いた差集合（set difference） と呼ぶ．集合Bから集合Aを引いた差集合を $B - A$ または $B ∖ A$ と記す．差集合 $B - A$ の内包的定義は以下の通り：

$B - A = {x | x \in B かつ x \notin A}$

以下の図は，集合 $A = {2, 4, 6, 8, 10}$ から集合 $B = {4, 8, 12, 16, 20}$ を引いた差集合 $A - B$ をベン図で表している．このケースでは $A - B = {2, 6, 10}$ となる．

差集合1

以下は，集合Bから集合Aを引いた差集合 $B - A$ を表したベン図である．このケースでは $B - A = {12, 16, 20}$ となる． 2つの図を比較したら分かるように，差集合 $A - B$ と $B - A$ は異なる（★Quiz3★）．

差集合2

部分集合#

2つの集合A，Bが与えられたとき，集合Bが集合Aの一部としてすっぽり入っているとき，集合Bは集合Aの部分集合（subset） であるという．もう少し堅い定義をすると，集合Bの任意の要素（あらゆる要素）が集合Aに属するとき，集合Bは集合Aの部分集合である，とする．集合Bが集合Aの部分集合であることを， $B \subset A$ と記す．

例えば，以下の図では集合 $A = {5, 10, 15, 20, 25, 30, 35}$ と集合 $B = {10, 20, 30}$ であり，集合Bの要素はすべて集合Aの要素なので， $B \subset A$ となる（★Quiz4★）．

部分集合

直積#

2つの集合AとBが与えられたとき，Aの要素とBの要素を1つずつ取り出して作れるすべての組（ペア）を集めた集合を直積集合（Cartesian productあるいはdirect product） あるいは単に直積と呼ぶ．集合AおよびBの直積集合は $A \times B$ と記す．直積集合 $A \times B$ の内包的な定義は以下の通り：

$A \times B = {(a, b) | a \in A, b \in B}$ ．

例を見てみよう．例えば， $A = {1, 3, 5}$ ， $B = {2, 4, 6}$ のとき，AとBの直積は

$A \times B = {(1, 2), (1, 4), (1, 6), (3, 2), (3, 4), (3, 6), (5, 2), (5, 4), (5, 6)}$

となる．

もう1つ例を見てみよう．直積 $R \times R$ は2つの実数の組の集合になる． 1つ目の $R$ の要素をx座標の値，2つ目の $R$ の要素をy座標の値とすれば， $R \times R$ は2次元平面と見なすことができる．

最後に数値ではない直積の例を見てみよう．集合 $C = {データベース, 機械学習}$ ，集合 $D = {優, 良, 可, 不可}$ が与えられたとき，集合Cと集合Dの直積は，

$C \times D = {(データベース, 優), (データベース, 良), (データベース, 可), (データベース, 不可), (機械学習, 優), (機械学習, 良), (機械学習, 可), (機械学習, 不可)}$

となる．

関係データベースは直積と関連が深い． 高校数学では学ばなかった（と思われる）直積であるが，きっちり概念を押さえておこう（★Quiz5★）．

写像#

写像とは，2つの集合間の対応づけを表すものである．集合 $X$ に属するどの要素も，ルール $f$ で集合 $Y$ に属するいずれかの要素に対応づけすることが可能なとき， $f$ を「 $X$ から $Y$ への写像」と呼ぶ． $f$ が $X$ から $Y$ への写像であることを，以下のように記す．

$f : X \to Y$

また，写像 $f$ によって集合 $X$ の要素 $x$ が集合 $Y$ の要素 $y$ に対応することを，以下のように記す（矢印の種類が異なることに注意）．

$f : x \mapsto y$

このとき， $y$ を写像 $f$ による要素 $x$ の像（あるいは値） と呼び， $f (x)$ と記すこともできる．

最も馴染みのある写像の一つは関数である．例えば，小売店で商品を購入する際には，商品価格 $x$ に対して消費税10%分を加算した料金を支払う．最終的な支払い料金 $y$ を計算する関数 $f$ は

$y = f (x) = 1.1 x$

と書ける．商品価格や最終的な支払い料金は実数であり，関数 $f$ は実数から実数への写像になるため，

$f : R \to R$

と書くことができる．また，

$f : x \mapsto 1.1 x$

と書くこともできる．

関数ではない現実的な写像の例を示そう．大学では，学生が履修した科目に対して「優」「良」「可」「不可」の4段階の成績が付けられることが多い．今，集合 $S$ は学生の集合，集合 $C$ は科目の集合としたとき，集合 $S$ と $C$ の直積集合 $S \times C$ は（考えられうる）学生の科目の履修状況と見なせる（見なすことにしよう）．例えば， $S = {山畑滝子, 川澄桜, . . .}$ ， $C = {線形代数, データベース, . . .}$ とすると，

$S \times C = {(山畑滝子, 線形代数), (山畑滝子, データベース), (川澄桜, 線形代数), . . .}$

といった感じになる．

さて，成績の種別を表す集合を $U = {優, 良, 可, 不可}$ とすると，各学生の各科目に成績を付けるという行為（ $f_{採点}$ ）はまさに集合 $S \times C$ から $U$ への写像と見なすことができる．よって，以下のように書くことができる．

$f_{採点} : S \times C \to U$

定義域と値域#

上で写像 $f : X \to Y$ の概念を導入したが，写像元と写像先に名前を付けておくと便利なため，3つの概念を導入する．

1つ目は定義域である．集合 $X$ から集合 $Y$ への写像 $f$ が与えられたとき，集合 $X$ を写像 $f$ の定義域と呼ぶ．

2つ目は終域である．集合 $X$ から集合 $Y$ への写像 $f$ が与えられたとき，集合 $Y$ を写像 $f$ の終域と呼ぶ．

3つ目は値域である．集合 $X$ から集合 $Y$ への写像 $f$ が与えられたとき， $f$ によって写された集合 $X$ の要素の集合を写像 $f$ の値域と呼ぶ．値域は $Image f$ と記される．値域は少しややこしいが，定式化すると以下のように書ける

$Image f = {f (x) | x \in X}$

終域と値域の違いが分かりづらいかもしれないが，値域は終域の要素（ $y \in Y$ ）の中でも， $y = f (x)$ を満たすような $x$ が存在する $y$ の集合を表す．図にすると以下のようになる（図は「群論への第一歩（結城浩著, SBクリエイティブ）」から山本が書き起こし編集）（★Quiz6★）．

クイズ#

Q1. 外延的定義#

以下の集合 $S_{1}$ ， $S_{2}$ ， $S_{3}$ を外延的定義で記せ．ただし

$S_{n a m e} = {y a m a b a t a, k a w a s u m i, t a n a b e}$
関数 $f (x)$ は文字列xを”x@nagoya-c.ac.jp”という文字列に変換する関数

とする．

$S_{1} = {2 x | x \in N, 1 \leq x \leq 10}$

$S_{2} = {3 x | x \in N, x < 6}$

$S_{3} = {f (x) | x \in S_{n a m e}}$

Q2. 内包的定義#

以下の集合 $S_{4}$ ， $S_{5}$ ， $S_{6}$ を内包的定義で記せ．

$S_{4} = {- 3, - 2, - 1, 0, 1, 2, 3}$

$S_{5} = {3, 8, 13, 18, 23}$

$S_{6} = {- 3, - 8, - 13, - 18, - 23}$

Q3. 和集合，積集合，差集合#

上記Q1およびQ2で扱った集合をもとに，以下の集合の要素を求めよ．

$S_{7} = S_{1} \cup S_{2}$

$S_{8} = S_{1} \cap S_{2}$

$S_{9} = S_{1} - S_{2}$

$S_{10} = S_{2} - S_{1}$

Q4. 部分集合#

集合 $A$ ， $B$ ， $C$ を以下のように定義する．

$A = {線形代数, 微分積分}$

$B = {線形代数, 微分積分, データ構造, データベース, 機械学習}$

$C = {{線形代数, 微分積分}, B}$

このとき，以下の1からの命題が真か偽かを求めよ．

$データベース \in B$
$データベース \subset B$
$A \in B$
$A \subset B$
$A \in C$
$A \subset C$
$| A | = | B |$
$| A | = | C |$

※ 本問題は書籍「群論への第一歩: 集合、写像から準同型定理まで」に掲載された問題の改題である．

Q5. 直積#

集合 $S_{p r e f}$ および $S_{c i t y}$ を以下のように定義する．

$S_{p r e f} = {愛知, 岐阜, 三重}$

$S_{c i t y} = {名古屋, 岐阜, 津, 京都}$

このとき，集合 $S_{p r e f} \times S_{c i t y}$ の要素をすべて求めよ．

Q6. 写像#

Q5で扱った集合 $S_{p r e f}$ と $S_{c i t y}$ を再び用いる．

写像 $f$ は集合 $S_{p r e f} \times S_{c i t y}$ から集合 $R$ の写像であり， $p \in S_{p r e f}$ ， $c \in S_{c i t y}$ に対して，

\begin{array}{r} f (p, c) = {\begin{cases} 1 都 市 c が 都 道 府 県 p の 県 庁 所 在 地 の 場 合 \\ 0 そ れ 以 外 \end{cases} \end{array}

と定義する．

写像 $f$ の定義域，値域，像を列挙せよ．
$S = {(x, y) | (x, y) \in S_{p r e f} \times S_{c i t y}, f (x, y) = 1}$ となる集合 $S$ の要素を求めよ．