2
$\begingroup$

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

Help appreciated please.

  • 0
    @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.2011-12-02

4 Answers 4

6

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

I'll add Rasmus' answer in my own words, just for completion:

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.

  • 0
    @LiveYourLife: Sorry for the late reply. I added my response to your comment into my answer.2011-12-02
4

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.

2

Hints:

a) Read about Cantor's diagonal argument.

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.

  • 0
    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.2011-12-02
1

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.