seed comments on Diagonalization Fixed Point Exercises

[seed]

Ex 1.

Suppose there is a surjection f : S → P(S). Consider the set $X=\{x\in S|x\notin f(x\left)\right\}$ . Since f is a surjection, X = f(y) for some y in S. Does y lie in X? If $y\in X$ , then $y\in f\left(y\right)$ , so by definition of X, $y\notin X$ . If $y\notin X$ , then $y\notin f\left(y\right)$, so y must belong to X. Contradiction.

Ex 2.

Since there is a function $f:T\to T$ without fixed points, T must have at least two elements. Hence, there is a surjection $s:T\to \{0,1\}$ , which induces a surjection $T^S\to 2^S$ (a function $g:S\to T$ goes to $s\circ g$ ). So, if there were a surjection $S\to T^S$ , there would also be a surjection $S\to 2^S$ , which cannot be by previous exercise.

Ex 4.

Suppose $f:S\to \text{Comp}(S,\{T,F\left\}\right)$ is a computable surjective function. Consider the function $g:S\to \{T,S\}$defined by $g\left(s\right)=\neg f\left(s\right)\left(s\right)$. The function g is computable, therefore there should exist an $s^{\ast }\in S$: $f\left(s^{\ast }\right)=g$ .

Then $f\left(s^{\ast }\right)\left(s^{\ast }\right)=g\left(s^{\ast }\right)=\neg f\left(s^{\ast }\right)\left(s^{\ast }\right)$ . Contradiction.

Ex 5.

Suppose halt(x,y) is a computable function. Consider the function $f:S\to \{T,F\}$: $f\left(s\right)=\neg s\left(s\right)\text{if halt(s,s)}$; T if $\neg \text{halt}(s,s)$

Suppose $s^{\prime }$ is a Turing code of f. Since f halts everywhere, halt(s’, s’) = T. But then $s^{\prime }\left(s^{\prime }\right)=f\left(s^{\prime }\right)=\neg s^{\prime }\left(s^{\prime }\right)$ . Contradiction.

Ex 6.

Suppose that $f:X\to \text{Cont}(X,S)$ is a continuous surjection. Consider the function $g\in \text{Cont}(X,S)$ $g\left(x\right)=-f(x,x)$ (here—f(x, x) is a point diametrically opposed to f(x, x)). f is surjective, hence g = f(y), but then g(y) = f(y,y) = - f(y,y). Contradiction.

Ex 7. A quine in python3:

code = “”“code = {}{}{}{}{}{}{}
print(code.format(‘”’,‘”’,‘”’,code,‘”’,‘”’,‘”’))”””
print(code.format(‘”’,‘”’,‘”’,code,‘”’,‘”’,‘”’))

Ex 8. In python:

import inspect
def f(string):
return string[::-1]
def applytoself(f):
source = inspect.getsource(f)
return f(source)
applytoself(f)

‘\n]1-::[gnirts nruter \n:)gnirts(f fed’

Ex 9.

The formula for $\psi$ is $\forall x\left(\right(x=┌\psi ┐)\to \varphi (x\left)\right)$

Ex 11.

Suppose $\varphi$ is the formula $Bew\left(x\right)\to \psi$ . By the diagonal lemma, there exists a formula A such that $⊢A\leftrightarrow \left(Bew\right(A)\to \psi )$ .

Therefore, $⊢Bew(A\to (Bew\left(A\right)\to \psi \left)\right)$

By property c, $⊢Bew\left(A\right)\to Bew\left(Bew\right(A)\to \psi )$

Again by property c, $⊢Bew\left(Bew\right(A)\to \psi )\to \left(Bew\right(Bew\left(A\right))\to Bew(\psi \left)\right)$

Combining previous two implications, $⊢Bew\left(A\right)\to \left(Bew\right(Bew\left(A\right))\to Bew(\psi \left)\right)$

Since $⊢Bew\left(A\right)\to Bew\left(Bew\right(A\left)\right)$ , we have

$⊢Bew\left(A\right)\to Bew\left(\psi \right)$

Combining this with $⊢Bew\left(\psi \right)\to \psi$ , we get

$⊢Bew\left(A\right)\to \psi$

From this we get $⊢A$ , therefore, $⊢Bew\left(A\right)$ and $⊢\psi$ . QED.

[Rafael Harth]

Don’t know if this is still relevant, but on Ex9

you definitely can’t define $\psi$ this way. Your definition includes the godel numeral for $\psi$, which makes the definition depend on itself.

[Mark Xu]

Self-referential definitions can be constructed with the diagonal lemma. Given that the point of the exercise is to show something similar, you’re right that this solution is probably a bit suspect.

[Rafael Harth]

I might be wrong, but I believe this is not correct. The diagonal lemma lets you construct a sentence that is logically equivalent to something including its own godel numeral. This is different from having its own godel numeral be part of the syntactic definition.

In particular, the former isn’t recursive. It defines one sentence and then, once that sentence is defined, proves something about a second sentence which includes the godel numeral of the first. But what seed attempted (unless I misunderstood it) was to use the godel numeral $┌\psi ┐$ in the syntactic definition for $\psi$, which doesn’t make sense because $┌\psi ┐$ is not defined until $\psi$ is.