Rafael Harth comments on Diagonalization Fixed Point Exercises

Rafael Harth 16 Oct 2020 9:31 UTC
2 points
Last time, I got to Ex7. This time, I decided to do them all again before continuing.

Comment on Ex1-6

It gets easy if you just write down what property you want to have in first-order logic.

For example, for Ex1 you want a set $A$ that does the following:

$\forall x f (x) \neq A$

now if we consider a set as a function that takes an element and returns true or false, this becomes

$\forall x \exists y f (x) (y) \neq A (y)$

How do you get such a $y$ ? You can just choose $y := x$ , then

$\forall x f (x) (x) \neq A (x)$

and this is done by defining $A (x) := \neg f (x) (x)$ , i.e., $A := {x : x \notin f (x)}$ which is precisely the solution. This almost immediately answers Ex 1,2,4 and it mostly answers Ex6.

Another quine for Ex7, this time in python:
```
l = chr(123) # opening curly bracket
r = chr(125) # closing curly bracket
q = chr(39) # single quotation mark
t = chr(9) # tab
n = chr(10) # linebreak
z = [n, l+f"z[i]"+r+q+n+t+"+ f"+q]
x = [n+t, l+f"x[i]"+r]
e = [q, l+"e[i]"+r+q+", end="+q+q+")"]
for i in range(0,2):
        print(f'l = chr(123) # opening curly bracket{z[i]}'
        + f'r = chr(125) # closing curly bracket{z[i]}'
        + f'q = chr(39) # single quotation mark{z[i]}'
        + f't = chr(9) # tab{z[i]}'
        + f'n = chr(10) # linebreak{z[i]}'
        + f'z = [n, l+f"z[i]"+r+q+n+t+"+ f"+q]{z[i]}'
        + f'x = [n+t, l+f"x[i]"+r]{z[i]}'
        + f'e = [q, l+"e[i]"+r+q+", end="+q+q+")"]{z[i]}'
        + f'for i in range(0,2):{x[i]}print(f{e[i]}', end='')
```