目次

1. 集合

2. 写像

3. 関係

4. ブール代数

総目次に戻る

1. 集合

1.1 集合とは何か

【カントールによる集合の「定義」】

Unter einer ``Menge'' verstehen wir jede Zuzammenfassung M von bestimmten wohlunterschiedenen Objekten m unsrer Anschauung oder unseres Denkens (whelche die ``Elemente'' von M genannt werden) zu einem Genzen)

『集合』とはわれわれの直観または思考の対象であって 確定したよく区別しうるものたち m を全体にまとめたもの M の ことであるとする（ここで m は M の『要素』と呼ばれる）．

記号：m∈M

意味：m は集合 M の要素である

【例】すべての集合を集めたもの（仮に U と書くことにする）は集合 だろうか？ U が集合であるとすれば，U 自身も U の要素でなければ ならないから U∈U ということになる．しかし自分自身を要素として 含む集合というのはなんだか怪しい集合だ．ことによると U 自体は集合ではないかも知れない．それならば U∈U という状況は 避けられる．上の「定義」ではどちらが正しいか判断ができない．

この例をすこしひねると，ラッセルのパラドックス（逆理） と呼ばれる例ができる：

【ラッセルのパラドックス】 自分自身を要素としない（つまり X ∈ X とならない）集合 X を すべて集めたもの（仮に V と呼ぶことにする）は集合ではあり得ない．

【証明】V が集合であるとする．このとき V ∈ V であるかそうで ないかのどちらかである（集合でなければそもそもこれは意味がない）． V ∈ V であれば V は自分自身を要素とする集合なので，V の定義によって V ∈ V ではない．他方 V ∈ V でなければ，V は 自分自身を要素としない 集合だから，やはり V の定義によって，V ∈ V となる．いずれにせよ矛盾 している．結局 V が集合であるという仮定がおかしい．

ここでは集合とは何かという問題にはこれ以上立ち入らないで素朴に 考えて行くことにする．

1.2 集合のあらわし方

【列挙型の記述】

要素を列挙して集合をあらわす．たとえば {a₁, a₂,...,a_n} は n 個の要素 a₁, a₂,...,a_n からなる集合である．要素が無数に続くときも同様で，たとえば N = {0,1,2,3,...} は自然数全体の集合である．

【内包的な記述】

要素を特徴づける性質で集合を規定する．たとえば

{ x ∈N | x は 2,3,5 のいずれでも割り切れない}

というように縦線 | の右側に条件（これは実は「述語」である） を書く．

要素を一つももたない集合を空集合という． 空集合はφという記号であらわされる．

ちなみに，Zは整数の集合，Qは有理数の集合， Rは実数の集合，Cは実数の集合をあらわすのに 一般的に用いられる記号である．

1.3 包含関係

【定義】二つの集合 X, Y において，X のすべての要素が Y の要素でもあるとき，X は Y の部分集合であるといい， この関係（包含関係）を記号で X ⊆ Y とあらわす（X ⊂ Y と書くこともある）：

記号：X ⊆ Y

意味：X は Y の部分集合である

特に，空集合はすべての集合の部分集合である．

1.4 集合算

集合から新しい集合をつくる操作をいくつか説明する．

1.4.1 合併集合（union）あるいは結び（join）

二つの集合 X, Y の要素を全部合わせてできる集合を X, Y の合併集合（あるいは結び）と呼び， X ∪ Y であらわす．

1.4.2 共通集合（intersection）あるいは交わり（meet）

二つの集合 X, Y の両方に共通する要素だけを集めてできる 集合を X, Y の共通集合（あるいは交わり） と呼び，X ∩ Y であらわす．

1.4.3 差集合（difference）

二つの集合 X, Y に対して，X の要素であって Y の要素でない ものを集めてできる集合を X と Y の差集合と呼び， X - Y であらわす．X - Y と Y - X とは一般には異なる ことに注意．

1.4.4 これらに関する一般的等式

