Andrej Bauer wrote:
There seems to be an open question in regard to this, advertised by Alex Simpson and Martin Escardo: find a topos in which Cauchy reals are not Cauchy complete (i.e., not every Cauchy sequence of reals has a limit). For extra credit, make it so that the Cauchy completion of Cauchy reals is strictly smaller than the Dedekind reals.
this will give me negative credits one way or another, but here it goes: let a = (a_i) be a cauchy sequence of rationals between 0 and 1. (cauchy means |a_m - a_n| < 1/m + 1/n, as in andrej's message.) let b = (b_i) be the subsequence b_i = a_{2^i+3}. b and a are equivalent in the sense from the message, because |a_m - b_n| < 1/m + 1/(2^n+3) < 2/m + 2/n note that |b_i - b_{i+k}| < 1/(2^i+3) + 1/(2^(i+k)+3) < 1/(2^i+2) now define x_i to be the simplest dyadic that falls in the interval between b_i - 1/2^(i+2) and b_i + 1/2^(i+2). in other words, to get x_i, begin adding 1/2 + 1/4 + 1/8... until you overshoot b_i - 1/2^(1+2). if you also overshoot b_i + 1/2^(1+2), and the last summand was 1/2^k, skip it, and try adding 1/2^(k+1), etc. one of them must fall in between. a less childish way to say this is that x_i is the shortest irredundant binary (no infinite sequences of 1) such that |b_i - x_i| < 1/2^(i+2) so x = (x_i) is a cauchy sequence equivalent to b, with |x_i - x_{i+k}| <= |x_i-b_i| + | b_i - b_{i+k}| + |b_{i+k} - x_{i+k}| < < 1/2^(i+2) + 1/2^(i+2) + 1/2^(i+k+2) < < 1/2^i this means that the first i digits of x_i and x_{i+k} coincide. now let X be the binary number such that its first i digits are the same as in x_i, for every i. (if it ends on an infinte sequence of 1s, replace it by the corresponding irredundant representative.) this is clearly a constant cauchy sequence equivalent to x, so it is its limit. since x is equivalent to b |b_m - x_n| <= |b_m - b_n| + |b_n - x_n| < 1/2^(m+3) + 1/2^(n+3) + 1/2^(n+2) < 2/m + 2/n and b is equivalent to a, X is also the limit of a. is there an error in the above reasoning? i can't find it. on the other hand, i printed out the paper by alex and martin, and the conjecture is stated rather strongly, so i guess i must be missing something. -- dusko