closetsolipsist

• closetsolipsist 18 Jul 2024 16:46 UTC

  1 point

  0

  on: Di­ag­o­nal­iza­tion Fixed Point Exercises

  Here are my solutions to the first six problems:

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

  Solution:

  Suppose that $f:S\to P\left(S\right)$ is surjective. Then take $A=\{s\mid s\notin f(s\left)\right\}$. Since $f$ is surjective, there exists$t\in S$ such that $f\left(t\right)=A$. But then $t\in f\left(t\right)\iff t\in A\iff t\notin f\left(t\right)$, a contradiction.

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

  Solution:

  Suppose that $g$ were such a surjection. Then we may define a function $h:S\to T$ by $h\left(s\right)=\left(g\right(s\left)\right)\left(s\right)$. Now, since $g$ is surjective, there exists a $u\in S$ such that $g\left(u\right)=f\circ h$. Passing $u$ as an argument to both sides, we have $\left(g\right(u\left)\right)\left(u\right)=f\left(h\right(u\left)\right)$, so $h\left(u\right)=f\left(h\right(u\left)\right)$, contradicting the fact that $f$ has no fixed points.

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

  Solution:

  Define $h:S\to T$ by $h\left(s\right)=\left(g\right(s\left)\right)\left(s\right)$. Since $g$ is surjective, there exists $u\in S$ such that $g\left(u\right)=f\circ h$. Then take $x=h\left(u\right)$. From my proof above, $x$ is a fixed point of $f$.

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

  Solution:

  Suppose for the sake of contradiction that $f:S\to Comp(S,\{T,F\left\}\right)$ is a surjective computable function. Then the following is computable: $g\left(u\right)=\neg f^{\prime }(u,u)$. Since $f$ is surjective, there exists $v\in S$ such that $f\left(v\right)=g$, but then $f\left(v\right)\left(v\right)=g\left(v\right)=\neg f^{\prime }(v,v)=\neg f\left(v\right)\left(v\right)$, a contradiction.

  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.

  Suppose for the sake of contradiction that there exists such a computable function $halt(x,y)$. Then define a function $f:S\to Comp(S,\{T,F\left\}\right)$ as follows: for any string $x$, if $x$ is not a code for a Turing Machine, let $f\left(x\right)$ be the function sending all strings to $T$. If $x$ is a code for a Turing machine, let $f\left(x\right)$ be the function $y\mapsto halt(x,y)$. I claim this is a surjective computable function from $S$ to $Comp(S,\{T,F\left\}\right)$: to show it is surjective, for any computable function $g:S\to \{T,F\}$, there is a Turing machine which halts precisely when that function returns $T$. Letting $x$ be the code for that Turing machine, we then have $f\left(x\right)=g$. It’s also computable since we assume $halt(x,y)$ is computable. This contradicts the previous result, so we must have been wrong in our initial assumption.

  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.

  Suppose for the sake of contradiction that for some space $X$, $f:X\to Comp(X,S)$ is a surjective continuous function. Let $o:S\to S$ denote the continuous function giving the point on the opposite side of the circle. Then the following is continuous: $g\left(x\right)=o\left(f^{\prime }\right(x,x\left)\right)$. Since $f$ is surjective, there exists $y\in X$ such that $f\left(y\right)=g$, but then $f\left(y\right)\left(y\right)=g\left(y\right)=o\left(f^{\prime }\right(y,y\left)\right)=o\left(f\right(y\left)\right(y\left)\right)$, a contradiction.