Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm not so well up on my math, but I was wondering if the set of "[EDIT: finitely] decimal expressible" real numbers $R$ between $[0,1]$ is countable?

Wikipedia gives the definition:

A set $S$ is called countable if there exists an injective function $f$ from $S$ to the natural numbers $\mathbb{N}$

It would seem to my mathematically naïve brain that such an injective function exists—for any element $r \in R$ you can simply "reverse the number" and remove the decimal point to end up with, e.g.,:

$f(0.0001) = 10000$

This leads me to three questions:

  • Is this intuition correct?
  • Would this constitute a proof?
  • Can the result be extended to general real numbers between $[0,1]$?

Any help with terminology would also be great... E.g., I don't know a mathematical function for "reversing" a number...

Thanks!

(P.S., I've just noted a specific question here which is related and gives the general principle, but still doesn't answer my specific examples.)

share|improve this question
    
I'm only half interested in the result itself, but hoping to learn more about countability through setting this example for myself. I'm particularly interested in the answer to question 3... –  badroit Dec 18 '10 at 20:16
1  
What do you mean by "decimal expressible"? That the decimal expansion terminates? If that is what you mean then, yes, your intuition and proof are correct. –  Andres Caicedo Dec 18 '10 at 20:20
    
@Andres, thanks. Yes, for decimal expressible, I meant that the expansion terminates. And if the expansion doesn't terminate? The expansion of natural numbers doesn't terminate in the other direction so I can't see a way of disproving that an injective function exists. –  badroit Dec 18 '10 at 20:26
    
I think that a better title would help people answer your question and not that the interval is uncountable. Also, this is not really discrete mathematics as far as I can tell. –  Asaf Karagila Dec 18 '10 at 20:36
1  
I will note that this is a very typical thing to try; we used to see it in sci.math pretty much every other bimester or so. –  Arturo Magidin Dec 18 '10 at 20:43

6 Answers 6

up vote 3 down vote accepted

Your intuition is correct: the set of "decimal expressible" real numbers in [0, 1] such that the decimal expression has only finitely many nonzero digits is countable, and the "injective function" you gave works.

However, if you allow decimal expressions with an infinite number of decimals (e.g. 0.333...), then this no longer works. First of all, which natural number are you going to associate with 0.333...? In fact, if you allow decimal expressions with an infinite number of decimals, then the set you described becomes uncountable; for the justification of that, I'll point you to Cantor's Diagonal Argument.

To answer your three questions:

  1. Yes.

  2. Yes, all you needed to do is associate every element of your set with an element of the natural numbers (and vice versa), which you've done. If I give you a decimal expression with finitely many terms, you can give me the unique natural number that you've associated with that decimal expression, and if I give you a natural number, you can give me the unique (finite) decimal expression it corresponds to. This is exactly what it means for a set to be countable.

  3. No; again, see Cantor's Diagonal Argument.

share|improve this answer
    
"which natural number are you going to associate with $0.333...$?" My intuition would've said $...333$, but I think Rashkolnikov's comment below was the bit I was missing: natural numbers have finite digits, whereas reals may not. –  badroit Dec 18 '10 at 20:50
1  
Right. "333..." isn't a "legitimate" number, but "0.333..." is. –  Elliott Dec 18 '10 at 20:52

Yes, that works for terminating decimals (which does not include all rationals). More generally, it's simpler to note that the rationals are countable by mapping the reduced rational $\rm\ m/n\ \to\ 2^m\ 3^n\:.$ The same idea easily extends from pairs of naturals to all eventually zero sequences of naturals. Such arguments cannot be extended to all reals since the well-know diagonalization argument due to du-Bois-Reymond (and, later, Cantor) easily proves that that they are uncountable.

share|improve this answer
    
Interesting function for rationals, thanks. –  badroit Dec 18 '10 at 20:52

No they are not countable. Any real number can be expressed in decimal notation, and this representation may be infinite (non-terminating). And that's where your problem lies: how can you reverse an infinite decimal?

In my interpretation of your question there is no difference between what you are calling "decimal expressible" and real numbers, since any real number can be expressed in decimal notation. So the answer to part 3 is no, since the argument doesn't work as you can't reverse an infinite representation.

EDIT: In the light of your recent comment, if you are taking your expression "decimal expressible" to mean a terminating decimal, then yes these are countable. But unfortunately your argument cannot be extend to the reals in $[0,1]$ because of the problem of reversing a non-terminating decimal.

share|improve this answer
    
Derek, thanks. You are correct, in that any real number is decimal expressible. I should have said finitely decimal expressible. However, in the general case, the expansion of natural numbers in the other direction doesn't terminate either, so there should be a "duality" between the two sets, mirrored by the decimal point? Intuitively, the function exists, no? –  badroit Dec 18 '10 at 20:30
1  
Each natural number can be expressed using a finite number of digits. That has nothing to do with the fact that for any natural number, there is always a greater natural number. –  Raskolnikov Dec 18 '10 at 20:34
    
@Raskolnikov, I think that's the bit I was missing... A natural number can be expressed using finite digits, whereas a real can't. –  badroit Dec 18 '10 at 20:46

When I was taking my first course in set theory I asked my prof. (now my advisor) the same thing really.

First of all, the function is not well-defined, since there are numbers with several different decimal expansions (for example $\frac{1}{2} = 0.49999\ldots = 0.5$).

Let us assume that we only take the shortest finite expansion, it is possible but only for a very small portion of the numbers, for example $\frac{1}{3}$ has no finite decimal expansion, despite being a very simple rational number. So in fact, you don't really use even all the rational numbers in the interval.

Now assume that a number $x$ has a finite representation at all, that means that for some $n\in\mathbb{N}$ we have that $x$ has $n$ digits after the decimal point, namely $x\cdot 10^n\in\mathbb{N}$, so you only define your function on a small portion of the rational numbers in the interval $[0,1]$.

As pointed by Derek Jennings, some (in fact almost all) numbers doesn't have a finite decimal representation (and actually most numbers has no finite representation in any base you can choose), so even if you do define this function it will only cover a countable subset of the interval, whereas the interval itself is uncountable and much much bigger than $|\mathbb{N}|$.

So to answer your question, yes it is countable and your function (after correcting the minor problem of the uniqueness in the expression) is a proof for that.

share|improve this answer
    
@Asaf, thanks yep for pointing out the uniqueness issue. –  badroit Dec 18 '10 at 20:57
    
Good point. Luckily, we don't have to worry about nonuniqueness when the decimal expansions are finite. –  Elliott Dec 18 '10 at 21:02
    
@Elliott: As I remarked, even when there is a finite representation there might be an infinite one (actually, there will always be an infinite one) –  Asaf Karagila Dec 18 '10 at 22:06
    
Definitely. What I meant is that no two finite representations refer to the same number. –  Elliott Dec 18 '10 at 22:24

No, they are not countable. The proof uses an argument by contradiction. If you at all manage to list the real numbers into a countable list, you can always construct one which is not in the list. You can find a very neat exposition of the argument at the planetmath page.

share|improve this answer
    
I like these kinds of proofs. Must have been nice back in the day to come up with original proofs of this form. Seems like anything left to prove these days requires fourteen pages of dense ink... –  badroit Dec 18 '10 at 21:00

All rationals in [0,1] form a countable set. All algebraic numbers form a countable set. So all rationals that have a terminating decimal expansion, being a subset of a countable set, are countable.

share|improve this answer

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.