$|\mathbb{Z}|=|\mathbb{N}|$

Question

Hello all, if you could give some critique on my proof I would be grateful.

Show that $|\mathbb{Z}|=|\mathbb{N}|$ for,

$$\displaystyle f(n) = \begin{cases} 2|n|+1, \text{if} & n\leq0 \\ 2n, \text{if} & n>0\end{cases}$$

By the definition of cardinality (def. 2.10b) we note that if a function is bijective, cardinality of the sets equal to one another. So, we want to show that $f(n)$ is bijective. To prove that $f:\mathbb{Z}\rightarrow \mathbb{N}$ injective, we must show $\forall n_1,n_2\in \mathbb{Z}$, if $f(n_1)=f(n_2)$ then $n_1=n_2$ for both conditions of $f(n)$, so,

$f(n)=2|n|+1 $, if $ n\leq 0$
$2|n_1|+1 = 2|n_2|+1$
$2|n_1|=2|n_2|$
$|n_1|=|n_2|$

and

$f(n)=2n$, if $n>0$
$2n_1=2n_2$
$n_1=n_2$

Thus we see that $f(n)$ is clearly injective. To prove $f:\mathbb{Z}\rightarrow \mathbb{N}$ is surjective, meaning $\exists n\in \mathbb{Z},\forall r\in \mathbb{N}$ s.t. $f(n)=r$, again for both conditions,

$f(n)=2|n|+1 $, if $ n\leq 0$
$r=2|n|+1$
$r-1=2|n|$
$|n|=\frac{r-1}{2}$

and

$f(n)=2n$, if $n>0$
$r=2n$
$n=\frac{r}{2}$

Thus we see that for both conditions $f(n)=r$, and function $f:\mathbb{Z}\rightarrow \mathbb{N}$ is surjective. Hence, we prove $f:\mathbb{Z}\rightarrow \mathbb{N}$ is bijective as it is injective and surjective. Therefore, by definition of cardinality, we say that cardinality of $\mathbb{N}$ is equal to $\mathbb{Z}$. $\blacksquare$

Answer 1

You are very very close.

But:

You say "Now, suppose f(n) is injective, meaning ∀n1,n2∈Z, if f(n1)=f(n2) then n1=n2 for both conditions of f(n), so,..."

This is what you want to prove. You are not "supposing" it. ANd the "so...." does not follow as a result. What follows is your attempt to prove it.

ANd then

$f(n) = 2|n| + 1$ if $n \le 0$

$2|n_1| + 1 = 2|n_2| + 1$. But you do not know if $n_1, n_2$ are positive or negative. You must conisder all options that $f(n_1) = f(n_2)$ even if they are different signs.

And then you get:

$|n_1| = |n_2|$ therefore

$n_1 = n_2$. That is not true. It is possible that $n_1 = -n_2$.

You might need to do cases:

$f(n_1) = f(n_2)$

Case 1: $n_1 \le0; n_2\le 0$.

$2|n_1|+1 = 2|n_2| + 1$

$|n_1| = |n_2|$ but as $n_1 \le 0$ and $|n_2 \le 0$

$-n_1 = - n_2$ and $n_1 = n_2$.

Case 2: $n_1 > 0; n_2>0$.

Then $2|n_1| = 2|n_2|$

$|n_1| = |n_2|$ but as both are positive

$n_1 = n_2$.

Case 3: $n_1 \le 0$ and $n_2 > 0$

Then $2|n_1| + 1= 2|n_2|$.

This is an odd number equaling an even number. This is impossible.

Case 4: $n_1 > 0; n_2 \le 0$

This is no different essentially than case 3.

...

Notice it might be easier if you had done

$f(n) = -2n + 1$ if $ n \le 0$ and $f(n) = 2n$ if $n > 0$.

Then we could say $f(n_1) = f(n_2) $ means either

1) $-2n_1 + 1 = -2n_2 + 1$

2) $2n_1 = 2n_2$

3) $-2n_1 + 1 = 2n_2$

4) $2n_1 = -2n_2 + 1$.

1) and 2) both reveal $n_1 = n_2$.

3) $n_2 = -n_1 + \frac 12$. Which is impossible as the RHS is not an integer.

4) $n_1 = -n_2 + \frac 12$. Ditto.

.... oh.... Your surjectivity is kind of a mess.

To prove surjectivity you choose and arbitrary $r \in \mathbb N$ and prove there must be an $n \in \mathbb Z$ so that $f(n) = r$. You have to start with the $r$ and prove there is an $n$ that goes to it. You can't start with the $n$. You get $n = |\frac {r-1}2|$. Well, so? How do you know that that is even an integer. It isn't if $r$ is even. How do you know $r$ is odd?

So suppose $r \in \mathbb N$. Either $r$ is even. Or $r$ is odd$.

If $r$ is even let $n = \frac r2$. And $n > 0$ we know $n =\frac r2 > 0$.

So $f(n) = 2|n| = 2|\frac r2| = |r| = r$.

If $r$ is odd, let $n = -\frac {r-1} 2$. So $r \ge 1$ then $n = -\frac {r-1}2 \le 0$.

So $f(n) = 2|n| + 1= 2|-\frac {r-1}2| + 1 = 2*\frac {r-1}2 + 1 = (r-1) + 1 = r$.

So for any $r \in \mathbb N$ there will be an $n\in Z$ so that $f(n) = r$.

Again as youare defining $f$ in terms of whether $n$ is positive or non-positive, you don't/shouldn't define $f$ in terms of absolute values.

If $f(n) = 2|n| + 1$ then we know $n \le 0$ so just say $f(n) = -2n + 1$.

And if $f(n) = 2|n|$ when we know $n > 0$ so just say $f(n) = 2n$.

Also as Yves Daoust suggest:

consider defining $g: \mathbb N \to \mathbb Z$ as $g(n) = \frac n2$ if $n$ is even, and $g(n) = -\frac {n-1}2$ if $n$ is odd.

You'll find this direction is a bit easier and more natural (although your direction is also correct.)

If $n$ if even then $g(n) = \frac n2 > 0$. If $n$ is odd then $g(n) = -\frac {n-1} 2 \le 0$.

So if $g(n) = g(m) > 0$ then $m,n$ are both even and $\frac m2 = \frac n2$ so $m = n$.

And if $g(n) = g(m) \le 0$ then $m,n$ are both odd and $-\frac {m-1}2=-\frac {n-1}2$ so $m = n$.

So $g$ is injective.

And for any $r \in \mathbb Z; r >0$ then $n = 2r \in \mathbb N$ and $g(n) = \frac {2r}2 = r$.

And for any $r \in \mathbb Z; r \le 0$ then $n = -2r + 1 \in \mathbb N$ and $g(n)=- \frac {(-2r + 1)-1}2= r$.

So $g$ is surjective.

Answer 2

• Before you show that something is a bijection, first write down what is the function being discussed.

• We don't suppose something is an injective/ surjective if we want to prove that they are injective or surjective.

• From $|n|=\frac{r-1}2$, we do not have $n = |\frac{r-1}2|$.

• While $f$ is indeed injective, it is not clear to me how is it clear to you that it is injective. In fact your working of injective and surjective are exactly the same. To prove injective, assume $f(n_1)=f(n_2)$ and deduce that $n_1=n_2$.

• For the proof of surjection, hightlight that the preimage indeed comes from $\mathbb{Z}$.

Answer 3

Using common sense:

• send even naturals to positives,

• send odd naturals to negatives.

This is clearly reversible and establishes a bijection. Some care is required in the vicinity of $0$, but if necessary you can adjust by translation.