【第12回関西すうがく徒のつどい2日目】Friedberg-Muchnikの定理と有限害優先論法 #kansaimath
-
- いいね！0
関東すうがく徒のつどい
@kantotsudoi
よってf=Φ^A_jなるjが存在し， j∈A'⇒Φ^A_j(j)=f(j)=Φ^A_j(j)+1(矛盾) ￢j∈A'⇒Φ^A_j(j)↑⇔f(j)↑(全域性に矛盾) が分かる．いずれにしても矛盾したのでOK．■ #kansaimath
2019-10-28 00:56:03
関東すうがく徒のつどい
@kantotsudoi
thm[limit lemma, Shoenfield])A⊂ωとするとき，TFAE 1)A:limit computable，即ちg:ω^2→ω;comp. s.t. χ_A(x)=lim_{s→∞}g(x,s)なるgが存在する． 2)A:Δ^0_2-set，即ち∃R,S≦∅∀x[x∈A⇔∃y∀z[<x,y,z>∈R]∧∀y∃z[<x,y,z>∈S]] 3)A≦∅' #kansaimath
2019-10-28 01:11:06
関東すうがく徒のつどい
@kantotsudoi
1)⇒2):χ_A(x)=lim_{s→∞}g(x,s)なるAを取る．このとき x∈A⇔lim_{s→∞}g(x,s)=1⇔∃y∀z[y≦z∧g(x,z)=1] x∉A⇔lim_{s→∞}g(x,s)=0⇔∃y∀z[y≦z∧g(x,z)=0] と書かれるので，A∈Σ^0_2⋂Π^0_2=Δ^0_2である. #kansaimath
2019-10-28 01:23:46
関東すうがく徒のつどい
@kantotsudoi
2)⇒3):x,yを固定したとき∀z[<x,y,z>∈R]は∅'を用いて判定可能(<x,y,z>∈Rでないzを探索するプログラムが停止しないことと同値なので)．よってxに対して∃y∀z[<x,y,z>∈R](⇔x∈A)は∅'-c.e.である．同様にして∃y∀z[<x,y,z>∉S](⇔x∈\bar{A})も∅'-c.e.であり，A≦∅'が分かる． #kansaimath
2019-10-28 01:35:42
関東すうがく徒のつどい
@kantotsudoi
3)⇒1):∅'はc.e.集合なのでenumeration(K_s)_{s∈ω}(即ちK_sはfin.setの増加列で∅'=∪{K_s|s∈ω}および(x,s)→χ_{K_s}(x)がcomp.)．仮定よりχ_A=Φ^{∅'}_eなるeが取れて，g:ω^2→ωを次のように定められる：Φ^{K_S}_{e,s}(x)↓ならばg(x,s)=Φ^{K_S}_e(x)とし，そうでないならば0とする．#kansaimath
2019-10-28 02:02:20
関東すうがく徒のつどい
@kantotsudoi
thm)Low simple setが存在する prf)各eに対して次の要件を満たすようにすればよい． ・P_e:|W_e|=∞⇒W_e⋂A≠∅ ・N_e:∃^∞s[Φ^{A_s}_{e,s}(e)↓⇒Φ^A_e(e)↓] 十分であることは，A':limit comp.を保証するために次の成立を保証したいことによる：#kansaimath
2019-10-28 02:18:17
関東すうがく徒のつどい
@kantotsudoi
・Φ^{A_s}_e↓⇒∀^∞s[Φ^{A_s}_{e,s}(e)↓](これはOK) ・Φ^{A_s}_e↑⇒∀^∞s[Φ^{A_s}_{e,s}(e)↑] この2つ目の対偶を課していることから十分性が分かる． さて，要件に優先度P_0<N_0<P_1<N_1<…P_e<N_e<… で入れる．N_eのstage sでのrestraintをr(e,s)と書き， r(e,0)=0としておく．#kansaimath
2019-10-28 02:25:37
関東すうがく徒のつどい
@kantotsudoi
P_eの戦略)既にW_{e,s}⋂A_s≠∅であれば何もしない．そうでないとき，∃x∈W_{e,s}[x>2e∧x>max r(i,s)]だったらばA_sに対応するxを投入する． N_eの戦略)Φ^{A_s}_{e,s}(e)↓であれば，計算中にorcleに尋ねられた値の最大値をr(e,s+1)とする．そうでないときr(e,s+1)=r(e,s)とする． #kansaimath
2019-10-28 02:33:11
関東すうがく徒のつどい
@kantotsudoi
stage sでは，e≦sなるP_e戦略とN_e戦略のみを稼働させればよい(構成終了) あとは #十分考えれば自明 なのでOK．■ rem)\bar{A}が無限であるとは各P_eは高々1回しか元を投入しない． #kansaimath
2019-10-28 02:37:30
ぴあのん
@piano2683
つどい3日目セミナーいつぶりだったか調べてたけど少なくとも2014年9月の第5回つどい以降はルール追加だったらしい togetter.com/li/719476 #kansaimath
2019-10-28 03:09:40
