1 集合， ε-記号，集合の記法，集合算

‘オブジェクト’ の集まりを，（新しい）一つのオブジェクトと見なすとき，これを集合 (set) という．ここでは出発点となる基本的なオブジェクトは，

数: 0, 1, 2,… 数字: ‘0’, ‘1’, ‘2’, … その他の文字: a, b, c,…, ‘x’, ‘y’, ‘z’ などからなるとする．

x, y, z,… を要素に持つ集合を {x, y, z,…} と書く．たとえば，数 1, 2, 3 を要素として持つ集合を {1, 2, 3} であらわす．集合を要素とする集合も考える．例えば， {{1, 2}, 3} は，集合 {1, 2} と数 3 とを要素として持つ集合である．上で基本的なオブジェクトとしてとった， 0, 1, 2,…, ‘0’, ‘1’, ‘2’,…, ‘a’, ‘b’, ‘c’, は集合ではない．これらは原始元 (atoms) とよばれる．

y が集合 x の要素であることを y ∈ x であらわす． y は x の^{げん}元であるともいう．そうでないときは y ∉ x と書く．

例 1.1 1 ∈ {1, 2, 3}, ‘1’ ∉ {1, 2, 3}, {3, 4} ∈ {1, 2, {3, 4}}, 3 ∉ {1, 2, {3, 4}}.

集合はその要素が何であるか，という性質のみに注目して考える．特に，すべての a に対し a ∈ b ⇔ a ∈ b′ なら， b と b′ は等しいとする．したがって， ‘{’, ‘}’ による集合の記法で，要素をならべかえたり，重複して書いても，あらわす集合は同じである．

例 1.2 {1, 2, 3} = {2, 1, 3} = {1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3}.

例 1.3 {1} ≠ {{1}} である: {1} は 1 を唯一の要素とする集合で， {{1}} は {1} を唯一の要素とする集合である．我々の立場では 1 は最初にとったオブジェクトで集合ではなく， {1} は 1 を唯一の要素とする集合だから， 1 ≠ {1} となり，したがって， {1} ≠ {{1}} となることがいえる．

上の例でも述べたように，我々は，最初に仮定したオブジェクト 0, 1, 2, 3,…, ‘0’, ‘1’, ‘2’ ‘3’,…, ‘a’, ‘b’, ‘c’,… は集合ではないが，公理的集合論では，「すべての (数学的) オブジェクトは集合である」（つまり原始元は存在しない）という立場で議論をおこなう．この立場が十分に一般性を持つものであることの説明はすぐ後で与える．

何も要素として含まない，^{から}空の集合も考える．これを^{くう}空集合とよぶ．集合は要素のみから規定されるのだったから，空集合は，何も要素として含まないという性質で一意に決まることになる．この集合を ∅ であらわす．空集合は何も要素として含まないから，特に ∅ ∉ ∅ であることがわかる．

先にふれた，「すべてのオブジェクトは集合である」という（公理的）集合論の立場で，自然数を扱うスタンダードな方法として， 0, 1, 2, 3,… を，それぞれ集合 ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}},… として導入する．この立場では各々の自然数も集合で， 0 ∈ 1 ∈ 2 ∈ 3 ∈ 4 ⋯ となる．このようにして導入された数 n は “n 個の要素を持つ集合の代表” としてとらえることができる．無限個の要素を持つ集合（無限集合）も考察することができる．たとえば，

IN = {n | n は自然数},
D = {‘0’, ‘1’, ‘2’, ‘3’,…}

などとして，無限集合を導入する．無限集合を研究する分野は，無限組合せ論とよばれる集合論の一分野である．これに対し，主に有限集合の性質を調べる分野は有限組合せ論，あるいは単に組合せ論と呼ばれている．時々テレビに出てくる， Peter Frankl 氏は実は組合せ論の研究者でもある． a, b を集合として， a のどの要素をとっても，これが b の要素ともなっているとき， a は b に含まれる, または， a は b の部分集合であるといい，これを a ⊆ b とあらわす． a が b の部分集合でないときには，これを a ⊈ b であらわす．これは，「a の要素で b の要素でないものが存在する」ということである．次は定義から容易に示せる:

命題 1.4 (a) すべての集合 a に対し次が成り立つ: a ⊆ a, ∅ ⊆ a.

(b) a が空集合でないことと， ∅ ⊈ a とは同値である．

例 1.5 {1, 2, 3} ⊆ {1, 2, 3, 4, } ⊆ IN; {1, 2, 3, ‘4’} ⊈ IN.

a, b が集合であるとき， a ∪ b, a ∩ b, a \ b を

\begin{matrix}a ∪ b = & \{c | c ∈ a または c ∈ b\}, \\ a ∩ b = & \{c | c ∈ a かつ c ∈ b\}, \\ a \ b = & \{c | c ∈ a かつ c ∉ b\} \end{matrix}

