ゆるゆる べんきょう

暇だから哲学・数学・物理学をゆるく勉強しているよ

無限集合

集合論

ここからは、カントールの集合論に合流するのでさらっとやって終わりにしよう。章でいうと7章～

 

集合のサイズは 1対1対応の関係でそのサイズを測る。自然数で構成される集合をωと呼ぶ。ωと同じサイズの集合は可算集合であり、整数全体Zや、有理数全体のQが同じサイズに対応する。一方、対角論法を利用することにより、実数全体Rはωよりも大きなサイズであることが示される。

 

一般により大きな集合を作るためには、Powerを作ればよい。このようにして次々と大きい集合の列を作成することがある。一方、ωとRのサイズの間のサイズの大きさの集合があるか？は未解決の問題であり、連続体仮説（ωとω1の間のサイズは存在しない）が提唱されている。

 

連続体仮説は独立な公理だったような気がするが、、、11章でもう一回触れるのでそれまで待つか

自然数

集合論

自然数を 0 = Φ, 1 = 0∪{0}, 2=1∪{1}, ... で自然数を定義し、全ての自然数を含むような集合として、suscessor set が存在するという公理を採用する。この公理を用いると、ペアノの各種公理が「証明できる」。

 

自然数が定義できると、漸化式のような finite recursion を考えることができる。実際、「recursion theorem」によってそのような関数 ω -> A なる関数γが存在する。

 

上記によって自然数同士の各種演算「＋, ×」それに付随する各種定理が成立する。

 

やっと　１＋１＝２を証明することができた！

選択公理

集合論

f: Power(A) - {Φ} ->A なる選択関数が、任意の集合について存在するという公理が選択公理である。実際に構成してみるのではなく、その存在を示しているという定理。

 

選択公理は、他の公理とは独立であるため、選択公理を採用しない集合論もあってよいはずであるが、実際には多くの数学者がこれを採用している。ZFCのCが選択公理に相当。ただ、選択公理を利用しないでもよい数学の分野は広い。

 

以下に挙げる定理は選択公理の帰結であり、かつ、選択公理と同値であるため、どれか一つでも認めれば（公理として採用すれば）、選択公理を採用としたのと同様の集合論が出来上がる。

  • Hausdorff’s Maximal Principle

  • Zorn’s Lemma

  • well-ordering theorem

 

まあ、有名な話だよねえ。ツォルンの補題とか響きがかっこよすぎる

 

 

レポート: 集合論いったんまとめ

集合論

基本となる概念を大体学んだので、textbookを読み返して、書かれていることを整理してみた。復習というか、リマインダとしては使えると思うので、ここに記載する。

 

集合論

集合論は、一階述語論理に対し二項述語「∈」を加えて構成される理論である。
なお、集合論で項をクラスと呼ぶため、すべての項はクラスである。

1章
-----

・公理A1「axiom of extent」により、二項述語「＝」が定義できる。
・述語∈から、二項述語「⊆、⊂、⊃、⊇」が定義できる。
・述語⊆から、一項演算子「Pow」が定義できる。
・公理A2「axiom of construction」により、内包表現によりクラスを構成できる。
・A2より二項演算子「∪、∩」が定義できる
・A2より一項述語「・はユニバーサルクラス」「・は空クラス」が定義できる。
・述語∈から、一項演算子「'」（補集合）が定義できる。
・演算子'と演算子∩から二項演算子「-」が定義できる。
・A2から、一項述語「・はシングルトン」、「・はダブルトン」、「・は順序対」が定義できる。
・順序対から二項演算子「×」が定義できる。
・順序対から一項述語「・はグラフ」が定義できる。
・グラフに対して、一項演算子「-1」(逆)二項演算子「。」（合成）が定義できる。

・述語∈から、一項述語「・は集合」が定義できる（集合は要素の別名である）。
・公理A3「集合のサブクラスは集合である」
・公理A4「空クラスは集合である」
・公理A5「集合と集合のダブルトンは集合である」
・公理A6「Aが集合の集合なら、∪Aは集合である」
・公理A7「Aが集合なら、AのPowも集合である」
・公理A8「Aが集合なら、a∩Aが空クラスとなる要素aが存在する」

2章
------

・関数はある種の条件を満たしたグラフとしても定義できる
・関数に対して、一項述語「・はINJ（単射）」「・はSURJ（全射）」「・はBIJ（全単射）」が定義できる。
・関数に対して一項述語「・はinvertible」が定義できる。
・一対一対応に対するクラスに対して述語「≈」が定義できる。
・関数を利用して、インデックスされたクラス達の積Πが定義できる
・関数を利用して、二項演算子「^」（べき乗）が定義できる
・関数「2^A」と関数「Pow(A)」は一対一対応にある

・A9「axiom of replacement」関数f: A->B でAが集合でfが全射ならBは集合
・A9より有限要素数のクラスは集合であることが示される。
・インデックスクラスが集合であれば、インデックスされたクラス達は集合である

3章
------

・関係とは二項述語であり、それらの特徴は、「反射律、[反]対称律、推移律で測られる。
・グラフが関係を特徴づける（個々の要素に対して、関係の真偽や反射律等の成否を与える）。
・主に同値関係と、半順序関係を研究の対象とする。

