alternative definitions of countable

The following are alternative ways of characterizing a countable set.

Proposition 1.

Let A be a set and N the set of natural numbers. The following are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath:

  1. 1.

    there is a surjection from to A.

  2. 2.

    there is an injection from A to .

  3. 3.

    either A is finite or there is a bijection between A and .


First notice that if A were the empty setMathworldPlanetmath, then any map to or from A is empty, so (1)(2)(3) vacuously. Now, suppose that A.

(1)(2). Suppose f:A is a surjection. For each aA, let f-1(a) be the set {nf(n)=a}. Since f-1(a) is a subset of , which is well-ordered, f-1(a) itself is well-ordered, and thus has a least element (keep in mind A, the existence of aA is guaranteed, so that f-1(a) as well). Let g(a) be this least element. Then ag(a) is a well-defined mapping from A to . It is one-to-one, for if g(a)=g(b)=n, then a=f(n)=b.

(2)(1). Suppose g:A is one-to-one. So g-1(n) is at most a singleton for every n. If it is a singleton, identify g-1(n) with that element. Otherwise, identify g-1(n) with a designated element a0A (remember A is non-empty). Define a function f:A by f(n):=g-1(n). By the discussion above, g-1(n) is a well-defined element of A, and therefore f is well-defined. f is onto because for every aA, f(g(a))=a.

(3)(2) is clear.

(2)(3). Let g:A be an injection. Then g(A) is either finite or infiniteMathworldPlanetmath. If g(A) is finite, so is A, since they are equinumerous. Suppose g(A) is infinite. Since g(A), it is well-ordered. The (induced) well-ordering on g(A) implies that g(A)={n1,n2,}, where n1<n2<.

Now, define h:A as follows, for each i, h(i) is the element in A such that g(h(i))=ni. So h is well-defined. Next, h is injective. For if h(i)=h(j), then ni=g(h(i))=g(h(j))=nj, implying i=j. Finally, h is a surjection, for if we pick any aA, then g(a)g(A), meaning that g(a)=ni for some i, so h(i)=g(a). ∎

Therefore, countability can be defined in terms of either of the above three statements.

Note that the axiom of choiceMathworldPlanetmath is not needed in the proof of (1)(2), since the selection of an element in f-1(a) is definite, not arbitrary.

For example, we show that 2 is countableMathworldPlanetmath. By the propositionPlanetmathPlanetmathPlanetmath above, we either need to find a surjection f:2, or an injection g:2. Actually, in this case, we can find both:

  1. 1.

    the function f:2 given by f(a)=(m,n) where a=2m(2n+1) is surjective. First, the function is well-defined, for every positive integer has a unique representation as the productPlanetmathPlanetmath of a power of 2 and an odd numberMathworldPlanetmathPlanetmath. It is surjective because for every (m,n), we see that f(2m(2n+1))=(m,n).

  2. 2.

    the function g:2 given by f(m,n)=2m3n is clearly injective.

Note that the injectivity of g, as well as f being well-defined, rely on the unique factorization of integers by prime numbersMathworldPlanetmath. In this entry (, we actually find a bijection between and 2.

As a corollary, we record the following:

Corollary 1.

Let A,B be sets, f:AB a function.

  • If f is an injection, and B is countable, so is A.

  • If f is a surjection, and A countable, so is B.

The proof is left to the reader.

Title alternative definitions of countable
Canonical name AlternativeDefinitionsOfCountable
Date of creation 2013-03-22 19:02:49
Last modified on 2013-03-22 19:02:49
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 03E10