# Sets and Countablity

Is this set finite, countably infinite, or uncountable:

a) $V = \{f: \mathbb{N} \to \mathbb{N}\}$ (the set of all functions that map each natural number to a natural number.

b) $\mathbb{Z}^3=\{(a,b,c):a,b,c∈\mathbb{Z}\}$ (the set of triples of integers)

Can I just say that we can create a mapping for each triplet in the sense that $(0,0,0) \to 0$, $(1,0,0) \to 1$, $(1,0,1) \to 2$ etc... every triplet will be accounted for and only once (bijection). Therefore, it is countable?

c) $T = \{p(x) : p(x) = a_nx^n +\cdots + a_1x + a_0\mid n \in \mathbb{N},\; a_0, a_1, \ldots, a_n \in \mathbb{Z}\}$ (the set of all polynomials with integer coefficients, of any degree)

I believe you use induction on just a polynomial of degree 2 (whose countability proof is identical to the question above)...but am not exactly getting it

-
Can you use that a countable union of countable sets is countable? – Ilya Dec 2 '11 at 8:54
yes. i think so although could you give a little insight to that? – LiveYourLife Dec 2 '11 at 8:55
My first comment with prime numbers was a bit greedy, as @Matt has told me. You can just use the fact that $$\left|\bigcup\limits_{n=1}^\infty A_n\right| = |\mathbb N\times\mathbb N| = |\mathbb N|$$ where with regards to the last equality I've already replied in another comment to you. Here $A_n$ are any countable sets. – Ilya Dec 2 '11 at 9:51
@Ilya, LiveYourLife: This of course cannot be proved by induction, and requires more assumptions in your theory. If you are taking a naive course in set theory and discrete mathematics then you should find out if you are allowed to use this assumption. – Asaf Karagila Dec 2 '11 at 10:26

In a) the cardinality of the set in question is $|\mathbb{N}|^{|\mathbb{N}|}$, do you see why? To see what this means regarding cardinality note that $|\mathbb{R}| = 2^{|\mathbb{N}|}$. That's uncountable so your set in question is, too.

In b) you have a product of three countable sets. You can argue that $\mathbb{Z} \times \mathbb{Z}$ is countable by finding a bijection to $\mathbb{N}$ and then by induction, $\mathbb{Z}^3$ is countable as well. So: yes, you're right.

Edit If $f$ denotes the function that enumerates $\mathbb{Z}^{n-1}$ then you can define an onto function $F: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{Z}^n$ as follows:

$$(i,j) \mapsto (f(i), g(j))$$ where $g : \mathbb{N} \rightarrow \mathbb{Z}$ is defined as

$$g(j) := \begin{cases} k + 1 & j = 2k \\ -k & j = 2k + 1 \end{cases}$$

Note that this assumes that you showed that $\mathbb{N} \times \mathbb{N}$ is countable and that you know the theorem that says that if $X$ is a countable set and $h: X \to Y$ is surjective then $Y$ is countable.

c) is the same as b) if you replace $3$ by $n + 1$. See Asaf's or Rasmus' answer.

Edit 2

Note that you can think of the polynomial $p(x) = a_n x^n + \dots + a_0$ as a vector $(a_n , \dots , a_0) \in \mathbb{Z}^{n+1}$. Then $T = \{ p(x) \mid p(x) = a_n x^n + \dots + a_0 , n \in \mathbb{N}, a_i \in \mathbb{Z} \} = \bigcup_{n \in \mathbb{N}} \{ \mathbb{Z}^n \}$

You showed in b) that $\mathbb{Z}^n$ is countable so this is a countable union of countable sets and therefore countable, too.

Hope this helps.

-
In c), $n$ is not fixed. – Rasmus Dec 2 '11 at 9:03
@Rasmus: Oh. You're right! Let me fix my answer... – Rudy the Reindeer Dec 2 '11 at 9:05
@Rasmus: Ah, not necessary. You answered that quite well already. : ) – Rudy the Reindeer Dec 2 '11 at 9:06
thank you! this was very helpful. Although, I have one question: can you help me with the actual induction process? Base case: Z x Z is countable Inductive hyp: assume (Z)^(n - 1) is countable Inductive step: Z^n is also countable because the multiplication of two countable sets is countable, the two sets being Z^(n-1) and Z... is this how to do it? – LiveYourLife Dec 2 '11 at 9:27
Base: if $X_1,X_2$ are countable then $X_1\times X_2$ is countable (you can verify it be building bijection from pairs of positive integers $(m,n)$ to the set $\mathbb N$, e.g. considering $2^m3^n$). Inductive step: if $X_1\times\dots X_{n-1}$ is countable, hence $(X_1\times\dots X_{n-1})\times X_n$ is countable . – Ilya Dec 2 '11 at 9:48

Matt's answer gives you a good idea for (a),

(b) Union of countable sets is countable, so is the product of two countable sets. Using induction we can show that finite union of countable sets is countable, and finite products are countable.

(c) However, to show that the polynomials over $\mathbb Z$ are countable you need either to use an assumption that countably infinite unions are countable, or a clever trick.

The clever trick is that a polynomial can be identified by its coefficients, which are a finite subset of $\mathbb Z\times\mathbb N$. Finally, all finite subsets of countable sets give out a countable set.

-

Hints:

b) If your map is "take the sum of the three entries", then it is not injective because both $(1,0,0)$ and $(0,1,0)$ are mapped to $1$. Can you find a proof in your notes saying that if $X$ and $Y$ are countable then the product set $X\times Y$ is countable?

c) Try to find a surjection from $\bigcup_{n\in\mathbb N}\ \mathbb Z^n$ onto the set $T$. Then prove that $\bigcup_{n\in\mathbb N}\ \mathbb Z^n$ is countable as a union of countably many countable sets.

-
The fact that countable union of countable sets is countable requires some choice; however the fact that polynomials are countable does not need such assumption. – Asaf Karagila Dec 2 '11 at 9:06

Yet one more method:

a) Prove that if X is uncountable and f:X->Y is an injection then Y is uncountable (hint look at the contrapositive). There is a 'obvious' injection from the reals to N^N.

b) Once you show Z ~ N it's on;t neccesary to prove NxN ~ N; a standard way is to consider an injection from NxN to N from the use of primes. (hint: look at products of primes - pick exponents wisely). From an induction you then have the result (and equivalence of cardinilty).

c) This has been addressed by others well.

-