Diagonalization Fixed Point Exercises

Ex 8: (in Python, using a reversal function)

def f(s):
return s[::-1]

dlmt = '"""'
code = """def f(s):
return s[::-1]

dlmt = '{}'
code = {}{}{}
code = code.format(dlmt, dlmt, code, dlmt)
print(f(code))"""
code = code.format(dlmt, dlmt, code, dlmt)
print(f(code))

Ex 4

Given a computable function $\varphi :S\mapsto \text{Comp}(S,\{T,F\left\}\right)$, define a function $f:S\mapsto \{T,F\}$ by the rule $f\left(s\right)=\{\begin{array}{cc}T& \varphi \left(s\right)\left(s\right)=F\\ F& \varphi \left(s\right)\left(s\right)=T\end{array}$. Then $f$ is computable, however, $f\notin \varphi \left(S\right)$ because for $s\in S$, we have that $\varphi \left(s\right)\left(s\right)=F⟹f\left(s\right)=T⟹\varphi \left(s\right)\ne f$ and $\varphi \left(s\right)\left(s\right)=T⟹f\left(s\right)=F⟹\varphi \left(s\right)\ne f$.

Ex 5:

We show the contrapositive: given a function halt, we construct a surjective function $f$ from $S$ to $\text{Comp}(S,\{T,F\left\}\right)$ as follows: enumerate all turing machines, such that each corresponds to a string. Given a $t\in S$, if $t$ does not decode to a turing machine, set $f\left(t\right)\equiv F$. If it does, let $\left[t\right]$ denote that turning machine. Let $f\left(t\right)$ with input $s\in S$ first run halt$(t,s)$; if halt returns $F$, put out $F$, otherwise $\left[t\right]$ will halt on input $s$; run $\left[t\right]$ on $s$ and put out the result.

Given a computable function $g:S\mapsto \{T,F\}$, there is a string $t^{\ast }\in S$ such that $\left[t^{\ast }\right]$ implements $g$ (if the turing thesis is true). Then $g=f\left(t^{\ast }\right)$, so that $f$ is surjective.

Ex 6:

Let $h:R\mapsto S$ be a parametrization of the circle given by $h\left(r\right)\mapsto \left(\cos \right(r),\sin (r\left)\right)$. Given $p\in S$ and $r\in R$, write $p+r$ to denote the point $h(p^{\prime }+r)$, where $p^{\prime }\in h^{-1}\left(\right\{p\left\}\right)$. First, note that, regardless of the topology on $X$, it holds true that if $f:X\mapsto S$ is continuous, then so is $f_r:x\mapsto f\left(x\right)+r$ for any $r\in R$, because given a basis element $\left(h\right(a),h(b\left)\right)$ of the circle, we have $f_r^{-1}\left(B\right)=f^{-1}\left(h\right(a)-r,h(b)-r)$ which is open because $f$ is continuous.

Let $\varphi$ be a continuous function from $X$ to $\text{Cont}(X,S)$. Then ${\varphi }^{\prime }:X\times X\mapsto S$ is continuous, and so is the diagonal function $h:x\mapsto \varphi (x,x)$. Fix any $r\in (0,2\pi )$, then $f:X\mapsto S$ given by $f:x\mapsto \left({\varphi }^{\prime }\right(x,x)+r))$ is also continuous, but given any $x\in X$, one has $\varphi \left(x\right)\left(x\right)={\varphi }^{\prime }(x,x)\ne {\varphi }^{\prime }(x,x)+r=f\left(x\right)$ and thus $\varphi \left(x\right)\ne f$. It follows that $\varphi$ is not surjective.

Ex 7:

I did it in java. There's probably easier ways to do this, especially in other languages, but it still works. It was incredibly fun to do. My basic idea was to have a loop iterate 2 times, the first time printing the program, the second time printing the printing command. Escaping the " characters is the biggest problem, the main idea here was to have a string q that equals " in the first iteration and " + q + " in the second. That second string (as part of the code in an expression where a string is printed) will print itself in the console output. Code:

package maths;public class Quine{public static void main(String[]args){for(int i=0;i<2;i++){String o=i==1?""+(char)34:"";String q=""+(char)34;q=i==1?q+"+q+"+q:q;String e=i==1?o+"+e);}}}":"System.out.print(o+";System.out.print(o+"package maths;public class Quine{public static void main(String[]args){for(int i=0;i<2;i++){String o=i==1?"+q+""+q+"+(char)34:"+q+""+q+";String q="+q+""+q+"+(char)34;q=i==1?q+"+q+"+q+"+q+"+q:q;String e=i==1?o+"+q+"+e);}}}"+q+":"+q+"System.out.print(o+"+q+";"+e);}}}

