Difference between revisions of "Countable"
| Line 2: | Line 2: | ||
There is no smallest infinite 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. | There is no smallest infinite 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. | ||
| + | |||
| + | Since the natural numbers are [[ordered]] it is immediate that any countable set can also be [[ordered]]. Whether or not larger sets, especially the [[real numbers]], can be [[ordered]] is dependent on the [[axiom of choice]]. | ||
[[Category:Set theory]] | [[Category:Set theory]] | ||
Revision as of 20:16, June 11, 2008
A set X is countable if and only if there is a bijection from X to a subset set of natural numbers. Countable sets include finite sets, the set of integers, and the set of rational numbers.
There is no smallest infinite 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.
Since the natural numbers are ordered it is immediate that any countable set can also be ordered. Whether or not larger sets, especially the real numbers, can be ordered is dependent on the axiom of choice.