Given a computable function ϕ:S↦Comp(S,{T,F}), define a function f:S↦{T,F} by the rule f(s)={Tϕ(s)(s)=FFϕ(s)(s)=T. Then f is computable, however, f∉ϕ(S) because for s∈S, we have that ϕ(s)(s)=F⟹f(s)=T⟹ϕ(s)≠f and ϕ(s)(s)=T⟹f(s)=F⟹ϕ(s)≠f.
Ex 5:
We show the contrapositive: given a function halt, we construct a surjective function f from S to Comp(S,{T,F}) as follows: enumerate all turing machines, such that each corresponds to a string. Given a t∈S, if t does not decode to a turing machine, set f(t)≡F. If it does, let [t] denote that turning machine. Let f(t) with input s∈S first run halt(t,s); if halt returns F, put out F, otherwise [t] will halt on input s; run [t] on s and put out the result.
Given a computable function g:S↦{T,F}, there is a string t∗∈S such that [t∗] implements g (if the turing thesis is true). Then g=f(t∗), so that f is surjective.
Ex 6:
Let h:R↦S be a parametrization of the circle given by h(r)↦(cos(r),sin(r)). Given p∈S and r∈R, write p+r to denote the point h(p′+r), where p′∈h−1({p}). First, note that, regardless of the topology on X, it holds true that if f:X↦S is continuous, then so is fr:x↦f(x)+r for any r∈R, because given a basis element (h(a),h(b)) of the circle, we have f−1r(B)=f−1(h(a)−r,h(b)−r) which is open because f is continuous.
Let ϕ be a continuous function from X to Cont(X,S). Then ϕ′:X×X↦S is continuous, and so is the diagonal function h:x↦ϕ(x,x). Fix any r∈(0,2π), then f:X↦S given by f:x↦(ϕ′(x,x)+r)) is also continuous, but given any x∈X, one has ϕ(x)(x)=ϕ′(x,x)≠ϕ′(x,x)+r=f(x) and thus ϕ(x)≠f. It follows that ϕ is not surjective.
Ex 7:
I did it in java. There’s probably easier ways to do this, especially in other languages, but it still works. It was incredibly fun to do. My basic idea was to have a loop iterate 2 times, the first time printing the program, the second time printing the printing command. Escaping the ” characters is the biggest problem, the main idea here was to have a string q that equals ” in the first iteration and ” + q + ” in the second. That second string (as part of the code in an expression where a string is printed) will print itself in the console output. Code:
Ex 4
Given a computable function ϕ:S↦Comp(S,{T,F}), define a function f:S↦{T,F} by the rule f(s)={Tϕ(s)(s)=FFϕ(s)(s)=T. Then f is computable, however, f∉ϕ(S) because for s∈S, we have that ϕ(s)(s)=F⟹f(s)=T⟹ϕ(s)≠f and ϕ(s)(s)=T⟹f(s)=F⟹ϕ(s)≠f.
Ex 5:
We show the contrapositive: given a function halt, we construct a surjective function f from S to Comp(S,{T,F}) as follows: enumerate all turing machines, such that each corresponds to a string. Given a t∈S, if t does not decode to a turing machine, set f(t)≡F. If it does, let [t] denote that turning machine. Let f(t) with input s∈S first run halt(t,s); if halt returns F, put out F, otherwise [t] will halt on input s; run [t] on s and put out the result.
Given a computable function g:S↦{T,F}, there is a string t∗∈S such that [t∗] implements g (if the turing thesis is true). Then g=f(t∗), so that f is surjective.
Ex 6:
Let h:R↦S be a parametrization of the circle given by h(r)↦(cos(r),sin(r)). Given p∈S and r∈R, write p+r to denote the point h(p′+r), where p′∈h−1({p}). First, note that, regardless of the topology on X, it holds true that if f:X↦S is continuous, then so is fr:x↦f(x)+r for any r∈R, because given a basis element (h(a),h(b)) of the circle, we have f−1r(B)=f−1(h(a)−r,h(b)−r) which is open because f is continuous.
Let ϕ be a continuous function from X to Cont(X,S). Then ϕ′:X×X↦S is continuous, and so is the diagonal function h:x↦ϕ(x,x). Fix any r∈(0,2π), then f:X↦S given by f:x↦(ϕ′(x,x)+r)) is also continuous, but given any x∈X, one has ϕ(x)(x)=ϕ′(x,x)≠ϕ′(x,x)+r=f(x) and thus ϕ(x)≠f. It follows that ϕ is not surjective.
Ex 7:
I did it in java. There’s probably easier ways to do this, especially in other languages, but it still works. It was incredibly fun to do. My basic idea was to have a loop iterate 2 times, the first time printing the program, the second time printing the printing command. Escaping the ” characters is the biggest problem, the main idea here was to have a string q that equals ” in the first iteration and ” + q + ” in the second. That second string (as part of the code in an expression where a string is printed) will print itself in the console output. Code:
package maths;public class Quine{public 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);}}}”:”System.out.print(o+”;System.out.print(o+”package maths;public class Quine{public 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+”System.out.print(o+”+q+”;”+e);}}}