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

Is our universe of sets minimal?

Our physics is based on the real numbers. Physicists use the real numbers all over the place: quantum mechanics takes place in a complex Hilbert space, and the complex numbers are isomorphic to pairs of real numbers, while relativity theory takes place in a manifold that is locally isomorphic to a Lorentzian four-dimensional real space.

The real numbers are one of an infinite family of mathematical objects known as real closed fields. Other real closed fields than the real numbers could be used in physics instead—for instance, the hyperreals—and I think we would have the same empirical predictions. But the real numbers are simpler and more elegant: for instance, they are the only Dedekind-complete and the minimal Cauchy-complete real closed field.

At the same time, the mathematics behind our physics lives within a set theoretic universe. That set theoretic universe is generally not assumed to be particularly special. For instance, I know of no one who assumes that our set theoretic universe is isomorphic to Shepherdson’s/Cohen’s minimal model of set theory. On the contrary, it is widely assumed that our set theoretic universe has a standard transitive set model, which implies that it is not minimal, and few people seem to believe the Axiom of Constructibility which would hold in a minimal model.

This seems to me be rationally inconsistent. If we are justified in thinking that the mathematics underlying the physical world is based on a particularly elegant real closed field even though other fields fit our empirical data, we would also be justified in thinking it’s based on a particularly elegant universe of sets even though other universes fit our empirical data.

(According to Shipman, the resulting set theory would be one equivalent to ZF + V=L + “There is no standard model”.)

Properties, relations and functions

Many philosophical discussions presuppose a picture of reality on which, fundamentally, there are objects which have properties and stand in relations. But if we look to how science describes the world, it might be more natural to bring (partial) functions in at the ground level.

Objects have attributes like mass, momentum, charge, DNA sequence, size and shape. These attributes associate values, like 3.4kg, 15~kg m/s north-east, 5C, TTCGAAAAG, 5m and sphericity, to the objects. The usual philosophical way of modeling such attributes is through the mechanism of determinables and determinates. Thus, an object may have the determinable property of having mass and its determinate having mass 3.4kg. We then have a metaphysical law that prohibits objects from having multiple same-level determinates of the same determinable.

A special challenge arises from the numerical or vector structure of many of the values of the attributes. I suppose what we would say is that the set of lowest-level determinates of a determinable “naturally” has the mathematical structure of a subset of a complete ordered field (i.e., of something isomorphic to the set of real numbers) or of a vector space over such a field, so that momenta can be added, masses can be multiplied, etc. There is a lot of duplication here, however: there is one addition operator on the space of lowest-level momentum determinates and another addition operator on the space of lowest-level position determinates in the Newtonian picture. Moreover, for science to work, we need to be able to combine the values of various attributes: we need to be able to divide products of masses by squares of distances to make sense of Newton’s laws of gravitation. But it doesn’t seem to make sense to divide mass properties, or their products, by distance properties, or their squares. The operations themselves would have to be modeled as higher level relations, so that momentum addition would be modeled as a ternary relation between momenta, and there would be parallel algebraic laws for momentum addition and position addition. All this can be done, one operation at a time, but it’s not very elegant.

Wouldn’t it be more elegant if instead we thought of the attributes as partial functions? Thus, mass would be a partial function from objects to the positive real numbers (using a natural unit system) and both Newtonian position and momentum will be partial functions from objects to Euclidean three-dimensional space. One doesn’t need separate operations for the addition of positions and of momenta any more. Moreover, one doesn’t need to model addition as a ternary relation but as a function of two arguments.

There is a second reason to admit functions as first-class citizens into our metaphysics, and this reason comes from intuition. Properties make intuitive sense. But I think there is something intuitively metaphysically puzzling about relations that are not merely to be analyzed into a property of a plurality (such as being arranged in a ball, or having a total mass of 5kg), but where the order of the relata matters. I think we can make sense of binary non-symmetric relations in terms of the analogy of agents and patients: x does something to y (e.g. causes it). But ternary relations that don’t reduce to a property of a plurality, but where order matters, seem puzzling. There are two main technical ways to solve this. One is to reduce such relations to properties of tuples, where tuples are special abstract objects formed from concrete objects. The other is Josh Rasmussen’s introduction of structured mereological wholes. Both are clever, but they do complicate the ontology.