により定義する．

命題 1.6 X, Y ⊆ Z とするとき:

(i) X ∪ Y = Z \ ((Z \ X) ∩ (Z \ Y)); (ii) X ∩ Y = Z \ ((Z \ X) ∪ (Z \ Y)). (iii) X ⊆ Y ⇔ Z \ Y ⊆ Z \ X.

証明 (i) について示す． (ii) は同様に示せる．任意の z に対し， z ∈ X ∪ Y ⇔ z ∈ Z \ ((Z \ X) ∩ (Z \ Y)) となることが示せればよいが，これは

\begin{matrix}z ∈ X ∪ Y ⇔ & z ∈ X または z ∈ Y \\ ⇔ & z ∈ Z かつ z ∉ (Z \ X) またはz ∉ (Z \ Y) \\ ⇔ & z ∈ Z かつ (z ∈ (Z \ X) かつ z ∈ (Z \ Y)) でない \\ ⇔ & z ∈ Z \ ((Z \ X) ∩ (Z \ Y)) \end{matrix}

によりよい． ⊣ X ∩ Y = ∅ のとき，つまり， X と Y が共通の要素を持たないとき， X と Y は互いに素であるという．

2 集合の濃度，巾集合

X を有限集合とするとき， #(X) で X の要素の数をあらわす． #(X) は集合 X の濃度とも呼ばれる．例 2.1 #(∅) = 0; #({∅}) = 1; #({0, 1, 2, 3 |)} = 4. 次は明らかであろう: 命題 2.2 X, Y を有限集合とするとき:

(i) #(X ∪ Y) = #(X) + #(Y) − #(X ∩ Y). 特に， X と Y が互いに素なら #(X ∪ Y) = #(X) + #(Y) となる; (ii) X ⊆ Y なら， #(Y \ X) = #(Y) − #(X). X が集合のとき， X の^{べき}巾集合を

P(X) = {Y | Y ⊆ X}

と定義する． ∅ ⊆ X で X ⊆ X だから， ∅, X ∈ P(X) は常に成り立つ．例 2.3 (i) P(∅) = {∅}; (ii) P({0, 1}) = {∅, {0}, {1}, {0, 1}}; 演習問題 2.4 P({0, 1, 2}) は何になるか？ P(X) は X よりずっと大きな集合になる: 定理 2.5 X を有限集合とするとき， #(P(X)) = 2^{#(X)} が成り立つ．証明ここでは #(X) に関する帰納法による厳密な証明を与える． #(X) = 0 のとき，つまり X = ∅ のときには， P(X) = {∅} だから， #(P(X)) = 1 = 2^{0}. となり上の等式が成り立っていることがわかる． #(X) = k となるすべての X に対し上の等式が成り立っているとして， #(X) = k + 1 となるような X に対しても上の等式が成り立つことを示す． #(X) = k + 1 とすると X は空集合ではないから， x_{0} ∈ X を一つとり， X′ = X \ {x_{0}} とする．このとき，

Z = {Y ∪ {x_{0}} | Y ∈ P(X′)}

とすれば， P(X′) と Z の元の間に自然な一対一対応がとれるから， 2^{k} = #(P(X′)) = #(Z) となっている．明らかに P(X) = P(X′) ∪ Z だが， P(X′) と Z は互いに素だから，命題 2.2(i) の後半により，

\begin{matrix}#(P(X)) = & #(P(X′)) + #(Z) \\ = & 2^{k} + 2^{k} \\ = & 2^{k+1} \\ = & 2^{#(X)} \end{matrix}

となる．これが示したいことであった． ⊣

3 順序対，直積集合

{a, b} は要素のみに注目していたので {a, b} = {b, a} となるのだったが， a と b の順序を考慮に入れた組 (a, b) も考察の対象として扱えると具合がよい．そこで，ここでは，このような組をコードするような集合を次のようにして導入する:

(a, b) = {{a}, {a, b}}

として，これを a と b の順序^{つい}対と呼ぶ．次の定理は，上の定義が我々の目的にかなったものとなっていることを示している．

定理 3.1 (a, b) = (c, d) なら， a = c かつ b = d が成り立つ．

証明 a ≠ b のときと a = b のときに分けて考える． a ≠ b のときには， #((a, b)) = 2 だから， #((c, d)) = 2 となる．このことから c ≠ d がわかり， {a} = {c} かつ， {a, b} = {c, d} が分る．一番目の等式から， a = c が導け，これと二番目の等式から， b = d となる．

a = b のときには， (a, b) = {{a}} となるから， (a, b) = (c, d) により， {c} = {c, d} = {a} がわかる．したがって， c = d = a である． ⊣

a_{1},…,a_{n} に対し， (a_{1},…, a_{n}) を， (a_{1}, (a_{2},…, (a_{n−1}, a_{n})) ⋯) で定義する．このとき上の定理と同様に，

