Czynski

Jacob, or "Jisk" when there are too many Jacobs about and I need a nickname. Host of the North Oakland LW Meetups, every Tuesday.

Honestly pretty disappointed with the state of the modern LW site, but it's marginally better than other non-blogs so I'm still here.

It should be possible to easily find me from the username I use here, though not vice versa, for interview reasons.

20

Q1

We wish to show that the terms of form a Cauchy sequence, which suffices to demonstrate they converge in a complete space. Take , and WLOG . Then we know from the definition of contraction that . This converges to 0 as m increases, so the sequence is Cauchy.

It's easy to see that this makes the rate of convergence between terms of the Cauchy sequence exponentially quick. Intuitively that seems like it ought to make the sequence converge to its limit with the same speed, but I don't think that can be made rigorous without more steps.

Q2

Take a sequence . This converges to some . Suppose was not a fixed point. Then choose an . A sequence which converges to a limit has, for every , some such that . Then we know that but , contradicting the contraction condition. So there is at least one fixed point, .

Suppose there are two fixed points, , for distinct and . If so, , which again contradicts the contraction condition. So there is at most one fixed point.

Q3

Take as the space , with the usual metric. Define . This is a weak contraction (toward infinity) and has no fixed points within this space.

20

I hit that stumbling block as well. I handwaved it by saying "continue iterating until you have and such that , , and f has no local maxima or local minima on the open interval ", but that doesn't work for the Weierstrass function, which will (I believe) never meet that criterion.

10

My nontrivial answer for Q7, in Python:

with open("foo.py", "r") as foo:

print foo.read()

And for Q8:

def f(string):

return ''.join([chr(ord(c)+1) for c in string])

with open("foo.py", "r") as foo:

print f(foo.read())

20

Ah, yes, that makes sense. I got distracted by the definition of 's topology

and applied it to surjectivity as well as continuity.

30

For #6, I have what looks to me like a counterexample. Possibly I am using the wrong definition of continuous function? I am taking this one as my source.

Take as the topological space the real line under the Euclidean topology. Let be the point in at radians rotation. This is surjective; all points in are mapped to infinitely many times. It is also continuous; For every and neighborhood there is a neighborhood such that ,

The partial functions f(x) from are also continuous by the same argument.

20

I am confused by the introductory statement for #9. Is this an accurate rephrasing?

By representing syntax using arithmetic, it is possible to define a function as follows:

Define with image in , such that:

substitutes the Goedel-number of into (creating ) and then substitutes the Goedel-number of into some fixed formula to get a result in .

10

Minor correction for #7: You probably want to say "nonempty quine" or "nontrivial quine". The trivial quine works in many languages.

For Q2, I believe you aren't done:

You have established that there is at most one fixed point, but not that a fixed point exists.