使用して計算できる序数 $\Sigma^1_2$ そして $\Pi^1_2$ 真実?

3
Keshav Srinivasan 2019-11-13 06:00.

最も非再帰的順序数は $\omega_1^{CK}$、チャーチクリーネオーディナル。しかし、オラクルの利点を利用して、より多くの序数を計算できます。または、少なくとも、十分に強力なオラクルの恩恵を受けることができます。この答えは、一次算術のすべての真理のセットを使用しても、それ以上の序数を購入しないことを示しています。

しかし、私の質問は、すべてのセットを使用した場合、どのような序数が得られるかということです $\Sigma_2^1$ そして $\Pi_2^1$真実?つまり、$T$ 真のすべてのゲーデル数の集合である $\Sigma_2^1$ そして $\Pi_2^1$二階算術の言語でのステートメント。次に、コピーを使用して計算できる最も序数が少ないものは何ですか$T$ オラクルとして?

序数を正確に説明するのは難しいかもしれませんが、少なくともその大きさに上限と下限を設定できますか?いずれにせよ、私が尋ねる理由は、シェーンフェルドの絶対性定理とのこれらの種類の真理との関係のためです。

1 answers

4
Noah Schweber 2019-11-16 10:24.

セット $Th_{\Pi^1_2}(\mathbb{N})$ (これを「$X_2$")本当に非常に大きな序数を計算します;実際、非常に大きいので、それらの上限についてはまともな議論があります$\omega_1^{CK}(X_2)$ 「基本的に非コンクリート」です。

(以下では、簡単にするために極限順序数についてのみ考えています。これは、上記のYair Hayutのコメントの詳細であることに注意してください。)

アイデアは、 $L$定義可能なスコーレム関数があります。これは、「一次現象」が$L$ 比較的簡単に、つまり $\Pi^1_2$ 方法、およびそのようなものに対応するすべての序数は、から計算可能なコピーを持っています $X_2$。簡単にするために、すべての序数は極限序数であり、すべての理論にはKPi + V = Lが含まれているので、セットをまとめます。$A$ 対応する構造を持つ $(A; \in\upharpoonright A)$

  • ここには重要な微妙な点があることに注意してください。 https://en.wikipedia.org/wiki/Post%27s_theorem#Post's_theorem_and_corollaries、ただし、射影階層のレベルは、ハイパージャンプの反復に対応していません。特に、$\mathcal{O}^\mathcal{O}$あるgalacticallyよりも簡単$X_2$、および $\omega_1^{CK}(\mathcal{O}^{(n)})$ ただ $\omega_{n+1}^{CK}$。(重要な点は$\mathcal{O}^{(n)}\in L_{\omega_{n+1}^{CK}}$。)「明らかな」証拠がなぜであるかを確認するのは良い練習です $\mathcal{O}^\mathcal{O}\equiv_TX_2$内訳(ヒント:何を定量化しているかを考えてください...)

まず、セットアップ:

ために $A$ セット、しましょう $D(A)$ の定義可能な要素のセットである $A$ そしてしましょう $M(A)$ モストフスキ崩壊補遺 $A$。考えるべき重要なことは地図です$$A\mapsto M(D(A)).$$ 一般に $A$ そして $M(D(A))$お互いにほとんど関係がないかもしれません。ただし、万が一の場合に備えて、いくつかの非常に優れたことが起こります。$A=L_\theta$ いくつかの序列のために $\theta$

  • 以来 $L_\theta$ 定義可能なスコーレム関数があります。 $D(L_\theta)\preccurlyeq L_\theta$ など $M(D(L_\theta))\equiv L_\theta$

  • 結露によって $M(D(L_\theta))=L_{\theta'}$ いくつかのための $\theta'\le\theta$、と $\theta'=\theta$ iff $D(L_\theta)=L_\theta$ (つまり、 $L_\theta$ある点状に定義可能)。

(実際、私たちはそれも知っています $M(D(M(D(L_\theta))))=M(D(L_\theta))$ -つまり、適用後 $M\circ D$ ポイントごとに定義可能なものが得られますが、ここでは必要ありません。)


さて、これが上記の観察がどのように多くのポイントごとに定義可能なレベルにつながるかです $L$

仮定します $T$ 理論であり、 $L_\theta$ の最低レベルです $L$ 満足 $T$。それから$L_{\theta'}$ も満たす $T$ 私たちは持っている必要があります $\theta'=\theta$ -つまり、 $L_\theta$ ポイントごとに定義可能である。

特に、 $L_{\omega_{17}^{CK}}$ ポイントごとに定義可能です:取る $T$KPi + V = L +「16の許容序数があります。」同様に、$L_{\beta_0}$ ポイントごとに定義可能です。

確かに、それはのセットが $\alpha$ そのような $L_\alpha$ ポイントごとに定義可能であり、 $\omega_1^L$ (見る https://arxiv.org/pdf/1105.4597.pdf)。


OK、だから何?

まあ、もし $L_\alpha$ ポイントごとに定義可能であり、 $Th(L_\alpha)$ のコピーを計算します $\alpha$ -単に尋ねる $Th(L_\alpha)$どの式が序数に対応し、どのように順序付けられるべきか。だから特に、$L_\alpha$ ポイントごとに定義可能であり、 $Th(L_\alpha)\le_TX_2$ その後 $\alpha<\omega_1^{CK}(X_2)$

それで、次の観察で締めくくります。理論のために$T$$$\alpha_T=\min\{\beta: L_\beta\models T\}$$ (その慣習で $\alpha_T=0$ レベルがない場合 $L$ 満たす $T$)。次に、次のようになります。

定理:もし$T$ある計算、その後、$Th(L_{\alpha_T})$ です $\Delta^1_2$

(証拠:要点は $L_{\alpha_T}$ 実際には、のユニークなレベルです $L$ 満足 $T$ + "$T$ 推移的なモデルはありません。」 $L_{\alpha_T}\models\varphi$ のすべての十分に根拠のあるモデルの場合 $T$ + "$T$ 十分に根拠のあるモデルはありません」 $\varphi$ の十分に根拠のあるモデルがある場合 $T$ + "$T$ 十分に根拠のあるモデルはありません」 $\varphi$、およびこれらの最後の2つの句は $\Pi^1_2$ そして $\Sigma^1_2$ それぞれ。)

これをすべてまとめると、 $\alpha_T<\omega_1^{CK}(X_2)$ すべての計算可能性理論について $T$。例えば、$\beta_0<\omega_1^{CK}(X_2)$ (取る $T=ZFC -P + V=L$)。これは多かれ少なかれ、「下から」の特性評価を排除します$\omega_1^{CK}(X_2)$; リフレクションの原理とその同類の観点からの特徴づけが残っていますが、これは少しトートロジー的である可能性があります。したがって、最終的には、この序数は単純に大きすぎて十分に説明できないという議論としてこれを取り上げます。

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

グッドジョブ、ESPN

グッドジョブ、ESPN

今日のホワイトハウスの記者会見で、報道官のサラ・ハッカビー・サンダースは、スポーツセンターのホストであるイェメル・ヒルのドナルド・トランプに関する最近のツイートについてコメントするよう求められ、大統領と彼の政策を白人至上主義者として説明した。ヒルは彼女のつぶやきのためにESPNによって公に叱責されました。

アマゾンからのこのレミントンツールセールで髪を整える、スタイルを整える、乾かす、または取り除く

アマゾンからのこのレミントンツールセールで髪を整える、スタイルを整える、乾かす、または取り除く

基本的に頭のあらゆる部分から髪の毛を整えたり、ブロードライしたり、まっすぐにしたり、脱毛したりする必要がある場合は、このレミントンゴールドボックスが最適です。今日だけ、Amazonは、すでに人気のあるShortcut Pro Self-HaircutKitやPearlPro Ceramic Flat Ironのように、グルーミングをはるかに簡単にするヘアツールをマークダウンしています。

カナダの元桂冠詩人が、史上最高の文化の盗用でトゥパックとマヤアンジェロウから盗んだ

カナダの元桂冠詩人が、史上最高の文化の盗用でトゥパックとマヤアンジェロウから盗んだ

トゥパックシャクール(ティムモーゼンフェルダー/ゲッティイメージズ); マヤアンジェロウ(マーティンゴッドウィン/ゲッティイメージズ)移動、テイラースウィフト。ケンドールとカイリーは、必要な数の座席を持っています。

テスラは、ハリケーンイルマによる避難を容易にするために、フロリダでの車両の範囲を拡大しています

テスラは、ハリケーンイルマによる避難を容易にするために、フロリダでの車両の範囲を拡大しています

写真:Tesla Motorsフロリダに住んでいて、Tesla Model S、Model X 60、またはModel 60Dを使用している場合、車の自律性は50 km(約30マイル)高くなります。これは失敗ではなく、ハリケーンイルマによる避難作業を容易にするために会社自身が命じた自治権の一時的な延長です。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

ムーアの法則を超えて

ムーアの法則を超えて

計算に対する私たちの欲求とムーアの法則が提供できるものとの間には、指数関数的に増大するギャップがあります。私たちの文明は計算に基づいています—建築と想像力の現在の限界を超える技術を見つけなければなりません。

Language