5 ms·

There are, and it turns out that this is a significant mathematical concept. The integers between 0 and infinity are defined as "countably infinite". Other inf

There are, and it turns out that this is a significant mathematical concept. 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.

bombolo 3y ago
does decimal numbers mean fractions or real numbers? If it means fractions only, they are countable.
denton-scratch 3y ago
> The decimal (real) numbers between 0 and 1 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.
shidoshi 3y ago
This account discrete maths. Bravo!
dbtc 3y ago
"Countably infinite" makes zero sense to me. 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.
- feoren 3y ago
  > 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. 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.
  - dbtc 3y ago
    > And then infinitely later 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.
    - ironSkillet 3y ago
      Mathematicians consider two sets to be of the same size or more precisely "cardinality", if it is possible to construct a 1-1 map of elements from the first set to the second set. These maps can obviously be constructed for sets with finitely many elements, and they can be constructed for sets with an infinite number of elements as well. For instance, the set of all integers has the same cardinality of the set of all positive integers (just enumerate the integers alternating back and forth expanding from 0 - this constructs the 1-1 map). 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.
quantified 3y ago
Cantor's proof is a single attempt. Suppose you could construct a space-filling curve that did indeed map all numbers between 0 and 1 to all integers? Has there been a proof that such a curve does not exist? The fact that his proof leans on a specific set of decimal places at every juncture has always seemed a weakness of his proof, because you can always map any set of numbers from 0 to 1 with any set of decimal places to a set of integers.

bombolo 3y ago

does decimal numbers mean fractions or real numbers? If it means fractions only, they are countable.

denton-scratch 3y ago

> The decimal (real) numbers between 0 and 1 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.

shidoshi 3y ago

This account discrete maths. Bravo!

dbtc 3y ago

"Countably infinite" makes zero sense to me. 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.

feoren 3y ago
> 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. 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.
- dbtc 3y ago
  > And then infinitely later 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.
  - ironSkillet 3y ago
    Mathematicians consider two sets to be of the same size or more precisely "cardinality", if it is possible to construct a 1-1 map of elements from the first set to the second set. These maps can obviously be constructed for sets with finitely many elements, and they can be constructed for sets with an infinite number of elements as well. For instance, the set of all integers has the same cardinality of the set of all positive integers (just enumerate the integers alternating back and forth expanding from 0 - this constructs the 1-1 map). 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.

quantified 3y ago

Cantor's proof is a single attempt. Suppose you could construct a space-filling curve that did indeed map all numbers between 0 and 1 to all integers? Has there been a proof that such a curve does not exist? The fact that his proof leans on a specific set of decimal places at every juncture has always seemed a weakness of his proof, because you can always map any set of numbers from 0 to 1 with any set of decimal places to a set of integers.