・同値関係から、述語「～」が定義できる。
・同値関係から、述語「・は・を法とする・の同値クラス」が定義できる。
・同値クラスから、二項演算「A/G」が定義できる（集合の全ての要素の同値クラスを要素とする集合）。
・A/GはAのパーティションであることが示される。
・二つの粒度の異なる同値関係から、二項演算子「/」(quotient)が定義できる。
・同値関係Gが存在する際、カノニカル関数f:A->A/Gが定義できる。
・任意の関数fは t。s。r と分解できる。rはカノニカル関数である。
・上記は A -> A/G -> f(A) -> B と記載される。
・A/G->B なる関数として、関数のquointient「f/G」が定義できる。

4章
-------

・半順序クラスの要素に対して述語「≦」および「・と・は比較可能」が定義できる。
・半順序クラスのサブクラスに対して「・はchain」である（完全に順序付けされた・線形に順序づけされた）が定義できる。
・半順序クラスの要素から、「initial segment」が定義される。
・半順序関係クラスから、カットと呼ばれる操作が定義される。
・半順序関係クラスから、半順序関係の関数に対して、「・はincreasing/order preverving」が定義される
・半順序関係クラスから、半順序関係の関数に対して、「・はisomorphism」が定義される
・二つの半順序関係に対して述語「・は・とisomorphic」「≊」が定義できる。

・半順序クラスの要素に対して、述語「・はmax/min」が定義できる。
・半順序クラスの要素に対して、述語「・はgreatest/least」が定義できる。
・半順序クラスのサブクラスに対して、演算「v(・), λ(・)」(upper bounds, lower bounds)が定義できる。
・半順序クラスとそのサブクラスに対して「sup, inf」が定義できる。
・半順序クラスに対して、述語「・はconditionally complete」が定義できる。
・半順序クラスに対して、述語「・はlattice」が定義できる。
・半順序クラスに対して、述語「・はcomplete lattice」が定義できる。

・半順序クラスに対して、述語「・はfully ordered」が定義できる。
・半順序クラスに対して、述語「・はwell ordered」が定義できる。
・半順序クラスの要素に対して、述語「・は・のimmediate successor」が定義できる。
・半順序クラスの要素に対して、述語「・は・のsection」が定義できる。
・IND「principle of transfinite induction」が証明できる。
・well ordered なクラス同士はisomorphic か、どちらかがどちらかのinitial segmentとなることが示される。

 

ポセット（半順序集合）

集合論

集合Aにおける順序関係に関連していくつかの用語が定義される。「chain, initial segment, cut」

 

poset A, B 間の関数f に関して、いくつかの用語が定義できる。「increasing/order-preserving, isomorphism」 (poset A, B 間にisoなfunctionが存在するときにA,B を isomorphicという)。興味深いことに、「・と・はisomorphicである」という二項関係は同値関係である

 

poset Aの要素に関して、いくつかの用語が定義できる「max, min, greatest, least」。poset AのサブクラスB において、いくつかの用語が定義できる「upper bound, lower bound」。そしてそれらの集合としての「v(B), λ(B)」。「sup (greatest lower bound), inf (least upper bound)」。

 

束(lattice) は、任意のダブルトンがsup と inf を持つ poset として定義できる。それらのsup およびinf を ∨、∧で定義し、join, meet と呼ぶことにする。束は∧、∨に関して各種代数的性質を満たす（逆にこれらの代数的構造で束を定義することもできる）。束はブーリアン代数を構成する。

 

束には、complete という性質がある。これは任意の poset A のサブクラスに関して、inf が存在することである。

 

sup と inf は何度覚えてもすぐに忘れる・・・

 

 

 

同値関係

集合論

同値関係Gが集合Aにおいて定義されるということは、集合Aをパーティション分割することに等しい。パーティションとは、集合をナイフで分割するように、互いに共通部分が存在しないサブクラスを指す。全てのパーティションの和集合をとると、当然Aになる。冒頭の言明は、同値関係にある集合Aの各要素同士が同一のパーティションに分類されるということを指す。

 

 

 

A上で定義された同値関係Gに対して、AのサブクラスBにおける対応する同値関係をG[B] と書き、GのBに対する制約という。

 

A上で定義された同値関係G,Hにおいて、HがGを包含するとき、HはGより「細かい」といい、quotient という演算ができる。これは H/G というように表記して、 H/G = {(Gx,Gy): (x,y) ∈ H} というような集合をつくる演算である。なお、H/G は A/G において同値関係となる

 

同値関係Gは関数f: A→B からも生成することができる。すなわち、同一の値を持つ x, y : f(x) = f(y) を同値関係を持たせるのである。逆に同値関係Gが定義されているとき、 f: A→A/G なる関数f を簡単に作成することができ（つまり f(x) = Gx とする）、この関数をカノニカル関数という。

 

A/G と B は一対一対応の関係にあるという重要な定理が導かれる。

 

若干ややこしいが、図で書いてみると当たり前のことしか言っていないよな気がするね

 

次回は poset すなわち、順序関係について勉強