Blogs, Proofs

A number bigger than infinity!

During class today, I had a wonderful experience.  I was teaching my students about functions.  This may seem late in the semester to bring up such an elementary topic.  However, in my introduction to proofs class, we were more precisely defining a function, \(f\), from the sets \(A\) to \(B\) as a subset of \(A \times B\).  Doing this, we were able to present a connection between functions and relations.  We had finished talking about equivalence relations and partial ordering, so we were able to use something they were familiar with as another example of a relation.

In our discussion of functions, we looked at what it means for a function to be injective (1-1), surjective (onto) and bijective (1-1 and onto).  As a quick reminder, let \(f: A \to B\) be a function.  Then \(f\) is injective if, for each \(y \in B\), there is at most one \(x \in A\) such that \(f(x)=y\).  Furthermore, \(f\) is surjective if, for each \(y \in B\), there exists an \(x \in A\) such that \(f(x)=y\).  We then have that \(f\) is bijective if, for every \(y \in B\), there exists a unique \(x \in A\) such that \(f(x)=y\).

Using these properties

What they were able to notice right away is that, if \(f\) is surjective, then the cardinality of \(A\), \(|A|\), must be at least as large as the cardinality of \(|B|\).  That is, \(|A| \geq |B|\).  Similarly, if \(f\) is injective, then \(|A| \leq |B|\).  We then have that if \(f\) is a bijection we must have \(|A|=|B|\).  We then went through an example to show you could use this to show that two different sets would have the same cardinality.

Here we said, suppose that \(A=\left\{1,2,3\right\}\), then \(|\mathcal{P}(A)|=|\left\{(a_{1},a_{2}, a_{3})): a_{1},a_{2},a_{3} \in \left\{0,1\right\} \right\}\).  In other words, the size of the power set of a three element set is the same as the size of the set consisting of order triplets with entries being either \(1\) or \(0\).  I gave them some time to try to come up with a function to show this, but eventually I gave them the following.

Let \(f:\mathcal{P}(A) \to \left\{(a_{1},a_{2}, a_{3})): a_{1},a_{2},a_{3} \in \left\{0,1\right\} \right\}\) be given as follows.  If \(X \subset A\), then \(X\) is mapped to the ordered triple \((x_{1},x_{2},x_{3})\) where \(x_{i}=1\) if \(i \in X\) and \(x_{i}=0\) otherwise.  For example, the set \(f(\left\{1,3\right\})=(1,0,1)\) because one and three are in \(X\) but two is not.

Since a set \(X \subseteq A\) is uniquely determined by whether or not each element is in it and our tuple is determined by the 0 and 1s, we have that this function must be a bijection.

Generalizing this function

We just saw how nicely this worked for a three element set \(A\), but what if we had an arbitrary set \(A\)?  That is, if we define let \(B=\left\{(b_{a}:a \in A)\right\}\), is it true that \(f:|\mathcal{P}(A)=|B|\) given by \(X \mapsto (x_{a}:a \in A)\) where \(x_{a}=1\) if \(a \in X\) and \(x_{a}=0\) otherwise is a bijection?  Well, the argument follows exactly as it did above.  For each choice of is \(a \in X\) or is \(a \notin X\) we construct a different subset of \(A\) and all subsets are possible.  We therefore have that \(|\mathcal{P}(A)|=|B|\).

This went very well, so I was feeling like we should continue a little further.  I then looked at what would happen if we mapped \(A \to B\)?

In this case suppose that \(f:A \to B\).  Since \(f\) maps \(A\) to \(B\), we must have that \(f(y)=(x_{a}:a \in A)\) for all \(y \in A\).  While we don’t know exactly what the entries, we know that they must be defined.  In this way, we can define \(z_{y}=1\) if \(x_{y}=0\) in \(f(y)\) and \(z_{y}=0\) if \(x_{y}=1\) in \(f(y)\).  That is, we have that \(f(y)\) is an order tuple with entries for every element in \(A\).  It will therefore have an entry for \(y\) since \(y \in A\).  We are now defining a new element \(z \in B\) in such a way that the \(y\)th entry of \(z\) is not the same as the \(y\) entry of \(f(y)\).  However, since we did this for every \(y \in A\), there cannot be any element \(w \in A\) such that \(f(w)=z\).  That is, there are no functions from \(A \to B\) that are onto.  Therefore, \(|A| < |B|=|\mathcal{P}(A)|\).

And that means?

At least that was the question they had for me.  While they seem to follow the agree with each step of the proof the end result was a bit lost.  Therefore, I recapped for them, and I told them that what we had just proven is that the power set of a set is always strictly bigger than the original set.  They looked back as if to say, well isn’t that obvious?  Yes, I suppose it is in the finite case, but we didn’t work with finite sets above.  Therefore this is always true.  In particular, we have that \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\).

This is where they started to see what was going on.  That is, the set of natural numbers, \(\mathbb{N}\), is infinite.  However, if the cardinality of the power set of \(\mathbb{N}\) is strictly bigger than \(\mathbb{N}\), we have found a number bigger than \(\infty\).  They looked at the board, looked around the room, and finally a few of them said, “I don’t believe you!”

Finally!

As a mathematician, I have been telling all of my classes that they shouldn’t believe anything I say.  They should always check my work and make me prove to them any statements I make.  It’s not that I don’t want them to trust, rather it’s that I want them to “trust but verify” (a saying made popular by Ronald Reagan).  I have never had a class quite so enthusiastically do as I’ve asked them.  I could see them get excited.  They really tried to contemplate everything we had just worked through, looking for the smallest of mistakes.  Redoing the proof in their heads and trying to make sense of what they’ve just seen.  It was exciting to see my students acting like mathematicians.

After giving them some time to look at the proof, I finally told them, “I wasn’t the one that stated this, we all showed this together.  While you don’t have to believe me, we proved this together.  Therefore, you have to believe what you have proven.”  I went on to say that rather than thinking about something bigger than \(\infty\), we think of this as different types of infinite cardinalities.  We say that the cardinality of \(\mathbb{N}=\aleph_{0}\) where as its power set has cardinality \(2^{\aleph_{0}}\).  Most of them accepted this, so we moved on.  Of course, the next thing we worked through upset them even more, but I will cover that in the next post.

Conclusion

I hope you enjoyed hearing about the experience I had in class today.  It was truly one of those things that I hope will happen in every class.  That is, I watched my students actually mature mathematically and having a deeper understanding of what math is.  I hope you have had a similar experience of your student suddenly getting what you’ve been trying to show them.  If you have, let me know in the comments below.  If you liked the post, make sure to click the like button and share on Social Media.  Also, follow the blog in order to keep informed about new posts.  Next time, we will look at how the rest of the class went.

 

1 thought on “A number bigger than infinity!”

We'd love to hear your thoughts!

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