Countable set: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Peter Schmitt
mNo edit summary
 
(45 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{subpages}}
{{subpages}}
In [[mathematics]], a [[set]] is said to be '''countable'''  
In [[mathematics]], a [[set]] is said to be '''countable'''  
if its elements can be "numbered" using the [[natural number|natural numbers]].  
if its elements can be "numbered" using the [[natural number|natural numbers]].  
More precisely, this means that there exists  
More precisely, this means that there exists  
a one-to-one mapping from set to the set of natural numbers.   
a one-to-one mapping from this set to the set of natural numbers.   


A countable set is either '''finite''' or '''countably infinite'''.
A countable set is either '''finite''' or '''countably infinite'''.
A set which is not countable is called '''uncountable'''.
A set that is not countable is called '''uncountable'''.
 
Terminology is not uniform, however:
Some authors use "countable" in the sense of "countably infinite",
and "at most countable" instead of "countable".
Also, sometimes "'''denumerable'''" is used for "countably infinite".
<br>
On the other hand, one must not mix up countable sets with the related, but different,
concept of (recursively) [[enumerable set|enumerable sets]] from [[computability]] theory.
 
The set of natural numbers is countably infinite (of course), but there are also (only)
countably many integers, rational numbers, rational algebraic numbers, and enumerable sets of integers.
<br>
On the other hand, the set of real numbers is uncountable, and there are uncountably many sets of integers.


: Any subset of a countable set is countable.he
: Any subset of a countable set is countable.
: The image of a countable set (under any function) is a countable set.
: The image of a countable set (under any function) is a countable set.
: The countable union (i.e., the union of a countable family) of countable sets is countable.
: The countable union (i.e., the union of a countable family) of countable sets is countable.
: The [[Cartesian product]] of countable sets is countable.
: The [[Cartesian product]] of finitely many countable sets is countable.
 
In terms of cardinal numbers and their arithmetic the [[cardinality]] of a countably infinite set is [[aleph-0|aleph-null]],
and the last two properties can, more formally, be written as:
: <math>\aleph_0 + n = \aleph_0 + \aleph_0 = \aleph_0 \cdot \aleph_0 = \aleph_0^n = \aleph_0 </math>
 
Historically, the necessity to distinguish different "sizes" of infinity
was first observed by [[Georg Cantor]] late in the nineteenth century when he studied sets of real numbers.
He showed that the rational numbers are countable while the real numbers are not,
using arguments which are now known as Cantor's (first and second) [[Cantor's diagonal method|diagonal method]].
 
== Examples ==
 
The basic examples of (finite) countable sets are sets given by a list of their elements:
* The set of even [[prime number]]s that contains only one element: {2}.
* The set of prime numbers less than 10: {2,3,5,7}.
* The set of diagonals in a regular [[pentagon (geometry)|pentagon]] ABCDE: {AC,AD,BD,BE,CE}. (A,B,C,D,E denote the vertices of the pentagon.)
The empty set is countable even though it contains no elements to be counted.


However, in order to show that a set is countable, it is not necessary to provide such a list.
For instance,
* The set of positions in a game of [[chess]] or [[go]].
* the set of [[twin prime]]s is countable though it is not known whether it is finite, and
* the set of even numbers (greater than 2) that ''cannot'' be written as the sum of two primes is countable even though not a single such number is known (see [[Goldbach conjecture]]).


== Examples of countably infinite sets ==
== Examples of countably infinite sets ==


The set of [[integer]]s is enumerable.  Indeed, the function
=== Perfect squares ===


:<math> f(n) = (-1)^n\cdot \left\lfloor \frac{n+1}{2}\right\rfloor </math>
The set of perfect squares is countably infinite, as the following correspondence shows:
: <math> n \leftrightarrow n^2 </math>


is a [[bijection]] between the natural numbers and the integers:
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|-
|-
|''n'' || 0 || 1 || 2 || 3 || 4 || 5 || <math>\cdots </math>
|''n''           || 0 || 1 || 2 || 3 || 4 || 5 || <math>\cdots</math>
|-
|-
|''f''(''n'')|| 0 || -1 || 1 || -2  || 2 || -3 || <math>\cdots</math>
|''n''<sup>2</sup>|| 0 || 1 || 4 || 9 || 16 || 25 || <math>\cdots</math>
|-
|-
|}
|}