But unary partial functions—i.e., unary attributes—are all we need to reduce both properties and relations of arbitrary finate arity. And unary attributes like mass and velocity make perfect intuitive sense.

First, properties can simply be reduced to partial functions to some set with only one object (say, the number “1” or the truth-value “true” or the empty partial function): the property is had by an object provided that the object is in the domain of the partial function.

Second, n-ary relations can be reduced to n-ary partial functions in exactly the same way: x₁, ..., x_n stand in the relation if and only if the n-tuple (x₁, ..., x_n) lies in the domain of the partial function.

Third, n-ary partial functions for finite n > 1 can be reduced to unary partial functions by currying. For instance, a binary partial function f can be modeled as a unary function g that assigns to each object x (or, better, each object x such that f(x, y) is defined for some y) a unary function g(x) such that (g(x))(y)=f(x, y) precisely whenever the latter is defined. Generalizing this lets one reduce n-ary partial functions to (n − 1)-ary ones, and so on down to unary ones.

There is, however, an important possible hitch. It could turn out that a property/relation ontology is more easily amenable to nominalist reduction than a function ontology. If so, then for those of us like me who are suspicious of Platonism, this could be a decisive consideration in favor of the more traditional approach.

Moreover, some people might be suspicious of the idea that purely mathematical objects, like numbers, are so intimately involved in the real world. After all, such involvement does bring up the Benacerraf problem. But maybe we should say: It solves it! What are the genuine real numbers? It's the values that charge and mass can take. And the genuine natural numbers are then the naturals amongst the genuine reals.

Magnifying sets of real numbers

If S is a set of real numbers and a is a real number, let aS={ax:x∈S} be the set you get by magnifying S by a factor a.

Here's a funny thing. Some sets get bigger when magnified and some get smaller. For instance, if we take the interval [0,1] and magnify it by a factor of two, we get the interval [0,2], which is intuitively "twice as big". But if we take the natural numbers N and magnify them by a factor of two, 2N will be the even natural numbers, and so 2N will intuitively be "twice as small" as N.

Next observe that if R−[0,1] is the real numbers outside the interval [0,1], then 2(R−[0,1])=R−[0,2] is smaller. Magnifying a set by a factor greater than 1 magnifies both the filled in parts of the set and the holes in the set. The effect of this on the intuitive "size" of the set will depend on the interaction between the holes and the filled in parts.

And if we take the Cantor set C, then magnifying it by a factor of three makes the set be intuitively twice as large. I.e., 3C=C∪(2+C). This makes it very intuitive that the dimension of the set is log 2 / log 3 (which is indeed its Hausdorff dimension). For intuitively if we have an n-dimensional set, and we magnify it by a factor of a, its size is aⁿ. So if n is the dimension of the Cantor set, then 2=3ⁿ, and so n is log 2 / log 3.

Hyperintegers, cardinality and probability

Suppose F is an ordered field extending the reals. Then a subset Z of F closed under addition, subtraction and multiplication can be called a set of hyperintegers provided that for any x in F there is a unique n in Z such that n≤x<n+1. Every real closed field has a set of hyperintegers. Given a set of hyperintegers, we can call the non-negative ones "hypernaturals". Introduce the notation [x] for the set of all the hypernaturals smaller than x, for x in F. If x is itself a hypernatural, then [x] = {0,...,x−1}.

Here's an amusing and perhaps surprising little fact:

• If F has hyperintegers Z, and M is an infinite element in F, then [M] has at least the cardinality of the continuum, and in particular is uncountable.

(An infinite element is bigger in absolute value than every real.)

If F is a field of hyperreals, this follows from the fact that [M] is an internal set and not finite.

