Diagonalization Fixed Point Exercises
This is the second of three sets of fixed point exercises. The first post in this sequence is here, giving context.

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

Suppose that a nonempty set has a function from to which lacks fixed points (i.e. for all ). Convince yourself that there is no surjection from S to , for any nonempty . (We will write the set of functions from to either as or ; these are the same.)

For nonempty and , suppose you are given a surjective function from the set to the set of functions from to , and let be a function from to itself. The previous result implies that there exists an in such that . Can you use your proof to describe in terms of and ?

Given sets and , let denote the space of total computable functions from to . We say that a function from to is computable if and only if the corresponding function (given by is computable. Show that there is no surjective computable function from the set of all strings to .

Show that the previous result implies that there is no computable function from which outputs if and only if the first input is a code for a Turing machine that halts when given the second input.

Given topological spaces and , let be the space with the set of continuous functions from to as its underlying set, and with topology such that is continuous if and only if the corresponding function (given by ) is continuous, assuming such a space exists. Convince yourself that there is no space which continuously surjects onto , where is the circle.

In your preferred programming language, write a quine, that is, a program whose output is a string equal to its own source code.

Write a program that defines a function taking a string as input, and produces its output by applying to its source code. For example, if reverses the given string, then the program should outputs its source code backwards.

Given two sets and of sentences, let be the set of all functions from to defined by substituting the Gödel number of a sentence in into a fixed formula. Let be the set of all sentences in the language of arithmetic with one unbounded universal quantifier and arbitrarily many bounded quantifiers, and let be the set of all formulas with one free variables of that same quantifier complexity. By representing syntax using arithmetic, it is possible to give a function that substitutes its second argument into its first argument. Pick some coding of formulas as natural numbers, where we denote the number coding for a formula as . Using this, show that for any formula , there is a formula such that .

(Gödel’s second incompleteness theorem) In the set , there is a formula such that holds iff the sentence is not provable in Peano arithmetic. Using this, show that Peano arithmetic cannot prove its own consistency.

(Löb’s theorem) More generally, the diagonal lemma states that for any formula with a single free variable, there is a formula such that, provably, . Now, suppose that Peano arithmetic proves that for some formula . Show that Peano arithmetic also proves itself. Some facts that you may need are that (a) when a sentence is provable, the sentence is itself provable, (b) Peano arithmetic proves this fact, that is, Peano arithmetic proves , for any sentence and (c) Peano arithmetic proves the fact that if and are provable, then is provable.

(Tarski’s theorem) Show that there does not exist a formula with one free variable such that for each sentence , the statement holds.

Looking back at all these exercises, think about the relationship between them.
Please use the spoilers feature—the symbol ‘>’ followed by ‘!’ followed by space in your comments to hide all solutions, partial solutions, and other discussions of the math. The comments will be moderated strictly to hide spoilers!
I recommend putting all the object level points in spoilers and including metadata outside of the spoilers, like so: “I think I’ve solved problem #5, here’s my solution <spoilers>” or “I’d like help with problem #3, here’s what I understand <spoilers>” so that people can choose what to read.
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 ϕ:S↦Comp(S,{T,F}), define a function f:S↦{T,F} by the rule f(s)={Tϕ(s)(s)=FFϕ(s)(s)=T. Then f is computable, however, f∉ϕ(S) because for s∈S, we have that ϕ(s)(s)=F⟹f(s)=T⟹ϕ(s)≠f and ϕ(s)(s)=T⟹f(s)=F⟹ϕ(s)≠f.
Ex 5:
We show the contrapositive: given a function halt, we construct a surjective function f from S to Comp(S,{T,F}) as follows: enumerate all turing machines, such that each corresponds to a string. Given a t∈S, if t does not decode to a turing machine, set f(t)≡F. If it does, let [t] denote that turning machine. Let f(t) with input s∈S first run halt(t,s); if halt returns F, put out F, otherwise [t] will halt on input s; run [t] on s and put out the result.
Given a computable function g:S↦{T,F}, there is a string t∗∈S such that [t∗] implements g (if the turing thesis is true). Then g=f(t∗), so that f is surjective.
Ex 6:
Let h:R↦S be a parametrization of the circle given by h(r)↦(cos(r),sin(r)). Given p∈S and r∈R, write p+r to denote the point h(p′+r), where p′∈h−1({p}). First, note that, regardless of the topology on X, it holds true that if f:X↦S is continuous, then so is fr:x↦f(x)+r for any r∈R, because given a basis element (h(a),h(b)) of the circle, we have f−1r(B)=f−1(h(a)−r,h(b)−r) which is open because f is continuous.
Let ϕ be a continuous function from X to Cont(X,S). Then ϕ′:X×X↦S is continuous, and so is the diagonal function h:x↦ϕ(x,x). Fix any r∈(0,2π), then f:X↦S given by f:x↦(ϕ′(x,x)+r)) is also continuous, but given any x∈X, one has ϕ(x)(x)=ϕ′(x,x)≠ϕ′(x,x)+r=f(x) and thus ϕ(x)≠f. It follows that ϕ 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′(x,y) be the point in S1 at (x+y) radians rotation. This is surjective; all points in S1 are mapped to infinitely many times. It is also continuous; For every (x,y)∈X,X and neighborhood N(f′(x,y)) there is a neighborhood M(x,y) such that ∀p∈M, f(p)∈N
The partial functions f(x) from X→S1 are also continuous by the same argument.
Currying doesn’t preserve surjectivity. As a simple example, you can easily find a surjective function 2×2→2, but there are no surjective functions 2→22.
Ah, yes, that makes sense. I got distracted by the definition of Cont(A,B)’s topology
and applied it to surjectivity as well as continuity.
#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↦P(S) and let A={x∈Sx∉f(x)}. Suppose that A∈f(S), then let x∈S be an element such that f(x)=A. Then x∉f(x)=A⟹x∈A by definition, and x∈A=f(x)⟹x∉A. So x∉A⟺x∈A, a contradiction. Hence A∉f(S), so that f is not surjective.
Ex 2
Exercise 2: Since T is nonempty, it contains at least one element t0. Let h:T↦T be a function without a fixed point, then t0≠h(t0)=:t1, so that t0 and t1 are two different elements in T (this is the only thing we shall use the function h for).
Let Ψ:S↦TS for S nonempty. Suppose by contradiction that Ψ is surjective. Define a map f:S↦P(S) by the rule f(x)={s∈SΨ(x)(s)=t0}. Given any subset U⊂S, let g:S↦T be given by g:x↦{t0x∈Ut1x∉U Since Ψ is surjective, we find a s∗∈S such that Ψ(s∗)=g. Then f(s∗)=U. This proves that f is surjective, which contradicts the result from (a).
Ex 3
Exercise 3: By (2) we know that T={x}, and so f={(x,x)} and g={(s,h)s∈S} where h={(s,x)s∈S}. That means x=g(s)(s′)=fn(g(s)(s′)) for any s,s′∈S. and n∈N.
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∈S1,t∈S1) with image in S0, such that:
f substitutes the Goedelnumber of t into s (creating s′) and then substitutes the Goedelnumber of s′ into some fixed formula to get a result in S0.
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(S1×S1,S0). In what sense is S1×S1 a set of sentences (rather than a set of pairs of sentences)? What does an element of that set look like?
Yeah, it is just functions that take in two sentences and put both their Godel numbers into a fixed formula (with 2 inputs).
Minor correction for #7: You probably want to say “nonempty quine” or “nontrivial quine”. The trivial quine works in many languages.
My nontrivial answer for Q7, in Python:
with open(“foo.py”, “r”) as foo:
print foo.read()
And for Q8:
def f(string):
return ″.join([chr(ord(c)+1) for c in string])
with open(“foo.py”, “r”) as foo:
print f(foo.read())