The [[union (Mathematics)|union]] of the set of integers with any [[finite]] set is enumerable. For instance, given the finite set
This is an example of a proper subset of an infinite set that has as many elements as the set,
:<math>A = \{ a_0, a_1, \ldots, a_{n-1} \}</math>
a situation addressed by [[Galileo's paradox]].
with cardinality ''n'', this function will enumerate all elements of <math>A \cup \mathbb{N}</math>:


<math>i \mapsto \begin{cases} a_i, & i < n \\ i-n, & \mbox{otherwise} \end{cases}</math>
=== Integers ===


Interestingly, the union of any two enumerable sets is enumerable. Given <math>A=\{a_0, a_1, a_2, \ldots\}</math> and <math>B=\{b_0, b_1, \ldots\}</math> which are both enumerable, the function
The set of [[integer]]s is countably infinite. Indeed, the function
: <math> f(n) = (-1)^n\cdot \left\lfloor \frac{n+1}{2}\right\rfloor </math>
is a one-to-one correspondence between all natural numbers and all integers:


<math>i \mapsto \begin{cases} a_{i/2}, & i \mbox{ is even} \\ b_{(i-1)/2}, & i \mbox{ is odd} \end{cases}</math>
{| class="wikitable" style="text-align:center"
|-
|''n''      || 0 ||  1 || 2 ||  3 || 4 || 5  || <math>\cdots</math>
|- 
|''f''(''n'')|| 0 || -1 || 1 || -2 || 2 || -3 || <math>\cdots</math>
|-
|}


enumerates all elements of both sets. In fact, the union of an enumerable number of enumerable sets is still enumerable. Suppose we have a collection of sets <math>A_0 = \{a_{0,0}, a_{0,1}, a_{0,2}, \ldots\}, A_1 = \{a_{1,0}, a_{1,1}, \ldots\}, A_2, A_3, \ldots</math>. Then we can create a bijection between the whole numbers and all the elements of all the <math>A_i</math> as follows:
=== Union of two countable sets ===


<math>a_{i,j} \leftrightarrow \frac{(i+j)^2+i+j}{2}+j</math>
The [[union (Mathematics)|union]] of the set of natural numbers and any [[finite]] set is countable.
For instance, given the finite set
: <math> A = \{ a_0, a_1, \ldots, a_{n-1} \} </math>
of ''n'' elements, the function
: <math> f(i) \mapsto \begin{cases} a_i, & i < n \\ i-n, & \mbox{otherwise} \end{cases}</math>
shows that <math> A \cup \mathbb{N} </math> is countable.
 
{| class="wikitable" style="text-align:center"
|-
|''i''      || 0 || 1 || <math>\cdots</math> || ''n''-2 || ''n''-1 || ''n'' || ''n''+1 || ''n''+2  || <math>\cdots</math>
|- 
|''f''(''i'')|| ''a''<sub>0</sub> || ''a''<sub>1</sub> || <math>\cdots</math> || ''a''<sub>''n''-2</sub> || ''a''<sub>''n''-1</sub> || 0 || 1 || 2 || <math>\cdots</math>
|-
|}


Notice that this concept is used in the proof of the enumerability of the rational numbers, given below.


The [[rational number|set of rational numbers]] is an enumerable set.  Envision a table which contains all rational numbers (below).  One can make a function that ''dovetails'' back and forth across the entire area of the table.  This function enumerates all rational numbers.
More generally, consider two countably infinite sets:
: <math> A = \{a_0, a_1, a_2, \ldots \} </math> and <math> B = \{b_0, b_1, \ldots \} </math>
then
: <math> i \leftrightarrow \begin{cases} a_{i/2}, & i \mbox{ is even} \\ b_{(i-1)/2}, & i \mbox{ is odd} \end{cases} </math>
is a one-to-one correspondence between <math> \mathbb N </math> and <math> A \cup B </math>.
<br>


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|+Table of all rational numbers
|-
|-
!  !! 0 !! 1 !! 2 !! <math>\ldots</math>
|''i'' || 0 || 1 || 2 || 3 || <math>\cdots</math> || 2''k'' || 2''k''+1 || 2''k''+2 || 2''k''+3 || <math>\cdots</math>
|- 
|      || ''a''<sub>0</sub> || ''b''<sub>0</sub> ||  ''a''<sub>1</sub> || ''b''<sub>1</sub> || <math>\cdots</math> || ''a''<sub>''k''</sub> || ''b''<sub>''k''</sub> || ''a''<sub>''k''+1</sub> || ''b''<sub>''k''+1</sub> || <math>\cdots</math>
|-
|}
 
 
(Note that in the example of the integers the same method has been used:
Let ''A'' be the positive integers and ''B'' be the negative integers.)
<br>
This situation is illustrated by [[Hilbert's hotel]].
 
=== Rational numbers ===
 
The set of (positive) rational numbers is the set of fractions
 
: <math> \{ \tfrac p q \mid p,q \in \mathbb N \}. </math>
 
The fractions can be arranged in an infinite table, the ''q''-th row containing the fractions with denominator ''q'',
the ''p''-th column containing the fractions with numerator ''p''.
 
{| class="wikitable" style="text-align:center"
|-
!  !! 1 !! 2 !! 3 !! 4 !! <math>\ldots</math>
|-
|-
! 1
! 1
| <math>0\over{1}</math> || <math>1\over{1}</math> || <math>2\over{1}</math> || <math>\ldots</math>
| <math>\tfrac11</math> || <math>\tfrac21</math> || <math>\tfrac31</math> || <math>\tfrac41</math> ||<math>\ldots</math>
|-
|-
! 2
! 2
| <math>0\over{2}</math> || <math>1\over{2}</math> || <math>2\over{2}</math> || <math>\ldots</math>
| <math>\tfrac12</math> || <math>\tfrac22</math> || <math>\tfrac32</math> || <math>\tfrac42</math> ||<math>\ldots</math>
|-
|-
! 3
! 3
| <math>0\over{3}</math> || <math>1\over{3}</math> || <math>2\over{3}</math> || <math>\ldots</math>
| <math>\tfrac13</math> || <math>\tfrac23</math> || <math>\tfrac33</math> || <math>\tfrac43</math> ||<math>\ldots</math>
|-
! 4
| <math>\tfrac14</math> || <math>\tfrac24</math> || <math>\tfrac34</math> || <math>\tfrac44</math> ||<math>\ldots</math>
|-
|-
! <math>\vdots</math>
! <math>\vdots</math>
| <math>\vdots</math> || <math>\vdots</math> || <math>\vdots</math> || <math>\ddots</math>
| <math>\vdots</math>   || <math>\vdots</math>   || <math>\vdots</math>   || <math>\vdots</math>  || <math>\ddots</math>
|}
 
These fractions can be arranged in a sequence by sorting them according (''p''+''q'') and ''p'' like this
 
{| class="wikitable" style="text-align:center"
|-
|<math>p+q</math>    || 2 || 3 || 3 || 4 || 4 || 4 || 5 || 5 || 5 || <math>\cdots</math>
|- 
|<math>p</math>      || 1 || 1 || 2 || 1 || 2 || 3 || 1 || 2 || 3 || <math>\cdots</math>
|- 
|<math>\tfrac pq</math>|| <math>\tfrac11</math> || <math>\tfrac12</math> || <math>\tfrac21</math> || <math>\tfrac13</math> || <math>\tfrac22</math> || <math>\tfrac31</math> || <math>\tfrac14</math> || <math>\tfrac23</math> || <math>\tfrac32</math> || <math>\cdots</math>
|-
|                    || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || <math>\cdots</math>
|-
|}
|}


== Counterexamples ==
This correspondence can be described by the following formula:
 
: <math> \frac pq \leftrightarrow \frac {(p+q-1)(p+q-2)} 2 + (p-1) </math>
 
It does not matter that &mdash; because the fractions are not reduced &mdash; each rational number appears infinitely often.
The set of rational numbers corresponds to the set of reduced fractions that is (as subset of a countable set) also countable.


An '''uncountable set''' is one which is not countable. One example is the [[real number|set of real numbers]] is not enumerable, which we will prove by contradiction.  Suppose you had an infinitely long list of all real numbers (below), in no particular order, expressed in decimal notation.  This table, itself, is an enumeration function.  We demonstrate the absurdity of such a list by finding a number which is not in the list.
The same argument shows that the countable union of countable sets is countable, and also
that the Cartesian product of two countable sets is countable.
It is called [[Cantor's first diagonal method]].
 
== Real numbers ==
 
The set of real numbers is '''not''' countable.
The proof is a proof by contradiction, an [[indirect proof]]:
Suppose that the set of real numbers is countably infinite, then the interval
of real numbers ''r'' with <math> 0 \le r < 1 </math> is (as a subset) also countable,
and the interval can be written as a sequence:
 
:  <math> \{ r \mid 0 \le r < 1 , r \in \mathbb R \} = \{ r_i \mid i \in \mathbb N \} </math>
 
Since any real number between 0 and 1 can be written as a decimal number,
the sequence ''r<sub>i</sub>'' can be written as an infinitely long list of decimal numbers:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|+Enumeration of all real numbers
 
|-
! i !! r<sub>i</sub>
! Order !! Real Number
|-
|-
! 0
! 0
Line 92: Line 209:
! ...
! ...
| ...
| ...
|-
!
|0.55544...
|}
|}


Specifically, we construct a number which differs from each real number by at least one digit, using this procedure: If the ith digit after the decimal place in the ith number in the list is a five, then our constructed number will have a four in the ith place, otherwise a five.  From our example list, we would construct the number 0.55544...  By construction, this number is a real number, but not in our list. As a result, the enumeration function is not onto.
But this list cannot be complete:
<br>
To show this, we construct a real number ''r'' with a decimal expansion
which differs from each of the decimal numbers in the list by at least one digit,  
using the following procedure:
<br>
If the ''i''-th digit (after the decimal point) of the ''i''-th number in the list is a '''5''',
then we take '''4''' as the ''i''-th digit of the number, and if not, then we take '''5''' instead.
Thus, for any ''i'' the ''i''-th digit of the newly constructed number  
differs from the ''i''-th digit of the ''i''-th real number in the list,
and therefore the expansion of ''r'' does not appear in the list.
The expansion of ''r'' uses only the digits 4 and 5 and hence is unique,
therefore the real number ''r'' does not occur in the list.
Since this contradicts the initial assumption, this assumption, namely,
that the set of real numbers is countable, is wrong.


This is known as [[cantor's diagonal argument|Cantor's diagonalization argument]]. It is important to note that this argument assumes that two different decimal notations represent two different numbers. This is generally true, with one notable exception. Any digit followed by an infinite series of nines is equivalent to the same digit, increased by one, followed by an infinite series of zeros. For example, 0.3999… is equivalent to 0.4000…. This argument converts individual digits to either fours or fives, thereby avoiding any complications that could arise from this detail.
This is known as [[Cantor's diagonal argument|Cantor's diagonalization argument]].[[Category:Suggestion Bot Tag]]

Latest revision as of 11:01, 2 August 2024

This article has a Citable Version.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=Countable_set&printable=yes
This editable Main Article has an approved citable version (see its Citable Version subpage). While we have done conscientious work, we cannot guarantee that this Main Article, or its citable version, is wholly free of mistakes. By helping to improve this editable Main Article, you will help the process of generating a new, improved citable version.

In mathematics, a set is said to be countable if its elements can be "numbered" using the natural numbers. More precisely, this means that there exists a one-to-one mapping from this set to the set of natural numbers.

A countable set is either finite or countably infinite. A set that is not countable is called uncountable.

Terminology is not uniform, however: Some authors use "countable" in the sense of "countably infinite", and "at most countable" instead of "countable". Also, sometimes "denumerable" is used for "countably infinite".
On the other hand, one must not mix up countable sets with the related, but different, concept of (recursively) enumerable sets from computability theory.

The set of natural numbers is countably infinite (of course), but there are also (only) countably many integers, rational numbers, rational algebraic numbers, and enumerable sets of integers.
On the other hand, the set of real numbers is uncountable, and there are uncountably many sets of integers.

Any subset of a countable set is countable.
The image of a countable set (under any function) is a countable set.
The countable union (i.e., the union of a countable family) of countable sets is countable.
The Cartesian product of finitely many countable sets is countable.

In terms of cardinal numbers and their arithmetic the cardinality of a countably infinite set is aleph-null, and the last two properties can, more formally, be written as:

Historically, the necessity to distinguish different "sizes" of infinity was first observed by Georg Cantor late in the nineteenth century when he studied sets of real numbers. He showed that the rational numbers are countable while the real numbers are not, using arguments which are now known as Cantor's (first and second) diagonal method.

Examples

The basic examples of (finite) countable sets are sets given by a list of their elements:

  • The set of even prime numbers that contains only one element: {2}.
  • The set of prime numbers less than 10: {2,3,5,7}.
  • The set of diagonals in a regular pentagon ABCDE: {AC,AD,BD,BE,CE}. (A,B,C,D,E denote the vertices of the pentagon.)

The empty set is countable even though it contains no elements to be counted.

However, in order to show that a set is countable, it is not necessary to provide such a list. For instance,

  • The set of positions in a game of chess or go.
  • the set of twin primes is countable though it is not known whether it is finite, and
  • the set of even numbers (greater than 2) that cannot be written as the sum of two primes is countable even though not a single such number is known (see Goldbach conjecture).

Examples of countably infinite sets

Perfect squares

The set of perfect squares is countably infinite, as the following correspondence shows:

n 0 1 2 3 4 5
n2 0 1 4 9 16 25

This is an example of a proper subset of an infinite set that has as many elements as the set, a situation addressed by Galileo's paradox.

Integers

The set of integers is countably infinite. Indeed, the function

is a one-to-one correspondence between all natural numbers and all integers:

n 0 1 2 3 4 5
f(n) 0 -1 1 -2 2 -3

Union of two countable sets

The union of the set of natural numbers and any finite set is countable. For instance, given the finite set

of n elements, the function

shows that is countable.

i 0 1 n-2 n-1 n n+1 n+2
f(i) a0 a1 an-2 an-1 0 1 2


More generally, consider two countably infinite sets:

and

then

is a one-to-one correspondence between and .

i 0 1 2 3 2k 2k+1 2k+2 2k+3
a0 b0 a1 b1 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cdots} ak bk ak+1 bk+1 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cdots}


