# Diagonalization Fixed Point Exercises

This is the sec­ond of three sets of fixed point ex­er­cises. The first post in this se­quence is here, giv­ing con­text.

1. Re­call Can­tor’s di­ag­o­nal ar­gu­ment for the un­countabil­ity of the real num­bers. Ap­ply the same tech­nique to con­vince your­self than for any set , the car­di­nal­ity of is less than the car­di­nal­ity of the power set (i.e. there is no sur­jec­tion from to ).

2. Sup­pose that a nonempty set has a func­tion from to which lacks fixed points (i.e. for all ). Con­vince your­self that there is no sur­jec­tion from S to , for any nonempty . (We will write the set of func­tions from to ei­ther as or ; these are the same.)

3. For nonempty and , sup­pose you are given a sur­jec­tive func­tion from the set to the set of func­tions from to , and let be a func­tion from to it­self. The pre­vi­ous re­sult im­plies that there ex­ists an in such that . Can you use your proof to de­scribe in terms of and ?

4. Given sets and , let de­note the space of to­tal com­putable func­tions from to . We say that a func­tion from to is com­putable if and only if the cor­re­spond­ing func­tion (given by is com­putable. Show that there is no sur­jec­tive com­putable func­tion from the set of all strings to .

5. Show that the pre­vi­ous re­sult im­plies that there is no com­putable func­tion from which out­puts if and only if the first in­put is a code for a Tur­ing ma­chine that halts when given the sec­ond in­put.

6. Given topolog­i­cal spaces and , let be the space with the set of con­tin­u­ous func­tions from to as its un­der­ly­ing set, and with topol­ogy such that is con­tin­u­ous if and only if the cor­re­spond­ing func­tion (given by ) is con­tin­u­ous, as­sum­ing such a space ex­ists. Con­vince your­self that there is no space which con­tin­u­ously sur­jects onto , where is the cir­cle.

7. In your preferred pro­gram­ming lan­guage, write a quine, that is, a pro­gram whose out­put is a string equal to its own source code.

8. Write a pro­gram that defines a func­tion tak­ing a string as in­put, and pro­duces its out­put by ap­ply­ing to its source code. For ex­am­ple, if re­verses the given string, then the pro­gram should out­puts its source code back­wards.

9. Given two sets and of sen­tences, let be the set of all func­tions from to defined by sub­sti­tut­ing the Gödel num­ber of a sen­tence in into a fixed for­mula. Let be the set of all sen­tences in the lan­guage of ar­ith­metic with one un­bounded uni­ver­sal quan­tifier and ar­bi­trar­ily many bounded quan­tifiers, and let be the set of all for­mu­las with one free vari­ables of that same quan­tifier com­plex­ity. By rep­re­sent­ing syn­tax us­ing ar­ith­metic, it is pos­si­ble to give a func­tion that sub­sti­tutes its sec­ond ar­gu­ment into its first ar­gu­ment. Pick some cod­ing of for­mu­las as nat­u­ral num­bers, where we de­note the num­ber cod­ing for a for­mula as . Us­ing this, show that for any for­mula , there is a for­mula such that .

10. (Gödel’s sec­ond in­com­plete­ness the­o­rem) In the set , there is a for­mula such that holds iff the sen­tence is not prov­able in Peano ar­ith­metic. Us­ing this, show that Peano ar­ith­metic can­not prove its own con­sis­tency.

11. (Löb’s the­o­rem) More gen­er­ally, the di­ag­o­nal lemma states that for any for­mula with a sin­gle free vari­able, there is a for­mula such that, prov­ably, . Now, sup­pose that Peano ar­ith­metic proves that for some for­mula . Show that Peano ar­ith­metic also proves it­self. Some facts that you may need are that (a) when a sen­tence is prov­able, the sen­tence is it­self prov­able, (b) Peano ar­ith­metic proves this fact, that is, Peano ar­ith­metic proves , for any sen­tence and (c) Peano ar­ith­metic proves the fact that if and are prov­able, then is prov­able.

12. (Tarski’s the­o­rem) Show that there does not ex­ist a for­mula with one free vari­able such that for each sen­tence , the state­ment holds.

13. Look­ing back at all these ex­er­cises, think about the re­la­tion­ship be­tween them.

Please use the spoilers fea­ture—the sym­bol ‘>’ fol­lowed by ‘!’ fol­lowed by space -in your com­ments to hide all solu­tions, par­tial solu­tions, and other dis­cus­sions of the math. The com­ments will be mod­er­ated strictly to hide spoilers!

I recom­mend putting all the ob­ject level points in spoilers and in­clud­ing meta­data out­side of the spoilers, like so: “I think I’ve solved prob­lem #5, here’s my solu­tion <spoilers>” or “I’d like help with prob­lem #3, here’s what I un­der­stand <spoilers>” so that peo­ple can choose what to read.

• Ex 8: (in Python, us­ing a re­ver­sal func­tion)

def f(s):
re­turn s[::-1]

dlmt = ’“”“‘
code = “””def f(s):
re­turn s[::-1]

dlmt = ’{}’
code = {}{}{}
code = code.for­mat(dlmt, dlmt, code, dlmt)
print(f(code))”“”
code = code.for­mat(dlmt, dlmt, code, dlmt)
print(f(code))

• Ex 4

Given a com­putable func­tion , define a func­tion by the rule . Then is com­putable, how­ever, be­cause for , we have that and .

Ex 5:

We show the con­tra­pos­i­tive: given a func­tion halt, we con­struct a sur­jec­tive func­tion from to as fol­lows: enu­mer­ate all tur­ing ma­chines, such that each cor­re­sponds to a string. Given a , if does not de­code to a tur­ing ma­chine, set . If it does, let de­note that turn­ing ma­chine. Let with in­put first run halt; if halt re­turns , put out , oth­er­wise will halt on in­put ; run on and put out the re­sult.

Given a com­putable func­tion , there is a string such that im­ple­ments (if the tur­ing the­sis is true). Then , so that is sur­jec­tive.

Ex 6:

Let be a parametriza­tion of the cir­cle given by . Given and , write to de­note the point , where . First, note that, re­gard­less of the topol­ogy on , it holds true that if is con­tin­u­ous, then so is for any , be­cause given a ba­sis el­e­ment of the cir­cle, we have which is open be­cause is con­tin­u­ous.

Let be a con­tin­u­ous func­tion from to . Then is con­tin­u­ous, and so is the di­ag­o­nal func­tion . Fix any , then given by is also con­tin­u­ous, but given any , one has and thus . It fol­lows that is not sur­jec­tive.

Ex 7:

I did it in java. There’s prob­a­bly eas­ier ways to do this, es­pe­cially in other lan­guages, but it still works. It was in­cred­ibly fun to do. My ba­sic idea was to have a loop iter­ate 2 times, the first time print­ing the pro­gram, the sec­ond time print­ing the print­ing com­mand. Es­cap­ing the ” char­ac­ters is the biggest prob­lem, the main idea here was to have a string q that equals ” in the first iter­a­tion and ” + q + ” in the sec­ond. That sec­ond string (as part of the code in an ex­pres­sion where a string is printed) will print it­self in the con­sole out­put. Code:

pack­age maths;pub­lic class Quine{pub­lic 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);}}}“:”Sys­tem.out.print(o+“;Sys­tem.out.print(o+“pack­age maths;pub­lic class Quine{pub­lic 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+“Sys­tem.out.print(o+“+q+“;”+e);}}}

