Countable set: Difference between revisions

Revision as of 17:58, 12 June 2009

Main Article

Discussion

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

Citable Version ^[?]

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.

[edit intro]

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 set to the set of natural numbers.

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

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.

Examples of countably infinite sets

Integers

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

f(n)=(-1)^{n}\cdot \left\lfloor {\frac {n+1}{2}}\right\rfloor

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

n	0	1	2	3	4	5	$\cdots$
f(n)	0	-1	1	-2	2	-3	$\cdots$

Union of to countable sets

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

A=\{a_{0},a_{1},\ldots ,a_{n-1}\}

of n elements, the function

i\mapsto {\begin{cases}a_{i},&i<n\\i-n,&{\mbox{otherwise}}\end{cases}}

shows that $A\cup \mathbb {N}$ is countable.

Interestingly, the union of any two enumerable sets is enumerable. Given $A=\{a_{0},a_{1},a_{2},\ldots \}$ and $B=\{b_{0},b_{1},\ldots \}$ which are both enumerable, the function

$i\mapsto {\begin{cases}a_{i/2},&i{\mbox{ is even}}\\b_{(i-1)/2},&i{\mbox{ is odd}}\end{cases}}$

enumerates all elements of both sets.

Rational numbers

In fact, the union of an enumerable number of enumerable sets is still enumerable. Suppose we have a collection of sets $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$ . Then we can create a bijection between the whole numbers and all the elements of all the $A_{i}$ as follows:

$a_{i,j}\leftrightarrow {\frac {(i+j)^{2}+i+j}{2}}+j$

Notice that this concept is used in the proof of the enumerability of the rational numbers, given below. e 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.

Table of all rational numbers
	0	1	2	$\ldots$
1	$0 \over {1}$	$1 \over {1}$	$2 \over {1}$	$\ldots$
2	$0 \over {2}$	$1 \over {2}$	$2 \over {2}$	$\ldots$
3	$0 \over {3}$	$1 \over {3}$	$2 \over {3}$	$\ldots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

Counterexamples

An uncountable set is one which is not countable. One example is the 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.

Enumeration of all real numbers
Order	Real Number
0	0.32847...
1	0.48284...
2	0.89438...
3	0.00154...
4	0.32425...
...	...

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.

This is known as 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.

@@ Line 16: / Line 16: @@
 == Examples of countably infinite sets ==
-The set of [[integer]]s is enumerable.   Indeed, the function
+=== Integers ===
-:<math> f(n) = (-1)^n\cdot \left\lfloor \frac{n+1}{2}\right\rfloor </math>
+The set of [[integer]]s is countable (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:
-is a [[bijection]] between the natural numbers and the integers:
 {| class="wikitable" style="text-align:center"
 |-
@@ Line 29: / Line 30: @@
 |}
-The [[union (Mathematics)|union]] of the set of integers with any [[finite]] set is enumerable.  For instance, given the finite set
+=== Union of to countable sets ===
-:<math>A = \{ a_0, a_1, \ldots, a_{n-1} \}</math>
-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>
+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> 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.
 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
@@ Line 39: / Line 43: @@
 <math>i \mapsto \begin{cases} a_{i/2}, & i \mbox{ is even} \\ b_{(i-1)/2}, & i \mbox{ is odd} \end{cases}</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:
+enumerates all elements of both sets.
+=== Rational numbers ===
+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:
 <math>a_{i,j} \leftrightarrow \frac{(i+j)^2+i+j}{2}+j</math>
 Notice that this concept is used in the proof of the enumerability of the rational numbers, given below.
+e [[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.
-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.
 {| class="wikitable" style="text-align:center"

Countable set: Difference between revisions

Revision as of 17:58, 12 June 2009

Contents