Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
I wish I could upvote this twice. Awesome question. –  David Roberts Dec 20 '10 at 6:20
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
@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? –  David Feldman Dec 19 '10 at 20:30
    
Since my last comment, I have found this (useful): zianet.com/k5am/math/mandelkern-bwp.pdf –  David Feldman Dec 19 '10 at 21:15
2  
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. –  Daniel Mehkeri Dec 19 '10 at 21:40
    
On reflection I was reading "isomorphism between numeral systems of various radix" WITHOUT taking a quotient as mentioned by Peter in the comments to Andrej's answer. If you take this quotient (and this seems more reasonable) then I think (I'm less sure) it's still true that any non-trivial isomorphism implies all of them, but the principle is LLPO (ncatlab.org/nlab/show/principle+of+omniscience) rather than LPO and countable choice may be involved. The effective topos still violates LLPO and satifies countable choice. –  Daniel Mehkeri Dec 20 '10 at 4:58
add comment

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.

share|improve this answer
1  
@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.”) –  Peter LeFanu Lumsdaine Dec 18 '10 at 17:59
    
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] –  Peter LeFanu Lumsdaine Dec 18 '10 at 18:06
    
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? –  Peter LeFanu Lumsdaine Dec 18 '10 at 18:13
1  
@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. –  David Feldman Dec 19 '10 at 1:49
1  
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. –  Andrej Bauer Dec 19 '10 at 6:48
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.