For #6, I have what looks to me like a counterexample. Possibly I am using the wrong definition of continuous function? I am taking this one as my source.

Take as the topological space $X$ the real line under the Euclidean topology. Let $f^{\prime }(x,y)$ be the point in $S_1$ at $(x+y)$ radians rotation. This is surjective; all points in $S_1$ are mapped to infinitely many times. It is also continuous; For every $(x,y)\in X,X$ and neighborhood $N\left(f^{\prime }\right(x,y\left)\right)$ there is a neighborhood $M(x,y)$ such that $\forall p\in M$, $f\left(p\right)\in N$

The partial functions f(x) from $X\to S_1$ are also continuous by the same argument.

Thoughts on #10:

My solution for #12:

#1

Let f be such a surjection. Construct a member of P(S) outside f's image by differing from each f(x) in whether it contains x.

#2

A nonempty set has functions without a fixed point iff it has at least two elements. It suffices to show that there is no surjection from S to S -> 2, which is analogous to #1.

#3

T has only one element. Use that one.

#7 Haskell

source = "main = putStrLn (\"source = \" ++ show source ++ \"\\n\" ++ source)"
main = putStrLn ("source = " ++ show source ++ "\n" ++ source)

Is #8 supposed to read "Write a program that takes a function f taking a string as input as input, and produces its output by applying f to its source code. For example, if f reverses the given string, then the program should outputs its source code backwards."?

If so, here.

source = "onme = putStrLn $ f $ \"source = \" ++ show source ++ \"\\n\" ++ source"
onme f = putStrLn $ f $ "source = " ++ show source ++ "\n" ++ source

Ex 1

Exercise 1: Let $f:S\mapsto P\left(S\right)$ and let $A=\{x\in S|x\notin f(x\left)\right\}$. Suppose that $A\in f\left(S\right)$, then let $x\in S$ be an element such that $f\left(x\right)=A$. Then $x\notin f\left(x\right)=A⟹x\in A$ by definition, and $x\in A=f\left(x\right)⟹x\notin A$. So $x\notin A⟺x\in A$, a contradiction. Hence $A\notin f\left(S\right)$, so that $f$ is not surjective.

Ex 2

Exercise 2: Since $T$ is nonempty, it contains at least one element $t_0$. Let $h:T\mapsto T$ be a function without a fixed point, then $t_0\ne h\left(t_0\right)=:t_1$, so that $t_0$ and $t_1$ are two different elements in $T$ (this is the only thing we shall use the function $h$ for).

