aがbに還元可能なマッピングの場合、aの補体はbの補体に対して還元可能です

Question

私は計算の理論の最終のために勉強していますが、この声明がfalseに当てはまるかどうかに答える適切な方法に苦労しています。

によって 意味 $ leq_m $の次のステートメントを作成できます。

$ w in iff f（w） in b rightarrow w notin a iff f（w） notin b $

これは私が立ち往生しているところです。そのような計算可能な関数$ f $があるので、AからBがある場合にのみマッピングを提供すると言いたいと思います。

これを正しくフレーズする方法や、正しい軌道に乗っている場合はわかりません。

Answer 1

デイブが言ったように、それは単純な論理的等価性から続きます：$ p leftrightarrow q $は$ lnot p leftrightarrow lnot q $と同じです。ここで、$ p = w を$および$ q = f（w） in b $に入れます。

$ a leq_m b $は、すべての$ w $に対して合計計算可能な$ f $ stがあることを意味します。

$ w in leftrightarrow f（w） in b $。

上記の議論によって、これはと同じです

$ w notin a leftrightarrow f（w） notin b $。

または同等に

$ w in bar {a} leftrightarrow f（w） in bar {b} $。

したがって、同じ$ f $は、$ bar {a} leq_m bar {b} $であることを示しています。

Answer 2

$ a leq_m b $は、a leftrightarrow f（w） in b $のみで$ w in leftrightarrow f（w） in b $ then $ a leq_m b $が、相互のものではありません