帰納的可算ではない算術集合はありますか?

2
Miral 2020-09-07 11:02.

私たちはそれを言います $k$-ary関係 $r$ 以上 $\mathbb{N}$数式がある場合は算術です$\varphi (\vec{a})$$k$ 自由変数 $\vec{a}$、そのような、すべての $\vec{n}=(n_1,\dots, n_k)\in\mathbb{N}^k$

$$r(\vec{n}) \text{ holds }\ \text{ iff }\ \ \mathbf{N}\vDash\varphi(\vec{\underline{n}})$$

どこ $\mathbf{N}$ は算術の標準モデルです(つまり、 $\mathbf{N}=\langle\mathbb{N}, +, \cdot, s, 0, =\rangle$)、 $\vec{\underline{n}}$ それは $k$-タプル $(\underline{n_1},\dots,\underline{n_k})$ そして $\underline{n_i}$ それは $n_i$ アプリケーション $s$ のシンボル $0$ シンボル(つまり、 $ss\cdots ss0$ $\ n_i$ 時間)。

関数は、関係として算術的である場合、算術的であると言います。

帰納的可算集合が $R$算術です。しかし、その逆はどこにも見つかりませんが、帰納的可算ではない算術集合を取得する方法がわかりません。

私の最初の質問は、すべての算術集合が帰納的可算であるかどうか、またはこれの反例があるかどうかです。

そして、反例があれば、別の質問があります。

総関数の場合、総関数があります $f$ 式がある場合は再帰的です $\varphi(\vec{a},b)$$k+1$ 自由変数 $\vec{a}, b$ そのような

  1. $f(\vec{n})=m$ 意味する $\text{PA}\vdash \varphi(\underline{\vec{n}}, \underline{m})$ すべてのために $\vec{n}, m\in\mathbb{N}$

  2. $\text{PA}\vdash\exists b (\varphi(\underline{\vec{n}}, b)\wedge (\forall c (\varphi(\underline{\vec{n}}, c)\rightarrow b=c)))$ (どこ $\text{PA}$ ペアノ算術理論です)。

この定義は、最初の定義のより強力なバージョンとして私には見えます。特に、再帰的ではない算術集合があることがわかっているので(再帰的に列挙可能な集合は再帰的ではないため)、定義されている数式全体に対して、代わりに同様の特性があります。$\mathbf{N}$、ペアノ算術で(したがって、実際には、での定義可能性の観点から帰納的集合の特性があります。 $\text{PA}$ その特性関数は、可能な出力として1と0を使用する完全再帰関数であるため)。

私の2番目の質問は、帰納的可算集合ではない算術集合がある場合、この他の2つの間の定義可能性に関する特性はありますか?

要約すると、帰納的可算集合ではない算術集合はありますか?答えが「はい」の場合、帰納的可算集合の自然数による定義可能性の観点からの特徴はありますか?

ありがとう

1 answers

3
Noah Schweber 2020-09-07 11:32.

はい、これらはたくさんあります-そして関連する概念は算術的階層です。

それが今、削除答えに登場した、特に以来、ここに対処する混乱の価値の潜在的なポイントがあります:私たちがすることはできませんconflate「真で$\mathbb{N}$「で証明可能 $\mathsf{PA}$。 "特に、各式について $\varphi$ セット $$\{x: \mathsf{PA}\vdash\varphi(x)\}$$ 確かに再ですが、それはセットが $$\{x: \mathbb{N}\models\varphi(x)\}$$ reに近い場所にいる必要があります


これが簡単な要約です。すべての式$\psi$ 算術の言語では($\mathsf{PA}$-おそらく)フォームの1つと同等 $$Q_1x_1Q_2x_2....Q_nx_n\varphi(x_1,...,x_n)$$ ここでそれぞれ $Q_i$ は数量詞です(どちらか $\forall$ または $\exists$)および $\varphi$ 有界量化(形式の量化子)のみを使用します $\forall y<n$ そして $\exists y<n$)。によって定義されたセットの複雑さの上限を取得できます$\psi$ 見て:

  • 最も外側の定量化子 $Q_1$、および

  • 数量詞の交代の数( "$\forall\exists$「または」$\exists\forall$"-これは、数量詞の総数よりはるかに少ない可能性があります)。

