Difference between revisions of "Countable"
Jump to navigation
Jump to search
Masterbratac (talk | contribs) m (bold title, nicifying link, +links) |
(expand) |
||
| Line 1: | Line 1: | ||
| − | A [[set]] X is '''countable''' if and only if there is a [[bijection]] from X to the set of [[Natural Numbers|natural numbers]]. Countable sets include the set of [[integer]]s and the set of [[rational number]]s. | + | A [[set]] X is '''countable''' if and only if there is a [[bijection]] from X to the set of [[Natural Numbers|natural numbers]]. Countable sets include the set of [[integer]]s and the set of [[rational number]]s. Countable sets are said to have [[cardinality]] <math>\aleph</math>. |
| + | |||
| + | There is no smallest countable set. Indeed, the set of natural numbers is in bijection with the natural numbers without 0: subtracting 1 from every number gives a bijection from the first set to the second. Repeating this process shows that for any initial segment of the the natural numbers (such as {1, 2, ..., n}), we have a bijection between the set of natural numbers and the set of natural numbers without this segment. The bijection is simply subraction by n. | ||
[[Category:Set theory]] | [[Category:Set theory]] | ||
Revision as of 20:38, February 23, 2008
A set X is countable if and only if there is a bijection from X to the set of natural numbers. Countable sets include the set of integers and the set of rational numbers. Countable sets are said to have cardinality <math>\aleph</math>.
There is no smallest countable set. Indeed, the set of natural numbers is in bijection with the natural numbers without 0: subtracting 1 from every number gives a bijection from the first set to the second. Repeating this process shows that for any initial segment of the the natural numbers (such as {1, 2, ..., n}), we have a bijection between the set of natural numbers and the set of natural numbers without this segment. The bijection is simply subraction by n.