Back to index
Transcript 03:
Aaron Turner:
So now we're going to look at cardinal numbers and in particular of course infinite cardinal numbers. So we'll consider the infinite cardinal numbers, which are also known as the transfinite cardinals. So what does it mean for two possibly infinite sets to have the same size? What does that really mean? So the elements of a set are like we've seen unordered, two sets, possibly infinite sets are said to be equinumerous, which means they have the same size, if there is a one-to-one correspondence between them (one-to-one correspondences are also called bijections). So we'll see what a one-to-one correspondence is in a minute. Oh, here we go. So a one-to-one correspondence means that the elements of the first set can be partnered off with the elements of the second set. So here's a finite example as well as a counter example. So if you look at the two sets on the left, there is a bijection between them. You see I've paired off (there's four elements in each) and I've paired them off one-to-one.
Aaron Turner:
And the two sets on the right, there is no bijection between them. They have different numbers of elements. So I was able to pair off A1, A2 and A3 but there's nothing for A4 to be paired off with. So they're different sizes because the elements can't be paired off. Now an infinite example, obviously I can't write this out in full, but here are two notionally infinite sets on the left, A1, A2, A3, A4 continuing forever, and similarly on the right. Now it is possible to establish a bijection between them just pairing the elements off as before but continuing forever infinitely, which I've tried to indicate by that dotted line.
Aaron Turner:
So this is all great, but how can we determine the specific cardinal number corresponding to the size of a set, a possibly infinite set? So we'll just define something here. We'll define cardinal_set(C) to mean the unordered set of all cardinal numbers strictly less than C, where C is any cardinal number (and don't worry we'll see some examples). Now if set X is equinumerous with cardinal_set(C), then the size of X [denoted size(X)] is C. So here's again, a really simple example. The set A on the left and on the right, I can barely read it from here. That probably says cardinal_set(4). So on the left we've got the set A with four elements. On the right, we've got cardinal_set(4), which contains the set of all cardinal numbers strictly less than four, i.e. zero, one, two, three and we can establish a bijection between them so they're equinumerous, which means that size(A) is a four. Simple enough.
Aaron Turner:
It may seem that we're being overly ... that these are overly simple, but when it gets infinite, things get tricky. So if the cardinal numbers are limited to just the natural numbers N, zero, one, two, three, et cetera, then obviously this is only going to work for finite sets X. So ... we need some more numbers. In order to be able to handle infinitely large sets, we're going to need more cardinals than just the set of natural numbers. And the first such infinite cardinal, the smallest infinite cardinal, is called ℵ0 [aleph-zero] and by definition if we take cardinal_set(ℵ0), which means the set of all cardinal numbers less than ℵ0, then the size of that set is ℵ0.
Aaron Turner:
And here's an example. So again, we have the set A on the left is an infinite set, A1, A2, A3, A4 increasing infinitely. On the right, we have cardinal_set(ℵ0), which is all the numbers, all the cardinal numbers less than ℵ0, which is of course just the natural numbers, zero, one, two, three, et cetera (everything less than ℵ0), so size(A) [that infinite set A] is ℵ0.
Aaron Turner:
So we can make a few definitions now we have a bit more information. So any set X for which size(X) is less than ℵ0 is called finite or finitely large. Sometimes it's useful to explicitly say finitely large to avoid confusion with ordinal numbers [as sequences may be finitely long], which we'll get to later. So a set X, for which size(X) is less than or equal to ℵ0 is called countable or countably large. A set X for which size(X) is equal to ℵ0 is called denumerable or denumerably large. So in particular, cardinal_set(ℵ0), which is of course the set of natural numbers, is therefore both countable and denumerable. So a set X for which size(X) is greater than ℵ0 is called uncountable or uncountably large.
Aaron Turner:
So following our earlier definition of equinumerosity, it can be seen, well we're about to see that infinite sets and the arithmetic of transfinite cardinals behave counter-intuitively. So it's not what we're used to with natural numbers or even real numbers. So for example, imagine the set of all natural numbers N, which is of course cardinal_set(ℵ0). Now remove all of the odd numbers, leaving just the even numbers, which we'll call E. Now you'd expect E to be smaller than the set N that we started off with. But no, the set of all even numbers E is still exactly the same size as the original set of all natural numbers N. And here we can see we've got the set of all natural numbers N on the left and the set of all even numbers E on the right. And it's possible to establish a bijection between them, pairing them off.
Aaron Turner:
So zero with zero, one with two, two with four, three with six, et cetera. So the size of the even numbers E is the same as the size of the natural numbers N. Okay, again, it's weird. It's going to get a lot weirder yet. So brace yourself! So now let's have another example, let's imagine a denumerably infinite set. So ... it has size ℵ0, so the set S, so S1, S2, S3, S4 et cetera. And by definition, size(S) is ℵ0. So now copy everything in S over to a new set T and then add to T a single new element. Now despite the fact that we've just added a new element, an additional element, the new set T is still the same size as the original set S. So how does that work?
Aaron Turner:
So here we've got the original set S on the left and we've got the new set T on the right. And you can see they're both infinite, they both go on forever. But all that's happened is we've established a bijection between the two of them. We've put the new element, which I call T0, essentially we've paired it off with S1 and then everything else just moves down. So S2 is paired with ... S1. S3 is paired with S2 et cetera. And so this basically means that ℵ0 + 1, which is the same as 1 + ℵ0 equals aleph-zero. Weird, but this is how infinite cardinal numbers work.
Aaron Turner:
So let's try another one. So now imagine two denumerable sets S, which is S0, S1, S2, S3, ad infinitum and T which is T0, T1, T2, T3, ad infinitum. Now obviously the size of both of these sets, S and T is ℵ0. They are both denumerable like I said. Now copy everything from S and T over to a brand new set U, and the new set U is still the same size as each of the original sets S and T.
Aaron Turner:
And here you go. This is how we've done it. So there's the set S on the left, the set T in the middle and this is the new set U on the right. And what we've done is we've established a bijection between S and T and we've established a bijection between T and U, so they're all the same size, which is ℵ0. And what this means is ℵ0 + ℵ0, which is the same as 2 × ℵ0, which is the same as ℵ0 × 2, is still equal to ℵ0.
Aaron Turner:
Okay, one more. Now imagine the set of all positive natural numbers N+, which is one, two, three, four, so it's the natural numbers but doesn't include the number zero. And we're going to construct the set Q+ of positive rational numbers [fractions] of the form x/y, where both x and y are positive natural numbers, so no zeroes involved. Now we're going to lay these out in order in a two-dimensional table, with the numerators x running left to right across the columns and the denominators y running down the rows. So the numerators are the top line of a fraction and they run left to right across the columns, and the denominators, which are the bottom line of a fraction, run down the rows. And so obviously in this table, there are going to be ℵ0 rows and each of those rows has ℵ0 columns.
Aaron Turner:
Nevertheless, the complete table, if we counted all the cells, still only has ℵ0 entries. So how does that work? So here's the table laid out as I said, and we can establish a bijection [between the cells of the table and the natural numbers 0, 1, 2, 3, ...]. If you look at the red arrows, we can count [through the natural numbers 0, 1, 2, 3, ...] starting from the top left [1/1] ([which we'll call] zero). Then we move right one [to 2/1] and we call that one. Then we go diagonally down [to 1/2], and we call that two. Then we go straight down to [1/3], and we call that three. Then we go diagonally up [to 2/2]. So you see we can establish a bijection between every entry in this table and the set of natural numbers. So if we establish a bijection between the entries of this table and the set of natural numbers, ... they must be the same size. So arithmetically, this basically means that ℵ0 × ℵ0 equals ℵ0, and well, we've tried everything, haven't we? We've tried adding things, we've tried multiplying things and it's starting to look as though it's impossible to construct an infinite set larger than the set of natural numbers, in which case we won't need any infinite cardinals larger than ℵ0.
Aaron Turner:
Cantor to the rescue, right. The powerset of a set X, which is denoted P(X), with that sort of double P, ... consists of exactly the subsets of X. So we take all the subsets of X (including the empty set { } and X itself) and we build a new set from those subsets. And that new ... set, P(X), is actually going to be larger than the original set X. So let's say again, for any set X, including infinite sets X, the size of P(X) is greater than the size of X, which means that however large a set X we might start with ... we can always construct a larger set Y just by constructing P(X).
Aaron Turner:
And ... then, because we've got a set which is larger than the set we started with, let's say we started with a set of size ℵ0, we're going to need a cardinal number now that is larger than ℵ0. So however large an infinite cardinal C we might have, we're always going to need a larger infinite cardinal D. So because of this, we know that there exists a never ending supply of increasingly large infinite cardinals. So ℵ0 is the size of the ... set of natural numbers, and this is ... less than the size of the powerset of the set of natural numbers, which is in itself then smaller than the size of the powerset of the powerset of the set of natural numbers, et cetera. Now this is one mechanism we know of that we can use to generate larger and larger infinite sets, thereby needing larger and larger infinite cardinals. However, it might not be the only method. There may be infinite cardinals other than the ones we can generate through this method.
Aaron Turner:
Nevertheless, considering all of the infinite cardinals that exist, the successively larger cardinals after ℵ0 are called ℵ1, ℵ2, ℵ3, et cetera, and in general, ℵi and there exists an ℵi for every ordinal number i, and we're going to see in a minute just how many ordinal numbers there are, [and] however many ordinal numbers there are, that's how many different size infinities there are.
Back to index