If and is countable, take the injection restricted to .

In particular any subset is countable: by the well-ordering principle there is a least element ; remove it and repeat to list . If the process terminates, is finite and so countable. Otherwise the map with is well-defined and injective, and it is also surjective, because every has fewer than elements of below it, so for some . Thus is a bijection and is countably infinite.