Definition: If there exists a 1-1 mapping of onto , we say that and can be put in 1-1 correspondence , or that and have the same cardinal number , or briefly, that and are equivalent, and we write . This relation clearly has the following three properties:
- It is reflexive: .
- It is symmetric: if , then .
- It is transitive: if and , then .
Definition: For any positive integer , let be the set whose elements are the integers, ; let be the set of all positive integers. For any set , we say:
- (a) is finite if for some positive integer .
- (b) is infinite if is not finite.
- (c) is countable if .
- (d) is uncountable if is neither finite nor countable.
- (d) is at most countable if is finite or countable.
Remark: A finite set cannot be equivalent to one of its proper subsets. However, this is possible for infinite sets. In fact, we could restate the definition (b): is infinite if for some .
Theorem 1 Every infinite subset of a countable set is countable.
Proof: Suppose and is infinite. Arrange the elements of which are all distinct in a sequence . Then we construct a sequence as follows:
Let be the smallest number such that . Note exists because is well-ordered. After choosing , we let be the smallest number greater than such that .
Then consider the function where . We then check is indeed a bijection. It is one-to-one because is a distinct sequence; then for any , we have . must be surjective for otherwise, there exists is not in the image of contradicting the fact that .
Corollary 2 Every subset of an at most countable set is at most countable.
Proof: Let be an at most countable set and . If is finite, then is must also be finite. So let us assume is countable. Then cannot be uncountable by theorem 1.
Corollary 3 An at most countable set that contains a countable subset is countable.
Proof: Let be at most countable and is countable. If is countable then we are done. So we need to prove that cannot be finite. Suppose is finite then there exists a bijection . Let . Then the composition must be injective. However, by pigeonhole’s principle we know this cannot happen, thus a contradiction.
Theorem 4 Countable unions of countable sets is countable.
Corollary 5 At most countable unions of at most countable sets is at most countable.
Let be an arbitrary family of sets. We define the Cartesian product to be all the functions such that . We can think of as an evaluation of at the -th entry. For example if , is simply the first entry of the Cartesian product.
Theorem 6 Finitely many Cartesian products of countable sets is countable.
Theorem 7 Countable Cartesian products of countable sets is uncountable.
Proof: Let where is countable for each . Let be an enumeration. For each we pick two different element . Consider the following function:
Note obviously. However, note for all because differs from every at least at . Thus in not countable.
Corollary 8 Let be the set of all sequences whose elements are the digis 0 and 1. Then is uncountable.
Proof: Remember the set is indeed identified with the Cartisian product . Although we cannot directly apply theorem 7 because is finite, we still can use the same Cantor trick. Let be an enumeration of . We define the following function
Again obviously, but differs from for every . Thus is uncountable.
Theorem 9 There exists no surjection from a set to .
Proof: We prove by contradiction. Let be a surjection. By definition, for any there exists such that . Consider the following set
So has an pre-image in . Let such that . It is either or . If it is the first case, then and by definition, but his contradicts the fact that . If it is the second case, we have , so and , contradiction again. Hence cannot be a surjection and the proof is complete.