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

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)$).

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.)

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$?

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)$.

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.

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

8. 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.

9. 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 $S_0$ be the set of all sentences in the language of arithmetic with one unbounded universal quantifier and arbitrarily many bounded quantifiers, and let $S_1$ 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\in Syn(S_1\times S_1,S_0)$ 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 $\phi$ as $┌\phi ┐$. Using this, show that for any formula $\varphi \in S_1$, there is a formula $\psi \in S_0$ such that $\varphi (┌\psi ┐)\leftrightarrow \psi$.

10. (Gödel's second incompleteness theorem) In the set $S_1$, there is a formula $\neg Bew$ such that $\neg Bew(┌\psi ┐)$ holds iff the sentence $\psi$ is not provable in Peano arithmetic. Using this, show that Peano arithmetic cannot prove its own consistency.

11. (Löb's theorem) More generally, the diagonal lemma states that for any formula $\varphi$ with a single free variable, there is a formula $\psi$ such that, provably, $\varphi (┌\psi ┐)\leftrightarrow \psi$. Now, suppose that Peano arithmetic proves that $Bew\left(\psi \right)\to \psi$ for some formula $\psi$. Show that Peano arithmetic also proves $\psi$ itself. Some facts that you may need are that (a) when a sentence $\psi$ is provable, the sentence $Bew\left(\psi \right)$ is itself provable, (b) Peano arithmetic proves this fact, that is, Peano arithmetic proves $Bew\left(\psi \right)\to Bew\left(Bew\right(\psi \left)\right)$, for any sentence $\psi$ and (c) Peano arithmetic proves the fact that if $\chi$ and $\chi \to \zeta$ are provable, then $\zeta$ is provable.

12. (Tarski's theorem) Show that there does not exist a formula $\varphi$ with one free variable such that for each sentence $\psi$, the statement $\varphi (┌\psi ┐)\leftrightarrow \psi$ holds.

13. 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.