0
$\begingroup$

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.

  • 0
    These proofs work. You were very precise and detailed.2012-09-11
  • 0
    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.2012-09-11
  • 0
    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.2012-09-11
  • 0
    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.2012-09-11
  • 0
    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.2012-09-11
  • 0
    Ok, I see what you mean. Thanks joriki and Henry.2012-09-11

1 Answers 1