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
    Can you use that a countable union of countable sets is countable?2011-12-02
  • 0
    yes. i think so although could you give a little insight to that?2011-12-02
  • 0
    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.2011-12-02
  • 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