Yesterday I studied the cardinality of infinite sets and, I must say, it was the first time I have ever distrusted math. That is, it was the first time I have not bought – hook, line and sinker – something about math that was proven to me by a mathematics professor.
This is not to say that I think it is untrue. I am saying that the truth of the cardinality of infinite sets is so at odds with my intuition that I am having trouble believing it. And I could use a bit more explanation, I think, to clear up a few things.
- The distinction between the rules governing finite and infinite sets. For example, we can say that the odd numbers are a proper subset of the integers. We know this absolutely, correct? Yet, we can then prove using diagonalization that the set containing all odds and the set containing all integers have the same cardinality, which is Aleph-null.
How is that we can allow such discontinuity in our understanding of these sets? How can both of those two statements be simultaneously true? How, if A is a proper subset of B, can |A|=|B|? I know this doesn't hold when we limit the conversation to finite sets. However, I don't understand why we can't make the same assertion about these two infinite sets – or at least not definitively say they both have cardinality Aleph-null.
- Proving that the reals don't form a bijective map to Aleph-null. This was proven by trying to map the reals onto the naturals. More specifically, the professor considered only the continuum and showed that the continuum can't map to the naturals and therefore neither can the reals.
The professor did this by showing that any list of natural numbers could never contain all the reals because we can always create at least one new number not contained in the list.
HOWEVER, it felt like a bit of flashy wording to me. If we can do this and then say "look, we didn't account for this number" and furthermore not be allowed to say "okay, but I still have this natural number to which I can map that real number" in this instance, why do the same arguments not apply to other instances? That is, why can't I do the exact same thing when dealing with the mapping between odds/integers?
I know this isn't the typical question for stackexchange, but I really want to nail this down. Don't get me wrong, I know the information. I can apply the information. However, I don't necessarily believe the information and that bothers me a bit.
Best Answer
Your (understandable) disbelief seems to hinge mostly on one idea: The assertion that if $A\subsetneq B$ then $\#A<\#B$.
This is obviously true for finite sets, but as you have learned not for infinite ones, at least given the standard definition of cardinality (not necessarily the only possible one), which asserts that two sets are of equal cardinality if they can be put in bijective correspondence.
A very simple example using this definition is the following: Take the natural numbers $\mathbb N$. Now remove the number $1$. You have a new set that is s strict subset of $\mathbb N$, but if you relabel (i.e. put in correspondence) every element $n$ of that new set with the "label" $n-1$, you suddenly have every single natural number showing up again, despite having removed one at the beginning. Therefore, by the definition of cardinality given above, the cardinalities of the two sets are indeed equal.
The whole apparent paradox disappears the moment you understand that it is not the nature of infinite sets that violates your intuition, but the (re)definitions of common concepts such as "size" when applied to those sets. You are welcome to define cardinality in a way that is compatible with the intuition of inclusion and relative size. The reason why mathematicians don't do the same is that it leads to inconsistencies in set theory.
To put it succinctly: Of course there are more integers than even integers – except if you take "more" to mean set-theoretic cardinality. No conflict with intuition at all.