Wenn A auf B reduzierbar ist, ist die Ergänzung von A zu kartierbar auf die Komplement von B zu kartierbar

Question

Ich studiere für mein Finale in der Berechnungstheorie und kämpfe darum, die richtige Art zu beantworten, ob diese Aussage für False zutrifft.

Bis zum Definition von $ leq_m $ Wir können die folgende Anweisung erstellen.

$ w in a iff f (w) in b rightarrow w notin a iff f (w) notin b $

Hier bin ich festgefahren, ich möchte sagen, dass wir uns nur die Zuordnung von A nach B von A nach B geben, wenn es eine gibt, da es sonst nicht die Zuordnung von A nach B gibt, sonst wird es sonst nicht.

Ich weiß nicht, wie ich das richtig formulieren soll oder ob ich überhaupt auf dem richtigen Weg bin.

Answer 1

Wie Dave sagte, folgt es aus einer einfachen logischen Äquivalenz: Stecken Sie jetzt $ p = w in a $ und $ q = f (w) in b $.

$ A leq_m b $ bedeutet, dass es für alle $ W $ ein total berechnetes $ f $ stiriert.

$ w in a leftrightarrow f (w) in b $.

Nach dem obigen Argument ist dies dasselbe wie

$ w notin a leftrightarrow f (w) notin b $.

Oder gleichwertig

$ w in bar {a} leftrightarrow f (w) in bar {b} $.

Und daher zeigt dasselbe $ f $, dass $ bar {a} leq_m bar {b} $.

Answer 2

$ A leq_m b $ implie $ w in a leftrightarrow f (w) in b $ nur auf die andere Weise gilt, wenn $ w in a leftrightarrow f (w) in B $, dann $ a LEQ_M B $, aber nicht revanchiert