1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ All countable infinite sets have the same cardinality. For example , the rational numbers have the same cardinality as the natural numbers. This is still true for the numbers algebraic over the rationals. $\endgroup$ – Peter Mar 13 '18 at 19:57
  • 1
    $\begingroup$ I just want to say that I like the effort you have put into making this post accessible with the formatting and math and all. Keep up the good work. $\endgroup$ – Mankind Mar 13 '18 at 19:59
  • $\begingroup$ Sorry I am very new to latex and it seems I copied wrong question, edited. $\endgroup$ – C. Ekinci Mar 13 '18 at 20:00
  • $\begingroup$ Ah! Thanks for the edit ... that makes more sense! I wondered what was going on :) $\endgroup$ – Bram28 Mar 13 '18 at 20:00
  • 1
    $\begingroup$ A minor oversight. If $f(n_1) = f(n_2)$ it possible (hypothetically) that $n_1\le 0$ is even and $n_2 > 0$ (or vice versa) Is you must prove that if $2|n_1| + 1 = 2|n_2|$ is impossible. ... Actually $|n_1| = |n_2| \not \implies n_1 = n_2$. $|n_1| = |n_2|\implies n_1 = \pm n_2$. $\endgroup$ – fleablood Mar 13 '18 at 20:22
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for taking the time to write this! $\endgroup$ – C. Ekinci Mar 13 '18 at 21:04
2
$\begingroup$
  • 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}$.
$\endgroup$
  • $\begingroup$ Thanks, inexperience with latex. I edited. $\endgroup$ – C. Ekinci Mar 13 '18 at 20:10
  • $\begingroup$ you might like to rule out $f(n_1) = f(n_2)$ where $n_1 \le 0$ and $n_2 >0$ too. $\endgroup$ – Siong Thye Goh Mar 13 '18 at 20:13
2
$\begingroup$

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.

$\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.