Elementary set theory homework proofs

Question

I've been given some statements to prove using only the following facts.

1. The set of all integers is countably infinite.

2. Let $X$ and $Y$ be sets and suppose $f:X\rightarrow Y$ is surjective. If $X$ is countable, then $Y$ is also countable.

3. The union of a countably infinite family of sets is countable.

I'd like your opinion on my proofs. I feel like the first could be simpler.

Exercise 1. The set $\mathbb{Z}\times\mathbb{Z}$ is countable.

Proof. Let $A_n=\{n\}\times\mathbb{Z}$ for each $n\in\mathbb{Z}$. Define a mapping $f:\mathbb{Z}\rightarrow A_n$ by $f(x)=(n,x)$ for all $x\in\mathbb{Z}$. To see that $f$ is surjective, consider $(n,p)\in A_n$. Since $p\in\mathbb{Z}$, $f(p)=(n,p)$. Thus, $f$ is surjective. By (2), since (1) $\mathbb{Z}$ is countable, $A_n$ is countable.

Let $S=\{A_n:n\in\mathbb{Z}\}$. Notice that $S$ is infinite since it is indexed over $\mathbb{Z}$. Define $g:\mathbb{Z}\rightarrow S$ by $g(x)=A_x$ for all $x\in\mathbb{Z}$. To see that $g$ is surjective, consider $A_q\in S$. Since $q\in\mathbb{Z}$, $g(q)=A_q$. Thus, $g$ is surjective. By (2), $S$ is countable. Thus, $S$ is a countably infinite family of countable sets.

Let $U=\bigcup S$. Then, by (3), $U$ is countable. To see that $U=\mathbb{Z}\times\mathbb{Z}$, we will show that $U$ and $\mathbb{Z}\times\mathbb{Z}$ are subsets of each other.

Let $x\in U$. Then $x\in A_n$ for some $n\in\mathbb{Z}$. Hence, $x=(n,p)$ for some $p\in\mathbb{Z}$. Therefore, $x=(n,p)\in\mathbb{Z}\times\mathbb{Z}$, and it follows that $U\subseteq\mathbb{Z}\times\mathbb{Z}$.

Let $x\in\mathbb{Z}\times\mathbb{Z}$. Then $x=(p,q)$ for some $p,q\in\mathbb{Z}$. Thus, $x\in A_p$, which implies that $x\in U$. Therefore, $\mathbb{Z}\times\mathbb{Z}\subseteq U$, and it follows that $U=\mathbb{Z}\times\mathbb{Z}$.

Therefore, $\mathbb{Z}\times\mathbb{Z}$ is countable.

Exercise 2. Every infinite subset of a countable set is countable.

Proof. Let $X$ be a countable set and let $Y$ be an infinite subset of $X$. Then $X$ is countably infinite and there exists a surjection $f:\mathbb{N}\rightarrow X$. Since $Y\subseteq X$ and $Y$ is nonempty, there exists a surjection $g:X\rightarrow Y$. Thus, $gf:\mathbb{N}\rightarrow Y$ is a surjection. Therefore, by (2), $Y$ is countable.

Answer 1

To reduce the number of unanswered questions, I answer here (albeit belatedly).

Your first proof is just fine. However, depending on what your definition of "countable" is, you may not have followed the instructions for your second proof. Consider the two following definitions (the first of which is standard, and the second of which is equivalent but nonstandard).

1. A set $X$ is said to be countable if there is an injective function $X\to\Bbb N$.
2. A set $X$ is said to be countable if there is a surjective function $\Bbb N\to X$.

If you were given the latter definition, then your second proof is just fine (though, as joriki and Henry pointed out in the comments above, the fact that $X$ is countably infinite needn't even be mentioned). However, if you were given the former definition, then you didn't follow the directions, as you concluded without "acceptable" justification that the surjection $f:\Bbb N\to X$ exists.

Now, there are easy fixes for this. The simplest is just to use the surjection $g:X\to Y$, which is easily constructed (if you want to be cautious) by fixing some $y_0\in Y$ and letting $g(x)=x$ for $x\in Y$, $g(x)=y_0$ otherwise. Since $X$ is countable, then your given fact 2 shows us that $Y$ is countable. Alternately, you can show that there is a surjection $f:\Bbb N\to X$ as follows:

• Since $X$ is countable, then there is an injective function $h:X\to\Bbb N$.
• Since $X$ has an infinite subset $Y$, then $X$ is non-empty, so in particular, we can fix an element $x_0\in X$.
• Define $f:\Bbb N\to X$ by $f(n)=x$ if there is some $x\in X$ such that $h(x)=n$ (such $x$ will be unique if it exists, since $h$ is injective) and $f(n)=x_0$ if $n$ isn't in the range of $h$. $f$ can readily be shown to be a surjective function, and at that point, you can proceed as in your proof.

There are other ways we can fix it, too, but these are probably the simplest.