• For #6, I have what looks to me like a coun­terex­am­ple. Pos­si­bly I am us­ing the wrong defi­ni­tion of con­tin­u­ous func­tion? I am tak­ing this one as my source.

Take as the topolog­i­cal space the real line un­der the Eu­clidean topol­ogy. Let be the point in at ra­di­ans ro­ta­tion. This is sur­jec­tive; all points in are mapped to in­finitely many times. It is also con­tin­u­ous; For ev­ery and neigh­bor­hood there is a neigh­bor­hood such that ,

The par­tial func­tions f(x) from are also con­tin­u­ous by the same ar­gu­ment.

• Cur­ry­ing doesn’t pre­serve sur­jec­tivity. As a sim­ple ex­am­ple, you can eas­ily find a sur­jec­tive func­tion , but there are no sur­jec­tive func­tions .

• Ah, yes, that makes sense. I got dis­tracted by the defi­ni­tion of ’s topol­ogy

and ap­plied it to sur­jec­tivity as well as con­ti­nu­ity.

• #1

Let f be such a sur­jec­tion. Con­struct a mem­ber of P(S) out­side f’s image by differ­ing from each f(x) in whether it con­tains x.

#2

A nonempty set has func­tions with­out a fixed point iff it has at least two el­e­ments. It suffices to show that there is no sur­jec­tion from S to S → 2, which is analo­gous to #1.

