I want to know if there are more decimal numbers between 0 and 1 than there are integers between 0 and infinity.
The integers between 0 and infinity are defined as "countably infinite". Other infinities are considered countably infinite, or the "same" infinity, if and only if you can arrange it in a list such that each item in the list pairs to an integer in our 0 to infinity list. So the set of even numbers is countably infinite because for every i that is an even number, it pairs with the number i/2.
To demonstrate: 0 -> 0, 2 -> 1, 4 -> 2, 6 -> 3, ...
The decimal (real) numbers between 0 and 1 are not countably infinite, and we know this from a concept called Cantor diagonalization. What Cantor did was a proof by contradiction: assume that the numbers are countably infinite, then you can arrange them in a list. However, he then builds a number by altering the first decimal place of the first number, the second decimal place of the second number, and so on. Finally, he shows that this built number is both a real number and is not on the list. Therefore, the real numbers between 0 and 1 cannot be ordered into a list, therefore they are not countably infinite, and there are more decimal numbers between 0 and 1 than integers between 0 and infinity.
If it means fractions only, they are countable.
The way I parse "decimal number" in this context is a number expressible as a (finite?) string of decimal numerals. Those numbers are not reals, they are rationals.
Whatever method you use to generate your decimals, you can just slap an integer on each step of the way. You'll never run out of integers.
I'll put Cantor and his proof in a box, tell him to give me his fancy decimals quick as he can, and I can match each one with an integer no problem.
And pairing one infinite list with another infinite list doesn't make either one any more countable, because however high you count, they keep on going.
Exactly correct! This holds true of everything you can generate stepwise, even infinite sets. Cantor proved that you cannot "generate" (stepwise) all Reals between 0 and 1. Any infinite set you can generate stepwise is Countably Infinite.
> I'll put Cantor and his proof in a box, tell him to give me his fancy decimals quick as he can, and I can match each one with an integer no problem.
Exactly correct! And then infinitely later, when you're "done", having generated every Real between 0 and 1, he will then generate a new Real not on your list. Oops! You have not generated all Reals between 0 and 1, even with infinite time.
> And pairing one infinite list with another infinite list doesn't make either one any more countable, because however high you count, they keep on going.
Exactly correct! Any two sets you can pair together (via a bijection) have the exact same cardinality. Neither is more infinite nor countable than the other. Cantor proved you cannot "pair" the Reals with the Natural Numbers.
You and Cantor agree completely. You're very close to understanding why the Reals are bigger.
There can be no 'and then' after infinitely later.
I don't see why stepwise is important but that must be the key to Cantor's proof.
If he gives me 1.1 1.2 1.3 and I pair with 1 2 3, then he gives me 1.11 and I pair with 4, that seems fine as far as counting is concerned.
The ordering could be entirely random, I don't see how it makes a difference. There will always be enough integers to match.
Is it that my black box metaphor is cheating by coercing a truly 'parallel' generation of decimals into a linear operation? But even then, if I'm getting exponentially bigger chunks of new decimals, I can provide equally large chunks of integers... so it still doesn't make sense to me. Infinity is infinity and you cannot count it.
We can prove that no such 1-1 map exists between the integers (an infinite set) and the decimals in the interval [0,1] (another infinite set). The proof is by contradiction, meaning that we assume such a 1-1 map exists and prove it leads to a contradiction, therefore our assumption that the 1-1 map exists must be false.
So suppose we were able to construct a map from all decimals in [0,1], by enumerating them according to some clever rule. Let d_i be the ith digit of number i in your mapping. For each I pick another different digit d_i'. Let's construct the number with decimal representation D = . d_0' d_1' d_2' ...
Assuming we have our 1-1 map, it must be somewhere in our mapping. Let's say it's element k. By our labeling concention the kth decimal digit of D is actually d_k. However, this contradicts our method of construction of D. Therefore our assumption that there is a 1-1 map between decimals in [0,1] and the integers must be false.
It is in this sense that there are infinities of different sizes.
They aren’t actually different sizes, though.
All this proves is that under specific set theoretic assumptions, a contradiction arises if you define “size” as “cardinality” and assume that a particular bijective relation exists between your two infinite sets.
It doesn’t actually mean the sets have different sizes, it just means they differ under a set of assumptions that may (or may not) be useful for your purposes.
What's your precise definition of size that allows someone to actually make a rigorous argument comparing the size of any two sets?
Similarly, I can also work around Russel’s paradox by introducing infinite universes, but that doesn’t actually resolve the paradox, it just provides a set (ha ha) of rules that may be leveraged to formalize the Set category and otherwise prove useful things.
Just because your formalization admits a proof by contradiction doesn’t actually prove two infinite sets have different sizes, it just proves that a contradiction exists under your assumptions.
Well, yes. :)
Exactly correct! Any bijection between the naturals and the reals would suffice to show that they're the same cardinality; the order does not matter. I think where you're getting confused is just in who's trying to do what; who's the "protagonist" and "antagonist" in the proof.
Cantor is not trying to overwhelm you with so many real numbers that you run out of integers. Instead, he completely accepts and agrees with everything you're saying. And then he says: okay, pick any numbering of the reals you like. 1.11 is 4, 1.111 is 76, and 1.1111 is 445662323. It doesn't matter. You pick the pairing. Write your pairing down on an infinitely long sheet of paper. If the reals and integers have the same cardinality, there must be some way to write them all down on an (infinitely long) list. Pick any one and write it down.
Cantor's only job now is to show you that any real number exists that is not on your list. To do this, he constructs a number a digit at a time. He looks at the 1st digit of the 1st number, and writes down a different digit for his 1st digit. He looks at the 2nd digit of the 2nd number, and writes a different one for his 2nd digit. He looks at the nth digit of the nth number and writes a different one down for that digit, for every digit. Real numbers never run out of digits, so this goes on forever.
If this number he has written down is on your list, you should be able to point to a number on your list and say "Aha! You see, that is just real # 65,334,649!" but you can't, because it's different from that number in its 65,334,649th digit. It is truly different from every number on your list. And so there are more reals than integers.
The claim is that all of them are on the list. The constructed number proves that claim false.
It's a proof by contradiction. If you assume there is any way to write an infinite numbered list of all reals, then Cantor shows it's possible to come up with a number not on your list. The construction uses your list as input, and given any list, can always produce a real number not on that list. Therefore there is no way to write an infinite numbered list of all reals.
It relies on the fact that real numbers have (countably) infinite digits, and therefore infinite "degrees of freedom" to be different. This may be one reason it's hard to accept. A "true" real number can contain infinite information in a single number. For instance, we can jam all of the naturals into a single real by just concatenating their decimal representations: 0.1234567891011121314151617181920212223...
This one single real number encodes the full infinite natural number line. That hopefully gives you a sense of why the "infinite digits" definitions of reals makes them qualitatively "bigger" than any number that has finite representation.
I see how a list of reals is like 2D list of infinities, so one grows from the middle and the other grows from the end, but they're both still infinite. I guess I'm still stuck in a 'mechanical' approach and not a mathematical one. I'm not sure I want to leave ;) This has been fascinating to think about anyway.
If I do that then Cantor will never have a chance to give me his 'gotcha' number, because I'll always be writing on my infinite paper ;)
A mathematician compares the size of two sets of stuff by pairing off items from each set, but this is not a mechanical process taking a finite or even unbounded amount of time: they just need to show such a mapping exists or that nonexistence would lead to a contradiction; they don't need to actually carry out the process mechanically. By definition (according to mathematicians), something is countable if it is the same size as the set of natural numbers {0, 1, 2, ...} or smaller, and "countably infinite" just means it is the same size as the naturals (and not smaller, which would make it finite).
A small minority of mathematicians hold the position that proof-by-contradiction is not good enough, and that you really do need to positively prove something. They are called intuitionists.
Presumably, an even smaller minority of mathematicians hold the position that this proof must (theoretically) be able to be carried out in a mechanical manner. They're some flavor of constructivists, but maybe they're better called programmers. <- This is where you are.
if not then they are equal, if yes then there are more decimal numbers between 0 and 1 than integers.
Everybody experienced writing irrational numbers using decimal notation in school, so those definitely count.
I've seen them expressed as letters or formule
You've proved my point. It's either π or 3.14. Except that the latter is a rational number :)
Weird, I just assumed that was normal in most education systems. I don't know how you'd get a sense of the rough scale of various common irrationals, without having some idea what they look like when represented in decimal notation. Such representations are normal starting not later than when we start seriously working with circles, in US school, and never really stop coming after that. Estimation exercises lean heavily on having some idea of the decimal representation.
> You've proved my point. It's either π or 3.14. Except that the latter is a rational number :)
Never claimed π is 3.14, so no, I didn't at all prove your point. I wrote that it's very well known that it starts that way. When a normal person says "decimal number" they mean to include π, because any usefully-precise decimal representation of it's going to involve a decimal point. At least in the US, they saw it represented "3.14..." or "3.1459..." or whatever, many, many times in school. It's obviously, to a non-mathematician, a "decimal number". They mean "the real numbers" (or, perhaps, depending on context, exclusively the parts of the reals that aren't whole integers), except that name is harder to remember than the incorrect (but more common and intuitive) "decimal numbers".
For me a "decimal number" is a number represented in base 10. Which is why I was asking. I even googled and there is no real definition.
I'm currently reading one. Looking good so far. I'll let you know after I finish.
To be pedantic, we experienced writing approximations of these numbers in decimal arithmetic.
[EDIT] Look, I don't mean to be a dick, performative misreading and plainly-unnecessary "correction" are just two of my least-favorite types of HN post. I probably should have just downvoted the original performative misreading (not yours, the one up-thread) and not Assumed Good Faith that the original poster genuinely doesn't understand what every non-math-nerd means when they say or write "decimal number" (it's the ones you write with a decimal. It's... so very simple, that's why non-math-nerds use that and not "real number", the definition of which they've long since forgotten. "Well but you can't actually represent irrationals them entirely in decimal notation" great, wonderful, has zero bearing on what people mean by it).
“Decimal numbers” is not a term routinely used by mathematicians (quite distinct from primary and secondary teachers of arithmetic who are, unfortunately, rarely mathematicians), precisely because of the confusion you, perhaps unwittingly, elicited. If you mean by this phrase all infinite series with a decimal approximation, then you’re talking about the reals. Some people thought you meant this!
Other people, also quite reasonably, interpret “the Decimal numbers” to mean all numbers that can actually be expressed with (finite) decimal notation, in which case you are talking about (a subset of) the rationals.
It is extremely important, when discussing different sets, to be clear about the difference between these two.
Goodness this is like talking to GPT at times.
A decimal number is a rational whose denominator is an integer power of 10.
And anyway, is Sqrt(2)/2 such a number?
There are not more numbers with terminating decimals between 0 and 1 than integers.
- No, even if you include all the decimals which can be individually described in any notation whatsoever.
You can disregard all the arguments in the other comments about whether "decimals" includes fractions like 1/7 using decimal repeat notation, or irrationals described by a formula like sqrt(2), or transcendentals from mathematical definitions like pi and e.
Those are interesting and deep rabbit holes, but they don't change the answer to your question, because it is still "no" with all of those. Even with all possible definitions which can be written in any symbolic language. This is because the set of all possible definitions which can be written can be enumerated systematically in a list, and mapped 1:1 to all the integers.
- Yes, if you include all the other numbers in the range 0 to 1 which are not ones you can individually describe. Most real numbers in the range 0 to1 are actually these type of "individually undescribables". But I can't point out an individual one, of course.
The "real numbers" contain these. They are present due to a consequence of logic that keeps regular math simpler and more consistent than it would be otherwise.
(Aside: The question of whether 1/3 = 0.3(repeating), times 3 = 0.9(repeating), is equal to 1 is an example of choosing the simpler and more consistent logic. Of course 1/3 times 3 is 1 so 0.9(repeating) must be defined as equal to 1, or fractions wouldn't be consistent with decimals...)
But the rationals (fractions), algebraic numbers (solutions to polynomials with integer coefficients, such as square roots), computables (numbers you can define by any algorithm), and even some types of uncomputables (such as all Chaitin's constants for all enumeration rules), and all mathematically individually definable transcendental numbers like pi/4 and e/3 do not contain these.
It follows that all the "individually undescribables" in the real numbers can only, conceptually, be imagined as infinitely long decimals with no repeats and no pattern to the digits definable by a finite-length rule in any language. You obviously can't write one of them down, you can only conceptualise what one already written down might look like. (For example a spiral of digits of ever descreasing size would fit one in finite area.) And we can only reason about them as a set by logical construction.
If you were to pick a random real number uniformly (ie. fairly) from the range 0 to 1 by picking a sequence of random decimal digits, it would ɓe one of these infinitely long decimals with probability 1. Because simple random values from a continuous range are like this, perhaps this explains why they are actually a natural and not unreasonable concept.
So the answer depends on whether your meaning of "decimal numbers" means the "real numbers" in the continuous range 0 to 1, or just certain ways of writing numbers. From the other comments, evidently some people include all sort of things in their idea of "decimals" including 1/3 = 0.333...(repeating) and the exact value of pi/4 for example, not just finite strings of digits. While other people think of "decimals" as being only strings of digits you can write down, so they would not include the exact value of pi/4 for example. These two meanings of "decimal numbers" give different answers to your question.
For example, there is infinity between 0.1 and 0.2, and infinity between 0.1 and 0.11, etc. i.e. infinite sets of infinity rather than one set of infinity.
In the end it's all infinity, but their sets have higher cardinality described in Aleph terms ... (or something)