[Turing Machine Problem] A set S is countable if S is finite or there is a 1-1 function from N, the set of natural numbers onto S.

i. Prove that for any finite alphabet , is countable.

ii. Show that any subset of a countable set is countable.

iii. As a corollary show that any decidable set is countable.

Hint: You can use the fact that a decidable set can be enumerated in increasing order.

No spamming Please