The proof is very simple. For x in F, let floor(x) be the unique n in Z such that n≤x<n+1. Let A be the set of numbers of the form floor(xM) for x a real number in [0,1). Observe that A is a subset of [M]. Moreover, A has the same cardinality as the set of real numbers in [0,1), since the function f(x)=floor(xM) from the real numbers in [0,1) onto A is one-to-one. To see that it's one-to-one, observe that if f(x)=f(y) for real x and y, then |xM−yM|<1. Unless x=y, then M<1/|x−y|, and M is finite. So x=y. So A has the cardinality of the continuum as the set of real numbers in [0,1) does. Thus, [M] has at least the cardinality of the continuum, since A is a subset of [M].

This helps improve on and slightly generalize the argument here that infinitesimals are too small to model outcomes of infinite fair countable lotteries. Suppose we say that the probability of getting an outcome n in a lottery with possible outcomes 0,1,2,... is an infinitesimal u in an ordered field F extending the reals that has hyperintegers. But u is of the right size (if it's the reciprocal of a hyperinteger) or just slightly too small (otherwise) for being the probability of getting outcome n in a fair lottery on the set [1/u]. But the set [1/u] is much much bigger than the set {0,1,2,...}, since [1/u] is uncountable while {0,1,2,...} is countable.

Countable additivity

One of the Kolmogorov axioms of probability says that if A₁,A₂,... is a countable sequence of disjoint sets, then P(A₁∪A₂∪...)=P(A₁)+P(A₂)+.... I once (when writing my Philosophia Christi paper on fine and coarse tuning) thought that while we had intuitive reason to accept unrestricted additivity (where we do not restrict to countably many sets) and we had intuitive reason to accept finite additivity, there was no in-between reason for accepting countable additivity. Since unrestricted additivity is unsupportable (if you pick a random number between 0 and 1, the probability of picking any particular number is zero, and the sum of the uncountably many probabilities of particular numbers will be zero, but the probability of the union of these singleton sets is one), I thought we should go for finite additivity.

When I thought this, I was wrong, because at the time I didn't know about the phenomenon of non-conglomerability which countable additivity seems to be needed for ruling out. Non-conglomerability is where you have a measure P of probabilities (maybe not technically a probability measure), a set E of events where each event in E has non-zero probability and it is certain that exactly one of the events in E will happen, and an event A such that P(A|B)>x for all B in E but P(A)<x. In such a case, your probability of A is less than x even though you know that no matter which event in B will happen, you will have P(A)>x. This is pathological.

It is well-known that countable additivity entails conglomerability. I like proving this with a two-step argument. The first step is an easy argument that if the set E of events is countably additive, then because P(A)=P((A∩B₁)∪(A∩B₂)∪...)=P(A∩B₁)+P(A∩B₂)+..., if we have P(A|B)>x for all B in E, then P(A)>x as well.

The second step in the proof is that if the members of a set E of disjoint events each have non-zero probabilities, then E has only countably many events in it. This step allows us to rule out non-conglomerability using only countable additivity. This step follows from the following fact about real numbers

1. If E is a set and f is a function that assigns to each member of E a non-negative number such that for any finite sequence x₁,...,x_n of distinct members of E we have f(x₁)+...+f(x_n)≤1, then all but countably many members of E are zero,

by letting f=P and using the finite additivity of P.

If we need countable additivity precisely to rule out non-conglomerability, then we have an explanation of why it only has to be countable additivity. The reason has to do with the property (1) of real numbers, which property in turn follows from the fact that the real numbers are Archimedean—for every pair of positive real numbers x and y, there is a finite natural number n such that nx>y.

In other words, we have countable additivity in the probability calculus precisely because the probability values have a countable-like, i.e., Archimedean, structure. (Another way of seeing the countable structure of the reals: they are the completion of the rationals.)

And if generalize the values of the probability function to a larger, non-Archimedean field, we will need to require something stronger than countable additivity in order to avoid non-conglomerability.

Real numbers

For a long time I've been puzzled—and I still am—by this. Our physics is based on the real numbers (complex numbers, vectors, Banach spaces—all that is built out of real numbers). After all, there are non-standard numbers that can do everything real numbers can. So what reason do we have to think that "the" real numbers are what the world's physics is in fact based on?

I think one can use this to make a nice little argument against the possibility of us coming up with a complete physics—we have no way of telling which of the number fields is the one our world is based on.