Every subset of a countable set is countable. State whether the above statement is true or false with reason.

GATE 1994 · Discrete Mathematics · Countable/Uncountable Set · medium

Answer: TRUE: any subset B of a countable A inherits an enumeration, so B is finite or countably infinite, hence countable.

1. Enumerate the countable set A: Since A is countable, list its elements as a_1, a_2, a_3, ... (a finite list if A is finite). Every element of A, and hence of any subset B, appears somewhere in this list.
2. Restrict the list to B and re-index: Walk through a_1, a_2, ... and keep only the terms that lie in B, relabelling them b_1, b_2, b_3, .... If only finitely many survive, B is finite; otherwise the survivors form an infinite sub-sequence in bijection with N. Either way B is countable, so the statement is TRUE.