Blogs, Proofs

Are those really the same size?

In A number bigger than infinity! I described the experience I had during my introduction to proofs class.  In particular, we were able to prove a result that seemed counter intuitive. In doing so, the students were prompted to deepen their understanding of mathematics as a whole.  We left off the last post half way through that lecture, and there were still more surprises.

When are things the same size?

In the earlier part of the lecture, we had shown that two sets are the same size if there is a bijection between them (a 1-1 onto function).  We then showed that no such function can exist between the natural numbers and the power set of natural numbers.  This then showed us that there was something larger than the size of the natural numbers.

As this set in for more students and they accepted the idea of infinities of different size we moved onto a new example.  In particular, we looked at the function \(f: \mathbb{N} \to \mathbb{Z}\) given by \[f(x)=\begin{cases} -\frac{x+1}{2} \text{ if } x \text{ is odd}\\ \frac{x}{2} \text{ if } x \text{ is even.} \end{cases}\]

We then looked at whether this was a function, one-to-one or onto.  You can quickly see that this is a well defined function, and the inverse is \[f^{-1}(y)= \begin{cases} -2y-1 \text{ if } y < 0 \\ 2y \text{ if  } y \geq 0,\end{cases}\] is also a well defined function.  Since, \(f\) has an inverse, it must be a bijection.

We had just gotten done talking about how there were different infinite cardinalities, so most of them didn’t see the implication of this. I then continued and said, “Therefore, there are an equal numbers of integers and natural numbers.”

“But, all natural numbers are integers, and there are integers that aren’t natural numbers, so that can’t be true.”  This was likely on most of their minds, but one of them managed to get the thought out first.

“But, we have just shown the cardinality of each set is the same, so there are not more integers than natural numbers.”  I replied.

“I don’t like it,” was the response I received.

This time around I could tell that they believed their proof to be true, because they had followed along the whole time.  However, even though they accepted the result, they really didn’t like it.  They seemed to be genuinely interested, but they were also shaken because the results weren’t working out the way they would have guessed.

Rational numbers

“How do you think the size of the rational numbers compares to size of the natural numbers?” I asked them.

You could see that they were contemplating the prospect that this was again the same size, but they didn’t really want it to be.  I gave them a moment, then I started writing the following table at the board.

0
1
2
3
\(\frac{0}{1}\)
\(\frac{1}{1}\)
\(\frac{2}{1}\)
\(\frac{3}{1}\)
\(\frac{1}{2}\)
\(\frac{2}{3}\)
\(\frac{3}{2}\)
\(\frac{1}{3}\)
\(\frac{2}{5}\)
\(\frac{3}{5}\)

This then continues of to the right and down forever. We skip \(\frac{2}{2}\) and \(\frac{2}{4}\) because they are represented by \(\frac{1}{1}\) and \(\frac{1}{2}\), respectively. If the rational are the same size are the natural numbers, that is if they are countable, then we will be able to enumerate them.

In order to do this, we start in the upper left hand corner and map and number \(\frac{0}{1}\) as \(1\). We then move right and number \(\frac{1}{1}\) as 2. We can then continue numbering by moving down, right, up, right, down 2, left 2, down … and we continue on in a spiraling manner. Continuing indefinitely, we will have assigned a natural number to every rational number.

Hence, the positive rational numbers are countably infinite.  In order to get that the set of all rationals is countable infinite, we can adjust the process so that we use the odds in the manner described above to enumerate the positive rationals and the evens to enumerate the negative numbers. Therefore, the set of rational numbers has the same cardinality as the natural numbers.

What about the real numbers?

The students had now gotten the point and were no longer surprised. In this state of acceptance, I asked them, “How many real numbers are there compared to natural numbers?”

They seemed to deflate as they just accepted that, again, these would be the same. I let them think that as I started to construct a function.

We began by stating that every real number can be expressed as an infinite decimal. Now, if we consider each entry of the decimal as a component of a tuple, we get that we can represent the real numbers as the tuples \((a_{i}:i \in \mathbb{Z})\), where each \(a_{i} \in \mathbb{Z}\) and \(1\leq a_{i} \leq 9\).

Now, they were following along, but I’m not sure they saw what we had. We next note that if the set \(B\) that contains all such tuples where all entries are either \(0\) or \(1\), then clearly \(B \subseteq \mathbb{R}\). Therefore, \(|\mathbb{R}| \geq |B|=|\mathcal{P}(\mathbb{Z})| > |\mathbb{Z}|=|\mathbb{N}|\).

I could actually see relief at this point as they realized that there are indeed more real numbers than rational numbers. Therefore, I let them know this would also mean that there are more irrational numbers than rational. While it seemed like this was a new idea to them, they longer seemed shocked by what was happening.

Conclusion

As we finished up this proof, the lecture was finally finishing. The class collectively was both exhausted and exhilarated. Not only had they learned something new in the lecture, but they had learned answers to many questions they had never thought to ask. It seemed to open their minds to the prospect that there may be even more out there to learn.

I hope they continue to feel that way, and I hope that by reading their story, you too will be opened up to the possibility that there are things to learn that you have never thought of. That there are so many things that are not known inspires me to continually learn. It’s exciting to be able to share that feeling with both you and my students.

If you liked the story, make sure to click the like button below, or to share the post on Social Media. If you’ve ever been in a class, as student or teacher, where your mind opened to new and exciting possibilities, please let me know by commenting below.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.