定理 3.2 (a_{1},…, a_{n}) = (b_{1},…, b_{n}) なら， a_{1} = b_{1}, a_{2} = b_{2},,…,a_{n} = b_{n} が成り立つ．証明演習． ⊣

集合 X, Y に対し， X と Y の直積（デカルト積 (Cartesian product) ということもある）を

X × Y = {(x, y) | x ∈ X, y ∈ Y }

で定義する． (x, y) の定義により， X × Y ⊆ P(P(X ∪ Y)) となっていることがわかる（演習問題）． X × X のことを X^{2} とも書く．

命題 3.3 X, Y, Z を集合とするとき，

(i) X × (Y ∩ Z) = (X × Y) ∩ (X × Z); (X ∩ Y) × Z = (X × Z) ∩ (Y × Z). (ii) X × (Y ∪ Z) = (X × Y) ∪ (X × Z); (X ∪ Y) × Z = (X × Z) ∪ (Y × Z). (iii) Y と Z が互いに素なら， X × Y と X × Z も互いに素になる．同様に X と Y が互いに素なら X × Z と Y × Z も互いに素になる． ⊣

次の定理は，直観的には明らかであるが，厳密な証明は，たとえば #(Y) に関する帰納法を用いて，定理 2.5と同様にして与えることができる:

定理 3.4 X と Y を有限集合とするとき， #(X × Y) = #(X) × #(Y) となる． ⊣

上の等式で，左辺の ‘×’ は直積集合の演算で，右辺の ‘×’ は数のかけ算である．順序対を使って， n ≥ 2 に対し n-組 (a_{0},…, a_{n−1}) を，

(a_{0},…, a_{n−1}) = (a_{0}, (a_{1},… (a_{n−2}, a_{n−1})) ⋯)

で定義すると，

命題 3.5 (a_{0},…, a_{n−1}) = (b_{0},…, b_{n−1}) なら， a_{0} = b_{0} かつ， a_{1} = b_{1} かつ， … かつ， a_{n−1} = b_{n−1} となる．

証明 n に関する帰納法による． n = 2 のときには，定理 3.1 によりよい．すべての k-組に対し，命題が成り立つと仮定して， k +1-組に対しても命題が成り立つことを示す． (a_{0},…, a_{k}) = (b_{0},…, b_{k}) とする．このとき， (a_{0},…, a_{k}) = (a_{0}, (a_{1},…, a_{k})), (b_{0},…, b_{k}) = (b_{0}, (b_{1},…, b_{k})) だから，ふたたび定理 3.1により， a_{0} = b_{0} かつ (a_{1},…, a_{k})) = (b_{1},…, b_{k})) となることがわかる．したがって帰納法の仮定から， a_{0} = b_{0} かつ， a_{1} = b_{1} かつ， … かつ， a_{n−1} = b_{n−1} がわかる． ⊣

n-組を使って， n-個の集合 X_{0},…,X_{n−1} に対し，

X_{0} × ⋯ × X_{n−1} = {(x_{0},…, x_{n−1}) | x_{0} ∈ X_{0},…, x_{n−1} ∈ X_{n−1}}

とする．このとき，

命題 3.6 X_{0},…,X_{n−1} をそれぞれ有限集合とするとき， #(X_{0} × ⋯ × X_{n−1}) = #(X_{0}) × ⋯ × #(X_{n−1}) となる．

証明演習． ⊣

4 ２項関係

二つの自然数 x, y に対して “x は y より大きい”, “x は y を割りきる” などという “関係” を考えることができる．これらの関係は，それぞれ

\begin{matrix}\{(x, y) ∈ IN^{2} | x < y\}, \\ \{(x, y) ∈ IN^{2} | x は y を割りきる\} \end{matrix}

という集合で “コード” されていると考えることで，ふたたび集合として扱うことができるようになる．一般には， X と Y を集合とするとき， X × Y の部分集合を（X と Y の要素間の）関係という． R ⊆ X × Y を関係として見るときには， (x, y) ∈ R を x R y とも書くことにする．同様に (x, y) ∉ R は x R̸ y とも書く． X = Y で R ⊆ X^{2} のときには， R は X 上の２項関係であるという． X と Y がともに有限集合の場合には， X と Y の元の関係の全体は， P(X × Y) であるから，このような関係の個数は， #(P(X × Y)) = 2^{#(X×Y)} = 2^{#(X)×#(Y)} となる．

例 4.1 IN 上の２項関係 R を

R = {(x, y) ∈ IN^{2} | x は y の因数}

で定義すると， R は次の二つの性質を満たす:

(i) x R y かつ y R y なら， x R z (ii) x R y かつ y R x なら， x = y.

