I Are Some Real Numbers Countable and Others Uncountable?

[emptyboat]

I think that real number is countable. Because there is one to one correspondence from natural numbers to (0,1) real numbers.

0.1 - 1
0.2 - 2
0.3 - 3
...
0.21 - 12
...
0.123 - 321
...
0.1245 - 5421
...

I think that is a one-to-one corresepondence. Any errors here?

 

[fresh_42]

Yes. They are uncountable. Assume that your list contains all real numbers. Now add 1 to the first digit of the first number, add 1 to the second digit of the second number, 1 to the third digit of the third number, and so on. If you find a 9, then turn it into a zero.

The number you get, if you concatenate all changed digits is a number that was not in your list, i.e. whichever list you choose, there is a number that is not listed. Hence the real numbers are uncountable.

 

[emptyboat]

Yes. They are uncountable. Assume that your list contains all real numbers. Now add 1 to the first digit of the first number, add 1 to the second digit of the second number, 1 to the third digit of the third number, and so on. If you find a 9, then turn it into a zero.

The number you get, if you concatenate all changed digits is a number that was not in your list, i.e. whichever list you choose, there is a number that is not listed. Hence the real numbers are uncountable.

Your logic is like this.

1 - 1
2 - 2
3 - 3
...
10 - 10
11 - 11
...
123-123
...

Assume that this list contains all natural numbers. Now add 1 to the ones place of the first number.(1+1=2), add 1 to the tens place of the second number(0+1=1), add 1 to the hundreds place of the third number(0+1=1), and so on. (If you do it third times, you get 112.)

The number you get, if you concatenate all changed digits is a number that was not in your list, i.e. whichever list you choose, there is a number that is not listed. Hence the natural numbers are uncountable.

 

[fresh_42]

Your logic is like this.

1 - 1
2 - 2
3 - 3
...
10 - 10
11 - 11
...
123-123
...

Assume that this list contains all natural numbers. Now add 1 to the ones place of the first number.(1+1=2), add 1 to the tens place of the second number(0+1=1), add 1 to the hundreds place of the third number(0+1=1), and so on. (If you do it third times, you get 112.)

The number you get, if you concatenate all changed digits is a number that was not in your list, i.e. whichever list you choose, there is a number that is not listed. Hence the natural numbers are uncountable.

No. Natural numbers are not infinitely long. My argument goes like this:
0.168435 ...
0.899958 ...
0.915476 ...
0.153798 ...
...
turns into

0.268435 ...
0.809958 ...
0.916476 ...
0.153898 ...
...
If we have e.g. 0.5, then we write it as 0.5000000 ...

You cannot do this with natural numbers.

 

[emptyboat]

No. Natural numbers are not infinitely long. My argument goes like this:
0.168435 ...
0.899958 ...
0.915476 ...
0.153798 ...
...
turns into

0.268435 ...
0.809958 ...
0.916476 ...
0.153898 ...
...
If we have e.g. 0.5, then we write it as 0.5000000 ...

You cannot do this with natural numbers.

If I
1
2
3
4
...
turns into

2
12
103
1004

I can go on this process.

Natural numbers have the potential to be infinitely long.

 

[jim mcnamara]

Yes, the reals are infinite and the natural number are infinite. Up to this point you got it.
But naturals are countably infinite. The reals are uncountably infinite. Not the same.

I do not see where things got confused, but I think that @fresh_42 did not want to explicitly inflict Cantor's proof on you. I think he is using the proof in "example mode". He can correct me.

Further reading which I hope helps you:
https://en.wikipedia.org/wiki/Countable_set

 

[FactChecker]

I think that real number is countable. Because there is one to one correspondence from natural numbers to (0,1) real numbers.

0.1 - 1
0.2 - 2
0.3 - 3
...
0.21 - 12
...
0.123 - 321
...
0.1245 - 5421
...

I think that is a one-to-one corresepondence. Any errors here?

All the numbers you listed have finite length and end in infinite 0's. At what point would you count 0.1212121212...?
And there are a lot more where that came from. I think that you can see that you have only counted a tiny, tiny subset of the real numbers.
EDIT: In fact, this method misses a lot of rational numbers, which are countable. 0.12121212.. = 12/99.

 

[Dale]

