# Concept of cardinality and infinite sets

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?

• I'm tempted to tag your question as philosophy as well. Two sets having the same size means exactly there existing a bijection between the sets, by definition. So when you ask how you can realize that this is true, I can only interpret this as meaning there is an objective truth that we're trying to get to (this is called Realism), hence the tag philosophy. But if you want to ask about the motivation for this definition of "two sets having the same size", that seems less philosophical and clearer. – Git Gud Oct 2 '18 at 4:20
• As I think you understand from your fourth paragraph, not every attempt at forming a bijection will be fruitful, and there's no logical reason to suggest that initially failing to find a bijection means that there is no bijection. Sometimes it just means that you need to look a bit harder, or be a bit more clever. – Theo Bendit Oct 2 '18 at 4:20
• Since the idea that "a proper subset has strictly lesser cardinality" is not true in general, perhaps it's worth reading up on why it is true in the finite case? – Theo Bendit Oct 2 '18 at 4:23
• @NuntractatusesAmável Equivalent assuming (a very weak version of) the axiom of choice holds. – spaceisdarkgreen Oct 2 '18 at 4:35
• The basic concept one must learn is that "size" isn't about whether things have things can sometimes have left over or can be put into different looking boxes. "size" is entirely about pairing items up one-to-one and nothing else. So sometimes having numbers left over does not matter. As for the intuition: If you have an infinite set you can always fit one more in (or one more out) without it becoming bigger or smaller... because it is infinite. .... – fleablood Oct 2 '18 at 4:52

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.

A finite set has a specific number of elements in it. A finite set might have $$7$$ elements or it might have $$2,137$$. But it does have a specific number.

And if you add a few elements or take a few elements away then you get a different number. This is because adding and subtracting numbers gives you... different numbers.

Infinite sets do not have any specific number of elements in it. Adding or subtracting a few elements will not change how many elements you have. You can even remove every other element (thus remove an infinite number) and still have an infinite number. (Remove all odds from all the integers you are still left with all the evens).

So because you can always add or subtract and not change size, you can always find some way to rearrange infinite things so that you have left overs. Or you can rearrange so you dont "have enough". So the possibility of maybe having leftovers or maybe not having enough, can't and doesn't actually matter when it comes to cardinality.

What does matter is if you HAVE to have left overs. Or if you will never have enough. It doesn't matter if you might have leftovers but if you HAVE TO have left overs and can't avoid, then they are not the same size.

And if you CAN have it work out evenly and avoid leftovers or find a way so that you have "just enough", if that is possible (not every time but if it possible to sometimes have it perfectly even) then we say they are the same "size". Well, we don't. We say they are the same cardinality. As "size" is misleading and actually meaningless now.

Foe example $$\mathbb Z \to \mathbb N$$ via, if $$x > 0$$ then $$x\to x$$ will have "leftovers". None of the negatives are mapped. But that's fine. That's just one way of doing it.

We could have done. $$\mathbb Z \to \mathbb N$$ via, if $$x <0$$ then $$x\mapsto 2^{|x|}$$ and if $$x \ge 0$$ then $$x\mapsto 3^x$$. Then we don't have any leftovers. We have the opposite problem. We don't have enough! we only mapped to the powers of $$2$$ and $$3$$. No other primes and no other composites get mapped to at all.

But that doesn't matter. That was only one way of doing it. We can also do. If $$x \le 0$$ them $$x\mapsto 2|x|+1$$ and $$x > 0$$ then $$x\mapsto 2x$$. That is one to one and we have no left overs and they all fit. That we could do that is what matters. That there were other unsuccessful ways does not.

Another example: $$\mathbb Z \to \mathbb R$$. If we come up with an injective map (so that no two integers map to the same real number) then we will never have leftovers and we will never have enough. And we can never do it evenly. So they are different cardinalities.