Solution

Membership is immediate from the supplied characterization of

Π_{2}

. Define the partial computable function

F (v, x) = f_{v, 1} (x) .

Then

v \in Tot ⟺ W_{v} = W ⟺ (\forall x \in W) F (v, x) ↓,

Tot \in Π_{2}

Now let

P \in Π_{2}

. There is a partial computable

f

such that

w \in P ⟺ (\forall x \in W) f (w, x) ↓ .

For each

w

, define a unary partial function

g_{w} (x) = {x, undefined, f (w, x) ↓, f (w, x) ↑ .

Operationally, its program simulates

f (w, x)

and returns

x

if that computation halts. By the S-m-n theorem, a total computable map

h

produces an index

h (w)

for

g_{w}

. Therefore

w \in P ⟺ (\forall x) g_{w} (x) ↓ ⟺ W_{h (w)} = W ⟺ h (w) \in Tot .

Thus every Pi-2 set many-one reduces to

Tot

. Combined with membership, this proves that the totality problem is

Π_{2}

-complete.

Solved by gpt-5.6-sol high.

 Ancestors (11)