4

I have seen proofs of a bijection $f:\mathbb{N} \to \mathbb{Z}$ where

$$f(n) = \begin{cases} \frac{n}{2} & n\text{ is even} \\ -\frac{n + 1}{2} & \text{else} \end{cases}$$

This shows that $\mathbb{Z}$ is countably infinite, that is, $f$ is one-to-one. We can also see that $f$ is onto. Therefore $\mathbb{N}$ and $\mathbb{Z}$ have the same number of elements.

But at the same time, we have $\mathbb{N} \subseteq \mathbb{Z}$. To show $\mathbb{N}$ is a proper subset of $\mathbb{Z}$, it would suffice to show that $\mathbb{Z}$ contains at least one element that $\mathbb{N}$ does not. Notice $-1 \in \mathbb{Z}$ and $-1 \notin \mathbb{N}$, so $\mathbb{N} \subset \mathbb{Z}$ and thus $|\mathbb{N}| < |\mathbb{Z}|$.

I assume this has something to with the fact that these are infinite sets, but I still can't put my finger on exactly why this can happen. If I could have some help understanding why this can happen, that would be great.

memerson
  • 923
Justin
  • 133
  • 8
    In fact, this is one of the mathematical definitions of infinite: 'can be put into 1:1 correspondence with a proper subset of itself'. One search phrase that might get you some helpful information is Hilbert Hotel. – Steven Stadnicki Apr 23 '21 at 04:28
  • 1
    $A \subset B$ (proper inclusion) only tells you $|A| \le |B|$. You can still have $|A| = |B|$. – stoic-santiago Apr 23 '21 at 04:33
  • 4
    The principle that $A\subsetneq B\implies\vert A\vert<\vert B\vert$, while absolutely true for finite sets, is not true for infinite sets; indeed, that's really their defining feature. It might help to go back and see the proof of that "obvious principle" for finite sets (specifically: show that if $A\subsetneq B$ and $A,B$ are finite then there is no injection of $B$ into $A$). It's surprisingly nontrivial! – Noah Schweber Apr 23 '21 at 04:37
  • @NoahSchweber That sounds like an interesting and helpful proof to see. Do you have a link by chance? – Justin Apr 23 '21 at 04:46
  • @epsilon-emperor This is only with infinite sets, correct? I don't see how this couldn't be the case with finite sets. – Justin Apr 23 '21 at 05:00
  • @Justin Yes, equality is possible only if $A$ and $B$ both are infinite. $|A| \le |B|$ holds generally, regardless of what $A$ and $B$ are. – stoic-santiago Apr 23 '21 at 05:10
  • "In mathematics you don't understand things. You just get used to them." --John von Neumann – Nate Eldredge Apr 23 '21 at 05:11
  • 1
    Think as to why is seems intuitive that a proper subset should be smaller than the super element. It probably is because a proper subset should have fewer elements so it'd be smaller. But why would a proper subset having fewer elements mean a set is smaller? Well if it has fewer it can't have as many... but how many do they have. They both have infinite so taking elements away won't reduce anything. Missing elements only make a set smaller if there aren't enough other elements to make up for the missing elements. But if the sets are infinite there's no shortage of elements. – fleablood Apr 23 '21 at 05:46
  • " it would suffice to show that Z contains at least one element that N does not." But that would only suffice if we assume $|\mathbb Z| - 1 < |\mathbb Z|$. It is true that $\mathbb N$ does not contain $-1$. So wherease $\mathbb Z$ will have an infinite number of elements, then $\mathbb N$ can only have..... infinity - 1?? ... this is really a bad way of thinking about bout if $|\mathbb N| = \infty$ then $\mathbb {-n|n\in\mathbb Z}$ is alse $\infty$. And $\mathbb Z$ is both those sets and $0$. So $|\mathbb Z|$ ought to be $2\infty + 1$. But is $2\infty + 1$ any bigger than $\infty$? – fleablood Apr 23 '21 at 05:54

3 Answers3

4

Let's consider an example that is a bit easier to deal with: \begin{align} A &= \{1,2,3,4,\dots\}, \\ B &= \{0,1,2,3,\dots\}. \end{align} It's easy to see that $A\subsetneq B$ and yet $A\to B, k \mapsto k-1$ is a bijection.

The conclusion that $|A|<|B|$ doesn't work for infinite sets, since there are always elements to "fill the gaps". In this example, removing $0$ from $B$ you get a gap at $0$, but $1$ can fill that gap. Now there's a gap at $1$, but $2$ can fill that gap, … Since this "gap filling process" never ends, there is no gap that can't be filled and we get $|A|=|B|$.

Christoph
  • 24,912
0

In fact, it can be shown that for a set $S $, being infinite, or of infinite cardinality, is equivalent to the having the property of being in bijection with a proper subset $P\subsetneq S $.

Of special interest is the (Hilbert's hotel) shifting function, $f(x)=x+1$ from the whole numbers to the naturals.

0

Therefore $\mathbb{N}$ and $\mathbb{Z}$ have the same number of elements.

Wrong. They have the same cardinality. But it has nothing to do with the number of elements.

If we compare their numerocities, then $n(\mathbb{N})=\frac{n(\mathbb{Z})}2-\frac12$

Anixx
  • 9,119