Solution Verification: Is the set of all finite subsets of $\mathbb N$ countable or uncountable? I'm pretty sure this is right, just need a quick look over.
It's countable. The set $S$ of all finite subsets of $\mathbb N$ is $\bigcup_{k \in \mathbb N} U_k$ where $U_k$ is the set of subsets of size $k$. If we prove $U_k$ is countable, we then know that $S$ is countable because the countable union of countable sets is itself countable. To show that $U_k$ is countable, note that we can view $U_k$ as ordered k-tuples $(u_{1},\cdots,u_{k})$ such that $u_i < u_{i+1}$ for $1 \leq i \leq k$ because every element in the subset must be distinct and thus must have a strict order. Also note that $\mathbb N^k = \underbrace{\mathbb N \times \cdots \times \mathbb N}_{\text{k copies}}$ is countable because the Cartesian product of a finite number of countable sets is countable. Since $U_k$ is a subset of $N^k$, we know that $U_k$ is countable because the subset of a countable set is itself countable. Since $U_k$ is countable, we have showed that $S$ is countable.
 A: Alternatively,  the set of all finite subsets of $\Bbb N$ corresponds (in a natural way) to the finite binary decimals between $0$ and $1$.  Hence it's a subset of $\Bbb Q$ (since an irrational has an infinite decimal).  Hence countable.
A: Yes, this is correct. There are a number of other cute ways to prove this result:

*

*The uniqueness of prime factorization gives a bijection $n \mapsto (\nu_2(n), \nu_3(n), \dots)$ from $\mathbb{N}$ to the set of finite sequences of elements of $\mathbb{N}$, so the latter is countable. Since the set of finite subsets of elements of $\mathbb{N}$ injects into the set of finite sequences (e.g. by writing the subset in increasing order), the set of all finite subsets is also countable.

*The uniqueness of continued fraction expansions gives a bijection from the set $\mathbb{Q}_{\ge 1}$ of rational numbers greater than or equal to $1$ to, again, the set of finite sequences of elements of $\mathbb{N}$, so the latter is countable, and then we conclude as above.

Playing around with these sorts of arguments leads to the following general heuristic: a set is (at most) countable precisely when an element of it can be specified using a "finite amount of information." To make this precise, we can say that a finite amount of information is a finite string of letters (a "word") from a finite alphabet; this includes, notably, any finite English sentence or finite mathematical expression using a finite set of mathematical symbols (including digits)! Then we just need to prove that the set of finite words from a finite alphabet is countable, which is straightforward, e.g. using lexicographic order, or equivalently base $b$ representations where $b$ is the size of the alphabet.
So: how do we specify a finite subset of $\mathbb{N}$ using a finite amount of information, or more precisely using a finite word from a finite alphabet? We can simply list its elements in increasing order, separated by commas: e.g. $1, 3, 7, 9, 20, 36$. This is a finite string from the alphabet given by the digits $0$ through $9$ together with the comma. The same argument immediately shows that the set of finite sequences of elements of $\mathbb{N}$ is countable too, as above.
You can try to go through all the classic properties of countability this way. For example, why is the product $X \times Y$ of two countable sets countable? Because "a finite amount of information plus a finite amount of information is a finite amount of information"; more explicitly, if the elements of $X$ are represented as finite words on some alphabet $A$, and the elements of $Y$ are represented as finite words on some alphabet $B$, then the elements of $X \times Y$ can be represented as finite words on the alphabet $A \sqcup B \sqcup \{ , \}$, just by writing down the $A$-word, then a comma, then the $B$-word. (And actually we don't even need the comma, we can just interleave the letters of the $A$-word and the $B$-word, like $a_1 b_1 a_2 b_2 \dots$, but this would be harder to read!)
Once you're comfortable enough with this heuristic you should be able to identify almost instantly when a set is countable. Here are some exercises you can try (in each case, try asking: what finite amount of information would suffice to specify an element?):

*

*The set of algebraic numbers is countable.


*The set of computable numbers is countable.


*The set of definable numbers is countable (although this ends up being subtle; see this classic MO answer).
