Countable set: Difference between revisions
imported>Martin Goldstern (→Examples of enumerable sets: n-1. N, not Z) |
imported>Martin Goldstern m (natural nuimbers -- equivalent, but more custmary) |
||
| Line 1: | Line 1: | ||
In [[mathematics]], a [[set]] X is said to be '''enumerable''' or '''countable''' if there exists a [[one-to-one]] [[map|mapping]] from the set of [[ | In [[mathematics]], a [[set]] X is said to be '''enumerable''' or '''countable''' if there exists a [[one-to-one]] [[map|mapping]] from the set of [[natural number]]s [[onto]] X. By the definition, an enumerable set has the same [[cardinality]] as the set of natural numbers. | ||
Enumerable sets are subject to many useful properties. [[inductive proof|Inductive proofs]] rely upon enumeration of induction variables. | Enumerable sets are subject to many useful properties. [[inductive proof|Inductive proofs]] rely upon enumeration of induction variables. | ||
== Examples of enumerable sets == | == Examples of enumerable sets == | ||
The set of [[inter number]s is enumerable. Indeed, the function | |||
:<math> f(n) = (-1)^n\cdot \lfloor \frac{n+1}{2}\rfloor </math> | |||
is a bijection between the natural numbers and the integers: | |||
{| 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> | |||
|- | |||
|} | |||
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. | 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. | ||
| Line 21: | Line 32: | ||
| <math>0\over{3}</math> || <math>1\over{3}</math> || <math>2\over{3}</math> || <math>\ldots</math> | | <math>0\over{3}</math> || <math>1\over{3}</math> || <math>2\over{3}</math> || <math>\ldots</math> | ||
|- | |- | ||
! <math>\ | ! <math>\vdots</math> | ||
| <math>\ | | <math>\vdots</math> || <math>\vdots</math> || <math>\vdots</math> || <math>\ddots</math> | ||
|} | |} | ||
Revision as of 08:12, 20 April 2007
In mathematics, a set X is said to be enumerable or countable if there exists a one-to-one mapping from the set of natural numbers onto X. By the definition, an enumerable set has the same cardinality as the set of natural numbers.
Enumerable sets are subject to many useful properties. Inductive proofs rely upon enumeration of induction variables.
Examples of enumerable sets
The set of [[inter number]s is enumerable. Indeed, the function
- 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 f(n) = (-1)^n\cdot \lfloor \frac{n+1}{2}\rfloor }
is a bijection between the natural numbers and the integers:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 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 } |
| f(n) | 0 | -1 | 1 | -2 | 2 | -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 \cdots} |
The 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.
| 0 | 1 | 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 \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 0\over{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 1\over{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 2\over{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 \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 0\over{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 1\over{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 2\over{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 \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 0\over{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 1\over{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 2\over{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 \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 \ddots} |
The union of the set of integers with any finite set is enumerable. For instance, given the finite set
- 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 A = \{ a_0, a_1, \ldots, a_{n-1} \}}
with cardinality n, this function will enumerate all elements of 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 A \cup \mathbb{N}} :
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 i \mapsto \begin{cases} a_i, & i < n \\ i-n, & \mbox{otherwise} \end{cases}}
Counterexamples
The set of real numbers is not enumerable, which we will prove by contraction. 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.
| 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.