closetsolipsist

Posts
Comments

Posts

Comments

Comment by closetsolipsist on Diagonalization Fixed Point Exercises · 2024-07-18T16:46:48.712Z · LW · GW

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

Solution:

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

2. Suppose that a nonempty set $T$ has a function $f$ from $T$ to $T$ which lacks fixed points (i.e. $f (x) \neq 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 (s) = (g (s)) (s)$ . Now, since $g$ is surjective, there exists a $u \in S$ such that $g (u) = f \circ h$ . Passing $u$ as an argument to both sides, we have $(g (u)) (u) = f (h (u))$ , so $h (u) = f (h (u))$ , 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 (x) = x$ . Can you use your proof to describe $x$ in terms of $f$ and $g$ ?

Solution:

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

4. Given sets $A$ and $B$ , let $C o m p (A, B)$ denote the space of total computable functions from $A$ to $B$ . We say that a function from $C$ to $C o m p (A, B)$ is computable if and only if the corresponding function $f^{'} : C \times A \to 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 $C o m p (S, {T, F})$ .

Solution:

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

5. Show that the previous result implies that there is no computable function $h a l t (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 $h a l t (x, y)$ . Then define a function $f : S \to C o m p (S, {T, F})$ as follows: for any string $x$ , if $x$ is not a code for a Turing Machine, let $f (x)$ be the function sending all strings to $T$ . If $x$ is a code for a Turing machine, let $f (x)$ be the function $y \mapsto h a l t (x, y)$ . I claim this is a surjective computable function from $S$ to $C o m p (S, {T, F})$ : 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 (x) = g$ . It's also computable since we assume $h a l t (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 $C o n t (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 C o n t (A, B)$ is continuous if and only if the corresponding function $f^{'} : C \times A \to 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 $C o n t (X, S)$ , where $S$ is the circle.

Suppose for the sake of contradiction that for some space $X$ , $f : X \to C o m p (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 (x) = o (f^{'} (x, x))$ . Since $f$ is surjective, there exists $y \in X$ such that $f (y) = g$ , but then $f (y) (y) = g (y) = o (f^{'} (y, y)) = o (f (y) (y))$ , a contradiction.

User info

Posts

Comments