(Note that in the example of the integers the same method has been used: Let A be the positive integers and B be the negative integers.)
This situation is illustrated by Hilbert's hotel.

Rational numbers

The set of (positive) rational numbers is the set of fractions

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ \tfrac p q \mid p,q \in \mathbb N \}. }

The fractions can be arranged in an infinite table, the q-th row containing the fractions with denominator q, the p-th column containing the fractions with numerator p.

1 2 3 4 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots}
1 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac11} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac21} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac31} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac41} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots}
2 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac12} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac22} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac32} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac42} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots}
3 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac13} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac23} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac33} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac43} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots}
4 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac14} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac24} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac34} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac44} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots}

These fractions can be arranged in a sequence by sorting them according (p+q) and p like this

2 3 3 4 4 4 5 5 5
1 1 2 1 2 3 1 2 3
0 1 2 3 4 5 6 7 8

This correspondence can be described by the following formula:

It does not matter that — because the fractions are not reduced — each rational number appears infinitely often. The set of rational numbers corresponds to the set of reduced fractions that is (as subset of a countable set) also countable.

The same argument shows that the countable union of countable sets is countable, and also that the Cartesian product of two countable sets is countable. It is called Cantor's first diagonal method.

Real numbers

The set of real numbers is not countable. The proof is a proof by contradiction, an indirect proof:

Suppose that the set of real numbers is countably infinite, then the interval of real numbers r with is (as a subset) also countable, and the interval can be written as a sequence:

Since any real number between 0 and 1 can be written as a decimal number, the sequence ri can be written as an infinitely long list of decimal numbers:

i ri
0 0.32847...
1 0.48284...
2 0.89438...
3 0.00154...
4 0.32425...
... ...
0.55544...

But this list cannot be complete:
To show this, we construct a real number r with a decimal expansion which differs from each of the decimal numbers in the list by at least one digit, using the following procedure:
If the i-th digit (after the decimal point) of the i-th number in the list is a 5, then we take 4 as the i-th digit of the number, and if not, then we take 5 instead. Thus, for any i the i-th digit of the newly constructed number differs from the i-th digit of the i-th real number in the list, and therefore the expansion of r does not appear in the list. The expansion of r uses only the digits 4 and 5 and hence is unique, therefore the real number r does not occur in the list. Since this contradicts the initial assumption, this assumption, namely, that the set of real numbers is countable, is wrong.

This is known as Cantor's diagonalization argument.

Retrieved from "https://citizendium.org/wiki/index.php?title=Countable_set&oldid=968552"