定理の証明

困難は分割せよ

3. ^{定理の証明}

• A6≤T B^かつB 6≤T A^{であることは，各}e ∈ω^{に対し要件}(requirement) R⁰_e: χ_A 6= Φ^B_e, AはBからΦ_eによっては計算されない

R¹e: χ_B 6= Φ^A_e B はAからΦeによっては計算されない

が成立することと同値．

• R⁰eが成立することは，あるx∈ωに対してΦ^B_e(x)↑^または

χ_A(x)6= Φ^B_e(x)↓となることと同値．このxをR⁰e の成立の証拠(witness) という．R¹_e ^{についても同様．}

• 全ての要件を成立させるような戦略を一足飛びに考えるのは大変なので，

個々の要件Rⁱeを成立させるための小さな戦略(Rⁱe戦略)を作り，それらを 並列に稼動させることを考える．

23/34

困難は分割せよ

3. ^{定理の証明}

• A6≤T B^かつB 6≤T A^{であることは，各}e ∈ω^{に対し要件}(requirement) R⁰_e: χ_A 6= Φ^B_e, AはBからΦ_eによっては計算されない

R¹e: χ_B 6= Φ^A_e B はAからΦeによっては計算されない

が成立することと同値．

• R⁰eが成立することは，あるx∈ωに対してΦ^B_e(x)↑^または

χ_A(x)6= Φ^B_e(x)↓となることと同値．このxをR⁰e の成立の証拠(witness) という．R¹_e ^{についても同様．}

• 全ての要件を成立させるような戦略を一足飛びに考えるのは大変なので，

個々の要件Rⁱeを成立させるための小さな戦略(Rⁱe戦略)を作り，それらを 並列に稼動させることを考える．

R

ⁱe

戦略

3. ^{定理の証明} R⁰e戦略がどのようになっているべきかを考える．(R¹e についても同様)

Rⁱe戦略(理想)

1. 証拠の候補x∈ωを選ぶ．

2. Φ^B_e^s(x)↓かどうかをチェックし，もしそうならχ_As(x)6= Φ^B_e^s(x)となるよ うにA_sを変更する

B_sを変更してもΦ^B_e^s(x)の計算結果が変わるとは限らないので．

．

そうでないなら，計算を続ける．

24/34

R

ⁱe

戦略

3. ^{定理の証明} R⁰e戦略がどのようになっているべきかを考える．(R¹e についても同様)

Rⁱe戦略(理想)

1. 証拠の候補x∈ωを選ぶ．

2. Φ^B_e^s(x)↓かどうかをチェックし，もしそうならχ_As(x)6= Φ^B_e^s(x)となるよ うに A_sを変更する．

そうでないなら，計算を続ける．

ところが，Φ^B_e^s(x)↓^{かどうかは}(K₀ の決定不能性より)有限ステップでは判定 できない条件である．よって，「今のところΦ^B_e,s^s(x)↓であるかどうか」というこ としか知ることはできない．B_sが有限集合であることからΦ^B_e,s^s(x)↓^は実際に 有限ステップで判定可能な条件である．

R

ⁱe

戦略

3. ^{定理の証明} R⁰e戦略がどのようになっているべきかを考える．(R¹e についても同様)

Rⁱe戦略(修正版1)

1. 証拠の候補x∈ωを選ぶ．

2. Φ^B_e,s^s(x)↓かどうかをチェックし，もしそうならχ_As(x)6= Φ^B_e^s(x)となるよ うに A_sを変更する．そうでないなら，計算を続ける．

ところが，Φ^B_e^s(x)↓^{かどうかは}(K₀ の決定不能性より)有限ステップでは判定 できない条件である．よって，「今のところΦ^B_e,s^s(x)↓であるかどうか」というこ としか知ることはできない．B_sが有限集合であることからΦ^B_e,s^s(x)↓^は実際に 有限ステップで判定可能な条件である．

24/34

R

ⁱe

戦略

3. ^{定理の証明} R⁰e戦略がどのようになっているべきかを考える．(R¹e についても同様)

Rⁱe戦略(修正版1)

1. 証拠の候補x∈ωを選ぶ．

2. Φ^B_e,s^s(x)↓かどうかをチェックし，もしそうならχ_As(x)6= Φ^B_e^s(x)となるよ うに A_sを変更する．そうでないなら，計算を続ける．

また，一度A_sに投入した自然数を取り出すことはできないので，χ_As(x) = 1 をχ_As+1(x) = 0に変更することはできない．つまり，x6∈A_sだったものを x∈A_s+1 にする，という変更しかできない．よって証拠の候補xはx6∈A_sと なるように選ぶ必要がある．A_sは有限集合なので，このようなxを必ず取るこ とができる．

R

ⁱe

戦略

3. ^{定理の証明} R⁰e戦略がどのようになっているべきかを考える．(R¹e についても同様)

Rⁱe戦略(修正版2)

1. 証拠の候補x∈ωをx6∈A_sとなるように選ぶ．

2. Φ^B_e,s^s(x)↓かどうかをチェックし，もしそうならΦ^B_e^s(x) = 0のときはxを A_sに投入する．そうでないなら，計算を続ける．

また，一度A_sに投入した自然数を取り出すことはできないので，χ_As(x) = 1 をχ_As+1(x) = 0に変更することはできない．つまり，x6∈A_sだったものを x∈A_s+1 にする，という変更しかできない．よって証拠の候補xはx6∈A_sと なるように選ぶ必要がある．A_sは有限集合なので，このようなxを必ず取るこ とができる．

24/34

ドキュメント内 Friedberg-Muchnikの定理と有限害優先論法 (ページ 40-48)