Last time I talked briefly about pretend mathematicians. Y’know, people who’ve actually never studied the stuff they’re claiming to refute. Because “common sense” tells them it’s wrong. And “common sense” is, as we all know, the guiding principle of mathematics.
So this time I’ll actually get into cardinality and infinite sets a bit.
First, a preface. Infinity, as it is defined mathematically, is not an object of any kind. It’s not a number. It’s not a set. So what is it?
As it relates to calculus, infinity is a limiting principle. To avoid a rigorous discussion, it’s best to look at it through an example. Take an everyday function like . We write:
This notation reads: The limit of as x goes to infinity equals the limit of as x goes to infinity equals infinity. In other words, we’re asking the question: If x were to never stop getting larger, what would happen to the function ? In this case, the function itself would never stop getting larger either. So we write that its limit is infinity.
Now let’s stop here for a second to clear something up. Infinity still is not a number. This is a notation that mathematicians use for convenience. It’s understood that when a limit of a function equals infinity that that function does not have a limit, not that its limit is actually a number called “infinity”. In more technical terms, the function is said to diverge.
The second way in which infinity is used in mathematics is in regards to sets, specifically the number of elements of a set. If you’re not familiar with the term, a set is just a collection of things.
The notation goes as follows. Say you have a set of the numbers 3,4,5, and 6. We would write the set as , or for convenience, . An object is an element of a set if is itself a set and if it is “inside” of . may also be referred to as a subset of . Subsets of are considered elements of , not . So at the very least, , and it has one element. could have more elements; at the very least, it must have in there.
The example in the previous paragraph is of a finite set. A set is finite if it has finitely many elements. Basically, it just means that if you started counting the number of elements, you would eventually finish. Now we’ll introduce the concept of cardinality. A cardinality describes the number of elements of a set. The set has a cardinality of 4, because it has 4 elements. Quickly we can see that if a set has cardinality that is a natural number, then it is finite. (Refer to the math symbols page if you don’t know what natural numbers are).
So what does an infinite set look like? Well, a set is infinite if it’s not finite. Pretty simple. But it gets a bit more complicated. This is where intuition and common sense may fail you if you aren’t careful.
Take the set of natural numbers. Clearly this set is infinite, because for any number that you give me, I can just add another natural number to it and get a bigger number. It has another property which is quite obvious, but turns out to be significant. No matter what element you choose from , I can tell you at what position your element lies in the set. So if you choose 2,044, I know the number is the 2,044th element of the set. In general, the natural number is the element of the set .
For this reason, is called countably infinite. It may have an infinite number of members, but no matter what member you may pick, I can tell you at what position it lies in the set. So let’s call the cardinality of this set . This is simply a notation, not a number.
So let’s talk a little bit about a different set. Let’s call it . is the set of all even natural numbers. You can clearly see that this set is also countably infinite. If you give me any element in the set, I know its position is . So, for example, 2 is the first element, 4 is the second, 6 is the third, etcetera.
But how does compare to ? It may seem at first glance that is “bigger” than , because is a subset of . First, remember that these sets are both infinite, which should tip you off that common sense might fail you this time. Second, remember that we’re not necessarily concerned with the values of each element, but with the number of elements in total. How can we prove that and actually have the same cardinality?
Let’s take each element of and pair it with a unique element of . If we can do this for every single element of and , they must have the same number of elements. So define a function , where is any natural number. This does exactly what we wanted to do, because no matter if a natural number is even or odd, multiplying it by 2 makes it even. And we can see that each element of one set has a unique partner from the other. We can see that if one element of either set had to pair with two partners to make things fit that the other set would be the bigger set.
It’s easy to see, then, (or prove) that every countably infinite set has the exact same cardinality. The set of odd natural numbers. The set of integers. The set of primes. All of them.
It gets trickier though. Let’s consider the set of real numbers . is the set of all rational and irrational numbers. So it includes everything from the integers to fractions to numbers like that have infinitely many digits.
How does compare to ? Well is clearly a subset of . But, as we know, that doesn’t mean they don’t have the same cardinality.
Remember that our special property from countably infinite sets was that we knew at what position every element lay in the set. Let’s simplify things a bit and only take the set of nonnegative real numbers. Well, we know what the first element of the set is. It’s zero. What’s the next greatest element? Is it .01? No, because .001 is greater than zero but is less than .01. But .0001 is greater than zero and less than .001. And so on and so on. We can quickly see that no matter what “second element” you pick, I can find a smaller one that’s still greater than zero. Aside from the first element, then, asking about the “position” of an element in is meaningless. is what’s called uncountably infinite.
So let’s look at a smaller set, the set of real numbers between and including 0 and 1. We’ll denote that as [0,1]. Clearly [0,1] has a first element and a last element. But [0,1] is still uncountable. It’s still meaningless to talk about the “second element” or the “third element” of [0,1]. Okay, so it’s uncountable, but is it infinite? Well yeah, it is. Let’s take a subset of [0,1], and call it (0.5,0.7). So this is the set of all numbers between 0.5 and 0.7, not including 0.5 and 0.7. This set doesn’t even have a first or a last element. 0.5 isn’t in the set. So what’s the first element? 0.50000001? Well 0.500000001 is less than that, but still greater than 0.5. We arrive at the same conundrum. So we see that we can create infinitely many numbers in this interval (0.5,0.7). No matter what two different numbers in the interval you pick, I can find a new number between those numbers.
Clearly if (0.5,0.7) has infinitely many elements, then so does [0,1]. So [0,1] is uncountably infinite as well. Thus, is uncountably infinite. You can extend this reasoning and show that the set of real numbers [0,1] and [0,2] have, seemingly paradoxically, the same cardinality. You can then show that and any interval subset of have the same cardinality.
This seems unbelievable, but it’s true. I’ll do the first example. We need to pair every element of [0,1] with an element of [0,2]. Well, we can just use the same function we used before, . For a quick check that this works, note that the midpoint of [0,1] corresponds to the midpoint of [0,2]. .
Now, you should keep in mind that we’re still talking about the number of elements of the set, not the values. It’s easy to forget that. Yes, the interval [0,1] has a finite length. It’s just 1-0=1. We’re concerned about the number of elements in the interval, not the difference between the first and last elements.
So how can we compare and ? Well, every interval subset of has infinitely many elements. Every interval subset of , on the other hand, has finitely many elements. Clearly, then, is much bigger than . In other words, the cardinality of is less than the cardinality of . We denote the cardinality of as and say that . (Note that this is a cardinal, not an arithmetic, ordering; isn’t a number, remember).
So I hope that was understandable. I tried not to use so much jargon. If you have any questions, comments, responses, you know what to do. Next time we’ll talk about the continuum hypothesis and sets with even bigger cardinalities!