Mentioned in

Diagonalization Fixed Point Exercises

13Adele Lopez

13Rafael Harth

12Czynski

3Adele Lopez

2Czynski

11Gurkenglas

11Rafael Harth

9James Payor

9Czynski

4Vladimir Mikulik

6Scott Garrabrant

3Czynski

9Czynski

New Comment

13 comments, sorted by Click to highlight new comments since: Today at 11:47 PM

Ex 4

Given a computable function , define a function by the rule . Then is computable, however, because for , we have that and .

Ex 5:

We show the contrapositive: given a function halt, we construct a surjective function from to as follows: enumerate all turing machines, such that each corresponds to a string. Given a , if does not decode to a turing machine, set . If it does, let denote that turning machine. Let with input first run halt; if halt returns , put out , otherwise will halt on input ; run on and put out the result.

Given a computable function , there is a string such that implements (if the turing thesis is true). Then , so that is surjective.

Ex 6:

Let be a parametrization of the circle given by . Given and , write to denote the point , where . First, note that, regardless of the topology on , it holds true that if is continuous, then so is for any , because given a basis element of the circle, we have which is open because is continuous.

Let be a continuous function from to . Then is continuous, and so is the diagonal function . Fix any , then given by is also continuous, but given any , one has and thus . 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 the real line under the Euclidean topology. Let be the point in at radians rotation. This is surjective; all points in are mapped to infinitely many times. It is also continuous; For every and neighborhood there is a neighborhood such that ,

The partial functions f(x) from are also continuous by the same argument.

#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 and let . Suppose that , then let be an element such that . Then by definition, and . So , a contradiction. Hence , so that is not surjective.

Ex 2

Exercise 2: Since is nonempty, it contains at least one element . Let be a function without a fixed point, then , so that and are two different elements in (this is the only thing we shall use the function for).

Let for nonempty. Suppose by contradiction that is surjective. Define a map by the rule . Given any subset , let be given by Since is surjective, we find a such that . Then . This proves that is surjective, which contradicts the result from (a).

Ex 3

Exercise 3: By (2) we know that , and so and where . That means for any . and .

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 as follows:

Define with image in , such that:

substitutes the Goedel-number of into (creating ) and then substitutes the Goedel-number of into some fixed formula to get a result in .

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 S, the cardinality of S is less than the cardinality of the power set P(S) (i.e. there is no surjection from S to P(S)).

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

For nonempty S and T, suppose you are given g:S→TS 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(x)=x. Can you use your proof to describe x in terms of f and g?

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′:C×A→B (given by f′(c,a)=f(c)(a)) is computable. Show that there is no surjective computable function from the set S of all strings to Comp(S,{T,F}).

Show that the previous result implies that there is no computable function halt(x,y) from S×S→{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.

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→Cont(A,B) is continuous if and only if the corresponding function f′:C×A→B (given by f′(c,a)=f(c)(a)) 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.

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 f taking a string 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.

Given two sets A and B of sentences, let Syn(A,B) be the set of all functions from A to B defined by substituting the Gödel number of a sentence in A into a fixed formula. Let S0 be the set of all sentences in the language of arithmetic with one unbounded universal quantifier and arbitrarily many bounded quantifiers, and let S1 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 f∈Syn(S1×S1,S0) 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 ϕ∈S1, there is a formula ψ∈S0 such that ϕ(┌ψ┐)↔ψ.

(Gödel's second incompleteness theorem) In the set S1, there is a formula ¬Bew such that ¬Bew(┌ψ┐) 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 Bew(ψ)→ψ 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 Bew(ψ) is itself provable, (b) Peano arithmetic proves this fact, that is, Peano arithmetic proves Bew(ψ)→Bew(Bew(ψ)), 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.