Are Some Real Numbers Countable and Others Uncountable?

[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?

 

[WWGD]

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?

It depends if by $\infty$ you mean $| \mathbb N |$ or $| \mathbb R |$. First is ( or can be seen as; it's equivalent to ) the set of all sequences of Real numbers ( using $A^B$ as the set of all maps from A to B ), second is the set of all functions from the Reals to itself ). If you see R as a metric space, first is metrizable, second one is not. Cardinalities are different. Maybe someone can double-check my set theory/infinite arithmetic, which is pretty rusty. Assuming continuum hypothesis , $2^{\aleph_0}=\aleph_1$. Then $| |\mathbb R|^{|\mathbb N| } = 2^{ \aleph_0 \times \aleph_0}= 2^{\aleph_0^2}= 2^{ \aleph_0}$ while $|\mathbb R|^{| \mathbb R| }= 2^{ \aleph_0 \times \aleph_1}= 2^{ \aleph_1}$

 

[dextercioby]

Yes, sorry, not fully explicit. The $\infty$ in my post is the cardinality of $\mathbb N$. So you say that $\left| \mathbb{R}^{|\mathbb{N}|}\right| = \aleph_1 \equiv |\mathbb{R}|$.

 

[WWGD]

Yes, sorry, not fully explicit. The $\infty$ in my post is the cardinality of $\mathbb N$. So you say that $\left| \mathbb{R}^{|\mathbb{N}|}\right| = \aleph_1 \equiv |\mathbb{R}|$.

Yes, but please wait for someone to double-check my arithmetic. I haven't done any in a really long time.

 

[PAllen]

Yes, but please wait for someone to double-check my arithmetic. I haven't done any in a really long time.

Looks ok to me, but I am also rusty on this, so consider it a fractional vote of confidence.

 

[TeethWhitener]

It depends if by $\infty$ you mean $| \mathbb N |$ or $| \mathbb R |$. First is ( or can be seen as; it's equivalent to ) the set of all sequences of Real numbers ( using $A^B$ as the set of all maps from A to B ), second is the set of all functions from the Reals to itself ). If you see R as a metric space, first is metrizable, second one is not. Cardinalities are different. Maybe someone can double-check my set theory/infinite arithmetic, which is pretty rusty. Assuming continuum hypothesis , $2^{\aleph_0}=\aleph_1$. Then $| |\mathbb R|^{|\mathbb N| } = 2^{ \aleph_0 \times \aleph_0}= 2^{\aleph_0^2}= 2^{ \aleph_0}$ while $|\mathbb R|^{| \mathbb R| }= 2^{ \aleph_0 \times \aleph_1}= 2^{ \aleph_1}$

You don’t even need the continuum hypothesis, as $|\mathbb{R}|=2^{|\mathbb{N}|}$. The rest of the math looks fine to me.

 

[vortextor]

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.

Premises:
The real numbers include all the rational numbers and all the irrational numbers.
An irrational number has a representation of infinite length that is not, from any point, an
indefinitely repeating sequence of finite length.
A rational number has a terminating sequence or has an indefinitely repeating sequence of finite length.
The set of rational numbers is countable, and the set of real numbers is uncountable.
My conclusion;
Since any irrational number can be transformed in an infinite set of rational numbers with
terminating sequence, the set of rational numbers must be more dense and uncountable ?
This is obviously invalid, however I can't see why?

 

[WWGD]

Yes, sorry, not fully explicit. The $\infty$ in my post is the cardinality of $\mathbb N$. So you say that $\left| \mathbb{R}^{|\mathbb{N}|}\right| = \aleph_1 \equiv |\mathbb{R}|$.

Correct. Sorry for delay in replying.

 

[jbriggs444]

Premises:
The real numbers include all the rational numbers and all the irrational numbers.
An irrational number has a representation of infinite length that is not, from any point, an
indefinitely repeating sequence of finite length.
A rational number has a terminating sequence or has an indefinitely repeating sequence of finite length.
The set of rational numbers is countable, and the set of real numbers is uncountable.
My conclusion;
Since any irrational number can be transformed in an infinite set of rational numbers with
terminating sequence, the set of rational numbers must be more dense and uncountable ?
This is obviously invalid, however I can't see why?

Can you justify the implicit assertion I have highlighted above? I do not even understand what it is saying.

Best guess: You can chop the decimal representation of an irrational number into an infinite number of pieces, each distinct from one another and each corresponding in some way to a unique rational number. So if there are infinitely many rational numbers for any single irrational number, how can there be more irrational numbers than rational numbers.

So far, so good. This is all correct. For one irrational number there is indeed a deterministic generating procedure we can use to generate an associated countably infinite set of rational numbers.

So what? Will the countably infinite set of rational numbers generated for the next irrational you pick re-use any of the rational numbers you found for the first irrational. If so, the union of all generated rational numbers for all irrational numbers can remain a countable set despite being the union of an uncountable number of countable sets.

 

[TeethWhitener]

Since any irrational number can be transformed in an infinite set of rational numbers with
terminating sequence,

But you can generate an infinite set of irrational numbers from an irrational number as well:
$$\pi=3.14159\ldots$$
$$\pi-3=0.14159\ldots$$
$$\pi-3.1=0.04159\ldots$$
etc., each of which is a new irrational. So your argument just tells you that rationals are dense in the reals, but nothing about how numerous the rationals vs. reals are.

 

[TeethWhitener]

Can you justify the implicit assertion I have highlighted above? I do not even understand what it is saying.

I think he’s referring to the sequence $\{3,3.1,3.14,3.141,\ldots\}$ of rationals converging on the irrational $\pi$. I could be wrong though.

 

[jbriggs444]

I think he’s referring to the sequence $\{3,3.1,3.14,3.141,\ldots\}$ of rationals converging on the irrational $\pi$. I could be wrong though.

Yeah, reasoned my way to such a conclusion. However, an uncountable union of distinct countable sets can be countable.

 

[TeethWhitener]

However, an uncountable union of distinct countable sets can be countable.

This immediately jumped out at me as obviously false, but then I put some thought into it and realized that the (uncountable) union of all subsets of $\mathbb{N}$ satisfies this. Very cool.

 

[sysprog]

This immediately jumped out at me as obviously false, but then I put some thought into it and realized that the (uncountable) union of all subsets of $\mathbb{N}$ satisfies this. Very cool.

How?

 

[FactChecker]

Premises:
The real numbers include all the rational numbers and all the irrational numbers.
An irrational number has a representation of infinite length that is not, from any point, an
indefinitely repeating sequence of finite length.
A rational number has a terminating sequence or has an indefinitely repeating sequence of finite length.
The set of rational numbers is countable, and the set of real numbers is uncountable.
My conclusion;
Since any irrational number can be transformed in an infinite set of rational numbers with
terminating sequence, the set of rational numbers must be more dense and uncountable ?
This is obviously invalid, however I can't see why?

I might have steered this thread wrong. My statement was just to encourage one to accept that the cardinality of the irrationals may be greater than the cardinality of the rationals. It may not withstand serious scrutiny.
You should not equate density with cardinality. Both rationals and irrationals are dense in the real line, but they have different cardinalities.

 

[Jarvis323]

The set of computable real numbers is actually countable.

https://en.m.wikipedia.org/wiki/Computable_number

In other words, if there is a rational or irrational number you can generate, there is a turing machine to generate it, and that turing machine is a finite object (can actually be encoded as a natural number itself), and of course the set of turing machines is one to one with the natural numbers.

 

[Jarvis323]

Personally I think that English language expressions like "A has the same amount of elements as B" to say A and B have the same cardinality is misleading.

For example, the set of integers include every natural number in addition to every negative integer. It is perfectly valid to say in the English language that the integers have more elements than the natural numbers in my opinion, and that is not a statement that is formally about cardinality.

What cardinality is, and how people talk about it, are two different things, and in my opinion this is one of the main sources of confusion.

 

[TeethWhitener]

How?

The union of all subsets of $\mathbb{N}$ is $\mathbb{N}$, but the cardinality of the set of subsets of $\mathbb{N}$ is $2^{|\mathbb{N}|}>|\mathbb{N}|$.

 

[Infrared]

The union of all subsets of $\mathbb{N}$ is $\mathbb{N}$, but the cardinality of the set of subsets of $\mathbb{N}$ is $2^{|\mathbb{N}|}>|\mathbb{N}|$.

But there isn't an uncountable family of $\textit{disjoint}$ subsets of $\mathbb{N}.$

 

[jbriggs444]

But there isn't an uncountable family of $\textit{disjoint}$ subsets of $\mathbb{N}.$

I said "distinct" not "disjoint". But yes, I agree that you can't find an uncountable family of disjoint subsets.

 

[Jarvis323]

Any set of finite elements is countable. Which also means that even unions of uncountably many disjoint subsets of finite objects would be countable, if there were an uncountable number of disjoint subsets of finite elements.