この理論はペアノ算術の保守的な拡張ですか?

1
Zuhair 2019-09-19 13:05.

基礎となるロジックは、アイデンティティを備えた2ソートされた一階述語論理であり、セットメンバーシップのプリミティブシンボルが追加されています。 $\in$ および二項関係の厳密な $<$。どこ$\in$は、第1ソートオブジェクト(ナチュラルを表す小文字で表される)から第2ソートオブジェクト(ナチュラルのセットを表す大文字で表される)への関係であり、<関係は第1ソートオブジェクトに制限された二項関係です。恒等関係は制限されていません。

公理の分類:

ばらばら: $\forall x,Y (x \neq Y)$

存在: $\exists x (x=x)$

余分な論理的公理:

  1. 秩序だった公理

    非対称: $ x < y \to \neg (y < x) $

    推移的: $ x < y \land y < z \to x < z$

    接続詞: $ x \neq y \leftrightarrow (x < y \lor y < x)$

    十分に設立された: $\exists n \in X \to \exists n \in X \forall m \in X (n \leq m)$

  2. 有限性: $\exists n \in X \to \exists n \in X \forall m \in X (m \leq n)$

  3. 潜在的な無限大: $\forall x \exists y (x < y)$

  4. 拡張性: $\forall X \forall Y [\forall z (z \in X \leftrightarrow z \in Y) \to X=Y]$

  5. セットフォーメーション: if$\phi(m)$ は次の式です $m$ 無料ですが $X$ 無料ではありません、そしてすべての閉鎖: $$\forall n \exists X \forall m (m \in X \leftrightarrow m < n \land \phi(m))$$、は公理です。

この理論はの保守的な拡張ですか $\sf PA$

この理論は、算術プリミティブを簡単に定義できるという考え方です。 $0$は存在の公理と秩序の公理から証明可能であり、後継関数と先行関数の両方は、十分な根拠と有限性の公理と潜在的な無限の公理から証明可能です。帰納法の原理は、集合の形成と秩序化の公理から証明できます。これで、「<」が最初の並べ替えオブジェクトに対して十分に確立された関係であるため、再帰的定義がサポートされます。これは、解決策があるため、このプロパティを使用して、再帰的カウント関数を定義します。$\#$ 集合と数では、その関数が数を数えるという考えなので、任意の集合Kの最初の要素は $K$ (に関して $<$ 関係)は、このカウント関数によってに送信されます $1$、次の大きな要素 $K$ 番号に送信されます $2$ など、カウント関数は再帰的であり、の各要素を送信します。 $K$ の前の要素のその関数の値の後継に $K$ 番号が割り当てられるmin(k)に到達するまで $1$。このカウント関数を使用して、の最大要素に割り当てられた値$K$ のカーディナリティになります $K$、すなわち、の要素の数 $K$。次に、通常の集合論的な方法で、自然の総和を、それらのカーディナリティが総和の引数である互いに素な集合の和集合のサイズとして簡単に定義できます。乗算はもう少し複雑ですが、要素間の間隔が等しい分割セットを使用し、その関数を使用して乗算を簡単に取得できます。正式な後処理は次のとおりです。

再帰的に定義します。 $\#^K (x) = n \leftrightarrow [x=min(K) \land n=1] \lor [x \in K \land x > min(K) \land n= S[\#^K(P^K(x))]$

どこ $P^K(x) = y \leftrightarrow x \in K \land y \in K \land y < x \land \not \exists z \in K (y < z < x)] $

後継者を次のように定義します。 $x=S(y) \iff y < x \land \not \exists z (y < z < x)$