Let $\Psi :S\mapsto T^S$ for $S$ nonempty. Suppose by contradiction that $\Psi$ is surjective. Define a map $f:S\mapsto P\left(S\right)$ by the rule $f\left(x\right)=\{s\in S|\Psi (x\left)\right(s)=t_0\}$. Given any subset $U\subset S$, let $g:S\mapsto T$ be given by $g:x\mapsto \{\begin{array}{cc}{t}_0& x\in U\\ t_1& x\notin U\end{array}$ Since $\Psi$ is surjective, we find a $s^{\ast }\in S$ such that $\Psi \left(s^{\ast }\right)=g$. Then $f\left(s^{\ast }\right)=U$. This proves that $f$ is surjective, which contradicts the result from (a).

Ex 3

Exercise 3: By (2) we know that $T=\left\{x\right\}$, and so $f=\left\{\right(x,x\left)\right\}$ and $g=\left\{\right(s,h)|s\in S\}$ where $h=\left\{\right(s,x)|s\in S\}$. That means $x=g\left(s\right)\left(s^{\prime }\right)=f^n\left(g\right(s\left)\right(s^{\prime }\left)\right)$ for any $s,s^{\prime }\in S$. and $n\in N$.

Attempted solution and some thoughts on #9:

Q7 (Python):

Y = lambda s: eval(s)(s)
Y('lambda s: print("Y = lambda s: eval(s)(s)\\nY({s!r})")')

Q8 (Python):

Not sure about the interpretation of this one. Here's a way to have it work for any fixed (python function) f:

f = 'lambda s: "\\n".join(s.splitlines()[::-1])'

go = 'lambda s: print(eval(f)(eval(s)(s)))'

eval(go)('lambda src: f"f = {f!r}\\ngo = {go!r}\\neval(go)({src!r})"')

I am confused by the introductory statement for #9. Is this an accurate rephrasing?

By representing syntax using arithmetic, it is possible to define a function $f$ as follows:

Define $f(s\in S_1,t\in S_1)$ with image in $S_0$, such that:
$f$ substitutes the Goedel-number of $t$ into $s$ (creating $s^{\prime }$) and then substitutes the Goedel-number of $s^{\prime }$ into some fixed formula to get a result in $S_0$.

I’m confused about Q9.

Given the way $Syn(A,B)$ is defined, it’s unclear to me how we ensure type correctness of $Syn(S_1\times S_1,S_0)$. In what sense is $S_1\times S_1$ a set of sentences (rather than a set of pairs of sentences)? What does an element of that set look like?

Ex 1.

Ex 2.

Ex 4.

Ex 5.

Ex 6.

Ex 7. A quine in python3:

Ex 8. In python:

Ex 9.

Ex 11.

Minor correction for #7: You probably want to say "nonempty quine" or "nontrivial quine". The trivial quine works in many languages.

Ex8

def apply(f):
    l = chr(123) # opening curly bracket
    r = chr(125) # closing curly bracket
    q = chr(39) # single quotation mark
    n = chr(10) # linebreak
    z = [n+"    ", l+f"z[i]"+r+q+n+"        + f"+q]
    x = [n+"        ", l+f"x[i]"+r]
    e = [q, l+"e[i]"+r+q+")"+n+"    print(f(sourcecode))"]
    sourcecode = ""
    for i in range(0,2):
        sourcecode += (f'def apply(f):{z[i]}'
        + 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'n = chr(10) # linebreak{z[i]}'
        + f'z = [n+"    ", l+f"z[i]"+r+q+n+"        + f"+q]{z[i]}'
        + f'x = [n+"        ", l+f"x[i]"+r]{z[i]}'
        + f'e = [q, l+"e[i]"+r+q+")"+n+"    print(f(sourcecode))"]{z[i]}'
        + f'sourcecode = ""{z[i]}'
        + f'for i in range(0,2):{x[i]}sourcecode += (f{e[i]}')
    print(f(sourcecode))

Last time, I got to Ex7. This time, I decided to do them all again before continuing.

Comment on Ex1-6

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='')

Here are my solutions to the first six problems:

1. Recall Cantor’s diagonal argument for the uncountability of the real numbers. Apply the same technique to convince yourself than for any set $S$, the cardinality of $S$ is less than the cardinality of the power set $P\left(S\right)$ (i.e. there is no surjection from $S$ to $P\left(S\right)$).

Solution:

2. Suppose that a nonempty set $T$ has a function $f$ from $T$ to $T$ which lacks fixed points (i.e. $f\left(x\right)\ne x$ for all $x\in T$). Convince yourself that there is no surjection from S to $S\to T$, for any nonempty $S$. (We will write the set of functions from $A$ to $B$ either as $A\to B$ or $B^A$; these are the same.)

Solution:

3. For nonempty $S$ and $T$, suppose you are given $g:S\to T^S$ a surjective function from the set $S$ to the set of functions from $S$ to $T$, and let $f$ be a function from $T$ to itself. The previous result implies that there exists an $x$ in $T$ such that $f\left(x\right)=x$. Can you use your proof to describe $x$ in terms of $f$ and $g$?

Solution:

4. Given sets $A$ and $B$, let $Comp(A,B)$ denote the space of total computable functions from $A$ to $B$. We say that a function from $C$ to $Comp(A,B)$ is computable if and only if the corresponding function $f^{\prime }:C\times A\to B$ (given by $f^{\prime }(c,a)=f\left(c\right)\left(a\right))$ is computable. Show that there is no surjective computable function from the set $S$ of all strings to $Comp(S,\{T,F\left\}\right)$.

Solution:

5. Show that the previous result implies that there is no computable function $halt(x,y)$ from $S\times S\to \{T,F\}$ which outputs $T$ if and only if the first input is a code for a Turing machine that halts when given the second input.

6. Given topological spaces $A$ and $B$, let $Cont(A,B)$ be the space with the set of continuous functions from $A$ to $B$ as its underlying set, and with topology such that $f:C\to Cont(A,B)$ is continuous if and only if the corresponding function $f^{\prime }:C\times A\to B$ (given by $f^{\prime }(c,a)=f\left(c\right)\left(a\right)$) is continuous, assuming such a space exists. Convince yourself that there is no space $X$ which continuously surjects onto $Cont(X,S)$, where $S$ is the circle.

Solution to 8 implemented in python using zero self-reference, where you can replace f with code for any arbitrary function on string x (escaping characters as necessary):

edit: fixed spoiler tags