外側の数量詞がである上記のタイプの式 $\exists$ そしてそれは $i$-多くの数量詞の交代が呼び出されます $\Sigma_{i+1}$; 外側の数量詞が$\forall$ そしてそれは $i$-多くの数量詞の交代が呼び出されます $\Pi_{i+1}$

算術的階層と計算の複雑さの間の関係の最初の部分は次のとおりです。

セットは、それがによって定義可能である場合に限ります $\Sigma_1$ 式。

こちらをご覧ください。より一般的には、一方では算術的階層とチューリング還元性およびチューリングジャンプとの間には関係があります。

それぞれについて $n\in\mathbb{N}$ 我々は持っています $X\le_T{\bf 0^{(n)}}$ iff $X$ によって定義可能です $\Sigma_{n+1}$ $X$ によって定義可能です $\Pi_{n+1}$ 式。

これはPostによるものです。また、ショーンフィールドの限界補題が興味深いと感じるかもしれません。reではない算術セットの最も単純な自然な例、または実際にチューリング-任意のリセットと同等(「停止問題の補集合」などを除外するため)は、私の意見では、停止するチューリングマシンのインデックスのセットです上のすべての入力。このセットは、しばしば「$\mathsf{Tot}$「(「合計」の場合)、チューリング次数があります ${\bf 0''}$ そして $\Pi_2$ だがしかし $\Sigma_2$

(セットは $\Sigma_n$ それがによって定義可能である場合 $\Sigma_n$ 式、および同様に $\Pi_n$; また、セットは$\Delta_n$ それが両方である場合 $\Sigma_n$ そして $\Pi_n$。「」のようなものはないことに注意してください$\Delta_n$ 式」-一方、 $\Sigma_n$-ネスと $\Pi_n$-nessは構文プロパティであり、 $\Delta_n$-nessは本当に「セマンティック」です。)

