9
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ I wish I could upvote this twice. Awesome question. $\endgroup$
    – David Roberts ♦
    Commented Dec 20, 2010 at 6:20

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ @Daniel. Terrific - is this your own thinking or do you have a reference? (I often teach future teachers, so I collect material on elementary mathematics from an advanced viewpoint). Can you offer a canonical example of a topos where where LPO fails? $\endgroup$
    – David Feldman
    Commented Dec 19, 2010 at 20:30
  • $\begingroup$ Since my last comment, I have found this (useful): zianet.com/k5am/math/mandelkern-bwp.pdf $\endgroup$
    – David Feldman
    Commented Dec 19, 2010 at 21:15
  • 2
    $\begingroup$ The extrapolation is mine but the basic stuff on decimal expansions goes back to Brouwer, and is repeated in many introductory texts on constructive mathematics, such as Bishop's Foundations of Constructive Analysis, which is also I think where the name LPO is introduced. The effective topos violates LPO, but I don't know if it's the best/canonical example of that. $\endgroup$
    – Daniel Mehkeri
    Commented Dec 19, 2010 at 21:40
  • 1
    $\begingroup$ @DavidFeldman, I would say there's some sense in which Johnstone's topological topos (ncatlab.org/nlab/show/Johnstone%27s+topological+topos) is a "canonical" one where LPO fails. It's generated by the one-point compactification $\mathbb{N}_\infty$ of $\mathbb{N}$, which can be defined internally to it as "the set of nondecreasing binary sequences", and maps out of that object detect all the "topology" of other objects. [cont.] $\endgroup$
    – Mike Shulman
    Commented Jul 27, 2015 at 5:06
  • 1
    $\begingroup$ ...moreover, $\mathbb{N}+1$ includes into $\mathbb{N}_\infty$ as the sequences that are 1 at at some known place or constantly 0, and the localization at this inclusion is equivalent to Set. So "once you force LPO to hold, you get all of classical logic." $\endgroup$
    – Mike Shulman
    Commented Jul 27, 2015 at 5:06
8
$\begingroup$

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

  1. 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$).
  2. 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.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ @Andrej: “It is well known how to fix the situation”: that’s very nice, and I for one didn’t know it before now! Is there a canonical reference for it? (There’s a great quotation from John Baez which I unfortunately can’t find, something like: “This is ‘well-known’ in the peculiar mathematical sense of the phrase, i.e. there exist a handful of people to whom it is old hat.”) $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Dec 18, 2010 at 17:59
  • $\begingroup$ Re-reading the question, actually, I think it’s asking something slightly different from how you present the answer here (though your answer is a very nice one). If I understand right, it’s not asking about the real numbers in toposes, nor assuming that they have radix representations, it’s saying: construct rings (hopefully fields) defined like “$n$-ary radix representations of reals”, and then ask if these rings (for various $n$) are isomorphic to each other. [cont’d] $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Dec 18, 2010 at 18:06
  • $\begingroup$ However, several important parts of an answer to the OP are in yours: for each base $b$, the ring of “$b$-ary radix reps” is a subring of the ring of “non-decreasing Cauchy sequences of rationals converging faster than $1/b^n$”, and by well-known results on Cauchy sequences (…I wish I knew a reference! Is this in Bishop?…) these rings are all isomorphic to each other. So the question becomes: are the rings of radix reps proper subrings of the rings of rapid monotone Cauchy sequences of rationals? $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Dec 18, 2010 at 18:13
  • 1
    $\begingroup$ @Peter: For now, I'm agnostic about taking quotients, but I still see a problem. Perhaps my "..."'s mislead you. Maybe you can't be sure they're all 3's and 6's, respectively. At some point you might hit an event that makes the finite answer start .9... unambiguously, or 1.0... unambiguously, but the algorithm could also run forever without terminating in a decision even about how the answer starts. You're say, well if it runs forever without a decision, that tells you to accept either beginning (quotient). But it's not an effective procedure if you have to run it forever. $\endgroup$
    – David Feldman
    Commented Dec 19, 2010 at 1:49
  • 1
    $\begingroup$ I see, you'd like to think just about the representations. Well then, we need to be careful. Reals which have a radix expansion are not a ring. $\endgroup$
    – Andrej Bauer
    Commented Dec 19, 2010 at 6:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .