自然数集合の束は豊かである
The lattice of sets of natural numbers is rich (jdh.hamkins.org)
要約
自然数集合の冪集合束 P(N) は、部分集合関係で順序付けられた構造を持ち、有限集合は下位に、補有限集合は上位に位置する。この束は、自然数、整数、さらには有理数といったあらゆる可算順序を埋め込むことができる普遍性を持つ。驚くべきことに、この束は実数連続体 R のコピーをも含み、可算集合のみからなるにもかかわらず非可算な連鎖が存在しうることを示している。
全文翻訳
自然数集合の束は豊かである
$\newcommand\of{\subseteq}\newcommand\N{\mathbb{N}}\newcommand\R{\mathbb{R}}\def<#1>{\left\langle#1\right\rangle}\newcommand\Z{\mathbb{Z}}\newcommand\Q{\mathbb{Q}}\newcommand\ltomega{{{<}\omega}}\newcommand\unaryminus{-}\newcommand\intersect{\cap}\newcommand\union{\cup}\renewcommand\emptyset{\varnothing}$自然数集合の冪集合束 $<P(\N),\of>$ の広大で密集した領域を探求しましょう。
この束には、自然数集合 $A\of\N$ のあらゆるものが含まれており、それらを部分集合関係 $A\of B$ で考えます。これは束順序です。なぜなら、2つの集合の和集合 $A\union B$ は包含関係における最小上界であり、共通部分 $A\intersect B$ は最大下界だからです。実際、$A\intersect(B\union C)=(A\intersect B)\union(A\intersect C)$ という関係から分配束であり、さらに冪集合代数としてブール代数であり、すべてのブール代数は分配束です。
空集合 $\emptyset$ はもちろん束の最下位にある大域的な最小元であり、全体集合 $\N$ は最上位にある最大元です。単集合 $\set{n}$ は $\emptyset$ から一段上の原子であり、その補集合 $\N\setminus\set{n}$ は $\N$ から一段下の余原子です。一般的に、有限集合は束の地上の底付近に集まっており、$\emptyset$ に有限の距離で近く、一方、余有限集合は天上の頂上付近にそびえ立っています。対照的に、その間の広大な中心領域には、素数、平方数、平方因子を持たない数、合成数など、多くの深く興味深い集合を含む無限かつ余有限でない集合が見られます。
質問。 自然数集合の冪集合束 $P(\N)$ の部分順序として、どのような馴染みのある順序を見つけることができるでしょうか?
初期区間の連鎖を単純に考慮することで、自然数順序 $<\N,\leq>$ のコピーを $P(\N)$ の中に簡単に見つけることができます。
$$\emptyset\of\set{0}\of\set{0,1}\of\set{0,1,2}\of\cdots$$
この列は、メイン図の左側をはしごのように登っていきます。好奇心旺盛な読者は、これらの集合はすべて有限であり、したがって私たちが言ったように地球にしがみついていると考えられますが、それでもこの列には $\N$ という大域的な最大元以外の上の界が存在しないことに気づくでしょう。つまり、任意の自然数は最終的に包含されます。したがって、このはしごで天国まで登っていきます。このはしごは束の頂上まで伸びていますが、どの段でもずっと地球の近くにとどまっています。
それらの集合の補集合も同様に、無限に下降する列を形成します。
$$\cdots\ \of\ \N\setminus\set{0,1,2}\ \of\ \N\setminus\set{0,1}\ \of\ \N\setminus\set{0}\ \of\ \N$$
この余有限集合の連鎖は、メイン図の右側を、天国から垂れ下がる結ばれたロープのようにぶら下がっています。このロープの各結び目は余有限集合であり、私たちはそれを頂上に非常に近いと考えましたが、それでもロープは地球に向かって誘うようにぶら下がっています。なぜなら、$\emptyset$ 以外の下の界は存在しないからです。
離散整数順序 $<\Z,\leq>$ のコピーを見つけることはできますか?
はい、できます。例は、メイン束図の右側にある赤い連鎖、空間に吊るされたスカイクレーンとしてすでに表示されています。奇数の集合に立って、一度に1つの偶数を追加することで離散的なステップで上昇できます。または、連続する奇数を削除することによって同様に下降することもできます。結果は整数順序 $\Z$ に同型な離散連鎖であり、極端な点 $\emptyset$ と $\N$ 以外は有界ではありません。
有理直線 $<\Q,\leq>$ のような密な順序を見つけることはできますか?
何ですって?自然数集合の束の中に密な順序を見つけたいのですか?束には基本的に離散的な性質があると考えがちなので、それは不可能に思えるかもしれません。結局のところ、任意の集合の最も近い隣人は、ちょうど1つの要素を追加または削除することによって得られます。これを行うと、厳密な中間集合なしで離散的なステップで上下します。束の本質的に離散的な性質は、密な順序 $<\Q,\leq>$ を埋め込むことができないことを示唆していますか?
いいえ!驚くべき事実は、実際に有理直線を有理直線 $<\Q,\leq>$ を冪集合束 $P(\N)$ に埋め込むことができるということです。実際、それよりもはるかに多くのことが真実です。任意の可算順序を $P(\N)$ に埋め込むことができることがわかります。どこにでも存在するすべての可算順序は、自然数集合の束の中に存在します。
定理。 自然数上の冪集合束 $P(\N)$ は、すべての可算順序に対して普遍的です。つまり、可算な定義域上のすべての順序関係は、$<P(\N),\of>$ の部分順序と同型です。
証明。 まず、任意の順序関係 $<L,\preccurlyeq>$ が、集合のコレクション上の部分集合関係 $\of$ と同型であることを証明しましょう。すなわち、各 $q\in L$ に対して、$q{\downarrow}$ を $q$ の下向き集合、つまり $q$ の先行集合とします。
$$q{\downarrow}=\set{p\in L\mid p\preccurlyeq q}\of L$$
これは $L$ の部分集合であり、私が主張するのは次のことです。
$$p\preccurlyeq q\quad\text{ if and only if }\quad p{\downarrow}\of q{\downarrow}.$$
これはほとんど明白です。順方向の含意については、$p\preccurlyeq q$ ならば、$p$ の下にあるすべての順序要素も $q$ の下にあるため、$p{\downarrow}\of q{\downarrow}$ となります。逆に、$p{\downarrow}\of q{\downarrow}$ ならば、$p\in p{\downarrow}$ なので、$p\in q{\downarrow}$ でなければならず、したがって所望の $p\preccurlyeq q$ となります。したがって、写像 $p\mapsto p{\downarrow}$ は、元の順序 $<L,\preccurlyeq>$ からすべて下向き集合の族 $\set{p{\downarrow}\mid p\in L}$ への、部分集合関係を用いた同型写像です。
証明を完了するには、可算無限集合 $L$ の冪集合束 $P(L)$ が $P(\N)$ と同型であり、有限集合 $L$ の場合は自然数の有限集合以下の冪集合束と同型であることを観察するだけです。これは、 $L$ と自然数集合との任意の全単射が、それぞれの部分集合の対応する同型写像を誘導するためです。したがって、所望のように $L$ のコピーを $P(\N)$ の中に見つけることができます。 $\Box$
証明をより具体的にするために、2つのステップを組み合わせることができます。たとえば、$<L,\preccurlyeq>$ が任意の可算順序関係である場合、定義域集合 $L=\set{p_0,p_1,p_2,\ldots}$ を列挙し、各 $p\in L$ に対して $A_p=\set{n\in\N\mid p_n\preccurlyeq p}\of\N$ とします。これは $p$ の下向き集合に似ていますが、要素そのものではなく、要素のインデックスを使用します。 $p\preccurlyeq q$ ならば $A_p\of A_q$ であり、したがって写像 $p\mapsto A_p$ は $<L,\preccurlyeq>$ から $A_p$ のコレクションへの順序同型写像であり、所望の通りです。
有理数の集合 $\Q$ は可算であるため、上記の普遍性定理のインスタンスとして、有理直線 $<\Q,\leq>$ のコピーを冪集合束 $<P(\N),\of>$ の中に見つけることができると結論付けられます。有理直線のエレガントな明示的な表現を冪集合束に見つけることができますか?有理数を可算で無限に続く密な線形順序として特徴付けることを考慮すると、可算で無限に続く密な線形順序を形成する $P(\N)$ の連鎖を見つけるだけで十分です。
しかし、まだあります!実際、自然数上の冪集合束に実数直線 $<\R,\leq>$ のコピーを見つけることができます!待ってください…本当に?それはどのように可能なのでしょうか?実数は非可算であり、したがってこれは自然数集合の束における非可算連鎖になるはずですが、$A\of\N$ のすべての部分集合は可算であり、 $A$ に追加できる要素は可算個しかありません。束の中に非可算連鎖が存在する可能性があるのはなぜでしょうか?
説明しましょう。
定理。 自然数上の冪集合束 $<P(\N),\of>$ は非可算連鎖を持ち、実際、実数連続体 $<\R,\leq>$ のコピーを持っています。
証明。 自然数上の冪集合束 $P(\N)$ に有理直線 $<\Q,\leq>$ のコピーが存在することはすでに観察しました。つまり、写像 $q\mapsto A_q\of\N$ が存在し、任意の有理数 $p,q\in\Q$ に対して次のようになります。
$$p<q\quad\text{ if and only if }\quad A_p\of A_q$$
この埋め込みを完成させることで、所望の実数連続体のコピーを見つけることができます。すなわち、任意の実数 $r\in\R$ に対して、次のように定義します。
$$A_r=\bigcup extbackslash\substack{q\leq r\ q\in\Q} A_q.$$
有理数 $q$ の集合 $A_q$ が連鎖を形成するため、$r\leq s$ ならば $A_r\of A_s$ となることは容易にわかります。そして、$r<s$ ならば、$A_r$ は $r<q<s$ となる有理数 $q$ のある $A_q$ に厳密に含まれ、したがって $A_s$ に厳密に含まれます。これから、$r\leq s$ ならば $A_r\of A_s$ となり、所望のように実数順序のコピーを冪集合束に見つけることができました。 $\Box$
このセクションの驚くべき出来事を締めくくるために、別の衝撃的な事実を証明しましょう。冪集合束 $P(\N)$ の中に非可算反鎖(連続体個のペアごとに比較不能な集合のコレクション)も見つけることができます。
定理。 自然数上の冪集合束 $<P(\N),\of>$ は、連続体個のペアごとに比較不能な集合のコレクションである非可算反鎖を持ちます。
証明。 有限二分列の木 $2^{\ltomega}$ を考えます。これはすべての有限二分列の集合であり、$s\leq t$ が $t$ が $s$ を拡張する場合(末尾にさらなる二進数字を追加することによって)成り立つという関係で順序付けられています。これは可算順序関係であるため、普遍性定理により $P(\N)$ の中にコピーを見つけることができます。しかし、もう少し具体的にしましょう。木 $2^{\ltomega}$ の各ノード $s$ に、異なる自然数をラベル付けします。木を通過する無限二分経路 $x\in 2^\omega$ に対して、経路に沿って現れる数の集合を $A_x$ とします。各 $A_x$ は無限ですが、$x\neq y$ ならば、$x$ と $y$ は最終的に分岐し、その結果 $A_x$ と $A_y$ は有限個の数しか共通しません。特に、$A_x$ も $A_y$ も互いに部分集合ではないため、冪集合束の中に反鎖を見つけることができました。二分木を通過する経路の数は、無限二分列の数であり、所望のように実数の連続体の濃度と同じです。 $\Box$
したがって、束 $P(\N)$ は豊かな複雑性を提供します。しかし、そこには均質性も見いだせるでしょうか?束の中心領域にある集合、つまり無限かつ余有限な集合に身を置いてみてください。より大きな集合を作るために追加できるさまざまな新しい要素があります。この要素だけを追加することも、その要素だけを追加することも、無限にある新しい原子のいずれかを追加してより大きな集合を作ることもできます。そして、それらの原子の任意の組み合わせを追加できます。したがって、束の任意の余有限点の真上には、全体の束の完全なコピーが見られます。任意の余有限集合から見上げると、常に同じように見えます。
定理。 自然数集合の束は、いくつかの点で均質です。
- 任意の与えられた余有限集合 $A\of\N$ の上の集合の束は、全体の冪集合束 $P(\N)$ と同型です。
- 任意の与えられた無限集合 $B\of\N$ の下の集合の束は、全体の冪集合束 $P(\N)$ と同型です。
- 任意の2つの無限かつ余有限な集合 $A,B\of\N$ に対して、$P(\N)$ の自己同型写像が存在し、$A$ を $B$ に写します。
証明。 まず、ステートメント (2) を証明しましょう。任意の無限集合 $B\of\N$ と、その下の $P(\N)$ の部分束(つまり、 $B$ のすべての部分集合の冪集合束 $P(B)$)を考えます。 $B$ は無限集合の自然数であるため、$B$ と $\N$ の間の全単射 $\pi:B\to\N$ が存在します。したがって、全単射を適用することによって、$B$ の部分集合を $\N$ の部分集合に変換できます。すなわち、任意の $X\of B$ に対して $\bar\pi(X)=\pi[B]=\set{\pi(b)\mid b\in X}$ と定義します。 $\pi$ は単射なので、$X\of Y$ ならば $\bar\pi(X)\of\bar\pi(Y)$ であり、 $\pi$ は全射であるため、写像 $\bar\pi$ は $P(\N)$ に写ります。なぜなら、すべての $Z\of\N$ は $Z=\bar\pi(X)$ となり、ここで $X=\pi^{\unaryminus 1}Z=\set{b\in B\mid \pi(b)\in Z}$ となるからです。したがって、$\bar\pi$ は束 $P(B)$ と $P(\N)$ の同型写像です。所望の通りです。
ステートメント (1) については、任意の余有限集合 $A\of\N$ を考え、$A{\uparrow}$ を $A$ の上の冪集合束の部分、つまり $A\uparrow=\set{X\of\N\mid A\of X}$ とします。補集合 $B=\N\setminus A$ は無限であるため、$B$ と自然数全体の集合との間の全単射 $\pi:B\to\N$ が存在します。私は、束 $A{\uparrow}$ が束 $P(B)$ と同型であると主張します。ステートメント (2) により、これは $P(\N)$ と同型であることがわかっています。これを見るには、 $A$ を含む任意の集合 $X$ から $A$ を除くだけです。残りは $B$ の部分集合であり、 $B$ のすべての部分集合が実現されます。より具体的には、$A\of X$ ならば $\tau(X)=X\setminus A=X\intersect B$ と定義し、$A\of X$ ならば $X\of Y$ ならば $\tau(X)\of\tau(Y)$ であり、すでに $A$ を含む集合に対して成り立つことを観察します。そして、$Z\of B$ ならば、$Z=\tau(A\union Z)$ となります。したがって、$\tau$ は束 $A{\uparrow}$ と $P(B)$ の同型写像であり、ステートメント (2) により、全体の束 $P(\N)$ と同型です。所望の通りです。
最後に、2つの無限かつ余有限な集合 $A,B\of\N$ を固定します。特に、$A$ と $B$ は、補集合 $\N\setminus A$ と $\N\setminus B$ と同様に、全単射です。これらの2つの全単射を組み合わせることで、 $A$ を正確に $B$ に写す、つまり $\pi[A]=B$ となるような、 $\N$ 自身への全単射 $\pi:\N\to\N$ を得ることができます。(読者には、私の本でこの構成について注意深く説明する演習があります。) $\pi$ は $\N$ 自身への全単射であるため、$\bar\pi(X)=\pi[X]$ for $X\of\N$ と定義される束の対応する自己同型写像を誘導します。これは $P(\N)$ 自身への同型写像であり、$\bar\pi(A)=\pi[A]=B$ となります。所望の通りです。 $\Box$
定理のステートメント (3) は、任意の2つの無限かつ余有限な集合は、互いに自己同型像であるため、$P(\N)$ の束において同じ構造的役割を果たし、すべて同じ束論的性質を持つことを示しています。したがって、この定理に照らして、束内の特定の集合に関する構造定理を探すべきではありません。むしろ、$P(\N)$ の構造理論は、私が上で証明した定理のように、全体としての構造に関するものです。
これは、現在執筆中の私の本『Topics in Logic』からの抜粋です。第3章、関係論理に関する章に掲載されており、特に自然数集合の束に関するサブセクションを含む順序に関するセクションが含まれています。なぜなら、私はそれが魅力的だと感じるからです。