上の (i), (ii) の性質は，それぞれ，推移律，反対称律とよばれる．つまり，上の例の R は，推移律と反対称律を満たす． R は推移的かつ反対称的であるとも言う． X 上の２項関係が推移的かつ反対称的であるとき， “R は xRy を y は x より大きいか等しい” と解釈することで， X 上のある種の大小関係を規定していると考えられる．そこで，このような R を X 上の半順序と呼ぶ．ここで半̇順序と言ったのは， x, y ∈ X をとったときに， x と y が必ずしも比較可能でない，つまり x R y も y R x も成り立たない可能性もある，ということを強調している． X 上の半順序 R で， X の任意の任意の二つの元が比較可能となっているとき，つまり，任意の x, y ∈ X に対し x R y か y R x のどちらかが成り立つとき， R は全順序，または線型順序であるという． IN 上の普通の大小関係 ≤ はそのようなものの例である:

例 4.2 IN 上の２項関係 R を

R = {(x, y) ∈ IN^{2} | x ≤ y}

で定義すると， R は例 4.1の (i), (ii) および (iii) すべての x, y (∈ IN) に対し， x R y か y R x の少なくとも片方は成り立つ．を満たす．つまり R は X 上の全順序となっている．える X が有限集合のとき， X 上の全順序は全部で #(X)! 個ある（演習）． X 上の半順序の個数はいくつか？（演習: ちょっと難しい）．

X 上の２項関係 R が，

(i) すべての x ∈ X に対し x R x （反射律） (ii) すべての x, y ∈ X に対し， x R y なら y R x （対称律） (iii) すべての x, y ∈ X に対し， x R y, y R z なら x R z （推移律）

を満たすとき， R は X 上の同値関係であるという．

例 4.3 X を集合とするとき,

(i) R = {(x, x) | x ∈ X} は同値関係になる， x R y ⇔ x = y である．

(ii) R = X × X は同値関係である．すべての x, y ∈ X に対し， x R y が成立する．

(iii) X = IN として， n ∈ IN とする． x R_{n} y ⇔ |x − y| は n で割りきれる，により R_{n} を定義すると， R_{n} は同値関係となる． x R_{n} y は x を n で割ったときの余りと y を n で割ったときの余りが等しいという関係になっている．

R を X 上の同値関係として， x ∈ X に対し， x の R に関する同値類 E_{R}(x) を

E_{R}(x) = {y ∈ X | x R y}

と定義する．

補題 4.4 R を集合 X 上の同値関係とするとき，任意の x, y ∈ X に対し， E_{R}(x) = E_{R}(y) または， E_{R}(x) ∩ E_{R}(y) = ∅ のどちらかが成り立つ．

証明 E_{R}(x) ∩ E_{R}(y) ≠ ∅ として， E_{R}(x) = E_{R}(y) となることを示す．このために E_{R}(x) ⊆ E_{R}(y) と E_{R}(x) ⊇ E_{R}(y) を示す．まず z ∈ E_{R}(x) とする．仮定により， z_{0} ∈ E_{R}(x) ∩ E_{R}(y) が存在する． x R z だから，対称律により z R x である．一方 x R z_{0} となっている．したがって，推移律により， z R z_{0} である．また， y R z_{0} だから， z_{0} R y が対称律によりわかる．したがって推移律から， z R y となる．ふたたび対称律により， y R z となり z ∈ E_{R}(y) がわかる．以上により， E_{R}(x) ⊆ E_{R}(y) が示せたが， E_{R}(x) ⊇ E_{R}(y) も同様に示せる． ⊣

上の証明では実は反射律は用いられていないことに注意する．集合の族 P = {X_{1}, X_{2},…} は，互いに素で（つまり i ≠ j のときには X_{i} ∩ X_{j} = ∅ で） ⋃ P = X_{1} ∪ X_{2} ∪ ⋯ として X = ⋃ P となるとき， X の分割であるという．

補題 4.5 R が X 上の同値関係のとき， P_{R} = {E_{R}(x) | x ∈ X} は X の分割となる．証明補題 4.4 により， P は互いに素である． R が反射律を満たすことから，すべての x ∈ X に対し x ∈ E_{R}(x) となるが，このことから ⋃ P = X がわかる． ⊣

X の分割 P が与えられたとき， X 上の２項関係 E_{P} を

x E_{P} y ⇔ ある Y ∈ P に対し x, y ∈ Y となる

で定義すると， E_{P} は同値関係となる．さらに

補題 4.6 (a) R を X 上の同値関係とするとき， R = E_{P_{R}} が成り立つ．

(b) P を X の分割とするとき， P = P_{E_{P}} が成り立つ．

証明演習． ⊣

上の補題により， X 上の同値関係 R とこれに対応する X の分割 P_{R} は同一の實體の異なる表現となっていることがわかる．

5 木

