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 trying to understand the cardinality between the set of all infinite binary (base-2) fractions and the set of all infinite decimal (base-10) fractions.

I can easily think of infinite binary fractions that do not match up with infinite decimal fractions, such as $\frac{1}{1010} = 0.00011001100110011\ldots$ (in binary) is not infinite in decimal $\frac{1}{2} = 0.5$ but does every infinite decimal fraction pair up with an infinite binary one (ex: $\frac{1}{3} = 0.333333\ldots$ maps to $\frac{1}{11} = 0.010101\ldots$)? Or does the infinite binary set have greater cardinality?

Clarification

By "infinite" fraction I mean a fraction that only repeats non-zero values.

Example: $\frac{1}{2} = 0.5000\ldots$ (in decimal) and $\frac{1}{10} = 0.1000\ldots$ (in binary) would not be considered infinite fractions.

For context: I'm trying to determine if programming using decimal floating points is better than binary floating points because of less rounding issues due to these infinite fractions. I already know they are better in regard to having the same rounding issues as is experienced in the real world, which primarily uses a base-10 numeric system.

share|improve this question
    
the cardinality is just the same, it seems... but may i ask for one detail, so by infinite you mean, for instance, 0.100000000...000... does not belong to any of the sets you consider? –  W_D Jul 25 '13 at 18:31
    
$\frac1n$ in base $b$ will be non-terminating if at least one of the prime divisors of $n$ does not divide $b$. So, any $\frac1n$ in base $10$ will be non-terminating, must be non-terminating in base $2$. But what will happen, if $n=2^a\cdot5^b$ where $a\ge0,b>0$ ? –  lab bhattacharjee Jul 25 '13 at 18:31
    
@AlexWhite Yes, that's what I'm referring to. –  Nick Gotch Jul 25 '13 at 18:39
    
All decimals are infinite repeating, really. In base ten, even $0.5=0.4\overline{9}$. –  alex.jordan Aug 1 '13 at 18:58
    
@alex.jordan Do you have a source/proof for $0.5=4\overline{9}$? It just blows my mind. –  Nick Gotch Aug 1 '13 at 19:12

2 Answers 2

up vote 2 down vote accepted

Fractions have terminating decimal representations exactly when the (reduced) denominator factors into powers of $2$ and $5$ only, while they have terminating binary representations exactly when the denominator is a power of $2$.

So yes (if I understand the question), if a fraction does not terminate in decimal, its (reduced) denominator has a prime factor other that $2$ or $5$, and so it will repeat in binary too.

share|improve this answer
    
Thank you, this makes sense. –  Nick Gotch Aug 1 '13 at 19:31
    
@NickGotch Note that you can only find a terminating decimal representation of a fraction that has a repeating binary representation if the denominator only has powers of $2$ and $5$ in its prime factorization, and at least one power of $5$. So one-fifth would be such a number. (And the examples in your posted problem are not equivalent to each other - the binary example one-tenth, but the decimal one is one-half.) –  alex.jordan Aug 1 '13 at 22:01
    
Thanks. I did realize those weren't equivalent, I was just trying to think up quick examples of what I didn't mean by "infinite" fractions. –  Nick Gotch Aug 1 '13 at 22:11

Let $B,D$ denote the sets of all infinite binary fractions and infinite decimal fractions respec. Since all the infinite binary fractions of the form $$0.b_0b_1b_2\cdots$$have their $b$'s from $\{0,1\}$, they are just a subset of all the infinite decimal fractions of the form $$0.d_0d_1d_2\cdots$$ where the $d$'s are from $\{0,1,\cdots\ ,9\}$. So there exist a surjection from $B$ to some subset of $D$, namely $B$ itself. Now, clearly, if $0.d_1d_2d_3\cdots $ is any element from $D$, one can find a unique representation of that in $B$. So there exists a surjection from $D$ to some subset of $B$. Then, by Schroeder-Bernstein theorem $B$ and $D$ have the same cardinality.

share|improve this answer
    
I don't think this answer correctly answers the question based on how I'm defining "infinite fractions." See my clarification above. I still haven't been able to come up with a single infinite decimal fraction that maps to a finite binary fraction but I can easily find the reverse. If the cardinality is the same, I'd expect there to be some. –  Nick Gotch Aug 1 '13 at 16:36
    
@NickGotch, look at alex.jordan's comment. –  Samrat Mukhopadhyay Aug 1 '13 at 19:28

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.