I have seen a proof that says integers and natural numbers have the same cardinality. I understand that if we can prove there exists a bijection from $\Bbb N$ to a random set, then that set has the same cardinality as $\Bbb N$.
My question is what is wrong in me thinking the following-
If I map every natural number in $\Bbb N$ to every natural number in $\Bbb Z$, it seems to me that nonnegative integers are being left out. How, then, do $\Bbb N$ and $\Bbb Z$ have the same size? What implicit assumption have I made that is creating an issue?
I realize that certain functions cannot be used to prove two sets have the same size. For finite sets, if I can establish an injective function from $A$ to $B$ and there are elements in B being left out, then A and B do not have the same cardinality. This seems to not hold for infinite sets. What is the intuition behind that? How can I realize this to be true?
Best Answer
As a warm-up example, it's easiest to show that there'a a bijection between the natural numbers $\{0,1,2,3,\ldots\}$ and the even natural numbers $\{0,2,4,6,\ldots\}.$ This bijection takes the simple form $f(n) = 2n.$ You could make the same argument about these as you did for the integers and the naturals, since the evens are a proper subset of the naturals.
For a bijection between $\mathbb N,$ $\mathbb Z,$ simply find some orderly way to list off the integers one at a time. Like $f(0)=0, \;f(1)=1,\; f(2)=-1,\; f(3)=2,\; f(4) = -2,\ldots$
Hopefully these examples are enough to convince you that there can be a bijection between an infinite set and a proper subset. And the fact that the obvious inclusion that 'leaves the negative integers out' is not a bijection does not mean that no bijection exists.
As for why we say two sets that have a bijective correspondence have the same size, well, that's a choice we make for how to conceive of the informal notion of 'having the same size'. Basically, we just think if we can pair them off, one by one, with each element in one set corresponding to an element in another, then they have the same size. This certainly rings true in the finite case. But if we make this choice, we need to get comfortable with the fact that some properties of finite sets that have the same size do not hold for infinite sets, like that one can't be a proper subset of the other. But to say this decision to really care about bijections has been fruitful in mathematics would be an understatement.
Notice also that the notion of having a bijection is mathematically precise, whereas our decision to say 'that means they have the same size' doesn't really have any mathematical content at all, only philosophical content.