情報科学で非常に重要な役割をはたす半順序構造に木とよばれるものがある． (T, ≺) が木とは， ≺ は集合 T 上の半順序で， ≺ に関する T の最大元が存在し，任意の t ∈ T に対し， {s ∈ T | t ≺ s} は有限で ≺ はこの集合上で線型順序となっているようなものである． (T, ≺) が木のとき， T の ≺ に関する最大元を T の根とよび，各 t ∈ T を T のノードとよぶ． T の極小元は T 葉とよばれ， T の部分集合 B で ≺ が B の線型順序となっているようなものは T の枝とよばれる． T の枝 B でどんな B _{/} ⊆ B′ ⊆ T も枝にならないようなものを， T の極大枝とよぶ． s ∈ T が t ∈ T のすぐ次の元であるとは， s ≺ t かつ s ≠ t で，すべての s′ ∈ T に対し， s ≺ s′ ≺ t なら s = s′ かまたは s′ = t が成り立つこと． n ∈ IN に対し，木 (T, ≺) で，すべての t ∈ T が高々 n 個のすぐ次の元しか持たないとき， (T, ≺) は n-ary 木であるという．特に n = 2 のときには (T, ≺) は binary 木であるという．木 (T, ≺) はすべての t ∈ T に対し t のすぐ次の元は有限個しか存在しないとき，有限分岐であるという．

定理 5.1 （König の補題） (T, ≺) が有限分割の木で， T は無限のとき， (T, ≺) の枝で無限なものが存在する．

証明 T の元の列 t_{n}, n ∈ IN を帰納的に ⋯ ≺ t_{2} ≺ t_{1} ≺ t_{0} となるように以下のようにして定義する．このとき B = {t_{n} | n ∈ IN} は (T, ≺) の無限の枝となる．

t_{0} は T の ≺ に関する最大元とする．仮定により， t_{0} のすぐ次の元は有限個しか存在しない．これらをたとえば s_{1},…, s_{k} とすれば， T \ {t_{0}} = {s ∈ T | s ≺ s_{1}} ∪ ⋯ ∪ {s ∈ T | s ≺ s_{k}} となる．仮定により， T \ {t_{0}} は無限だから，少なくとも一つの 1 ≤ i ≤ k に対し， {s ∈ T | s ≺ s_{i}} は無限となる．このような i に対し， t_{1} = s_{i} とおく．

t_{0},…, t_{n} が， {s ∈ T | s ≺ t_{n}} が無限になるようにとれたときには，上と同じ論法から， t_{n} のすぐ次の元 t ∈ T で {s ∈ T | s ≺ t} が無限になるようなものがとれるから，このような t を t_{n+1} とすればよい． ⊣

演習問題 5.2 上の定理で， “(T, ≺) は有限分岐である” という条件は落とせないことを示す例を挙げよ．

6 写像

X と Y を任意の集合とするとき， X の各々の元を Y の元に対応させる “規則” f を X から Y への写像（あるいは関数）とよぶ． f が X から Y への写像であるとき，これを f : X → Y と書く． f によって X の元 x の対応させられる Y の元を f(y) と書く．

関係と同じように，写像もまた X ×Y の部分集合によりコードされていると考えることができる．この立場から写像の概念を以下のように再定義できる: f ⊆ X × Y が X から Y への写像（あるいは関数）であるとは，各 x ∈ X に対し， (x, y) ∈ f となる y ∈ Y がちょうど一つ存在することとする． f がこの意味で X から Y への写像であるとき， f : X → Y と書き， x ∈ X に対し，一意に決まる (x, y) ∈ f となるような y を f(x) とあらわす．

f がこの節の最初のパラグラフでの意味で X から Y への写像であるとき，

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

がこれに対応する二番目のパラグラフでの集合としての写像となる．最初のパラグラフでの写像の定義が “規則” という曖昧な表現を含んでいたのに対し，二番目のパラグラフでの定義は，集合の言葉を用いた曖昧さのないものになっていることに注意したい．

f : X → Y のとき， X を f の定義域とよび Y を f の値域とよぶ． Y の各元 y に対し， X の元で f(x) = y となるようなものが存在するとき， f は Y の上への写像である，あるいは f は全射であるという． X の任意の異なる二元 x, x′ に対し， f(x) と f(x′) も常に異なるとき， f は一対一写像または単射であるという． f が単射かつ全射のときには, f は全単射であるという． X と Y が有限集合のときには，単射 f : X → Y が存在すれば， #(X) ≤ #(Y) となり，全射 f : X → Y が存在すれば #(X) ≥ #(Y) となる．したがって，全単射 f : X → Y が存在するときには， #(X) = #(Y) が成り立つ． X と Y が無限集合の場合でも X から Y への全単射が存在するときには， X と Y は等しい無限の大きさを持つと考えることができる．

以下の定理は無限集合の性質を研究する集合論の出発点となったものである．

定理 6.1 (G. Cantor) 任意の集合 X に対し， X から，その巾集合 P(X) の上への写像は存在しない．