定義: $|K|=n \iff [K \text { is non empty } \land n= \#^K(max(K))] \lor [K \text { is empty } \land n=0]$

定義: $x + y = z \iff \exists X,Y,Z (X \text { disjoint } Y \land Z= X \cup Y \land |X|=x \land |Y|=y \land |Z|= z )$

定義: $X \text { is d partitioning set } \iff \forall L (\exists a,b \in X (a=P^X (b) \land L=\{n|a < n \leq b\}) \lor L=\{n| 0< n \leq min(X)\} \to |L|=d )$

定義: $X^*=\{n| \exists m \in X (0< n \leq m) \}$

定義: $x \times y = z \iff \exists X (X \text { is x partitioning set } \land |X|=y \land z= |X^*|) \lor [x=0 \land y \neq 0 \land z=0]$

1 answers

4
Noah Schweber 2019-09-20 10:29.

元のバージョンの間違いに対処するために真剣に編集されました。興味のある歴史をご覧ください。私が最初にしたすべての主張は真実だと思います、FWIW。


まず、述べたように質問を寝かせましょう。「標準モデル」を考えてみましょう$\mathcal{N}$ 一次部分であなたの理論の $\mathbb{N}$ と二次部分 $\mathcal{P}_{fin}(\mathbb{N})$ (そして通常の解釈 $<$ そして $\in$)。私たちは、自明我々が含まれてきたことから、ここで設定した形成とよくfoundednessを持っているすべてのものを我々はしたいこと(セットの形成は、もともと私をつまずいた、以下の繊細を提起します)

だが $\mathcal{N}$決定可能で、その完全な理論であること、$Th(\mathcal{N})$計算可能です(ここを参照)。PAは本質的に決定不可能であるため、決定可能モデルを持つ理論はPAを解釈できません。したがって、特にあなたの理論はそうではありません。実際、これをPAよりも大幅に低くすることができます。あなたの理論はロビンソン算術さえも解釈しません。

さて、かなり単純な議論は、実際にPA(そして実際にははるかに弱い理論)があなたの理論の一貫性を証明するという証拠にこの観察を持ち上げるべきであるように思われます。ただし、ここにはまだ快適に特定できていない微妙な点がいくつかあるので、後で編集するために残しておきます。以前の編集で私が与えた議論($Th(\mathbb{N}; <)$すべての有界定義可能集合を追加すると、理論のモデルに拡張されます)これ行いますが、深刻なギャップがあります。有界定義可能サブセットを定量化する機能を追加するときに議論する必要があるため、拡張の理解は簡単ではありません。私たちの最初の構造では、新しい有界定義可能集合を生成しません。これは本当だと思いますが、これについての完全な議論はまだありません。


ここで、コメントとその後の編集で生じたより一般的な質問に対処しましょう。

一階述語論理はいつ再帰による定義をサポートできますか?

確かに、本物の秩序だったとしても、一般的にはできません。 $\mathcal{N}_P=(\mathbb{N};<,+)$。明らかに、ここで乗算の再帰的定義を与えることができますが、$\mathcal{N}_P$ 決定可能です $(\mathbb{N};<,+,\times)$ あまりそうではないので、乗算は実際には一次定義可能ではありません $\mathcal{N}_P$

だから、この時点でそれは再帰によって定義がどのように振り返るのは良いアイデアだあるPAで例えば、時には可能。そこで行うことは有限シーケンスを使用することであり、これはペアリング(または道徳的に同等のもの)を介して行います。これは重要な依存関係です。コーディングシーケンスは定義の前に再帰があります。

これで、有限シーケンスを使用して、再帰的定義のインスタンスの「派生」を提供できます。たとえば、「手元に」加算があるとすると、「$a$ タイムズ $b$ 等しい $c$"は長さのシーケンスになります $b$ その最初の用語は $a$、最終学期は $c$、そして違いがあります $a$連続する用語の間。次に、誘導原理を呼び出して、適切な派生が存在することを証明できます。たとえば、乗算の合計は次のようになります。

すべてのために $a,b$、ユニークなものがあります $c$ 「の派生があるように$a$ タイムズ $b$ 等しい $c$、」

これは、おおまかに次のように、誘導によって証明されます。

  • 修正 $a$$b$ のために保持する原則の最小限の反例です $a$

  • 誘導(ベースケースは退屈です)によって、 $d$ 「」の派生があるような一意の番号である$a$ タイムズ $b-1$ 等しい $d$、」そして $\sigma$ その派生である。

  • 追加 $a+d$$\sigma$ 「の派生を与える$a$ タイムズ $b$ 等しい $a+d$"(だから取る $c=a+d$)。一意性を証明するために、「$a$ タイムズ $b$ 等しい $e$"(任意の $e$)の形式が必要です $e$ "の派生に追加$a$ タイムズ $b-1$ 等しい $u$" いくつかのための $u$。しかし帰納法によって$u$ です $d$、 そう $e=u+a=d+a=c$

しかし、これを開始できるのは、派生に関連するすべてのものが定義可能であることを示したです(したがって、シーケンスに関する推論は再帰に先行します)。


これに対する1つの解決策は、目的の部分を明示的にベイクすることです。 $\#$-操作。ただし、基になるロジックに再帰の定義を追加することもできます。これに対する最も単純なアプローチでは、最小不動点ロジック(LFP)が生成されます。LFPの考え方は、「段階的に構築される」定義を可能にすることです。式を考えてみましょう$\varphi$ 単一変数の $x$新しい単項述語記号と一緒に私たちの言語で$U$。から$\varphi$ 地図を取得します $m_\varphi$ 私たちの構造のサブセットについて $\mathcal{M}$$$A\mapsto\{x:\mathcal{M}_A\models\varphi(x)\},$$ どこ $\mathcal{M}_A$ の拡張です $\mathcal{M}$ 通訳で得た $U$ なので $A$

今なら $U$でのみ積極的に発生します$\varphi$、 地図 $m_\varphi$ その点で単調です $A\subseteq B\implies m_\varphi(A)\subseteq m_\varphi(B)$。あること、この手段最小不動点$m_\varphi$ -つまり、セット $LFP_\varphi$ そのような

  • $m_\varphi(LFP_\varphi)=LFP_\varphi$、および

  • いつでも $m_\varphi(X)=X$ 我々は持っています $X\supseteq LFP_\varphi$

基本的に、私たちは考えます $\varphi$ 部分近似から構築しようとしているオブジェクトへの移行方法を説明するように、そして $LFP_\varphi$ は、これまでに投入したすべてのもののセットです。最小不動点ロジックでは、基本的にビルドできます。 $LFP_\varphi$

もちろん、最小不動点は、私たちが望むように常に見えるとは限りません。たとえば、線形順序を考えてみましょう$\mathbb{N}+\mathbb{Z}$。LFPで「偶数」要素を定義しようとする自然な方法があります。$$\varphi(x,U)\equiv [x=0]\vee [\exists y\in U(x=SSy)]$$ (どこ $S$は後継操作であり、もちろん定義可能です)。だが$LFP_\varphi$ に拡張されません $\mathbb{Z}$-すべての部分:の最小不動点 $\varphi$はすべての標準偶数のみのセットです。

最小不動点ロジックについてはあまり知りません。これはコンピュータサイエンスのホットトピックですが、特に有限モデルに焦点が当てられています。その一般的なモデル理論はよく研究されていると思いますが、かなり複雑です。

Related questions

MORE COOL STUFF

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ウィリアム王子が 8 歳のときに寄宿学校に通わせたことについて、ダイアナ妃がどのように感じたかを学びましょう。

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

Shaquille O'Neal は最近、Big Chicken レストラン帝国を拡大するため、ダラス郊外に住居を購入しました。

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90日の婚約者」シーズン9のスター、イヴ・アレラーノが逮捕され、モハメド・アブデルハメドへの暴行容疑で家庭内暴力の罪に問われている.

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマン自身、ポール・ルーベンスと親密です。彼らの友情について彼女が言ったことを発見してください。

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

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

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

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

アレックストレベックはジェパディから簡単な医療休暇を取ります!

アレックストレベックはジェパディから簡単な医療休暇を取ります!

(写真:TCMのゲッティイメージズ、Emma McIntyre)Jeopardyへのビデオメッセージで!ファンのホストであるアレックス・トレベックは、10月からの転倒によって引き起こされた硬膜下血腫、またはバラエティが有益に説明しているように「脳の血栓」の手術を受けたことを明らかにしました。彼は完全に回復することが期待されていますが、彼はジェパディから脱退する予定です!彼が回復している間、しばらくの間スタジオ。

2018年のビデオゲームの予測

2018年のビデオゲームの予測

キングダムハーツIII私たち全員が核のホロコーストで死ぬわけではないと仮定すると、ビデオゲームは2018年に何をもたらすでしょうか?今週のKotakuSplitscreenで、いくつかの予測の時間です。最初のカークと私は、Gravity Rush 2ファン、警察のスワッティングコールで死にかけている罪のない男、そして以前のローガンポールの激しい論争を含む今週のニュース(13:46)について話します来年の大きな予測を立てます(34:16)。

十分な数のスクリーンを用意しているため、航空会社はシートバックエンターテインメントスクリーンを段階的に廃止しています

十分な数のスクリーンを用意しているため、航空会社はシートバックエンターテインメントスクリーンを段階的に廃止しています

写真提供者:Rich Polk / Getty Images飛行機に押し込み、実際の視線ではなく、視線を遮ることのない不自然に幸せな客室乗務員の写真に迎えられる時代は、もうすぐ終わるかもしれません。一部の航空会社では、ほぼすべての旅行で顔を罵倒する機内エンターテインメント画面が出ています。

グーグルマップはもはやあなたの安っぽい仕事について否定的なレビューを投稿することを許可しません

グーグルマップはもはやあなたの安っぽい仕事について否定的なレビューを投稿することを許可しません

写真:AP Googleは、元従業員が残した特定のビジネスレビューを禁止するようにマップポリシーを更新しました。Googleマップの「ユーザー投稿コンテンツポリシー」の新しいセクションで、Googleは「現在または以前の雇用経験について」のレビューを「利益相反」としてラベル付けするようになりました。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

水門の修理

水門の修理

天王星と海王星の間の領域に向かって宇宙を 3/4 g の低温で航行しながら、私たちは数週間燃え続けていました。Dawson Trawler の科学者が Yggdrasil ポータルと呼んだもの。

美しいもの

美しいもの

女性として、私は通常、関係を築くことをためらっています。私はいつも彼らに負けないように苦労しました。私は誰かと共有したいという衝動と戦わなければなりません。

逃走中の女性からの発信

最も家が必要なときに家のように感じる場所はありません。

逃走中の女性からの発信

私は誰よりも移動しました。父が住んでいた土地には、父が 1 歳馬を折るミニチュアの競馬場がありました。

死にゆく男から学んだ最大の人生の教訓

彼は、私たちが持っているのはこの現在の瞬間だけであることを知るのが遅すぎました。

死にゆく男から学んだ最大の人生の教訓

ブラッドは、カーキ色のショート パンツとポロ シャツを着たまま、白いゴルフ グローブを両手で高く引っ張ったまま、ベッドルームに入ってきました。彼は満面の笑みを浮かべながら、「今年は私の人生で最高の年だったと思います!」と言いました。通常は保守的な消費者である私たちは、通常とは異なることをしました。

Language