examples of countable sets
This entry lists some common examples of countable sets.
any subset of a countable set (proof (http://planetmath.org/SubsetsOfCountableSets)).
any finite product of countable sets (proof (http://planetmath.org/UnionOfCountableSets)).
the set of all finite subsets of a countable set.
Let be a countable set, and the set of all finite subsets of . Let be the set of all subsets of of cardinality at most . Then is countable, since is. Suppose now that is countable. The function where is easily seen to be onto. Since is countable, so is . Now, is just the union of all the countable sets , and this union is a countable union, we see that is countable too. ∎
the set of all cofinite subsets of a countable set. This is true, because there is a one-to-one correspondence between the set of finite sets and the set of cofinite sets: .
the set of all finite sequences over a countable set.
Let be a countable set, and the set of all finite sequences over . An element of can be identified with an element of , and vice versa (the bijection is clear). Therefore, can be identified with the union of , for . Since each is countable (because is), and we are taking a countable union, is countable as a result. ∎
fix countable sets . The set of all functions from finite subsets of into is countable.
For each finite subset of , the set of all functions from to is just , which has cardinality , and thus is countable since is. Since is just the union of all , where ranges over the finite subsets of , and there are countably many of them (as is countable), is also countable. ∎
fix countable sets and an element . The set of all functions from to such that for all but a finite number of is countable.
the set of all algebraic numbers
Let be the set of all algebraic numbers over . For each polynomial (in one variable ) over , let be the set of roots of over . By definition, is the union of all , where ranges over the set of all polynomials over . For any of degree , we may associate a vector :
The association can be reversed. So the set of all polynomials of degree is equinumerous to , and therefore countable. As is just the countable union of all , is countable, which means is countable also. ∎
the set of all algebraic integers, because every algebraic integer is an algebraic number.
the set of all words over an alphabet, because ever word can be thought of as a finite sequence over the alphabet, which is finite.
|Title||examples of countable sets|
|Date of creation||2013-03-22 19:02:59|
|Last modified on||2013-03-22 19:02:59|
|Last modified by||CWoo (3771)|