Radix notation and toposes - MathOverflow

Radix notation and toposes

2010-12-18T04:30:33Z

In classical logic plus ZF, the field of real numbers admits infinitely many isomorphic realizations as a numeral system --- as the radix varies. The intuitionistic status of these systems seems less clear however. First of all, the notion of "field" has several distinct intuitionistic interpretations (e.g. non-zero implies invertible; non-invertible implies zero; invertible or zero). And even with a way to set up things to make these numeral systems fields in some appropriate sense, one still may lack for the maps between them that make them isomorphic.

If a topos $T$ has a natural number object, surely one can make sense of "the numeral system with radix $n$" at least with $n$ any fixed (real world) natural number > 1. So fixing $T$ one gets an equivalence relation on the real world natural numbers according to the isomorphism of numeral systems of various radix. (Well, depending upon the topos and the interpretation of numeral system, perhaps one might have to discard some radices altogether, where one doesn't have total operations.)

My question: Can one realize any equivalence relation on the natural numbers by choosing some appropriate topos? Failing a full answer, what example topos distinguish some systems but not others?

Answer by Andrej Bauer for Radix notation and toposes

2010-12-18T16:23:00Z

First note that there are several inequivalent definitions of real numbers. The two most usual ones appearing in intuitionistic mathematics are:

Cauchy reals: constructed as a quotient of the space of rapidly converging Cauchy sequences of rational numbers. (A sequence $(a_n)_n$ is said to converge rapidly if $|a_n - a_m| \leq 2^{-\min(m,n)}$. Actually any other fixed rate of convergence will do, Bishop takes $|a_n - a_m| \leq 1/n + 1/m$).
Dedekind reals: constructed as two-sided cuts of rational numbers.

If countable choice is valid then the two constructions coincide, but in the general case the Cauchy reals form a subfield of the Dedekind reals.

The Dedekind reals are better behaved when we do not have countable choice. For example, they are Cauchy complete (by which I mean that Cauchy sequences of reals converge), but the Cauchy reals need not be Cauchy complete.

A radix representation of a real is a special kind of Cauchy sequence. For example, suppose $x$ is represented by the sequence $(d_n)_n$ in radix $r$, so that $x = \sum_n d_n r^{-n}$, where we require that $d_0 \in \mathbb{Z}$ and $d_n \in \lbrace 0,\ldots,r-1\rbrace$ for $n \geq 1$. Then this just says that $x$ is the limit of the Cauchy sequence of the partial sums. Crucially, the partial sums are monotonically increasing.

It may come as a bit of surprise, but intuitionistically it is not generally the case that every real number (Cauchy or Dedekind, it doesn't matter) has a radix representation. If every real had a radix representation then every real would be the limit of a monotonoically increasing Cauchy sequence, and that's problematic (ask another MO question if you want to know why). So I think you are making an unwarranted assumption in your question that all reals have radix representations.

It is well known how to fix the situation: we must allow negative digits, i.e., $d_n \in \lbrace -r+1, -r+2, \ldots, -1, 0, 1, \ldots, r - 1\rbrace$ in the above formula. With this change, the reals that have radix representations are precisely the Cauchy reals. And it does not matter which radix you take, they are all equivalent.

Answer by Daniel Mehkeri for Radix notation and toposes

2010-12-19T19:49:44Z

No, and actually, you cannot realise any non-trivial equivalence relation this way. If any of the (non-trivial) pairs of radix systems are isomorphic, they all are. It is "well-known" that not every real number has a decimal expansion. This extends to this situation.

Specifically, for any pair n and m (unless one divides the other), the assumption that every radix-n number has a radix-m expansion impies a weak form of the law of the excluded middle, called the limited principle of omniscience (LPO): this says that for every sequence of integers, either it is constant zero, or it has a non-zero element. Given a sequence of integers, you can construct a radix-n number such that the first digit of the corresponding radix-m number decides the answer. (E.g. given base-10 0.3333333... convert it to base-3, it's 0.100000... or 0.022222...)

Conversely if LPO holds, you can show all radix-n systems are equivalent.

It's also been pointed out that these number systems aren't necessarily even rings. The same thing happens - if any of them are rings, then LPO holds. And if LPO holds, then they are all fields (in any sense).

This reasoning goes through in any topos (even Pi-pretopos) with a natural numbers object.