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.

  • $\begingroup$ These proofs work. You were very precise and detailed. $\endgroup$ – William Sep 11 '12 at 16:48
  • $\begingroup$ Your use of "countable" and "countably infinite" is slightly confusing. Fact 2 is only true if you're using "countable" to mean "finite or countably infinite", not "countably infinite". But then the assumption in Exercise 2 that the subset is infinite is not required to prove that it's countable, and indeed your proof doesn't really use it; you conclude that $X$ is countably infinite but what follows would work just as well for $X$ merely countable. $\endgroup$ – joriki Sep 11 '12 at 16:55
  • $\begingroup$ In our course, we say a set $X$ is countable if it is finite or if there exists a bijection between $X$ and $\mathbb{N}$. We also call $X$ countably infinite in the second case. In exercise 2, I said the subset was countable because that's how the exercise is worded. $\endgroup$ – ohmygoodness Sep 11 '12 at 17:02
  • $\begingroup$ Perhaps there's a misunderstanding -- I wasn't commenting on the subset being countable but on it being infinite. I understand that this is part of the given wording of the exercise (so the given wording of the exercise is bad), but even so, your proof concludes that $X$ is countably infinite without ever using that fact. $\endgroup$ – joriki Sep 11 '12 at 17:36
  • $\begingroup$ Grad: I think @joriki is saying you could leave the words "$X$ is countably infinite and" out of your second proof and it would still be valid: indeed it would be better because it avoids using a fact you have not been told. $\endgroup$ – Henry Sep 11 '12 at 19:34

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.