#3

T has only one el­e­ment. Use that one.

source = “main = putStrLn (\“source = \” ++ show source ++ \“\\n\” ++ source)”
main = putStrLn (“source = ” ++ show source ++ “\n” ++ source)

Is #8 sup­posed to read “Write a pro­gram that takes a func­tion f tak­ing a string as in­put as in­put, and pro­duces its out­put by ap­ply­ing f to its source code. For ex­am­ple, if f re­verses the given string, then the pro­gram should out­puts its source code back­wards.“?

If so, here.

source = “onme = putStrLn $f$ \“source = \” ++ show source ++ \“\\n\” ++ source”
onme f = putStrLn $f$ “source = ” ++ show source ++ “\n” ++ source

• Ex 1

Ex­er­cise 1: Let and let . Sup­pose that , then let be an el­e­ment such that . Then by defi­ni­tion, and . So , a con­tra­dic­tion. Hence , so that is not sur­jec­tive.

Ex 2

Ex­er­cise 2: Since is nonempty, it con­tains at least one el­e­ment . Let be a func­tion with­out a fixed point, then , so that and are two differ­ent el­e­ments in (this is the only thing we shall use the func­tion for).

Let for nonempty. Sup­pose by con­tra­dic­tion that is sur­jec­tive. Define a map by the rule . Given any sub­set , let be given by Since is sur­jec­tive, we find a such that . Then . This proves that is sur­jec­tive, which con­tra­dicts the re­sult from (a).

Ex 3

Ex­er­cise 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 in­ter­pre­ta­tion of this one. Here’s a way to have it work for any fixed (python func­tion) 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 con­fused by the in­tro­duc­tory state­ment for #9. Is this an ac­cu­rate rephras­ing?

By rep­re­sent­ing syn­tax us­ing ar­ith­metic, it is pos­si­ble to define a func­tion as fol­lows:

Define with image in , such that:
sub­sti­tutes the Goedel-num­ber of into (cre­at­ing ) and then sub­sti­tutes the Goedel-num­ber of into some fixed for­mula to get a re­sult in .

• I’m con­fused about Q9.

Given the way is defined, it’s un­clear to me how we en­sure type cor­rect­ness of . In what sense is a set of sen­tences (rather than a set of pairs of sen­tences)? What does an el­e­ment of that set look like?

• Yeah, it is just func­tions that take in two sen­tences and put both their Godel num­bers into a fixed for­mula (with 2 in­puts).

• Minor cor­rec­tion for #7: You prob­a­bly want to say “nonempty quine” or “non­triv­ial quine”. The triv­ial quine works in many lan­guages.

• My non­triv­ial an­swer for Q7, in Python:

with open(“foo.py”, “r”) as foo: