0
$\begingroup$

I am very new to proofs so please excuse any trivial errors.

In lecture we were told that:

A set $\mathbb S$ is called finite if there exists a one-to-one mapping (bijective mapping) between $\mathbb S$ and the set $\mathbb N_n=\{0,1,2,3,...,n-1\}$ for some natural number $n$. A set is called countable infinite if there exists a bijective mapping between $\mathbb S$ and the set $\mathbb N=\{0,1,2,...\} $ of all natural numbers

I want to answer the following questions:

1. Show that the set $\mathbb S=\{a,b,c\}$ is countable

Does countable mean countable infinite? An attempt from another post on this site: For all triples $(a,b,c)$ there exists an according sum $S=a+b+c \implies ...$ But wouldn't the sum be a surjection between $\mathbb S$ and $\mathbb N$ and not a bijection?

2. Show that the set of integer numbers $\mathbb Z=\{0,\pm1,\pm 2,...\}$ is countable infinite

Before I continue with this proof I have a question about mapping. The definition says that "if there exists a bijective mapping...". In this context, can a function $f(x)$ be considered a mapping? If yes, then can't I just define myself some map $$f:\mathbb Z\to \mathbb N$$

and let $\space f$ be: $$x \mapsto \lvert x \rvert$$

which would then automatically imply that $\mathbb Z$ is countable infinite? (or wouldn't it)?

3. Show that $\mathbb S=\mathbb N \times \mathbb N=\{x |x=(p,q),p,q \in \mathbb N\}$ is countable infinite.

I am not sure about this one but if my "intuition" from 2) turns out to be correct I can maybe define some sort of norm and show that it is a bijection between $\mathbb S$ and $\mathbb N$

$\endgroup$
  • 1
    $\begingroup$ See Countable set: "In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set." $\endgroup$ – Mauro ALLEGRANZA Apr 26 '16 at 15:50
  • 1
    $\begingroup$ For 2. You need it to also be one-to-one. The issue with yours is that, for example, $3, -3\in\mathbb{Z}$ both map to $3\in\mathbb{N}$, but reversing it, $3\in\mathbb{N}$ cannot map to both $3$ and $-3$ in $\mathbb{Z}$ $\endgroup$ – Bonnaduck Apr 26 '16 at 16:10
  • $\begingroup$ @Bonnaduck That makes sense. Thanks! $\endgroup$ – bluemoon Apr 26 '16 at 16:17
1
$\begingroup$
  1. Any finite set is countable (check the definition of countable)

  2. Define $f : \mathbb{Z} \rightarrow \mathbb{N}$ as follows :

if $n \in \mathbb{N} $, $f(n)=2n$, otherwise (if $n < 0 $) $f(n)= 2|n|-1 $

  1. Define $f : \mathbb{S} \rightarrow \mathbb{N}$ as follows:

$\forall (p,q) \in \mathbb{S}, f(p,q) = \frac{(p+q-1)(p+q)}{2} + p + 1 $

This can be seen as "counting elements in a table by diagonal", usually used in order to show that $\mathbb{Q} $ is countable (https://www.google.fr/?gws_rd=ssl#q=count+rational+numbers)

$\endgroup$
  • 1
    $\begingroup$ $f(n) = 2 \mid n \mid - 1$ when $n<0$ would fit better if you want $f$ to be a bijection $\endgroup$ – charmd Apr 26 '16 at 15:54
  • $\begingroup$ Cool idea for 2. Thanks for your help! $\endgroup$ – bluemoon Apr 26 '16 at 16:23
1
$\begingroup$

Hints:

  1. Can you assign each member of $\mathbb{S}$ to a member of (for example) $N=\{4,6,9\}$ ($N=\{0,1,2\}$ is the proper set to do this following your definition)?

  2. Note that you can assign 0 from $\mathbb{N}$ to 0 in $\mathbb{Z}$, then 1 from $\mathbb{N}$ to 1 in $\mathbb{Z}$, then 2 from $\mathbb{N}$ to -1 in $\mathbb{Z}$, and so on... (Write this more formally).

  3. Consider the cartesian plane. You can draw the points $(p,q)$ as a grid that covers the first quadrant. You can trace them from $(0,0)$ to (1,0) to (0,1) to (0,2) to (1,1) to (2,0) to (3,0), etc... making something like a zigzag motion. Then each step corresponds to a natural number

$\endgroup$

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.