Effective Yak

This post is for a Redditor, u/EffectiveYak. He's a student at UTEP taking a course on discrete mathematics this semester. If you aren't Yak and stumbled in here looking for today's blog, it's the next one down. But if you're still here, take a seat - class is now in session.

***

Three vocabulary words - a set is a collection of elements. Mapping is how we match up elements in one set to elements in another. Your textbook might use other words.

Imagine you want to know if there are more Marvel superheroes than DC superheroes. This doesn't sound too hard to figure out, Just count all the superheroes in the set of Marvel superheroes, then count all the superheroes in the set of DC superheroes, and see which set has the most elements in it.

A six year old could explain this to me. It's very easy and intuitive.

There's another way to compare the size of sets, though. Imagine you take each Marvel superhero and draw a line from him or her to exactly one unique superhero in the DC set.

Thor maps to Superman, Captain America maps to Wonder Woman, Spiderman to Batman, and so on. It doesn't matter who you pick to map to as long as no other superhero maps to the same element.

One of three things will happen. First, you'll map every Marvel superhero to a unique DC superhero and you'll have some DC superheroes left over because DC has more superheroes.

Second, you'll run out of unique DC superheroes to map to because Marvel has more superheroes.

Or third, you can map each element in one set to exactly one unique element in the other set, meaning the two sets are the same size.

This technique is a little more cumbersome than just counting the elements in each set but it has one huge advantage - it works for infinitely large sets.

Let's consider the set of all the natural numbers from one to infinity. It's an infinitely big set. If we order the set from smallest element to biggest element then one is our first element, two is our second element, three is our third element, and on it goes. We call this a countable infinity because we can list the elements in order.

How about the set of all numbers if we count to infinity by hundreds? One hundred is our first element, two hundred is our second element, three hundred is our third, and so on. It's another countable infinity.

What about the set of all real numbers from zero to one?

Here's where things stop being intuitive. Our intuition tells us it's smaller than the other two sets because it's bounded. It has an upper limit. The other two sets go all the way to infinity but this set never goes past one.

But something funny happens when we try to order this set from the smallest element to the largest. Where do we begin?

I might say "One half is small, start there!"

But you add one to the denominator and say "One third is smaller."

"You're right," I say, "Start at one third!"

But you add one more to the denominator and say "One fourth is smaller."

I'm sure you see where this is going. No matter how small of a number I can imagine, no matter how close to zero I get, you can always point out an infinite number of real numbers greater than zero but smaller than the number I picked.

There's no way to order the set from the smallest element to the largest. We call this an uncountable infinity.

We've mentioned a few different sets. The set of Marvel superheroes is the smallest set because it has a finite number of elements. The other three sets, the natural numbers from one to infinity, the numbers we get if we count to infinity by hundreds, and the set of all real numbers between zero and one - which of these sets is largest?

One might argue the set of natural numbers is bigger than the set of numbers you'd get by counting to infinity by hundreds. After all, there's already a hundred elements in the first set by the time you get to the first element in the set by hundreds. But mapping shows us this is wrong. You can map one to one hundred, then two to two hundred, and three to three hundred. If you keep going you won't ever run out of elements in either set. One grows in value faster than the other but we aren't comparing the value of each element, only the number of elements, and we can keep counting the number of elements in both sets forever. The sets are the same size. All countable infinity sets are the same size. Some textbooks say they have the same cardinality, I think. It's been a long time since I took the class and I might have used the wrong word.

We can't map the elements of the set of real numbers from zero to one. It's uncountable so it can't be mapped to a countable set. We consider uncountable infinite sets larger than countable infinite sets.

I could still see when I spent a semester studying discrete mathematics but I really didn't need to. Nobody can visualize infinity. This is one of those rare college math classes where blindness isn't a disadvantage.

The class teaches people a new way to think. As a comp sci student you probably won't find a lot of use for countable and uncountable infinities but you'll probably discover many situations where you find mapping between sets of data helpful. Hopefully this semester will open your mind to a deeper understanding of infinite computer loops and mapping unique data points with each iteration of the loop.