Let S be a countable set and let T ⊆ S. Then T is countable. If T is finite, then we are done. Thus we may assume that T is infinite. This implies (Exercise 6) that S is infinite, so S is denumerable (since it is countable). Therefore, there exists a bijection f: N → S and we can write S as a list of distinct members

 

Since A is a nonempty subset of N, the Well-Ordering Property of ` implies A has a least member, say a₁. Similarly, the set A\{a₁} has a least member, say a₂. In general, having chosen a₁,…, a_k, let a_{k +1} be the least member in A\{a₁,…, a_k}. Essentially, if we select from our listing of S those terms that are in T and keep them in the same order, then an is the subscript of the nth term in this new list. Now define a function g: N → N by g(n) = an. Since T is infinite, g is defined for every n ∈ N. Since an +1 ∉ {a1,…, an}, g must be injective. Thus the composition f ° g is also injective. Since each element of T is somewhere in the listing of S, g(N) includes all the subscripts of terms in T. Thus f ° g is a bijection from N onto T and T is denumerable. Using Theorem 4.9, we can derive two very useful criteria for determining when a set is countable.