別の重要なクラスの例は、有界真理述語の概念から来ています。タルスキによると、セット$$\{\ulcorner\psi\urcorner: \mathbb{N}\models\psi\}$$ 算術ではありません(ここでは "$\ulcorner\cdot\urcorner$"はお気に入りのゲーデル数関数です。ただし、それぞれについて $n$ 真のゲーデル数のセット $\Sigma_n$ 文は確かに $\Sigma_n$。falseのゲーデル数のセット$\Sigma_n$ 文(またはチューリング-同等に真のゲーデル数のセット $\Pi_n$ したがって、文)は $\Pi_n$ だがしかし $\Sigma_n$。同様に、偽のゲーデル数のセット$\Pi_n$ 文(またはチューリング-同等に真のゲーデル数のセット $\Sigma_n$ 文)は $\Sigma_n$ だがしかし $\Pi_n$。今、本当に大きなものを選んでください$n$ (あれは、 $n>1$)。

Related questions

MORE COOL STUFF

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

今週のコミックコンですべての素晴らしいものに追いつく方法

今週のコミックコンですべての素晴らしいものに追いつく方法

サンディエゴコミックコンは今週開幕し、オタクのアナウンス、ポスター、予告編、お気に入りの番組や映画のからかいでいっぱいになります。SDCCは、コンベンションフロア全体の多くのパネルで行われているため、すべてに対応するのは難しい場合があります。

Googleの9千万ドルの和解はアプリ開発者にとってもGoogleにとっても勝利ですか?

Googleの9千万ドルの和解はアプリ開発者にとってもGoogleにとっても勝利ですか?

小さなアプリ開発者は金曜日に発表された法的な和解でグーグルから9千万ドルをこじ開けた。アップルとの同様の合意に続いて熱くなった。金曜日のブログ投稿で、Googleは、Androidメーカーが市場での優位性を悪用してPlayストア経由でのアプリ内購入に対して30%の料金を不当に請求したと主張するアプリ開発者との訴訟を解決するために、9千万ドルを支払うことに合意したと述べました。

RadioShackのTwitterはハッキングされていませんでした、それはただの暗号のサクラです

RadioShackのTwitterはハッキングされていませんでした、それはただの暗号のサクラです

今週、RadioShackのTwitterアカウントは、奇妙なものから完全にひどいものになりました。短い順序で、会社のフィード全体が、バイブレーター、「ビッグティット」(スペルミス)、有名人やその他の企業アカウントを荒らしているツイートなど、NSFW素材の真の山になりました。

ヒッグス粒子から10年後、物理学にとって次の大きなものは何ですか?

ヒッグス粒子から10年後、物理学にとって次の大きなものは何ですか?

大型ハドロン衝突型加速器のトンネル内にあるコンパクトミュオンソレノイド(CMS)検出器。2012年7月4日、CERNの科学者たちは、1960年代に最初に提案された素粒子であるヒッグス粒子の観測を確認しました。

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か月の娘、モナコに母乳育児をしていると語った。

Seguindo Todos os Protocolos (2022), de Fábio Leal

Seguindo Todos os Protocolos (2022), de Fábio Leal

Chico quer transar. Até aí, tudo bem.

多元宇宙—Junø

多元宇宙—Junø

チェーン間アカウントがJunoに登場します。異なるブロックチェーン間でスマートコントラクトの構成可能性と真の相互運用性を提供します。

#brand【ベター・コール・ソール!アメリカのテレビシリーズ「ブレイキング・バッド」に最高のビジネス例が隠されている】・・・ルールクリエイティブ

#brand【ベター・コール・ソール!アメリカのテレビシリーズ「ブレイキング・バッド」に最高のビジネス例が隠されている】・・・ルールクリエイティブ

1.ドラマを見た後、起業する考えはありますか?あなたのビジネスはボトルネックに遭遇しましたか?方向性がなくてわからない場合は、ドラマを追いかけて行くことを心からお勧めします。(?)ブラフではなく、最も完璧なビジネス例を隠すドラマがあります。2.ブレイキング・バッドとその弁護士ドラマ「ブレイキング・バッド」を見た友人たちは、演劇の中で、穏やかな表情で、弁護士のソウル・グッドマンに深く感銘を受けなければなりません。口を開けて、感覚の弱い傭兵の性格を持っています。道徳の面で、サル・グッドマンは無意識のうちに劇に欠かせない役割を果たし、彼自身のシリーズ「絶望的な弁護士」(ベター・コール・ソール)を生み出しました。ウェントウのテキストとビデオは、劇中のソウル・グッドマンのテレビコマーシャルです。製品(サービス)、競争戦略、市場ポジショニング、ブランド名、ターゲット顧客グループ、コミュニケーション軸から広告まで、サル・グッドマンの役割のビジネス設定は、「最低」と見なすことができる超超超超超超完全です。ブランドコミュニケーションのコスト」「変化」のモデル。なぜ?私の分析をご覧ください。3.ソウル・グッドマンの「事業戦略」1.基本情報ブランド名:Saul Goodman製品:法律相談サービス対象顧客:麻薬中毒、飲酒運転、事故など。法律知識の欠如は、一般的に公立弁護士にしか余裕がなく、真面目な弁護士も「特別な法律を持つ消費者」を避けます。恐れてはいけない「​​ニーズ」。コミュニケーションの主軸:この国のすべての男性、女性、子供は有罪判決を受けるまで無実だと思います。地域:アルバカーキ市スローガン:Thrallに電話したほうがいいです!(ベター・コール・ソール)広告:2つの可能性のある犯罪状況をシミュレートします+サウルの主張+サウルのスローガン2をより適切に呼び出します。

メインネットガイド— Arbitrum Odyssey Week 2

メインネットガイド— Arbitrum Odyssey Week 2

最新のアップデートを受け取るために私たちに従ってください。ニュースレター:https://www。

Language