モデル理論の面白い命題をちょっと紹介【Wathematica Advent Calendar 2022】

この記事はWathematica Advent Calendarの7/6の記事です。(ところで何をAdventしているのだろうか...?)

こんにちは！現在数学科3年のinaです。

皆さんは数学基礎論という分野をご存じでしょうか？大雑把に言うと数学基礎論は「数学」というシステムそのものを考察対象とする数学の分野のことです。(故にメタ数学なんて呼ばれることもあるようです。) ゲーデルの不完全性定理なんかは名前を聞いたことがある、という方も多いのではないでしょうか。

数学基礎論はさらにいくつかに細分することができますが、今回はその中の「モデル理論」という分野をすこ～しだけ紹介したいと思います。

記事中に出てくる証明は読み飛ばしても大丈夫です。証明を追うというよりはむしろどんな命題があるか・それは何を意味するのか、を理解していただけたら嬉しいです！

モデル理論とは？
コンパクト性定理
有限と無限の区別はできない？
Löwenheim-Skolemの定理
可算の中の非可算…??
おわりに
参考文献

モデル理論とは？

数学基礎論では、数学における「命題」を形式的な記号列("文"や"論理式"とよばれる *1 )にして扱います。この辺は細かい話は省略しますが、例えば

$任意の\epsilon > 0に対してあるn_0 \in \mathbb{N}があり、任意のn \in \mathbb{N}に対して、n>n_0ならば|a_n-a|<\epsilonである$

という命題を論理式化すると、

$\forall \epsilon > 0 \, \exists n_0 \in \mathbb{N} \, \forall n \in \mathbb{N}[ n>n_0 \rightarrow |a_n-a|<\epsilon$ ]

といった具合です。*2

さて、今作ったような論理式はあくまで"記号の列"であって、それ以上でもそれ以下でもありません。ですが例えば上に書いた記号列を見たとき、「この記号列は数列の収束を表しているんだな」と捉える人が多いはずです。これは、ただの記号の並びを実際の数学的な対象に対応づけていると考えることができます。この対応付けのことを「解釈」とよびます。

ここで重要なのは、解釈は一通りではないということです。例えば上の例では数列の収束以外の解釈は思い浮かばないと思うので、もう少し簡単な例を用意してみます。

$\forall A \forall B[A \leq B \lor B \leq A$ ]

この論理式の場合、次のような解釈を行うことができます:

① $A,B$ は実数、 $\leq$ は実数の通常の大小関係(この場合この命題は真)

② $A,B$ は集合、 $\leq$ は集合の包含関係(つまり通常は $A \subset B$ と書くようなものを記号を取り換えて $A \leq B$ と書いたということ。この場合命題は偽)

③ $A,B$ はグラフの頂点、 $A \leq B$ は $A$ を始点、 $B$ を終点とするパスが存在することを表す(この場合の真偽は考えているグラフによって異なる)

論理式が真になるような解釈のことを、論理式のモデルと呼びます。

コンパクト性定理

ちょっと強い定理を紹介します。(数学基礎論における)コンパクト性定理とは、以下の命題のことです:

$\Gamma$ を文の集合とする。この時 $\Gamma$ がモデルを持つことと、任意の $\Gamma$ の有限部分集合がモデルと持つことは同値。

証明はGödelの完全性定理*3を認めてしまえばすぐにできますが、一回省略します。コンパクト性定理を認めたうえで、次の定理を証明してみます:

$\Gamma$ を文の集合とする。 $\Gamma$ がいくらでも大きい有限モデルを持てば、 $\Gamma$ は無限モデルを持つ

(証明) 以下のような文たちを考える:

$\phi_2$ : $\exists v_1 \, \exists v_2 [v_1 \neq v_2$ ] (…"最低2個は元がある"みたいなことを指し示す)

$\phi_3$ : $\exists v_1 \, \exists v_2 \, \exists v_3 [v_1 \neq v_2 \land v_1 \neq v_3 \land v_2 \neq v_3$ ] (…"最低3個は元がある"ということ)

のように $\phi_n \, (n\in\mathbb{N})$ を定義する。*4

集合 $\Gamma_0 = \Gamma \cup \left( \underset{n \in \mathbb{N}}{\bigcup} \phi_n \right)$ を考えると、 $\Gamma_0$ の任意の有限部分集合はモデルを持つことがわかる。よってコンパクト性定理から、 $\Gamma_0$ もモデルを持つ。これは少し考えると有限モデルとはなりえないことがわかる。(証明終)

次にこの定理の帰結として、次のような面白い事実を紹介します。

有限と無限の区別はできない？

前の定理から、例えば次のような帰結が得られます:

任意の有限群で成り立つが、任意の無限群で成り立つような等式は存在しない

(証明) 群の元に関する等式 $\phi$ を任意にとる。群の3公理を論理式化したものをそれぞれ $g_1, g_2, g_3$ とし、 $\Gamma = \lbrace g_1, g_2, g_3, \phi \rbrace$ とする。

$\phi$ が任意の有限群で成り立つなら、 $\Gamma$ はいくらでも大きい有限モデルを持つ。よって $\Gamma$ は無限モデルを持つので、これは $\phi$ が成り立つような無限群が存在することを意味する。*5(証明終)

何が言いたいかというと、群の元の等式だけでは有限群か無限群かを区別することはできないのです！こういうように、数学の命題について主張できるのは数学基礎論の面白いところだと思っています。

※「Gは有限群である」という命題で有限群と無限群を区別できるのでは？と思われる方がいるかもしれませんが、今回の主張はあくまで「群の等式は存在しない」と言っています。(つまり例えば $aba^{-1}b^{-1}=e$ といった等式で、任意の有限群で成り立つが任意の無限群で成り立たないものは存在しないという意味です。) 「Gは有限群である」というのは集合論的な主張(有限と無限の定義など)を含んでいて、この場合モデルとしては群というよりむしろ集合論("集合"ではなく"集合論")を考えることになってしまいます。

Löwenheim-Skolemの定理

もう一つほどモデル理論のいい話を紹介したいのですが、そのためにLöwenheim-Skolemの定理と呼ばれるこれまた強い定理を紹介します。

論理式に用いる記号の数が可算*6であるとする。このとき文の集合 $\Gamma$ が無矛盾なら、 $\Gamma$ は可算なモデルを持つ。

この定理もGödelの完全性定理からすぐに得ることができます。さっき紹介したコンパクト性定理のときもそうでしたが、つまるところ完全性定理がかなり強いのです(ただし証明も大変)。詳しい人向けに言うと、完全性定理を証明する際に構築するモデルの濃度が文の集合の濃度と同じになるためこの帰結が得られます。

可算の中の非可算…??

この定理から得られるものとして、「Skolemのパラドックス」を紹介します。これは実際には矛盾は生じていないのですが、矛盾が生じていると誤解されがちな例です。

集合論の授業や教科書で、「集合とはものの集まりのことです」みたいなあいまいな説明をされてもやもやした経験はないでしょうか？しかし実は、集合を扱うための「集合論の公理」というものがあります。有名なのはZFC*7と呼ばれるものです。詳細は「公理的集合論」などで調べてください。

集合論の公理(例えばZFC)の文全体を $\mathcal{L}^{set}$ とします。これに出てくる記号の数は可算*8で、またこの公理系は無矛盾であると信じられています*9。よって先ほどのLöwenheim-Skolemの定理から $\mathcal{L}^{set}$ は可算なモデル $\mathcal{N}$ を持ちます。つまり、「集合全体」として可算集合を選ぶような解釈が存在するわけです。