Cardinality of sets - Even numbers, naturals, real

Question

Pardon me for asking a question that appears to have been asked many times before, but after browsing several questions here what I found were a bunch of questions that were tangential to my inquiries, however they didn’t really strike exactly what I meant.

I am quite new to set theory. I am currently studying the concept of cardinality, where so many have an existential crisis. When it comes to infinite sets, we say two sets have equal cardinality when it’s possible to establish a bijective correspondence between them.

After having the initial shock that Card($\mathbb{N}$) equals Card(Even), I’m trying to wrap my mind around the intuition as to why this is the case, but the cardinality of the reals is greater than that of natural numbers. I understand, in one case a bijection is possible, in the other it is not, but intuitively that does feel enough.

I’m not looking for a proof, to be honest, there are enough of them on the internet, it’s more like an intuition as to why there is a difference between the cases that I wanted. If anyone could help me, I would be deeply grateful.

Answer 1

It can take a long time to develop an intuition for infinite sets. Some may say that you cannot; you just calculate. This challenge applies to other areas of mathematics as well e.g. geometry in more than three dimensions. Can you visualize 4d Platonic solids? It is hard yet people have managed to classify them.

The first step is to remember what we mean by cardinality for infinite sets. Same size means that there is a bijection between them - that's it. You cannot count them in a usual sense.

An analogy that I sometimes use is a playground with a very large number of children. You want to know whether the number of boys and girls are the same. You cannot count them as they won't stay still. However, if you could get them to pair up and there was no unpaired boys or girls then you would know that there were the same number of each.

(Of course, this plan is also not very feasible in real life for many reasons. It is just a thought experiment.)

So, a bijection means that the sets are the same size without necessarily telling you want the size is.

A weirdness of infinite sets is that you can have a bijection to a strict subset. This is characteristic of infinite sets and is a possible alternative definition of infinite sets.

Back to my playground analogy. If all of the girls were paired with boys but there were some unpaired boys then you would be able to say that there were more boys (assuming only a finite number of children). In the infinite case, finding an injection that is not a bijection proves only that one set is $\le$ the other and not $<$. You need to prove that there cannot be a bijection.

Just keep on thinking of the simple map from the natural numbers to itself: $n \rightarrow 2n$. This must be the simplest example of a bijection from a set to a subset of itself. Or maybe $n \rightarrow n + 1$ is even simpler.

The next hardest bit is understanding the proof that the reals are bigger than the integers. The common proof seems to show that just one was missed. So, it is tempting to tack that on but applying the argument again shows that another was missed. We usually say that the reals are very much bigger not just a little bigger but that feeling depends on other results and is really just a feeling.

Hilbert's Hotel is a good though experiment for developing a feeling for infinite sets. Another recent question discussed it.

Answer 2

One way to think of a bijection from $A$ to $B$ is to think of it a mapping between $A$ and $B$, so that for every $a\in A$, there is exactly one $b\in B$ so that $a \to b$ and for every $b \in B$ there is exactly one $a\in B$ so that $a\leftarrow b$

It should be very intuitive, and even obvious, that $k \leftrightarrow 2k$ is exactly such a mapping between every natural number and every even natural.

Now to show there doesn't exist sum a mapping between integer is not at all obvious.

But there is Cantor's diagonal argument (google it):

If we imagine that every real number had an infinite decimal expansion (it could be ending with infinite $0$s.

Let's imagine that there is a mapping $\mathbb N \leftrightarrow \mathbb R$. We will show this is impossible.

Now let's create real number we will call $y$. Let $1 \leftrightarrow x_1$. Take the first decimal digit in $x_1$. Pick another digit that isn't $0$ or $9$ or whatever the first decimal digit in $x_1$ is. Make that the first decimal digit of $y$.

Let $2 \leftarrow x_2$. Take the second decimal digit in $x_2$. Pick another digit other than $0$ or $9$ or the second digit of $x_2$. Make that the second decimal digit of $y$.

Keep doing that. Let $k \leftrightarrow x_k$. Take the $k$th digit in $x_k$ and pick a *different digit to be the $k$th digit of $y$.

In the end $y$ is not equal to $x_1$ because they have different first digits. And $y$ is not equal to $x_2$ because they have different second digits. And $y $ is not equal to $x_k$ because they have different $k$ digits.

So $y$ is different from every real number that is mapped. So $y$ wasn't mapped and the map isn't complete.

We can not make a map. $|\mathbb N| \ne |\mathbb R|$.

Answer 3

As was noted in the comments, there is no real way to understand this purely intuitively. After all, all describable sets (where there is some finite characterization of every element), no matter how large, are still countable, yet the reals are somehow larger.

While there are a lot of proofs of how the reals are a bigger set than the naturals, I really enjoy Smullyan's proof in Satan, Cantor, and Infinity of the fact that any set can not be put in bijection with its powerset. (It's not hard to see that the powerset of the naturals can be embedded in the reals)

Suppose there is some set $S$ and some bijection $f:S\to\mathcal P(S)$. Let $L\subset S$ contain the lonely elements of $S$, those elements such that $s\notin f(s)$.

So what element maps to $L$? If $l$ is the element that maps to $L$, then either $l\in L$ or not. If $l\in L$, $l$ is lonely, so $l\notin L$. If $l\notin L$, then $l$ is not lonely, so $l\in L$.

This proof demonstrates that there are infinitely many infinite cardinalities, but tells us little about how many cardinalities are "in-between" any two cardinalities. Set Theory is weird.

Answer 4

I would say that a set of cardinality of $\mathbb{N}$ is the one whose members can be - intuitively - listed using a finite system.

What I mean by finite system is a rule to generate all the necessary members of the set given so that you can point to a finite step on which a specific member was generated. There can be no infinite jumps between generated members.

Examples:

1. Even naturals. The system is to list them one by one, on the position $k$ you get number $2k$. Simple as that.
2. Positive rationals, the bad way. You can start by listing first all the rationals as the fractions with 1 in the nominator. Then, after, well, infinite steps, you list all that have 2 in the nominator. See, the infinite jump there invalidates this system. Not all members are in finite positions in this list.
3. Positive rationals, the proper way. You need to create a 2D list: in the rows write down all the fractions with 1 in the nominator, in row 2 - with 2, in row $k$ - with $k$. In columns do the same with the denominator; so that in row $k$ and column $l$ you have a fraction $\frac{k}{l}$. And now the system is to start listing in the upper left corner of the 2D list and zigzaging to the right and down. In other words, you move along diagonal lines stretching from down-left to upper-right, the $m$th diagonal linking all the fractions whose nominator and denominator sum up to $m+1$. No infite jumps needed this time.

The point is, you can find such finite systems also for all the rationals (positive and negative) and even for the algebraic numbers. But you can't for the reals. They are ultimatively un-listable; you won't be able to devise a system to cover all the reals without inifite jumps.

Since it's hard to show that something is not possible to do (as opposed to showing the possible by actually doing it), mathematicians resort to reductio ad absurdum proofs you've seen already. Suppose that there is such a system for reals and watch how the whole mathematical world implodes because of the inconsistency.

I hope that intuition helps.