Exercise 1.4.10

Show that the set of all finite subsets of the natural numbers is countable.

Here is my shot at this one.

Proof: Let $S$ be the set of finite subsets of $\mathbb{N}$. Then $S$ can be defined as

$$S=\left\{{\{\emptyset\},\{\mathbb{N_1}\},\{\mathbb{N}_1\times\mathbb{N}_2\},.......,\{\mathbb{N_1}\times\mathbb{N_2}\times......\times\mathbb{N_n}}\}|n<\infty]\right\}. $$

Then recall that we discussed that there exists a bijective function such that
$$F:\mathbb{N_1}\to\mathbb{N_1}\times\mathbb{N_2}.$$
Thus $\mathbb{N_1}\times\mathbb{N_2}$ is countable. The subscripts are used here just to remain consistent. Then we can look at $\mathbb{N_1}\times\mathbb{N_2}\times\mathbb{N_3}$. becuase of the previous bijective funcion this problem boils down simply to $\mathbb{N_1}\times\mathbb{N_3}$. Which we can see from the last fuction is countable because $\mathbb{N}\times\mathbb{N}$ is countable. Thus expanding this for $\mathbb{N}_n$ can be looked at simply as $\mathbb{N_1}\times\mathbb{N_n}$ which by previous definitons is countable. Therefore because $S$ is simply the collection of countable sets this makes S countable itself.

I don't think I get it.

You're considering a set of countably infinite Cartesian products, rather than a set of finite lists of natural numbers.

I think it's as simple as showing how you would write the sets. It reminds me of the $\mathbb N$ $X$ $\mathbb N$ "table" we wrote down. There has to be a creative way to show how we would count every set. It helps to list all the ways it is "countable".

For instance all the sets that contain one element of $\mathbb N$ are infinitely countable because we can just pair them up with their natural numbers. (such as the set that contains 1 is counted first, the set that contains 2 is counted second).

We know that the sets with one element are countable, so if we can show the sets that contain two Natural numbers as elements are countable, we could probably prove this for all the countable sets in $\mathbb N$ through induction.

Obviously this isn't a proof I just wanted to share my approach.

Does the fact of whether the elements of a set are themselves countable or uncountable sets have a bearing on whether the set is countable? The set $\{\mathbb{R}, \mathbb{R}, \mathbb{R}\}$ has three elements, right?

As for me, I have no idea where to start.

Also, I'm not sure how the set we're considering is different from $\mathcal{P}(\mathbb{N})$, which is uncountable. Edit: Nevermind, $\mathcal{P}(\mathbb{N})$ contains $\mathbb{N}$ as well.

Well I remember going over count-ability in class. Like how the union of a finite set and a countably infinite set are countably infinite. That's why I assumed the induction method would work, because the set of all Sets with one Natural number in them ($S_{1}$) is countably infinite, and then the set containing two natural numbers ($S_{2}$) is countably infinite, we know that $S_{1} \cup S_{2}$ is countably infinite as well.

I'm not sure if that answers your question though, violin.

Yeah, totally. Honestly I just didn't consider your post deeply enough at first to realize what you were saying. Thanks for clarifying!

I'm stumped on this one man.

Note the sets of cardinality one, denoted $S_1=\{\{1\},\{2\},\{3\},\dots\}$ is countably infinite by the definition of countably infinite. Also notice the set $S_2=\{\{1,1\},\{1,2\},\{2,1\},\dots\}$ is countable by the diagonalization method that was shown in class. This shows the base case and by way of induction assume that the set $S_n$ for $n\in \mathbb{N}$ is countable. Our job is to show $S_{n+1}$ is countable. Note by the inductive hypothesis since $S_{n}$ has an ordering that corresponds to the natural numbers. We will let this ordering be $S_n=\{s_1,s_2,s_3,\dots\}$ where each $s_i$ is a set with $n$ natural numbers in it. Now we can construct a chart with $S_n$ along the top and $\mathbb{N}$ along the side and each section on the table is the union of these sets.

This can be found in the link here.

Once we have this chart, we can use diagonalization to give an ordering of these with the natural numbers. Then we have an ordering of the set $S_{n+1}$. Now by induction we have proven all subsets of cardinality $n$ are countable. Now we union them all together and we get a countable set by the theorem that says the union of infinitely many countable sets is countable. Thus the set of all finite subsets of the natural numbers is countable.

I think Jordan is on the right track! I also think this can be simplified by using the theorems we discussed in class, though.

Also, $\mathcal{P}(\mathbb{N})$ contains the set of all even numbers, the set of all multiples of 3, the set of every natural number except $1$, etc. These infinite sets make up the "bulk" of $\mathcal{P}(\mathbb{N})$ .
.

Ok, that makes a lot more sense as to why the powerset is uncountable. Thanks!