alternative definitions of countable
The following are alternative ways of characterizing a countable set.
. Suppose is a surjection. For each , let be the set . Since is a subset of , which is well-ordered, itself is well-ordered, and thus has a least element (keep in mind , the existence of is guaranteed, so that as well). Let be this least element. Then is a well-defined mapping from to . It is one-to-one, for if , then .
. Suppose is one-to-one. So is at most a singleton for every . If it is a singleton, identify with that element. Otherwise, identify with a designated element (remember is non-empty). Define a function by . By the discussion above, is a well-defined element of , and therefore is well-defined. is onto because for every , .
. Let be an injection. Then is either finite or infinite. If is finite, so is , since they are equinumerous. Suppose is infinite. Since , it is well-ordered. The (induced) well-ordering on implies that , where .
Now, define as follows, for each , is the element in such that . So is well-defined. Next, is injective. For if , then , implying . Finally, is a surjection, for if we pick any , then , meaning that for some , so . ∎
Therefore, countability can be defined in terms of either of the above three statements.
Note that the axiom of choice is not needed in the proof of , since the selection of an element in is definite, not arbitrary.
the function given by is clearly injective.
Note that the injectivity of , as well as being well-defined, rely on the unique factorization of integers by prime numbers. In this entry (http://planetmath.org/ProductOfCountableSets), we actually find a bijection between and .
As a corollary, we record the following:
Let be sets, a function.
If is an injection, and is countable, so is .
If is a surjection, and countable, so is .
The proof is left to the reader.
|Title||alternative definitions of countable|
|Date of creation||2013-03-22 19:02:49|
|Last modified on||2013-03-22 19:02:49|
|Last modified by||CWoo (3771)|