I have the following problem: suppose that we have an infinite set of symbols, $A = \{a_1, a_2, ...\}$ from which all Turing Machine input alphabets are chosen. Show how we could assign an integer to all Turing Machines that had a finite subset of these symbols as its input alphabet.
It seems to me that the set of all finite subsets of $A$ is the power set of $A$. But $P(A)$ is uncountable so I wouldn't be able to assign an integer to all Turing Machines that had an input alphabet in $P(A)$. What am I missing?
The set of all finite subsets of an infinite set is not its power set. For example, the set of all even numbers is in $\mathcal P(\Bbb Z)$, but it is not a finite subset of $\Bbb Z$.
The set of all finite subsets of a countable set is countable. Can you see why?