集合と論理・構造レジュメ加藤敦士 1 本発表の目的と流れ『証明できることは、科学において証明なしに信頼すべきでない』[1] 切断で有名なデデキントの言葉です。彼は集合についても” 証明” しようとしました。この試みはある程度成功し、ある程度失敗しました。デデキントは、19 世紀後半から 20 世紀前半の人ですので、21 世紀になった今現在の数学では、集合論は” 証明” しきれているのだろうと期待される方もいるかと思われます。しかし、幸運にも（不幸にも）未だにそはなされていないのです。そのおかげで、集合論に対する立場というのは様々あります。後で（もしくは発表で）話すと思いますが、この立場とは論理学における立場と言っても良く、論理と集合は現代数学においてほぼ同じものです。ならば、本発表ではどの立場を扱うのかと聞かれるでしょう。現代的な集合論を扱わないので、どの立場でもない、というのが半分正解です。素朴集合論というものを扱います。（図 1）図1 現代数学の概観この集合論を皆さんは気が付かないうちに使っています。ただ、無意識に使うのは怖いのでしっかり定式化しよう！というのが今回の目的の 1/10 であり、残りの 9/10 は定式化したおかげでいかに数学が見易くなるかを伝える事にあります。長くなってしまったので、ここら辺で流れを説明します。以下の順で話す予定です。 § 0：導入・論理貴学の説明 § 1：集合と写像・順序組（選択公理） § 2：一階述語論理（意味） § 3：構造 1 § 4：濃度・選択公理（§ 5：フリートーク）もしかすると順序が変わったり、話さないものがあったりするかもしれません。各セクションを 10∼15 分で話します。 2 予備知識発表を聞く上で、知っておいた方がいいことを簡潔に紹介・説明しておきます。所々、論理記号のみで書くのでわかりづらいかもしれまんせが、慣れるための練習だと思ってください。（帰ってから、もしくは発表の途中で見るように作っています。）定義には d、定理・命題には S を頭につけて、番号を振っておきました。あと余計なコメントやら問題がありますが、気にしなくていいです。 A. 集合の記法（ここで述べるのは記法であり、” 定義” ではない。このことが何を意味するのかは各人に答えを考えてもらいたい。）集合 A において、a が A の要素（元）である時、 a∈A (式 A-1) と表す。 (d.A-1) 「集合 A と B が等しい」とは、集合の要素が一致することである。これを (式 A-2) A=B と書く。 (式 A-1) から (式 A-3) A = B ⇔ ∀x(x ∈ A ↔ x ∈ B) （ここで x は何の要素であるのかが書かれていないことに注意せよ。）（では、要素同士が等しいとはどういうことになるだろうか） (d.A-2) 集合 A、B において、「A が B の部分集合である」とは、A の要素を B が必ず要素として持つことを言う。 A⊆B (式 A-4) と表す。これは (式 A-5) A ⊆ B ⇔ ∀x(x ∈ A → x ∈ B) である。 (d.A-3) 集合を表す際に {,} を用いる。 i) {a} は集合である。 ii) {a} ∋ a である。 iii) {a1 , · · · , an } も集合で、{a1 , · · · , an } ∋ ai (1 ≤ i ≤ n) である。 2 iv) { x | P (x) }（P (x) は命題）も集合である。 P (x0 ) が真 ⇔ x0 ∈ { x | P (x) } である。 a ∈ {{a}, b} は正しいか？問1 (d.A-3-1) ∀x(x ∈ / {, }) である。（ただし、a ∈ / A ⇔ ¬(a ∈ A) である。）つまり、要素を持たない集合 {, } というものを考えることができる。この集合を Ø と書く。 (d.A-4) 集合 A の部分集合のみを要素とする集合を A のべき集合と呼び P(A) と表す。P(A) ∋ {, } である。 ∀X ∈ P(A) (X ⊂ A) (式 A-6) 問2 (式 A-6) は不完全である。それはなぜか。 (d.A-5) ある集合 X において、その部分集合 A、B を考える。 i) B が A の補集合とは ∀x ∈ X(¬(x ∈ A ∧ x ∈ B) ∧ (x ∈ A ∨ x ∈ B)) (式 A-7) である。このとき B を Ac と表す。 ii) ある集合 C(⊆ X) が存在して (式 A-8) ∀x ∈ C(x ∈ A ∨ x ∈ B) ∧ ∀x ∈ A(x ∈ C) ∧ ∀x ∈ B(x ∈ C) となる時、C を A ∪ B と表し A と B の和集合と言う。 iii) ある集合 D(⊆ X) が存在して ∀x ∈ D(x ∈ A ∧ x ∈ B) ∧ ∀x ∈ A(x ∈ D ↔ x ∈ B) (式 A-9) となるとき、D を A ∩ B と表し、A と B の共通部分と呼ぶ。（添字集合族 (Aλ )λ∈Λ についての ∪ λ∈Λ ∩ Aλ 、 λ∈Λ Aλ も同様に定義底奥が、実際は少しめんどうだったりする。）問 3 X ⊃ A, B とした時、 P(A) ∋ {, }、P(B) ∋ {, } である。前者と後者は P(A)、P(B) の要素として等しいか？また P(X) の要素としてはどうか？以上が集合の記法である。既に習ったことがあるものばかりかもしれないが、基本なのであらためて述べた。 B. 写像・順序組・直積ここからは新しい知識が出てくると思われる。先に要点を述べるなら、写像と順序組は互いに定義しあえるということに注目してもらいたい。（公理論的集合論に片足をつっこんだ形になっている。） 3 (d.B-1) 順序対 ⟨,⟩ を定義する。（順序 2 組とも呼ぶ。） ∀x, y, z, w(⟨x, y⟩ = ⟨z, w⟩ ⇔ x = z ∧ y = w) (式 B-1) を満たす（部分）集合を順序対と呼ぶ。 i) 順序 3 組 ⟨x, y, z⟩ = ⟨x, ⟨y, z⟩⟩ として定義される。 ii) 順序 n − 1 組が定義さえれ、⟨a1 , · · · , an−1 ⟩ と表されるとき、順序 n 組は ⟨a1 , · · · , an ⟩ = ⟨a1 , ⟨a2 , · · · , an ⟩⟩ (式 B-2) で定義される。 (S.B-1-1) X ∋ x, y とするとき、 (式 B-3) ⟨x, y⟩ = {{x}, {x, y}} は (式 B-1) を満たす。({x}, {x, y} ∈ P(X)) P roof. (⇐) は明らかである。 (⇒) {{x}, {x, y}} = {z, {z, w}} から {x}, {x, y} ∈ {{z}, {z, w}}. x について、{x} = {z} または {x} = {z.w}. ・前者では {x, y} = {z, w} ⇒ {x, y} = {x, w} ⇒ y = w (x = y でも x ̸= y でも y = w である) ・後者では、{x} = {z, w} のとき x = z = w であるので {{x}, {z, w}} = {{x}, {x, x}} = {{x} (※ B − 1) ⇒ {x, y} = {x} ⇒x=y 上と合わせて、x = y = z = w □ (※ B-1) {a, a} = {a} ∵ {a, a} ⊇ {a}∼{a, a} ⊆ {a} (S.B-1-2) X = A ∪ B とし、a ∈ A、b ∈ B として ⟨a, b⟩ = {{a}, {a, b}} を順序対として定義できる。 P roof. (SB-1-1) から明らか。 □ (S.B-1-3) {{a}, {a, }} (a ∈ A, b ∈ B) は P(P(A ∪ B)) の要素であり、⟨a, b⟩ の集合は P(P(A ∪ B)) の部分集合となる。 P roof. {a} ∈ P(A), {a, b} ∈ P(A ∪ B) である。よって、P(P(A ∪ B)) の要素。 (d.A-3) の (iv) から φ(x) = ∃a ∈ A, ∃b ∈ B(x = {{a}, {a, b}} ∧ x ∈ P(P(A ∪ B))) 4 として、{ x | φ(x) } を考えればよい。 □ （本来の公理論的集合論では (iv) に制限が加えられる。しかし、実用上、素朴集合論の緩い定義で問題はない。）この順序対を用いて写像を定義する。対応も同様に定義できる。また、⟨a, b⟩ において、a = ⟨a1 , · · · , an ⟩ とすれば、n 変数の写像、対応も定義できる。 (S.B-1-2) の手法をよく覚えておいてほしい。これは、写像から直積（順序対）を定義するのに用いられる手法と同じである。 (d.B-1-4) A × B := { ⟨a, b⟩ | a ∈ A, b ∈ B } とし、A と B の直積と呼ぶ。 (d.B-1-5) f が写像であるとは f ⊂ A × B ∧ ∀a ∈ A ∃!b ∈ B(⟨a, b⟩ ∈ f ) となることを言う。（対応ならば唯一存在ではなく存在）このとき、a に対して ⟨a, b⟩ ∈ f となる b を f (a) と表す。この定義から通常の写像と同じものが作られている。私たちのイメージでは f : A → B だが、集合論としては f ⊂ P(P(A ∪ B)) なのだ。（図 2）図2 写像のイメージ問 4 A から B への写像全体はどのように表されるだろうか？厳密でなくてよいのでイメージしてほしい。素朴集合論的に写像から直積を定義してみよう。 (d.B-2) 写像 f : {1, 2} 7→ A1 ∪ A2 を考える。 (式 B-4) F := {f ∈ F |f (1) ∈ A1 ∧ f (2) ∈ A2 }・・・(※ B-2) は集合であり、⟨a1 , a2 ⟩ ∈ F として、f ∈ F (f (1) = a1 , f (2) = a2 ) を満たすものとして定義すると、これは順序対となる。・・・(※ B-3) この ⟨a1 , a2 ⟩ の集合を A1 と A2 の直積と定義する。 (※ B-2) F は {1, } から A1 ∪ A2 への写像の集合 (※ B-3) ⟨a1 , a2 ⟩ = ⟨x, y⟩ ⇔ a1 = 1, a2 = y P roof. (⇒) 自明。 5 (⇐) 2 つの写像 f 、g を考えると f (1) = a1 = x = g(1) ∧ f (2) = a2 = y = g(2) より f = g である。（写像として） □ この定義の方法だと写像とは何か？という疑問が出てくる。集合から定義していったほうが見通しがだいぶよい。図3 写像による直積の定義（この定義法は高校までの数学で案に用いられている） ※先の順序対との違いは、（元があった）集合では表現できず、集合とは別の次元として（たとえば、集合をモノとするなら写像は機能）写像を作り出さないといけない。これは面倒な話である。なので定義をきちんと書くのが難しかった。以上で集合についての予備知識の説明を終える。その他の分野に関しての話は発表中に適宜補う。参考文献 [1] デデーキント：数について（岩波書店, 1997：第 30 刷）引用のためだけに開いた。歴史的な価値はある。 [2] 河田敬義：自然数論：（森北出版, 1968：第 1 刷）まだ読み終わっていないが、デデキントの引用はこの本で見つけて、[1] から引用した。 [3] 本橋信義：集合序説（培風館, 2005：初版）論理学者の書いた素朴集合論の本。最初に読んだときは泣きそうだったが、今はいい友達。200p 弱なので飽き性の人におすすめ。 [4] 鈴木聡：記号論理入門講義（DTP 出版, 2013：第 4 刷） 120p ほどの薄さで記号論理の使い方を教えてくれる良書。完全性・健全性は面倒なので扱わないといういさぎよさも好感がもてる。他にも有名どころは少し見直した。 [3]、[4] をセットで読めば基礎はだいたいわかる（と思う）。 6 補足・論理記号について ∀：全ての∼, ∃：ある∼ ) 要素に対して用いる。 ) ¬：∼でない, ∧：かつ, ∨：又は命題に対して用いる。 → ならば ↔ は命題に対して用いる。P, Q を命題として P ↔ Q は (P → Q) ∧ (Q → P ) のこと。命題とは真か偽であることが一意に定まるもの。ただし、P (x) は命題だが、x のとる値に応じて真・偽が変わる。例 P (x) を x = 1 とする。 Q(x) を x2 = 1 とする。 ∀x ∈ R(P (x) → Q(x)) は真。 ∀x ∈ R(Q(x) → P (x)) は偽。 P → Q は¬P ∧ Q と同値。（背理法ではこれを用いることもある。）・立場について  ¬(¬P ) = P 二重否定  認める。（というか認めないとヤバイ） ¬A ∨ A 排中律 (¬B → ¬A ∧ A) → B 背理法・数学的な証明について ⇒ ：ならば, ⇔ ：同値) 推論について用いる記号。推論の規則については特に考慮せず普通にやりました。・論理記号の使用法について（第一階）述語論理の言語 L† は次のものからなる。（言語は記号列のことだと思ってください。）・文結合記号：¬, ∨, ∧, →, ↔ ・量子化：∀, {∃ ・個体記号変数：a, b, c, · · · 定数：α, β, γ, · · · ) ← 合わせて対象式と呼ぶ。・述語記号：P, Q, R, · · · ・関数記号：A, B, C, · · · ) ← 対象式と関数を合わせて項と呼ぶ。 7 ・等号：= ・補助記号：(, ) 集合論を記述する場合、述語を作成する際に ∈, ⊆, ⊊, ∪, ∩ を使用します。（これは定義していけばいい。） L† の原子論理式 ( t, s を項とするとき、 1 ⃝ t = s は原子論理式  t1 , · · · tn を項とするとき P が n 変数の述語なら   2  P (t1 , · · · tn ) ⃝ は原子論理式 L の論理式・原子論理式は論理式。・論理式 ψ, φ を用いて作られる。・ψ ∧ φ, ψ ∨ φ, ¬(ψ), ψ ↔ φ, ψ → φ は論理式。・∀x(ψ), ∃x(ψ) は論理式。論理式の中は自由変数がない時、それを閉論理式と呼び、真・偽はすでに決まっている。（構造が決まると同時に真・偽が定まる。説明は発表で行います。） 8