Is this proof of the uncountablility of the irrationals valid?

  • #1
Here is what I have come up with. It seems pretty sound to me, but I have little experience in pure math and want to be sure. (I know the easiest way is to show that R is not countable, Q is, so the irrationals, R-Q, is not, but I was wondering about this proof.)

Consider the following numbers:
0.1223334444...
0.112222333333...
0.111222222...
... (When numbers of two or more digits are encountered, they repeat in the same way, e.g. in the first number we would have ...99999999910101010101010101010.... )

These numbers are irrational, as they are non-repeating infinite decimals. They also form an countably infinite set, as they are infinite but can be listed.

However, for obvious reasons, ∏ is not included. Nor is e, √2, or many other irrationals.
Since the set of the irrationals contains more elements than a countable infinite set, it is uncountable. QED

Thanks for looking.
 

Answers and Replies

  • #2
35,138
6,889
Here is what I have come up with. It seems pretty sound to me, but I have little experience in pure math and want to be sure. (I know the easiest way is to show that R is not countable, Q is, so the irrationals, R-Q, is not, but I was wondering about this proof.)

Consider the following numbers:
0.1223334444...
0.112222333333...
0.111222222...
... (When numbers of two or more digits are encountered, they repeat in the same way, e.g. in the first number we would have ...99999999910101010101010101010.... )

These numbers are irrational, as they are non-repeating infinite decimals. They also form an countably infinite set, as they are infinite but can be listed.

However, for obvious reasons, ∏ is not included. Nor is e, √2, or many other irrationals.
Since the set of the irrationals contains more elements than a countable infinite set, it is uncountable. QED

Thanks for looking.
Just because you have a set that is "larger than" (has more elements than) some countably infinite set, that doesn't mean that the "larger" set is uncountably infinite. Consider the set {2, 4, 6, 8, ...}, which is a countably infinite set. By your reasoning (as I understand it), the set {1, 2, 3, 4, 5, 6, 7, 8, ...} is uncountably infinite because it has many more (an infinite number, actually) elements that are not also in the first set.
 
  • #3
I get the idea that infinite sets can have the same cardinality even if they are of different "sizes", and that is part of my confusion, because I recall that sort of reasoning being employed successfully in other proofs, although probably I am misinterpreting it.

For example, Cantor's diagonalization argument for the uncountablility of the real numbers basically shows that there are more real numbers than the elements of a countable set.
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
619
I get the idea that infinite sets can have the same cardinality even if they are of different "sizes", and that is part of my confusion, because I recall that sort of reasoning being employed successfully in other proofs, although probably I am misinterpreting it.

For example, Cantor's diagonalization argument for the uncountablility of the real numbers basically shows that there are more real numbers than the elements of a countable set.

Cantor's diagonal argument starts with ANY countable enumeration of the reals and then proves that must be another real. Your proof starts with a SPECIFIC enumeration of the irrationals and proves there must be another irrational. That's not good enough, as Mark44's example clearly shows. Infinite sets have proper subsets with the same cardinality. You have show that ANY countable list of the irrationals must leave out some irrational. Not just a specific one.
 
Last edited:
  • #5
35,138
6,889
But Cantor's proof is a proof by contradiction where he assumes that the reals are countable. The proof assumes that all of the reals can be placed in a (very long) list. Then, by showing that there is a number that can't possibly be on the list, he arrives at a contradiction.
 
  • #6
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722
I get the idea that infinite sets can have the same cardinality even if they are of different "sizes", and that is part of my confusion, because I recall that sort of reasoning being employed successfully in other proofs, although probably I am misinterpreting it.

For example, Cantor's diagonalization argument for the uncountablility of the real numbers basically shows that there are more real numbers than the elements of a countable set.

No, not exactly: it shows that any list (i.e., countable set) must contain a real not on the list. Therefore, you cannot list all of the real numbers. Cardinality arguments are not really part of the demonstration.
 
  • #7
29
1
Here is what I have come up with. It seems pretty sound to me, but I have little experience in pure math and want to be sure. (I know the easiest way is to show that R is not countable, Q is, so the irrationals, R-Q, is not, but I was wondering about this proof.)

Consider the following numbers:
0.1223334444...
0.112222333333...
0.111222222...
... (When numbers of two or more digits are encountered, they repeat in the same way, e.g. in the first number we would have ...99999999910101010101010101010.... )

These numbers are irrational, as they are non-repeating infinite decimals. They also form an countably infinite set, as they are infinite but can be listed.

However, for obvious reasons, ∏ is not included. Nor is e, √2, or many other irrationals.
Since the set of the irrationals contains more elements than a countable infinite set, it is uncountable. QED

Thanks for looking.

If a set of numbers contains "more elements" than a countable infinite set, that doesn't necessarily mean the set is uncountable.

Look at the set of all integers and the set of all even integers. The set of all integers has more elements than the set of all even integers. The set of all even integers is a countable infinite set. The set of all integers is countable not uncountable.
 
  • #8
35,138
6,889
If a set of numbers contains "more elements" than a countable infinite set, that doesn't necessarily mean the set is uncountable.

Look at the set of all integers and the set of all even integers. The set of all integers has more elements than the set of all even integers. The set of all even integers is a countable infinite set. The set of all integers is countable not uncountable.

See post #2. This is pretty much what I said.
 

Related Threads on Is this proof of the uncountablility of the irrationals valid?

  • Last Post
Replies
8
Views
1K
Replies
6
Views
1K
Replies
1
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
3
Views
4K
Replies
20
Views
4K
Replies
11
Views
796
Replies
2
Views
1K
Replies
10
Views
640
Top