証明 X から P(X) への全射 f が存在したと仮定して矛盾を導く． Y = {x ∈ X | x ∉ f(x)} とする． f は全射だから， x_{0} ∈ X で f(x_{0}) = Y となるものがある．もし x_{0} ∈ f(x_{0}) = Y とすれば， Y の定義から x_{0} ∉ Y となり矛盾である．一方 x_{0} ∉ f(x_{0}) = Y とすれば， Y の定義から x_{0} ∈ Y となってしまい再び矛盾である．

⊣

上の定理から，特に IN から， P(IN) への全射は存在しないことがわかる．このことは “P(IN) の大きさは， IN の大きさに比べてずっと大きい” と解釈することができる．なお P(IN) と IR の間には全単射が存在することが分かっているから，このことは， IR が IN に比べて本質的にずっと大きな集合であることも示している．

f : X → Y, g : Y → Z のとき， f と g の合成 g ∘ f : X → Z を，

\begin{aligned}g ∘ f = \{(x, z) ∈ X × Z | & ある y ∈ Y に対し \\ & (x, y) ∈ f かつ (y, z) ∈ g\} \end{aligned}

で定義する．（演習: g∘f が写像となることを示せ） x ∈ X に対し， g∘f(x) = g(f(x)) である． X′ ⊆ X の f : X → Y による像は

f[X′] = {y ∈ Y | ある x ∈ X に対し f(x) = y となる}

により定義される．同様に Y′ ⊆ Y の f による逆像は

f^{−1}[Y] = {x ∈ X | ある y ∈ Y に対し f(x) = y となる}

である．集合 X に対し X 上の恒等写像 id_{X} : X → X を

id_{X} = {(x, x) | x ∈ X}

とする．すべての x ∈ X に対し id_{x}(x) = x となる． f : X → Y が全単射のとき， f の逆写像 f^{−} : Y → X は，

f^{−} = {(y, x) | (x, y) ∈ f}

と定義される．

演習問題 6.2 f : X → Y が全単射のとき， f^{−1} ∘ f = id_{X} で f ∘ f^{−} = id_{Y} である．具体的な写像を定義するときによく用いられる方法に，場合わけによる定義と帰納的定義がある．これを次の例で見ておく:

例 6.3 (1) 偶数 n に対し値 1 をとり奇数 n に対し値 0 をとるような関数 f : IN → IN を

f(n) = \{ \begin{matrix}1, & n が偶数のとき \\ 0 & n が奇数のとき \end{matrix}

として定義する．

(2) n に対しフィボナッチ数列の第 n 項を与えるような関数 g : IN → IN は:

\begin{matrix}f(0) = 1, f(1) = 1, \\ f(n) と f(n + 1) の値が既に定義されたときf(n + 2) = f(n + 1) + f(n) とする \end{matrix}

により定義することができる．

7 記号列

記号 s_{0},…,s_{n−1} の列 s_{0} ⋯ s_{n−1} を考察する．形式的には，記号列 s_{0} ⋯ s_{n−1} は， (s_{0},…, s_{n−1}) あるいは，関数 f : {0,…, n − 1} → {s_{0},…, s_{n−1}} で f(i) = s_{i}, (i = 0,…, n − 1) となるものとして導入することができる．記号列 s⃗ = s_{0} ⋯ s_{n−1} の長さを l(s⃗) であらわす．長さが 0 の記号列 ϵ も考える．これは，集合としては空集合と同一視できる．この例では l(s⃗) = n である．記号列 s⃗ = s_{0} ⋯ s_{n−1} と t⃗ = t_{0} ⋯ t_{m−1} に対し， s⃗ と t⃗ の連結を s⃗ ^{⌢} t⃗ = s_{0} ⋯ s_{n−1}t_{0} ⋯ t_{m−1} と定義する．明らかに l(s⃗ ^{⌢} t⃗) = l(s⃗) + l(t⃗) となる． s⃗, t⃗ をそれぞれ s_{0} ⋯ s_{n−1} と t_{0} ⋯ t_{m−1} の省略形と見るときには，単に s⃗t⃗ で s⃗ と t⃗ の連結をあらわすこともある．また s⃗ = s_{0} ⋯ s_{n−1} が記号列で t が記号であるときも， s⃗ ^{⌢} t あるいは s⃗f で s_{0} ⋯ s_{n−1}t をあらわすことにする．

t⃗ = t_{0} ⋯ t_{m−1} である n ≤ m に対し s⃗ = t_{0} ⋯ t_{n−1} となっているとき， s⃗ は t⃗ の始片であるといる．またこのときには， t⃗ は s⃗ を拡張する，という言い方もする．記号の集合 S が与えられたとき， s⃗ = s_{0} ⋯ s_{n−1} が S の記号列であるとは， s_{0},…,s_{n−1} ∈ S となること．記号の集合 S に対し， S^{∗} で {s⃗ | s⃗ は S の記号列} をあらわす． S^{∗} 上の関係 ⊑ を

s⃗ ⊑ t⃗ ⇔ t⃗ は s⃗ の始片

で定義すると， (S^{∗}, ⊑) は ε を根とする木となる．特に #(S) = n のときには， (S^{∗}, ⊑) は n-ary 木となる．

8 命題論理

Σ を記号の集合として， ‘¬’, ‘∧’, ‘∨’, ‘→’ ‘(’, ‘)’ を Σ に含まれない記号とする．このとき Σ 上の命題論理の論理式を次のようにして定義する:

(i) Σ の各元は Σ 上の命題論理の論理式； (ii) φ, ψ ∈ Σ^{∗} が Σ 上の命題論理の論理式のとき，記号列 ¬φ, (φ ∧ ψ), (φ ∨ ψ), φ → ψ もΣ 上の命題論理の論理式; (iii) Σ 上の命題論理の論理式は以上の操作をくりかえして得られるものに限る．

上のように命題論理の論理式を考えるときには Σ の元は命題記号呼ばれる．

例 8.1 p, q, r ∈ Σ とするとき， (p ∧ q) ((¬p ∧ q) ∨ q) は Σ 上の命題論理の論理式である． (p¬q) p ∧ ∧q などは Σ 上の論理式ではない．

論理式それ自身は記号の列にすぎないが，これの解釈を次のように帰納的に定義する．まず， Σ から集合 {0, 1} への写像を付値とよぶことにする． 1 と 0 はそれぞれ， ‘真’ と ‘偽’ という値をコードしているものと考えると，付値 σ : Σ → {0, 1} は Σ の命題記号に真偽値を割り当てているものとなっている．付値 σ が与えられたとき，これを Σ 上のすべての命題論理の論理式に以下のようにした拡張したものを考える．つまり，論理式 φ が与えられたときにその付値 σ における評価 V (σ, φ) ∈ {0, 1} を以下のように帰納的に定義する:

(i) p ∈ Σ に対しては V (σ, p) = σ(p) とする． (ii) (a): φ が ¬ψ の形をしているときには，

V (σ, φ) = 1 ⇔ V (σ, ψ) = 0

とする． (b): φ が (ψ ∧ η) の形をしているときには，

V (σ, φ) = 1 ⇔ V (σ, ψ) = 1 かつ V (σ, η) = 1

とする． (c): φ が (ψ ∨ η) の形をしているときには，

V (σ, φ) = 1 ⇔ V (σ, ψ) = 1 または V (σ, η) = 1

とする． (d): φ が (ψ → η) の形をしているときには，

V (σ, φ) = 1 ⇔ V (σ, ψ) = 0 または V (σ, η) = 1

とする．評価 V (σ, ·) の定義が， Σ 上の命題論理の論理式の定義の (i) と (ii) に対応していることに注意する． Σ 上の命題論理の論理式の定義の (iii) により，上の (i), (ii) によりすべての論理式 φ に対し，その評価 V (σ, φ) が定義されることがわかる．このようなタイプの議論を φ の構成に関する帰納法と呼ぶことにする．

上の (ii) は， “ψ と η に対し V (σ, ·) の値がすでに決定されたときには， ψ と η の組合せによって得られている（それらより複雑な）論理式 φ に対する V (σ, ·) の値が， V (σ, ψ) と V (σ, η) から計算される” という形のものとなっていることに注意する． V (σ, φ) の値は実は， φ に現れる命題変数に関する σ の振る舞いだけで決定される．このことを正確に定式化するために，まず，論理式 φ にあらわれる命題変数の全体の集合 var(φ) を帰納的に定義する:

(i) p ∈ Σ に対しては var(p) = {p} とする． (ii) (a): φ が ¬ψ の形のときには， var(φ) = var(ψ) とする; (b): φ が (ψ ∧ η), (ψ ∨ η) あるいは (ψ → η) の形のときには， var(φ) = var(ψ) ∪ var(η) とする．

定理 8.2 σ と σ′ を Σ の付値として， φ を Σ 上の命題論理の論理式とする． σ と σ′ が var(φ) 上で一致するときには， V (σ, φ) = V (σ′, φ) となる．

証明 φ の構成に関する帰納法で証明する． φ が Σ の元 p であるときには， var(φ) = {p} だから， V (σ, φ) = σ(p) = σ′(p) = V (σ′, φ) となるからよい．

φ が ψ ∧ η で， ψ と η に対し定理が成り立っているときには， var(·) の定義から， var(ψ), var(η) ⊆ var(φ) であることに注意すると， V (σ, φ) = 1 ⇔ V (σ, ψ) = 1 かつ V (σ, η) = 1 ⇔ V (σ′, ψ) = 1 かつ V (σ′, η) = 1 ⇔ V (σ′, φ) により， V (σ, φ) = V (σ′, φ) が示せる．

φ が ¬ψ, ψ ∨ η あるいは ψ → η の場合も同様に示せる． ⊣

φ と ψ を命題論理の論理式とするとき， φ と ψ が同値とは，すべての付値 σ : Σ → {0, 1} に対し， σ ⊧ φ ⇔ σ ⊧ ψ が成り立つこと．定理 8.2により， φ と ψ が同値であることを確かめるには， var(φ) ∪ var(ψ) への付値の組合せのすべてについて，そこでの φ と ψ の真偽値を調べればよい．

例 8.3 (a) ¬p ∨ q は p → q と同値である．

(b) p ∧ q は ¬(¬p ∨ ¬q) と同値である．

(b) p ∨ q は ¬(¬p ∧ ¬q) と同値である．

証明これは以下の真偽表によって確かめられる:

(a): \begin{matrix}p & q & ¬q & (¬p ∨ q) & p → q \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix}

(b),(c): 演習． ⊣

ある n ∈ IN に対し， f : {0, 1}^{n} → {0, 1} となっいるような写像 f を真偽値関数とよぶ．

定理 8.2により， var(φ) ⊆ {p_{0}, p_{1},…, p_{n−1}} となる命題論理の論理式 φ に対し，真偽値関数 f_{φ} : {0, 1}^{n} → {0, 1} を次のようにして定義することができることがわかる: 任意の (τ_{0},…, τ_{n−1}) ∈ {0, 1}^{n} に対し， σ(p_{0}) = τ_{0},…,σ(p_{n−1}) = τ_{n−1} となるようなある付値 σ に対し， f_{φ}((τ_{0},…, τ_{n−1})) = V (σ, φ) とする．

定理 8.4 任意の真偽値関数 f に対し，命題論理の論理式 φ で f = f_{φ} となるものが存在する．

証明 ⊣

例 8.3により，定理 8.4はさらに以下の形に改良できる:

定理 8.5 任意の真偽値関数 f に対し，命題変数以外では ¬ と ∨ のみの現れるような命題論理の論理式 φ で f = f_{φ} となるものが存在する． ⊣

9 ブール代数

二項演算 +, · と単項演算 − および，定数 0, 1 を持つ代数的構造 (B, +, ·, −, 0, 1) がブール代数であるとは， B の任意の元 a, b, c に対し，次の等式 (L1)–(L3),(D), (E), (N), (C) が成り立つこととする:

(L1) x + y = y + x, x · y = y · x (L2) x + (y + z) = x + (y + z), x · (y · z) = (x · y) · z (L3) x + (x · y) = x, x · (x + y) = x (D) x · (y + z) = (x · y) + (x · z), x + (y · z) = (x + y) · (x + z) (E) x · 1 = x (N) x + 0 = x (C) x · −x = 0, x + −x = 1

工学でブール代数と言ったときには，次のような２元ブール代数を指すことが多い:

例 9.1 ∨, ∧, ¬ をそれぞれ真偽値関数 f_{p_{0}∨p_{1}}, f_{p_{0}∧p_{1}}, および f_{¬p_{0}} として， 2 = ({0, 1}, ∨, ∧, ¬, 0, 1) とすれば， 2 はブール代数となる（演習）．

例 9.2 (Lindenbaum-Tarski 代数) Σ を空でない記号の集合として， Σ 上の命題論理の論理式の全体の集合を F ml(Σ) とあらわす． Σ 上の同値関係 ∼ を

φ ∼ ψ ⇔ φ と ψ は同値

として定義し，論理式 φ のこの同値関係に関する同値類を [φ] とあらわすことにする．今， φ, ψ ∈ F ml(Σ) として，演算 +, ·, − と定数 0, 1 を

\begin{matrix}[φ] + [ψ] = & [φ ∨ ψ] \\ [φ] · [ψ] = & [φ ∧ ψ] \\ −[φ] = & [¬φ] \\ 0 = & [p ∧ ¬p] \\ 1 = & [p ∨ ¬p] \end{matrix}

と定義できる（つまりこの定義は [φ], [ψ] の代表元 φ, ψ には依存しないことが容易に示せる—演習）．このとき， (F ml(Σ), +, ·, −, 0, 1) はブール代数となる．このようなブール代数をこの形のブール代数を最初に研究した人たちの名前を冠して， Lindenbaum-Tarski 代数と呼ぶ．

例 9.3 （巾ブール代数） X を空でない集合とする． P(X) は， u, v ∈ P(X) に対し u + v = u ∪ v, u · v = u ∩ v, −u = X \ u, 1 = X, 0 = ∅ と定義することにより，ブール代数となる．このようなブール代数を X 上の巾ブール代数と呼ぶ． X が有限のときには P(X) も有限となるが，実は，すべての有限ブール代数は，本質的には巾ブール代数と一致することが示せる．