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.