I think that is a one-to-one corresepondence. Any errors here?

Besides the actual proofs that the reals are uncountable, it seems clear that your construction fails for real numbers greater than 1. I also don’t think it works for irrational numbers and maybe not even some rational numbers.

 

[TeethWhitener]

@fresh_42 left out the last step in the traditional diagonal argument:

No. Natural numbers are not infinitely long. My argument goes like this:
0.168435 ...
0.899958 ...
0.915476 ...
0.153798 ...
...
turns into

0.268435 ...
0.809958 ...
0.916476 ...
0.153898 ...
...
If we have e.g. 0.5, then we write it as 0.5000000 ...

You cannot do this with natural numbers.

After we have the second list:
0.268435 ...
0.809958 ...
0.916476 ...
0.153898 ...
we take the changed (bolded) numbers and make a new number (0.2068…) that wasn’t in the previous list. We know it wasn’t because if it were the nth number, its nth digit would be 1 less than it is.

 

[emptyboat]

It's very simple. (mirror refection with zero in center)

Every sigle-digit decimals correspond to every single-digit natural numbers(9 pieces).
(1-0.1, 2-0.2, 3-0.3, ..., 9-0.9)

Every two-digits decimals correspond to every two-digit natural numbers(90 pieces).
(10 - 0.01, 11 - 0.11, 12-0.21, ..., 97 - 0.79, 98 - 0.89, 99 - 0.99)

Every three-digits decimals correspond to every three-digit natural numbers(900 pieces).
(100 - 0.001, 101 - 0.101, 102 - 0.201, ..., 997 - 0.799, 998 - 0.899, 999 - 0.999)

And so on...

Every dicimals have countable digit decimals, aren't they?

If you let go of the mindset that Real numbers are uncountable, it's very simple and easy.
Aren't they?

 

[TeethWhitener]

Every dicimals have countable digit decimals, aren't they?

Prove it.

 

[emptyboat]

Prove it.

