.png){kind=spacer}
An international collaboration of engineers, scientists, and other domain experts, funded by philanthropists,
building the gold standard of Artificial General Intelligence, for all mankind.
- About
- 05 - (Infinite sets, bags, sequences, and cardinal and ordinal numbers)
Transcript 01:
Aaron Turner:
Aaron Turner:
In the last talk, we developed first-order logic with equality as an infinitely more expressive extension of propositional logic. This expressive power derives from FOLEQ's ability to make, and formally prove, universal and existential statements about infinite objects. In this talk, we're going to look at the concept of infinity. What do we mean by infinite objects? How do they behave? And just how big do they get?
Transcript 02:
Aaron Turner:
Aaron Turner:
First of all, we're going to look at sets, bags and sequences, which can be both finite and infinite. Then we're going to look at cardinal numbers and ordinal numbers. Then we're going to look at something, which I call ordinal cardinality, which is the sort of interplay between the two.
Aaron Turner:
So yes, these three different types of collections: sets, bags, which are also called multi-sets, and sequences, which I'll often just call seqs. They have different properties so they can be summarized as follows: With sets, both duplicates and order of the elements that they contain are insignificant. Duplicates are basically ignored and order's ignored. Order is insignificant. In bags, duplicates are allowed, so duplicates are significant, but order is not. In sequences, both duplicates and order [are] significant.
Aaron Turner:
Some simple examples, really. A set is an unordered collection of distinct elements. It's typical to denote a set by listing the elements inside curly brackets so that's what I've done here. So the set {a, b, c} is the same as the set {a, c, b} because order doesn't matter. And that's the same as the set {a, c, b, b} because the duplicate doesn't matter, which is again, of course, the same as the set {b, a, c, b}. A bit of notation: y ∈ x [y in x] where the "in" is denoted using that funny E symbol [∈] means y is a member of x (or y is an element of x).
Aaron Turner:
A bag is an unordered collection of not necessarily distinct objects (elements) and I've used these strange brackets/braces [⦃ ⦄] to denote bags. There's not really any convention on the notation for bags. So the bag ⦃a, b, c⦄ is the same as the bag ⦃a, c, b⦄ because order is unimportant. But those are not the same as the bag ⦃a, c, b, b⦄ because, in this case, the fact that there are two Bs is significant. However, that is the same as the bag ⦃b, a, c, b⦄ because order is, like I say, not significant.
Aaron Turner:
A sequence is a well-ordered collection of not necessarily distinct elements, so we're going to discuss what well-ordered means. For now just think of it as an ordered collection. So I'm going to use square brackets for sequences. In this presentation, I'm going to use a number of different representations for sequences and swap back and forth between them. But they all mean the same thing. You'll see what I mean.
Aaron Turner:
So the sequence [a, b, c] is not the same as the sequence [a, c, b] because the ordering in this case does matter. It is significant. That is not ... the same as the sequence [a, c, b, b] because, again, the duplicates are significant (the two Bs). Obviously, that is, again, not the same as the sequence [b, a, c, b] because, like I said, order is significant.
Aaron Turner:
These different types of collections, which can, like I say, they can be finite or infinite, are extremely useful for representing more complex mathematical concepts, especially for building mathematical models. They're also closely related in terms of how they may be collapsed into each other. For example, a sequence can be collapsed (by ignoring order) into its underlying bag. So if you take the sequence [b, a, c, b] and collapse it into a bag, we get the bag ⦃a, c, b, b⦄ where the order doesn't matter, but the duplicates (the fact that there are two Bs) does matter.
Aaron Turner:
A bag can be collapsed (by ignoring duplicates) into its underlying set. So we can take the bag ⦃a, c, b, b⦄ and collapse it into the set {a, b, c}, basically ignoring the duplicate B because we don't care about duplicates. Therefore, a sequence may be collapsed into a bag and then into a set. So, you just start with the sequence [b, a, c, b], collapse into a bag and then collapse that bag into a set and you get the set {a, b, c}.
Aaron Turner:
Now we are particularly interested here in two different properties of these collections, the size (or the cardinality) of a set (or a bag, we're going to focus on sets), which is represented by a cardinal number, and the length (or ordinality) of a sequence, represented by an ordinal number. So while everything is finite, if we're dealing with finite sets, finite bags or finite sequences, then each of these properties may be represented by a natural number, which is basically just a non-negative whole number (zero, one, two, three, et cetera). In other words, finite cardinal and ordinal numbers are just natural numbers.
Aaron Turner:
Again, this is a really simple example. The cardinality of the empty set { }, which I will call size({}), is zero. Similarly, the size of the set {a} is one, the size of the set {a, b} is two, the size of the set {a, b, c} is three. I'm keeping it really simple because it does get more complicated later on.
Aaron Turner:
So the ordinality of the empty sequence [ ], which I will call length([ ]), is zero. Similarly the length of the sequence [a] is one, the length of the sequence [a, b] is two, the length of sequence [a, b, c] is three.
Aaron Turner:
So that's simple enough. Once things become infinite, natural numbers are no longer sufficient.
Transcript 03:
Aaron Turner:
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.
Transcript 04:
Aaron Turner:
Aaron Turner:
Now what does well-ordering mean? Now it means that if you take a non-empty well-ordered, but possibly infinite sequence; if you write it out from left to right, then no matter which element you start from (you can start anywhere in the middle), if you move to the left and keep moving to the left, then you will eventually reach the first element. But if you move to the right and keep moving to the right, then it is not necessarily the case that you will ever reach any last element. That is, essentially, what well-ordering means. The mathematical definition is a little bit more complicated, but it's just easier to imagine, if you just think of sequences that can grow to the right forever, but to the left they're always finite (you can get to the beginning in a finite number of steps).
Aaron Turner:
So, now we know what well-ordered means. Two possibly infinite sequences are said to be order-isomorphic and therefore to be of the same length, if there is a well-order-preserving, one-to-one correspondence (also called an order-isomorphism) between them. That's a bit of a mouthful. We already know what a one-to-one correspondence is because we've seen what a one-to-one correspondence is (a bijection) when we were looking at ... infinite sets. So the only new thing here is this concept of it being well-order-preserving. We're going to have a look at some examples.
Aaron Turner:
Okay. So if we put these two things together, well-order-preserving, one-to-one correspondence; it means that the elements of the first sequence can be partnered off with the elements of the second sequence in such a way that if one element E precedes another element F in the first sequence, then the partner of element E precedes the partner of element F in the second sequence, and vice versa. So, we will see some examples, don't worry. So here's a finite example, and some counter-examples. So the two sequences on the left; top one, sequence A and the bottom one, sequence B. And you can see I've drawn some lines.
Aaron Turner:
Now this is an order-isomorphism between them. Those lines represent an order-isomorphism because they're in one-to-one correspondence [bijection] and the bijection preserves the well-order. If you look at the middle pair of sequences, the top line, sequence A, is obviously of length four. The bottom line, sequence B, is obviously of length three. So this is not an order-isomorphism because they're not in one-to-one correspondence. And we saw that, similarly, when we were looking at sizes, cardinality. So the one on the right is new. So again, we have sequence A and sequence B; both of length four ... and we've established a one-to-one correspondence; with those lines I've drawn. But it's not well-order-preserving, they don't preserve the order. So if you look in sequence A; A2 comes before A3. But if you look at sequence B, the partner of A2 (which is B3) comes after the partner of A3 (which is B2). Okay, so it swapped the order. In other words, it hasn't preserved the order.
Aaron Turner:
So, here's an infinite example, a relatively simple one. So both of these sequences, A and B, are infinite. And again, I've tried to indicate that there's an order-isomorphism between them by drawing those lines. And the dotted line to indicate that it continues forever. So again, that's all good as far as it goes. But how can we determine the specific ordinal number corresponding to the length of a possibly infinite sequence? So just as we did with cardinalities; we will define ordinal_seq(O) to mean the well-ordered sequence of all ordinal numbers strictly less than O, where O is any ordinal number. And if a sequence X is order-isomorphic to ordinal_seq(O), then the length of X [denoted length(X)] is O. Again, bit of a mouthful, but we'll have a look at some examples. Here's a finite example. So we have the sequence A1, A2, A3, A4, at the top and below we have ordinal_seq(4), in other words, the well-ordered sequence of all ordinal numbers strictly less than four, ie zero, one, two, three. And we've established an order-isomorphism between them.
Aaron Turner:
Therefore, the length of A (the top sequence), the length of sequence A is four. Pretty straight forward. ... So if the ordinal numbers are limited just to the natural numbers N, nought, one, two, three, et cetera, then this is obviously only going to work for finite sequences X. So just as we needed additional cardinal numbers, now we're going to need additional ordinal numbers. So in order to be able to handle infinitely long sequences, we're going to need more ordinals than just the set of natural numbers. The first such infinite ordinal is called ω0 [omega-zero] (and it's usually just shortened to ω). And by definition the length of ordinal_seq(ω) is ω. In other words, the length of the ... sequence comprising ordinal numbers less than ω (in other words, all the natural numbers) is ω. Which is what we'd expect.
Aaron Turner:
So here's an infinite example, and we've just extended the previous example infinitely. So the top sequence A is infinite in length; A1, A2, A3, A4, and then continues forever. The bottom sequence is the ordinal_seq(ω), so it comprises basically all the natural numbers in order, zero, one, two, three, et cetera ... forever. And we can establish an order-isomorphism between them. Therefore, the length of this sequence A, the infinite sequence A, is ω. And it's convenient at this point to introduce the concept of a matchstick diagram. So this bottom sequence, ordinal_seq(ω), can also be written out using a matchstick diagram as shown on the bottom right.
Aaron Turner:
And in these diagrams, as the numbers get larger, the matchsticks get smaller and smaller and smaller. And you can see it tapering off to infinity. And you'll see that's going to be useful in what we're looking at later. So again, exactly as we did for the cardinals, we can define a few things now. A sequence X for which length(X) is less than ω, is called finite or finitely long. A sequence X for which length X is less than or equal to ω, is called countable or countably long. A sequence X for which length X equals ω, is called denumerable or denumerably long. So, for example, ordinal_seq(ω) is therefore both countable and denumerable. And a sequence X for which length X is greater than ω is called uncountable or uncountably long.
Aaron Turner:
Right, it gets really fun now. Following our earlier definition of order-isomorphism, it can be seen that infinite sequences and thus the arithmetic of transfinite ordinals; behave counter intuitively. So imagine ordinal_seq(ω), which is the ordered sequence of all natural numbers. Now add a single new element at the beginning. At the beginning of this sequence. The new sequence is still the same length as the original, and here's my attempt at a diagram indicating that. So the top matchstick diagram is ordinal_seq(ω). The bottom matchstick diagram is basically ordinal_seq(ω), with an extra element. It says new element, tagged onto the beginning right at the front.
Aaron Turner:
And I've been able to indicate with the blue lines an order-isomorphism between these two matchstick diagrams, just by shifting everything along by one. Which means of course, that 1 + ω equals ω. Okay? Another example; imagine again ordinal_seq(ω), which is the ordered sequence of all natural numbers. Now this time we're going to add a single new element at the end of the sequence. Last time we added one to the beginning, now we're going to add a new element to the end of the sequence. The new sequence is now longer than the original. In other words, ordinal addition is not commutative.
Aaron Turner:
So with ordinals a and b; a + b is not necessarily the same as b + a. And here's, again, my matchstick diagrams. The top matchstick diagram is again, ordinal_seq(ω). As you can see it tapering off to infinity. And on the bottom, we also have ordinal_seq(ω). And then at the end I've tacked on a new element, and ... because we need to preserve order, when we're dealing with sequences (well-order), it is not possible to find an order-isomorphism between them. It doesn't exist. So they are not order-isomorphic. And basically, this means that 1 + ω, which we looked at last time, is not the same as ω + 1. And ω + 1 is, in fact, greater than ω.
Aaron Turner:
So, another example; imagine ordinal_seq(2) which is an ordinal sequence of just the numbers zero and one. Now take ω copies of that sequence and just concatenate them together. So starting from nothing, just concatenate ω copies of this simple two-element sequence, one after the other. And what do you know ... the new sequence is still the same length as ordinal_seq(ω). And again, here's another of my little diagrams trying to show this. So the top matchstick diagram is ordinal_seq(ω), the bottom matchstick diagram is ... basically I've just taken ordinal_ seq(ω) and I've doubled everything up. So I've got 0a and 0b. I've got 1a, 1b, 2a, 2b, et cetera. And as you can see, it's still possible to establish an order-isomorphism between them. And if you can establish an order isomorphism between them, that means they're the same length.
Aaron Turner:
So 2 × ω equals ω. Right, I think this is the last example. Well, the last example of weirdness. So now last time we concatenated ω copies of a sequence of length two, now we're going to concatenate two copies of a sequence of length ω. So, concatenate two copies of ordinal_seq(ω), one after the other. Now the new sequence is now longer than the original. In the last example, they were the same length. The new sequence, this time, is longer than the original. In other words, ordinal multiplication is not commutative. In other words, for two ordinal numbers, a, b; a × b does not necessarily equal b × a.
Aaron Turner:
And here, there's my matchstick diagram. So the top one is our old friend ordinal_seq(ω). The bottom one, I've taken two copies of ordinal_seq(ω) and I've just pasted them one after the other. So you've got ordinal_seq(ω) tapering off to infinity. And then you've got another infinite ordinal sequence starting at the number ω and then tapering off to [infinity]. So what that means is from an arithmetic ... perspective; it means that 2 × ω is not the same as ω × 2 ... 2 × ω is what we looked at last time. So with ω copies of 2 and it's not the same as ω × 2, which is 2 copies of ω ... [that's equal to ω + ω]. Anyway, it's greater than ω as you can see. Because we can't establish an order-isomorphism between them.
Aaron Turner:
So we've looked at a few strange examples now. So, in addition to starting to understand that ordinal numbers behave rather strangely, we can start to see how increasingly large ordinal numbers may be generated. So if we start from ordinal_seq(ω)... [Now I've gone back to a different way of writing sequences, I've just put them in square brackets.] So ordinal_seq(ω) is the sequence zero, one, two, three, dot, dot, dot. The next number in the sequence is the first infinite ordinal ω so zero, one, two, three, dot, dot, dot, ω. The next number after ω is called ω + 1 and is by definition numerically greater than all of its predecessors, including ω. So we've got zero, one, two, three, dot, dot, dot, ω; then ω + 1. And of course we can keep going forever. In which case we get zero, one, two, three, dot, dot, dot, ω, ω + 1, ω + 2, ω + 3, dot, dot, dot. Which, as we saw before, is basically two countably long sequences, one after the other.
Aaron Turner:
And just as we added ω onto the end of zero, one, two, three, dot, dot, dot; we can now add the new number ω2 (which means ω × 2) on to zero, one, two, three, dot, dot, dot, ω, ω + 1, ω + 2, dot, dot, dot. So, we get zero, one, two, three, dot, dot, dot, ω, ω + 1, ω + 2, dot, dot, dot, ω2. Now the new number, ω2, corresponds to the length of two countably long sequences, one immediately after the other. And there's a matchstick diagram indicating that. So yeah, it's convenient here to define zero, successor, and limit ordinals. There's a little diagram. But zero is the only zero ordinal. So right at the beginning there, on the left. A successor ordinal is any ordinal that immediately follows another one.
Aaron Turner:
So, for example, if i equals j + 1, then i as a successor ordinal, because it's following something else. It's the immediate successor of another ordinal. And a limit ordinal is any non-zero ordinal that is not a successor ordinal. So in this diagram here; the limit ordinals are ω and ω2. You see they're the first ordinals following a part of the matchstick diagram that tapers off to infinity.
Aaron Turner:
So, after ω2, we can keep going and we eventually get to zero, one, two, three, dot, dot, dot, ω, ω + 1, ω + 2, dot, dot, dot, ω2, ω2 + 1, ω2 + 2, dot, dot, dot, ω3. Where ω3 (ω × 3) corresponds to the length of three countably long sequences, one after the other. And we can just keep going forever. There's no end to this, honestly. So, eventually we would get to a countably long sequence of countably long sequences of length ω squared. That's what that looks like as a matchstick diagram. And you can see even the matchstick diagram's are tapering off as we progress along the countably infinite sequence of countably infinite sequences. And this is followed, soon after, by a countably long sequence of countably long sequences of countably long sequences of length ω cubed. And there's the matchstick diagram for that. So, we can continue in this fashion until we eventually get to ω to the power of ω. There you go. And this never ends. Okay?
Aaron Turner:
So the next notable ordinal is called ε0 [epsilon-zero]. And this is the limit of this sequence. So if you imagine ω, and ω to the power of ω, and ω to the power of ω to the power of ω; and ω to the power of ω to the power of ω to the power of ω. Just keep going, basically, forever. Okay? When the stack of exponents is ω high, that's ε0. So you could maybe start to see how long a sequence that is. But they don't stop there. They just get harder and harder to describe, to visualize and to imagine.
Aaron Turner:
So the next notable ordinal after ε0 is called ε1; and it's the limit of this sequence. So ε0, ε0 to the power of ε0, ε0 to the power of ε0 to the power of ε0; et cetera. You get the idea. And the next notable ordinal after ε1; is called ε2 and it's the limit to the sequence ε1, ε1 to the power of ε1, ε1 to the power of ε1 to the power of ε1; et cetera. And obviously, we can keep going like that forever. And in general, there exists an εi for every ordinal i, not just the successor ordinals I've shown here. There's an εi for limit ordinals i, as well. It's just they're constructed in a slightly different way, a more complex way. But I'm just trying to convey size now; just how big these things get.
Transcript 05:
Aaron Turner:
Aaron Turner:
So are there any ordinals that are uncountably large? Are they all denumerably large? The ordered sequence containing all ordinals of cardinality less than or equal to that of ω (which remember is ω0), has length ω1 (so this is a new ordinal we're introducing here). And ... if we take ordinal_seq(ω1), convert that into a bag and then that into a set and then take the size of that set, the cardinality of that set is greater than ℵ0. So ω1 is uncountably large. So there are uncountably large ordinals.
Aaron Turner:
And we can generalize this. For any ordinal i, the ordered sequence containing all ordinals of cardinality less than or equal to that of ωi has length ωi+1. And if we take ordinal_seq(ωi+1), convert that into a bag and then into a set, the size of that set is greater than the size of ordinal_seq(ωi) converted into a bag and then into a set. So we get a sequence. We get a never-ending sequence of [increasingly] larger omegas. And in fact there exists an ωi for every ordinal i, not just the successor ordinals shown here. So for limit ordinals i as well.
Transcript 06:
Aaron Turner:
Aaron Turner:
So as we've already alluded, infinites are at the heart of first-order logic with equality's power of expression. It's infinites that allow us to build highly complex and highly nuanced mathematical models.
Aaron Turner:
And the extent to which these models are complex and nuanced is determined by how large the ... the infinites can get. And, and I'm talking of course, infinite sets, infinite bags, infinite sequences, infinite numbers (which we now have), infinite relations, which we talked about... (actually it was the last talk), and infinite functions. All of these things can be infinite now. And with these incredibly large infinities that we've just discovered, and yes, we've now had an intuitive taste of just how incredibly large these infinites get.
Aaron Turner:
So that's it for today. In the next talk, we're going to start to use this power of expression to extend first-order logic with equality into set theory, so that we can then start to build some of those infinitely complex and infinitely nuanced mathematical models that we've just talked about, and which we will in fact need in order to construct our Big Mother artificial general intelligence. So that's it for me, until next time, during the pandemic, stay safe and thank you very much for your attention. Thank you.