Π01言明について理解しておこう (230ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
1(3): BLACKX ◆SvoRwjQrNc 02/23(日)18:43 ID:f/qalxpg(1/5) AAS
ZFCの無矛盾性を信じるだけでは, ZFCでの証明可能性から A (引用者注: Aは算術的定理)が真だとすることは, 一般的に正当化できないのである
ゲーデルの第二不完全性定理によると, ZFCが無矛盾であれば ZFC+「ZFCは矛盾している」 という理論も無矛盾であるが、この理論は真なるΠ01言明「ZFCは無矛盾である」を自明に反証できる。また、同じことだが、偽なる言明「ZFCは矛盾している」を自明に証明できる。
よって、証明されたとしても
無矛盾な理論のなかには, 証明できても偽である算術的言明がある
13(1): White Person 02/24(月)09:00 ID:JuEJqrhb(1/8) AAS
>>1
>ZFCの無矛盾性を信じるだけでは,
>ZFCでの証明可能性から A が真だとすることは,
>一般的に正当化できないのである
>ゲーデルの第二不完全性定理によると,
> ZFCが無矛盾であれば
> ZFC+「ZFCは矛盾している」 という理論も無矛盾であるが、
省10
202(1): poem 04/18(金)11:02 ID:e+YSIK1b(1/3) AAS
>>1 スレタイ、ド真ん中、荒らしじゃない話題
↓
マクロのランダムは多項式時間の終わらない計算がか？
2chｽﾚ:math
223: BLACKX ◆SvoRwjQrNc 08/31(日)05:09 ID:L3ewCuRA(1/3) AAS
ハローBLACKXです。
>>1～>>35はΠ01の大枠についての理解だったけどΠ01の中にもボレル集合と言う計算可能な一部閉集合が存在するものもある
ボレル集合は第一階論理の有効に公理化された理論Tごとに、 Tのすべての完備化の集合であり、Π1~0クラス。
さらに、各サブセットS2^ω Sの各要素がTの完備化を計算し、Tの各完備化がSの要素を計算する ような、効果的に公理化された理論Tが存在する。
したがってΠ01クラスの中にも事実上閉じたクラスであるボレル集合の存在によりディオファントス方程式の問10は近年の同値性からは計算可能な加算集合の導入によりグレーとなり一部否定の否定(一部反例あり)で研究対象が無く止まってしまっているのである。
再帰的に列挙可能な言語は、形式言語の計算可能に列挙可能な サブセットのため、集合Sは原始再帰関数の値域、またはΦです。S が無限であっても、この場合、値の繰り返しのチューリング停止が必要になることがあります。それを第2条件として半決定可能性(REクラス)と計算可能な領域で判断出来れば、
F(x)=1,または,undifedで解ける
省1
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.021s