Mathematical Logic Advent Calendar 2019の6日目の投稿記事です。

関数\(\mathbb{N} \to \mathbb{N}\)全体の集合を\(X\)、狭義単調増加関数全体の部分集合を\(X_0 \subset X\)、eventual dominationで与えられる\(X\)上の狭義半順序を\(<_{\textrm{ed}}\)と置きます。つまり\((f,g) \in X^2\)に対し、\(f <_{\textrm{ed}} g\)とは「\(n > N\)ならば\(f(n) < g(n)\)」が任意の\(n \in \mathbb{N}\)に対し成り立つような\(N \in \mathbb{N}\)が存在するということです。


Axiom(Dominating Linear Hierarchy
There exists a subset \(X_1 \subset X_0\) satisfying the following:
(1) \(X_1\) is cofinal in \((X,<_{\textrm{ed}})\), i.e. for any \(f \in X\), there exists a \(g \in X_1\) such that \(f <_{\textrm{ed}} g\).
(2) \(X_1\) is well-ordered in \((X,<_{\textrm{ed}})\), i.e. every non-empty subset \(S \subset X_1\) admits the least element with respect to \(<_{\textrm{ed}}\).

この記事ではDominating Linear Hierarchy Axiomが\(\textrm{ZFC}\)と矛盾しないことを証明します。ちなみに\(X\)全体ではなく計算可能関数\(\mathbb{N} \to \mathbb{N}\)全体のなす部分集合を考えて同様の定式化をした命題は、木原先生によると[1]ゲーデルが夢見ていた非常に重要な問題であり現在は未解決ながらも専門家たちの間では否定的に信じられているとのことだそうです。一方で計算可能性を外して関数全体を考えれば、少なくとも\(\textrm{ZFC}\)と矛盾しないというのが今回の内容です。一見すると考える関数を狭めた方が簡単そうに感じますが、当然\(X_1\)自体も候補が狭まるためにDominating Linear Hierarchy Axiomからはゲーデルの問題の無矛盾性は従いません。



Lemma(the countable domination
For any countable subset \(S \subset X\), there exists an \(f \in X_0\) such that \(g <_{\textrm{ed}} f\) for any \(g \in S\).
If \(S\) is finite, then \(f\) can be chosen to be \(1 + \sum_{g \in S} g\). Therefore it suffices to show the assertion in the case where \(S\) is an infinite set. Take a bijective map \(\iota \colon \mathbb{N} \to S\). Denote by \(f \in X\) the function which assigns \(n + \sum_{i,j=0}^{n} \iota(i)(j)\) to each \(n \in \mathbb{N}\). For any \(n \in \mathbb{N}\), we have \(f(n) < f(n+1)\) by definition. Therefore \(f\) is strictly increasing. For any \(i \in \mathbb{N}\), \(n > i\) implies \(\iota(i)(n) < f(n)\) for any \(n \in \mathbb{N}\), and hence \(\iota(i) <_{\textrm{ed}} f\) holds.


Theorem(Consistency of Dominating Linear Hierarchy Axiom
If \(\textrm{ZFC}\) is consistent, then Dominating Linear Hierarchy Axiom is not disprovable under \(\textrm{ZFC}\).
By Cohen's theorem, it suffices to show Dominating Linear Hierarchy Axiom under \(\textrm{ZFC} + \textrm{CH}\). By \(\textrm{CH}\) and \(\# X = 2^{\aleph_0}\), there exists a bijective map \(\iota \colon \omega_1 \to X\). For each \(\alpha \in \omega_1\), we construct an order-preserving map \(F_{\alpha} \colon (\alpha+1,\in) \to (X_0,<_{\textrm{ed}})\) whose values are by transfinite induction on \(\alpha\). Put \(S_{\alpha} := \{\iota(\alpha)\} \cup \bigcup_{\beta \in \alpha} F_{\beta}(\beta)\). Since \(\alpha\) is countable, so is \(S_{\alpha}\). Therefore \(\{f \in X_0 \mid \forall g \in S_{\alpha}, g <_{\textrm{ed}} f\}\) is non-empty by the countable domination Lemma. By the bijectivity of \(\iota\) and the well-foundedness of \(\omega_1\), \(\{\delta \in \omega_1 \mid \iota(\delta) \in X_0 \land \forall g \in S_{\alpha}, g <_{\textrm{ed}} \iota(\delta)\}\) admits the least ordinal \(\delta_{\alpha}\). Define \(F_{\alpha} \colon (\alpha+1,\in) \to (X_0,<_{\textrm{ed}})\) as the map which assigns \(F_{\beta}(\beta)\) to each \(\beta \in \alpha\) and \(\iota(\delta_{\alpha})\) to \(\alpha\). By the construction, \((F_{\alpha})_{\alpha \in \omega_1}\) forms a compatible system of order preserving maps, and hence extends to a common order-preserving map \(F \colon (\omega_1,\in) \to (X_0,<_{\textrm{ed}})\). Denote by \(X_1 \subset X_0\) the image of \(F\). Since \(F\) is order-preserving and \(\omega_1\) is well-founded, \((X_1,<_{\textrm{ed}})\) is well-founded. Let \(f \in X\). By the construction of \(F\), we have \(f <_{\textrm{ed}} \delta_{\iota^{-1}(f)} = F(\iota^{-1}(f)) \in X_1\). Thus \(X_1\) is cofinal in \((X,<_{\textrm{ed}})\).


  1. 急増加階層とゲーデルの夢, ビジービーバーQ&A: 計算不可能の鳥瞰図, とりマセ Σ^0_2, 2019.
特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。