If natural numbers have countable digits, and every dicimal also has countable digits.
(Because it's mirror refection with zero in center).
Natural numbers are countable and natural numbers are greater than digits of natural numbers, so digits of natural numbers are countable, and also every dicimal has countable digits.

 

[FactChecker]

If natural numbers have countable digits, and every dicimal also has countable digits.
(Because it's mirror refection with zero in center).
Natural numbers are countable and natural numbers are greater than digits of natural numbers, so digits of natural numbers are countable, and also every dicimal has countable digits.

What would you call $12/99 = 0.1212121212...= 0.121212\overline{12}$? Are you going to ignore all the rational numbers like that?

 

[TeethWhitener]

and every dicimal also has countable digits.

You can’t just assert the part I asked you to prove and expect anyone to buy it. If you want to assert that every infinite string can be mapped to the reversed infinite string, then yes, you’ve just effectively shown that you can map the real numbers to the real numbers. But you have to put “every dicimal” in 1-1 correspondence with every natural number first. You’ve been given a number of counterexamples at this point. I suggest you study them with a little bit of seriousness.

 

[emptyboat]

What would you call $12/99 = 0.1212121212...= 0.121212\overline{12}$? Are you going to ignore all the rational numbers like that?

12/99 is correspond to ...1212121212, but there is not such a natural number.

But I think if your logic is true, rational numbers are also uncountable.

In the case of rational numbers, countable means like that, it shows a possibility of one-to-one correspondence. But in the case of real numbers, the perspective changes.

 

[mathwonk]

pl;ace an interval of length 1/4 over the natural number 1. Then place an interval of length 1/8 over the natural number 2. then place an interval of length 1/16 over the natural number 3. ... continuing, you have covered the natural numbers by a sequence of intervals of length 1/2. but the unit interval [0,1] has length 1. contradiction.

 

[FactChecker]

12/99 is correspond to ...1212121212, but there is not such a natural number.

But I think if your logic is true, rational numbers are also uncountable.

No. It just shows that the natural numbers are not countable by your method. They are countable but your method is seriously flawed.

 

[emptyboat]

No. It just shows that the natural numbers are not countable by your method. They are countable but your method is grossly flawed.

Yes. I understand countable meaning and subtle difference between rational numbers and real numbers.

I pick a random rational number as 12/99 and if order can be given it's countable.

But if I pick π, I cannot give order to that number. So it's uncountable.

Thanks!

 

[FactChecker]

I think it is worthwhile to realize how easy it is to create irrational numbers. Just make sequences that never start repeating, like 0.101001000100001000000100000001000000001...
And for any such number, you can add it to a list of rational numbers to get a list of irrational numbers.
IMHO, that makes it easier to accept how the irrational numbers are such a huge set compared to the rationals (although it is not a proof by any means).
Cantor's proof is genius and is worth studying. Mathematicians of his time hated and resisted his conclusion that there are higher, uncountable, orders of infinity, but it was undeniable.

 

[mathman]

I think that real number is countable. Because there is one to one correspondence from natural numbers to (0,1) real numbers.

0.1 - 1
0.2 - 2
0.3 - 3
...
0.21 - 12
...
0.123 - 321
...
0.1245 - 5421
...

I think that is a one-to-one corresepondence. Any errors here?

You list has only numbers with finite decimal expansions - not enough.

 

[sysprog]

Not only are the reals uncountably infinite; also, any non-empty interval (open or closed) subset (no matter how small as long as it has non-zero extension) of $\mathbb{R}$ (the reals) that includes all of the reals that are within itself (inclusive or exclusive of boundaries) is also uncountably infinite.

 

[Svein]

And the set of all subsets of the real numbers are even more uncountable and so on...

 

[sysprog]

And the set of all subsets of the real numbers are even more uncountable and so on...

I trust that you understand that 'uncountable' is a 'yes-or-no' condition, and that therefore nothing can possibly be "even more uncountable" than something else that is 'uncountable' is; however, I think that it's worth pointing out that even the infinitesimal is exactly as 'uncountably infinite' in its fractional expansion as the entirety of $\mathbb{R}$ (the reals) in its fractional expansions is (the concept of divisibility may be regarded as inconsistent with the concept of infinitesimality; i.e., it could be not unrightly said that the infinitesimal is not divisible, wherefore, there could be no 'fractional expansion' of the infinitesimal).

 

[sysprog]

And the set of all subsets of the real numbers are even more uncountable and so on...

That reminds me of Russel's Paradox

 

[BWV]

The reals on [0,1] are easily countable, just paste them in Excel and click 'sort ascending'

 

[TeethWhitener]

I trust that you understand that 'uncountable' is a 'yes-or-no' condition, and that therefore nothing can possibly be "even more uncountable" than something else that is 'uncountable' is; however, I think that it's worth pointing out that even the infinitesimal is exactly as 'uncountably infinite' in its fractional expansion as the entirety of $\mathbb{R}$ (the reals) in its is.

I think @Svein is referring to the fact that the power set of $\mathbb{R}$ has a greater cardinality than $\mathbb{R}$.

 

[sysprog]

I think @Svein is referring to the fact that the power set of $\mathbb{R}$ has a greater cardinality than $\mathbb{R}$.

I think that you're right about that; however, I trust that he understands that the greater cardinality does not increase its uncountability, which of course cannot increase beyond 'uncountable' any more than a switched-on light switch can be more 'on' than 'on'.

 

[BWV]

Is this correct?

The cardinality of an interval in R is proportional to its length, and as it is uncountable, the cardinality of some arbitrarily small nonzero interval in R is greater than all of N

 

[sysprog]

Is this correct?

The cardinality of an interval in R is proportional to its length, and as it is uncountable, the cardinality of some arbitrarily small nonzero interval in R is greater than all of N

The cardinality of any non-empty interval of non-zero length in $\mathbb{R}$ is not proportional to its length; it's the same as that of the whole of $\mathbb{R}$ (and is therefore greater than that of $\mathbb{N}$). Although the length of 1 inch on a 12-inch ruler is obviously less than that of the 12 inches of such a ruler, the cardinality of the unit interval $[0,1]$ is the same as that of the interval $[0,12]$. The number of possible divisions is uncountably infinite in both cases. A discussion of matters fundamentally related to this can be found at https://plato.stanford.edu/entries/continuum-hypothesis/

 

[Svein]

I trust that you understand that 'uncountable' is a 'yes-or-no' condition

Some jokes fall more than flat.

 

[FactChecker]

Some jokes fall more than flat.

I think we should give some "artistic license" to the terminology used and recognize that @Svein has made an important point.

 

[sysprog]

Some jokes fall more than flat.

When you check your pockets on leaving the house $-$ let's see, keys, wallet, phone, TI-83 (graphing calculator), ok, good to go $-$ is a too-flat $-$ hmm $-$ more than flat $-$ maybe a B♭ (B flat) clarinet that's more than too flat maybe an A♮ (A natural) clarion?

 

[dextercioby]

I think @Svein is referring to the fact that the power set of $\mathbb{R}$ has a greater cardinality than $\mathbb{R}$.

Is the cardinality of the powerset of $\mathbb{R}$ (or $\mathbb{R}^n$, with $n$ finite) aleph_2?
If not, what is aleph_2?

 

[stevendaryl]

Is this correct?

The cardinality of an interval in R is proportional to its length, and as it is uncountable, the cardinality of some arbitrarily small nonzero interval in R is greater than all of N

No, that's not correct. The cardinality of an interval is not affected by its length. An interval of length 1 has the same cardinality as the full set of real numbers.

Two sets have the same cardinality if you can map one set to the other in a one-to-one fashion. The mapping:

$x \mapsto log(\frac{x}{1-x})$

maps any $x$ in the range $(0,1)$ to a real number in the range $(-\infty, +\infty)$, showing that those two ranges have the same cardinality.

 

[BWV]

Gazing up into the darkness I saw myself as a creature driven and derided by vanity; and my eyes burned with anguish and anger.

No, that's not correct. The cardinality of an interval is not affected by its length. An interval of length 1 has the same cardinality as the full set of real numbers.

Two sets have the same cardinality if you can map one set to the other in a one-to-one fashion. The mapping:

$x \mapsto log(\frac{x}{1-x})$

maps any $x$ in the range $(0,1)$ to a real number in the range $(-\infty, +\infty)$, showing that those two ranges have the same cardinality.

So do (0,1) and (0,12) in R have the same cardinality because a function exists to map them (multiply/divide by 12) or do, by definition, all uncountable sets have the same cardinality?

by the above, do (0,1) and (0,12) in the rationals have the same cardinality?

 

[stevendaryl]

So do (0,1) and (0,12) in R have the same cardinality because a function exists to map them (multiply/divide by 12) or do, by definition, all uncountable sets have the same cardinality?

No, there are uncountable sets with cardinality larger than the cardinality of all real numbers.

The question of whether there are uncountable sets with cardinality smaller than the cardinality of all real numbers is an unsolved problem. And unsolvable. Given the usual tools of mathematics, there is no way to prove or disprove the claim that the set of all real numbers is the smallest uncountable cardinality.

But certainly all sets of reals that are going to come up in ordinary mathematics are in one of three categories:

1. Finite sets.
2. Countably infinite sets.
3. Uncountably infinite sets.

by the above, do (0,1) and (0,12) in the rationals have the same cardinality?

Yes, every infinite set of rationals has the same cardinality.

 

[Infrared]

Is the cardinality of the powerset of $\mathbb{R}$ (or $\mathbb{R}^n$, with $n$ finite) aleph_2?
If not, what is aleph_2?

Allowing for $n\geq 2$ doesn't change anything since $\mathbb{R}$ and $\mathbb{R}^n$ have the same cardinality.

This question is an example of the generalized continuum hypothesis, which is known to be independent from ZFC (https://en.wikipedia.org/wiki/Continuum_hypothesis#The_generalized_continuum_hypothesis).

 

[TeethWhitener]

Is the cardinality of the powerset of R (or Rn, with n finite) aleph_2?
If not, what is aleph_2?

This depends on whether your system accepts or rejects the continuum hypothesis. The cardinality of the natural numbers is $\aleph_0$ and the cardinality of the real numbers is $2^{\aleph_0}$, but the continuum hypothesis (the assertion that $2^{\aleph_0}=\aleph_1$) is independent of the axioms of ZFC.

 

[FactChecker]

do, by definition, all uncountable sets have the same cardinality?

This part is not right. There are higher cardinal numbers. There is a whole sequence of them of increasing size.

 

[sysprog]

Cantor proved that the power set of $\mathbb{R}$ has cardinality greater than that of $\mathbb{R}$. The continuum hypothesis is that nothing has cardinality in between those. Please if you find such a thing, or can prove that there is no such thing, let us know.

 

[TeethWhitener]

do, by definition, all uncountable sets have the same cardinality?

Just to pile on, Cantor's theorem is that, for any set $A$, given its powerset $\mathcal{P}(A)$--defined as the set of all subsets of $A$--the cardinality of the powerset will always be strictly greater than the cardinality of the set: $|\mathcal{P}(A)|>|A|$

 

[WWGD]

Your logic is like this.

1 - 1
2 - 2
3 - 3
...
10 - 10
11 - 11
...
123-123
...

Assume that this list contains all natural numbers. Now add 1 to the ones place of the first number.(1+1=2), add 1 to the tens place of the second number(0+1=1), add 1 to the hundreds place of the third number(0+1=1), and so on. (If you do it third times, you get 112.)

The number you get, if you concatenate all changed digits is a number that was not in your list, i.e. whichever list you choose, there is a number that is not listed. Hence the natural numbers are uncountable.

What's the image of $\pi$? Or any other Irrational?
Sorry @emptyboat , I thought I was replying to the OP.

 

[WWGD]

Cantor proved that the power set of $\mathbb{R}$ has cardinality greater than that of $\mathbb{R}$. The continuum hypothesis is that nothing has cardinality in between those. Please if you find such a thing, or can prove that there is no such thing, let us know.

Good point. It's true for every set, finite or infinite.

 

[Jarvis323]

So do (0,1) and (0,12) in R have the same cardinality because a function exists to map them (multiply/divide by 12) or do, by definition, all uncountable sets have the same cardinality?

by the above, do (0,1) and (0,12) in the rationals have the same cardinality?

There is also measure theory which is probably more along the lines of your original intuition.

https://en.wikipedia.org/wiki/Lebesgue_measure#:~:text=Any closed interval [a, b,b and has measure zero.&text=Moreover, every Borel set is Lebesgue-measurable.

 

[stevendaryl]

There is also measure theory which is probably more along the lines of your original intuition.

Except that standard measure theory gives 0 as the measure for any collection of rational numbers. So it doesn't support the intuition that there are twice as many rationals in (0,2) as in (0,1).

 

[mathwonk]

but it is consistent with it since twice zero is zero. ?

 

[WWGD]

So do (0,1) and (0,12) in R have the same cardinality because a function exists to map them (multiply/divide by 12) or do, by definition, all uncountable sets have the same cardinality?

by the above, do (0,1) and (0,12) in the rationals have the same cardinality?

Yes, two sets have the same cardinality iff there is a bijection between them.

 

[sysprog]

So do (0,1) and (0,12) in R have the same cardinality because a function exists to map them (multiply/divide by 12) or do, by definition, all uncountable sets have the same cardinality?

by the above, do (0,1) and (0,12) in the rationals have the same cardinality?

Yes, two sets have the same cardinality iff there is a bijection between them.

That is of course true; however, it is clearly not true that "all uncountable sets have the same cardinality", $-$ e.g. $|2^\mathbb{R}|>|\mathbb{R}|$ (i.e., the cardinality of the power set of $\mathbb{R}$ is strictly greater than that of $\mathbb{R}$), and both $2^\mathbb{R}$ and $\mathbb{R}$ are uncountable sets.

 

[WWGD]

That is of course true; however, it is clearly not true that "all uncountable sets have the same cardinality", $-$ e.g. $|2^\mathbb{R}|>|\mathbb{R}|$ (i.e., the cardinality of the power set of $\mathbb{R}$ is strictly greater than that of $\mathbb{R}$), and both $2^\mathbb{R}$ and $\mathbb{R}$ are uncountable sets.

I agree. The fact that for any set S $|P(S)|>|S|$ proves this. And also proves there is no set of all sets. Its powerset would be of cardinality larger than it.

 

[dextercioby]

Is $\mathbb{R}^{\infty}$ properly defined (as infinity is properly understood in classical analysis)? If so, does it have the same cardinality as $\mathbb{R}^{n}$ for arbitrary but finite $n$? What would be a proof of that?