4
$\begingroup$

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

  • 0
    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...2010-12-18
  • 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.2010-12-18
  • 0
    @`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.2010-12-18
  • 0
    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.2010-12-18
  • 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.2010-12-18
  • 0
    Actually, it's a good example. I learnt a lot from thinking about it ;).2010-12-18
  • 0
    By the way, has anyone seen this set come up in another context?2010-12-18

6 Answers 6

4

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.

  • 0
    "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.2010-12-18
  • 1
    Right. "333..." isn't a "legitimate" number, but "0.333..." is.2010-12-18
2

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.

  • 0
    @`Asaf`, thanks yep for pointing out the uniqueness issue.2010-12-18
  • 0
    Good point. Luckily, we don't have to worry about nonuniqueness when the decimal expansions are finite.2010-12-18
  • 0
    @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)2010-12-18
  • 0
    Definitely. What I meant is that no two finite representations refer to the same number.2010-12-18
2

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.

  • 0
    Interesting function for rationals, thanks.2010-12-18
1

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.

  • 0
    `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?2010-12-18
  • 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.2010-12-18
  • 0
    @`Raskolnikov`, I think that's the bit I was missing... A natural number can be expressed using finite digits, whereas a real can't.2010-12-18
1

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.

  • 0
    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...2010-12-18
1

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.