• べき等律： X ∪ X = X, X ∩ X = X
• 可換律： X ∪ Y = Y ∪ X, X ∩ Y = Y ∩ X
• 結合律： (X ∪ Y) ∪ Z = X ∪ (Y ∪ Z), (X ∩ Y) ∩ Z = X ∩ (Y ∩ Z)
• 分配律： (X ∪ Y) ∩ Z = (X ∩ Z)∪(Y ∩ Z), (X ∩ Y) ∪ Z = (X ∪ Z)∩(Y ∪ Z)
• 吸収律： X ∪ (X ∩ Y) = X ∩ (X ∪ Y) = X
• ド・モルガンの法則の集合版： X - (Y ∪ Z) = (X - Y)∩(X - Z), X - (Y ∩ Z) = (X - Y)∪(X - Z)

【演習問題】これらが成立することを確かめよ．

これらの等式はあとでブール代数の概念と関わっている．

1.4.5 べき集合（power）

集合 X の部分集合を全部集めた集合を X のべき集合 と呼び，2^X あるいは P(X) であらわす． べき集合の要素はそれ自体が集合であることに注意．

【例】X = {a,b,c} のとき，2^X は次のような ６個の要素からなる集合である：

2^X = {φ, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

【注意】

• 有限集合 X の要素の個数を |X| であらわすことに すると，一般に |2^X| = 2^|X| という 関係がある．

• A ∈ 2^X に対して X との差 X - A を X における A の 補集合という．

1.4.6 直積集合（direct product）

二つの集合 X, Y に対して，X の要素 x と Y の要素 y を 組にしたもの（順序対という）と (x,y) と書く． 二つの順序対 (x,y) と (x',y') は x = x かつ y = y' で あるときに互いに等しいとみなす．X, Y の要素から得られる すべての順序対を集めて得られる集合をX と Y の直積 と呼び，X × Y であらわす．

同様に，任意個の集合 X₁,...,X_n からも，各集合から要素をそれぞれ一つずつ (x_i ∈ X_i）選びだしてならべる ことによって順序組 (x₁,...,x_n) ができる．これらの順序対をすべて集めて得られる集合 を X₁, ..., X_n の直積と呼び， X₁ × ... × X_n であらわす．

---

2. 写像

2.1 定義と概念

【写像】二つの集合 X, Y を考える． X の各要素 x に対して Y の一つの要素 y = f(x) を 対応させるもの f を X から Y への写像という． f が X から Y への写像であることを記号で f:X -> Y と あらわす．X から Y への写像をすべて集めてできる集合を Map(X,Y, Y^X, などの記号で あらわす．

【グラフ】

直積集合 X × Y の部分集合

G = { (x, f(x)) | x ∈ X}

を写像 f のグラフという．写像のグラフは 「X の各要素 x に対して G ∩ ({x} × Y) が ただ一つの要素からなる集合になる」 という特徴をもつ．実際，G ∩ ({x} × Y) = {(x,f(x))} となる．そこで逆に，この性質を もつような X × Y の部分集合を基礎にして写像の 概念を定義し直すこともできる（集合論ではむしろ それが普通のやり方である）．

【例】 多項式，指数関数，sin(x)，cos(x) などの函数は 数直線 R から数直線への写像である． 要するに，写像とは函数の概念の拡張である．

【例】 X = {a₁,...,a_m}, Y = {b₁,...,b_n} という 集合（有限集合）を考える．写像 f:X -> Y を一つ与える ことは次の表の下の段の空欄を Y の要素で埋めることに 相当する：

x	a1	a2	...	am
f(x)			...

空欄の埋め方は n ×…× n = n^m = |Y|^|X| あるから，X から Y への写像の 個数について

|Y^X| = |Y|^|X|

という等式が成り立つ．X から Y への写像全体の集合を Y^X という記号で表わすのは一つにはこのため である．

【例】集合 X から２個の要素からなる集合 {0,1} への 写像をすべて集めてできる集合 {0,1}^Xと X のべき集合 2^X = {A | A ⊆ X} の間には 次のように１対１対応がある：X の各部分集合 A に対して A の特性函数 χ_A: X → {0,1} を

χ_A(x) = 1 (x ∈ A)
χ_A(x) = 0 (それ以外)

で定義する．A に対して χ_A を対応させることで 写像

{0,1}^X → 2^X

ができる．これが１対１の対応（後で導入する言葉で言えば 全単射）を定める．実際，この対応を逆にたどるには 任意の写像 f: X → {0,1} に対して X の部分集合を A = {x ∈ X | f(x) = 1} と定めればよい．以上の意味で， べき集合の記号 2^X の ``2'' とは実は {0,1} の ことだったのである．

2.2 像・原像

【像】写像 f:X -> Y と X の部分集合 A に対して

f(A) = {f(x) | x ∈ A}

を f による A の像と呼ぶ．

【原像】同様に Y の部分集合 B に対して

f^-1(B) = { x ∈ X | f(x) ∈ B}

を f による B の原像と呼ぶ．

2.3 単射・全射・全単射

一般の写像 f:X -> Y を考える．

【単射】f(x) = f(x') ならばかならず x = x' と なるとき，f は単射であるという．これは y ∈ Y の 原像 f^-1(y) が高々１個の要素しかもたない 場合である．

【全射】どの y ∈ Y に対してもかならず f(x) = y という x ∈ X が存在するとき，f は全射 であるという．これは f(X) = Y ということと同じである．

【全単射】f が全射かつ単射であるとき，f は 全単射である，という．これは X の全要素と Y の全要素の間に x <-> f(x) によって１対１の対応が できている状況である．全単射 f:X -> Y に対しては 逆写像 f^-1:Y -> X を

f(x) = y 　<==>　 f^-1(y) = x

というように定めることができる．

2.4 写像の合成

【定義】二つの写像 f:X -> Y, g:Y -> Z に対して 合成写像 g。f:X -> Z を

g。f(x) = g(f(x))

で定義する．これは合成函数の概念の拡張である．

【結合律】三つの写像 f:X -> Y, g:Y -> Z, h:Z -> W の合成について

h。(g。f) = (h。g)。f （結合律）

が成り立つ．

【恒等写像】集合 X の各要素 x に対して 同じ要素 x を対応させる写像 id_X:X -> X を恒等写像という．任意の写像 f:X -> Y に対して

f。id_X = id_Y。f = f

となる．

---

3. 関係

集合の要素の間の関係を記号的に表現することもしばしば 行われる．たとえば a = b, a ≦ b, A ⊆ B はそのような 関係の典型例である．このようなものを一般的に考えてみる．

3.1 一般の n 項関係

【定義】集合 X に対して Xⁿ の部分集合 R （あるいは同じことだが，その特性函数 χ_R: Xⁿ → {0,1}）を X 上の n 項関係 という．対応する特性函数を X 上の n 項述語 という（1, 0 をそれぞれ真，偽とみなしている）． 特に n = 2 （２項関係）の場合，X の要素の組 (a,b) が R に属することを a R b と表わす．

同様にして，一般には異なる n 個の集合 X₁, ..., X_n の直積の上で 関係や述語を考えることもできる．

【注意】普通の感覚ではむしろ n 項述語を関係と呼ぶ ほうがわかりやすいだろう．その意味で χ_R の代わりに単に R と書くことも多い．これに対して， 集合としての R はその関係が成立している n 個の要素の組 (x₁, ..., x_n) を全部集めたものに 他ならない．集合論の立場では写像よりも集合のほうが より基本的なので，上のような言い方になる．

【例】

1. 任意の集合 X に対して要素の間の等号 a = b は X 上の ２項関係である．

2. 正の整数 n を一つ選び，a ≡ b mod n （a と b は n を法として合同）という関係を考えると，これは 整数全体の集合 Z の上の２項関係である．

3. 写像 f:X → Y が与えられたとする．X の要素 a, b に対して f(a) = f(b) となるとき a ≡ b と書くことに すると，≡ は X 上の２項関係である．

4. 大小関係 a ≦ b は実数の集合 R の上の ２項関係である．

5. 集合の包含関係 A ⊆ B は X のべき集合 2^X 上の２項関係である．

6. 写像 f: X → Y に対して R = {(x,y) ∈ X × Y | f(x) = y} と定義すると，これは Xの要素と Y の要素の 間の２項関係を与える．この場合，R は実は f のグラフ に他ならない，ということに注意．この意味で， ２項関係は写像（あるいはそのグラフ）の概念の拡張である， と考えることもできる．

7. 直積集合から別の集合への写像 f: X₁ × …× X_n-1 → X_n から同様にして n 項関係を定めることができる．この場合の R も写像の グラフである．

最初の三つの例は同値関係という概念に，また その次の二つの例は順序という概念に，それぞれ 一般化される．

3.2 同値関係

【定義】一般に，集合 X 上の２項関係 R が次の三つの 条件を満たすとき X 上の同値関係 であるという：

1. 反射律：任意の a ∈ X に対して a R a
2. 対称律：任意の a, b ∈ X に対して， a R b と b R a は同値
3. 推移律：任意の a, b ∈ X に対して， a R b かつ b R c ならば a R c となる

【演習問題】上の例の1,2,3が同値関係であることを 確かめよ．

3.3 順序

【定義】一般に，集合 X 上の２項関係 R が次の三つの 条件を満たすとき X 上の順序（あるいは 半順序）であるという：

1. 反射律：上に同じ
2. 反対称律：任意の a, b ∈ X に対して， a R b かつ b R a ならば a = b
3. 推移律：上に同じ

【演習問題】上の例の4, 5が順序であることを確かめよ．

---

4. ブール代数

ブール代数はブール束とも呼ばれる．これは 同じものに対する二通りの見方である．「代数」 は通常の数の四則や集合の集合算のように「演算」に 注目する考え方である．「束」は順序に基づく 考え方である．ここでは束としての見方には立ち入らないで， 主に演算の側面に焦点を絞る．

4.1 演算とは何か

ブール代数の定義を述べる前に，「演算」という ものの一般的な捉え方について触れておきたい．

【定義】一般に， 集合 X 上の n 項演算とは Xⁿ から X への写像のことである．（なお，行列とベクトルの積のように， 異なる集合の間の演算も考えられるが，これは X × Y -> Y などのように一般化して考えればよい．）

【例】整数の集合 Z 上の加法・減法・乗法は この意味での２項演算である．また符号の反転は１項演算 である：

演算	種類	写像
加法	２項	(x,y) -> x+y
減法	２項	(x,y) -> x-y
乗法	２項	(x,y) -> xy
反転	１項	x -> -x

4.2 ブール代数の定義

【定義】集合 L に二種類の２項演算 ∧:L × L -> L, ∨:L × L -> L が定義され，次の各条件が満たされて いるとき，L はブール代数であるという：

1. べき等律： x ∧ x = x, x ∨ x = x
2. 可換律： x ∧ y = y ∧ x, x ∨ y = y ∨ x
3. 結合律： (x ∧ y) ∧ z = x ∧ (y ∧ z), (x ∨ y) ∨ z = x ∨ (y ∨ z)
4. 吸収律： x ∨ (x ∧ y) = x ∧ (x ∨ y) = x
5. 分配律： (x ∨ y) ∧ z = (x ∧ z) ∨ (y ∧ z), (x ∧ y) ∨ z = (x ∨ z) ∧ (y ∨ z)
6. L には特別な要素 ⊥,Ｔが存在し，L のすべての 要素 x に対して x ∨ Ｔ = Ｔ, x ∧ ⊥ = ⊥ となる． さらに L のすべての要素 x に対して補要素と呼ばれる 要素 x ' が存在して x ∨ x ' = Ｔ, x ∧ x ' = ⊥ となる．

【注意】演算∧，∨を論理式における論理演算の∧，∨ と混同してはならない（関係はある --- 次章参照）．

4.3 ブール代数の例

べき集合 2^x は

• A ∨ B = A ∪ B
• A ∧ B = A ∩ B
• ⊥ = φ, Ｔ = X
• A ' = X - A

と解釈すればブール代数になる．

【演習問題】このことを確かめよ．

結局，集合算とはブール代数の一種だったわけである． 実は，有限集合でブール代数の構造をもつものは 実質的にはこのようなべき集合に限られることが 知られている．

---

キーワード

集合，要素（元），ラッセルのパラドックス，空集合，包含関係， 部分集合，合併集合（結び），共通集合（交わり）， 差集合，可換律，結合律，分配律，吸収律，ド・モルガンの法則， べき集合，補集合，順序対（組），直積，写像，写像のグラフ， 像，原像，単射，全射，全単射，合成，恒等写像，n 項関係， n 項述語，同値関係，順序，演算，ブール代数，ブール束

---