Cardinality of infinite sets - Help with intuition

Question

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.

1. 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.

2. 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.

Answer 1

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.

Answer 2

Since pew addressed the first part of your question, I'll address the second. Let's try to use a diagonalization argument to prove that there are more integers than odd integers.

We'll argue by contradiction. Suppose there is a way to list the numbers, $a_1$, $a_3$, $\dots$, using odd indices -- this is what it means to have the same size as the odd numbers. How can we construct a number that is not in our list?

In the proof that $[0,1]$ is uncountable, we used decimal expansions to make a counterexample. So let's try to use decimal expansions to make a number that is not in our list. Every number has a decimal expansion, after all.

In the proof that $[0,1]$ is uncountable, we made a decimal expansion that differed from every other decimal expansion in our list. So let's make a number that differs from every other number in our list in at least one spot in their decimal expansions.

But this is where the argument breaks -- every number has a finite decimal expansion, but there are infinitely many numbers. We can't make a number that has an infinite decimal expansion (although you can in other number systems, like the $2$-adics). If we could make such a number then we would get a contradiction, but we can't.

The reason that $[0,1]$ is uncountable is not that we can randomly pick something that's not in some list. Rather, $[0,1]$ is uncountable because real numbers have infinite decimal expansions.

Answer 3

I think it is fair to say that almost all people experience the same surprise when they first start to examine infinite sets. Our naive intuition is formed by our limited experience of a finite reality, so when we learn of a different (infinite) reality with properties directly opposed to our intuition, naturally we question things. The mathematical formalism (rigorous proofs) leads us to accept these mathematical truths, whether they conform to our intuition or not. Once we get a feel for these proofs and understand fully their detail, then we start to develop new intuitions about new landscapes, such as infinity. As a mathematician, it is important that you keep your mind open to new ideas, and not develop stubborn attitudes. The beauty of the subject should propel you in this direction. Our human mathematics shows us that the human mind can develop new intuitions.

---

Supplementary :

Counter-intuitive results in mathematics are not restricted to Set Theory, you will encounter them in almost any (higher) mathematical theory - and it is not just theorems which are the source. Definitions using generalization and abstraction can often leave us wanting intuition. For example, what does a seven-dimensional sphere look like?

You are reading this on a computer. Mathematics tells us that all computers are logically equivalent and that all they are doing is encoding information by adding natural numbers together. It is not intuitively clear (to me) how all of this computational complexity arises from just adding natural numbers together according to certain rules. For example, how can we expect to achieve machine intelligence just flipping bits in a finite string of ones and zeros?

Finally, spare a thought for all of those budding, young quantum theorists out there. They have only the mathematical formalism to guide them - intuition is alien. Yet quantum theory is very convincing when it comes to its ability to explain reality.