Fandom

625 ページ

ここで、以下の公理を考えます。

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$$.
Proof.
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}$$.
Proof.
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.