On finitistic addition

By a finite alphabet encoding of a set X, such as the real numbers, I mean a one-to-one function ψ from X to countably infinite sequences s₀s₁... taken from some finite alphabet. For instance, standard decimal encoding, with a decision whether to have infinite sequences of trailing nines or not, is a finite alphabet encoding of the reals, with the alphabet consisting of ten digits, a decimal point and a sign. Write ψ_k(x) for the kth symbol in the encoding ψ(x) of x.

A function f from Rⁿ to R is finitistic with respect to a finite alphabet encoding ψ provided that there is a function h from the natural numbers to the natural numbers such that the value of ψ_k(f(x₁,...,x_n)) depends only on the first h(k) symbols in each of ψ(x₁), ..., ψ(x_n).

This concept is related to concepts in “real computation”, but I am not requiring that the finite dependences be all implemented by the same Turing machine.

Theorem: Let X be any infinite divisible commutative group. Then addition on X is not finitistic with respect to any finite alphabet encoding.

A divisible group X is one where for every x ∈ X there is a y such that ny = x. The real numbers under addition are divisible. So are the rationals. So is the set of all rotations in the plane.

This has a somewhat unhappy consequence for Information Processing Finitism. If reality encodes real numbers in a discrete way consistent with IPF, we should not expect each real number to have a uniquely specified encoding.

Proof of Theorem: Suppose addition is finitistic with respect to ψ. Let F be the algebra on X generated by the sets of the form {x : ψ_k(x) = α}. If addition is finitistic, then for any A ∈ F, there is a finite sequence of pairs (A₁,B₁), ..., (A_N,B_N) of sets in F such that

1. {(x,y) : x + y ∈ A} = ⋃_i(A_i×B_i).

Therefore:

2. x + y ∈ A if and only if x ∈ ⋃{A_i : y ∈ B_i}.

Thus:

3.  − y + A =  ∪ {A_i : y ∈ B_i}.

Now as y varies over the members of X, there are at most 2^N different sets generated by the right hand side. Thus,  − y + A can take on only finitely many values. Hence, A has only finitely many translates.

But this is impossible. Let Z be the set of x such that x + A = A. This is an additive subgroup of X. Note that x + Z = y + Z iff x − y ∈ Z iff (x−y) + A = A iff x + A = y + A. Thus, if there are only finitely many x + A, there are finitely many x + Z. Hence X/Z is a finite group. Let n be its order. Then n[x] = 0 for every coset [x] = x + Z in R/Z. For any x ∈ X choose y such that ny = x. Then n[y] = 0, and so [x] = 0, thus Z = X. It follows that A is invariant under every translation, so it must be either ⌀ or X. Hence |F| ≤ 2, which is absurd since F is infinite as X is infinite and ψ is one-to-one.

(I got the main idea for this proof from the answer here.)