• fishfry
    2.6k
    In this thread, I was asked this question by @tim wood:

    Attempt at a coherent question here. Maybe best to leave it simple. What is an infinite ordinal?tim wood

    Rather than hijack the other thread, I'm top-posting this here in the Math section where it may serve as a general resource to interested readers.

    It's not particularly short, but I do believe it's simple, in the sense that you can read a little here and there and perhaps get the gist.

    Comments, questions, and criticisms gladly appreciated. In particular, please let me know if anything is unclear or needs more explanation.

    Contents
    * Ordinal numbers
    * Well-orders
    * Order-types
    * Some more ordinals
    * Uncountable ordinals
    * The Alephs
    * The von Neumann ordinals
    * The class of all ordinals
    * Ordinal arithmetic
    * Odds and ends about countable ordinals


    * Ordinal Numbers

    Most people have heard of Cantor's great discovery of the cardinal numbers, the Alephs, a way of assigning a measure of quantity to infinite sets. Far fewer have heard of ordinals, which were Cantor's other great discovery; and which are, in the modern formulation, logically prior to cardinals. Ordinals describe order, analogously to how cardinals describe quantity.

    Ordinals find applications in mathematical logic, proof theory, set theory, and theoretical computer science, as well as being fascinating objects of study in their own right.

    This article is a general introduction to the basics of the transfinite ordinal numbers.


    * Well-orders

    An ordinal number is the order-type of a well-ordered set. What does that mean?

    The core concept of ordinals is the idea of a well order. A well-order is an order relation on a set such that every nonempty subset has a smallest element.

    For example the usual order on the natural numbers is a well-order. The set of primes, the set of even numbers, the set of squares, each have a smallest member. Every possble nonempty set of the naturals has a smallest member, so the naturals are well-ordered by .

    On the other hand the usual order on the integers is not a well-order, because the negative numbers have no smallest element.


    * Order-types

    What we mean by an order-type is the "shape," or structure, of a well-ordered set.

    Consider for example the natural numbers in their usual order, 0, 1, 2, 3, 4, ...

    and the natural numbers with the positions of 1 and 2 switched, like this:

    0, 2, 1, 3, 4, 5, ...

    It's clear that this is a different order than the usual order; but that it's structurally the same. That is, there is an order-preserving bijection between the two ordered sets:

    0  1  2  3  4  5 ...
    ^  ^  ^  ^  ^  ^ ...
    |  |  |  |  |  | ...
    v  v  v  v  v  v ...
    0  2  1  3  4  5 ...
    

    In other words we can find a bijection between the two sets that preserves their respective orders. Such an order-preserving bijection is called an order-isomorphism.

    The "shape," or structure, of each of these well-ordered sets can be depicted as:



    On the other hand, consider the following interesting reordering of the natural numbers:

    1, 2, 3, 4, 5, ..., 0

    Here we have simply placed 0 at the end. We could, if we wanted to, formalize this by defining a new "funny order" relation defined like this:

    * If and , then .

    * for all .

    In other words is just like except that everyhing is "funny less than" 0.

    You should convince yourself that "funny less than" is a well-order.

    I should mention that each of the finite numbers 0, 1, 2, 3, ... is itself an ordinal representing a single order type. No matter how you rearrange finite set it's always got the same order type.

    There's a notation for an ordered set. We denote the natural numbers in their usual order as . That is, it's an ordered pair where the first item is the set, and the second is the particular order relationship on the set.

    Likewise represents the funny order on the naturals, the one with 0 at the end.

    There's a special notation for the ordered set , and that is . That is, stands for the natural numbers in their usual order.

    We can see right away that there is no order-isomorphism between these two ordered sets, because has a largest element, while doesn't.

    The shape, or structure, of looks like this:



    If the usual order 0, 1, 2, 3, ... is called , then our funny order is called ; that is, the successor of


    * Some more ordinals.

    We can play this game indefinitely. How about

    2, 3, 4, ..., 0, 1. That's a different order-type, named . And

    3, 4, 5, ..., 0, 1, 2 is .

    We can keep doing this over and over; and we can take the limit of this process to get . How would we represent that with a funny ordering of the naturals? This is the even-odd order:

    0, 2, 4, 6, ..., 1, 3, 5, 7, ... in which all the evens come before all the odds. It's just two copies of , one after the other. The ordinal is also notated , because ordinal multiplication is notated backwards. is 2 copies of . Apparently Cantor (who thought all this up) went back and forth on which way to notate ordinal multiplication, and in the end picked this one.

    How could we represent three copies, ? Instead of evens and odds, we can go by remainders mod 3:

    0, 3, 6, 9, ..., 1, 4, 7, 10, ..., 2, 5, 8, 11, ...

    We can do the same trick with remainders mod 4, 5, and so on, to represent . Eventually the upward limit of that process is copies of , or .

    But now the modulo remainder trick doesn't work; and it's clear that there are going to be a lot more ordinals than there are obvious ways to reorder the naturals to represent them. We need new ideas.

    But before going on, let's stop a moment to meet some more ordinals and make an amazing observation about them.

    The successor of is , then , and so forth, then , and we keep on going. In fact ordinals look sort of like polynomials in . This notation is known as Cantor normal form.

    Let's look at some more of these. After we run through , the upper limit of that process is . If we keep on going, we come to , , and so forth; and eventually to the coolest number that I know, an -sized exponental tower of 's. This number is called . Then there's a hierarchy , , and on and on. These are the epsilon numbers.

    Now here is the punch line.

    Every one of these ordinal numbers that I've shown so far is a countable set. It represents some well-ordering of .

    After all, rearranging the elements of a set does not alter its cardinality. So it's obvious that all have the same cardinality, and the epsilons you can take on faith. In fact the Wiki article on the epsilon numbers states that every epsilon number whose index is countable is itself countable.

    I should note in case the exponentiation caused confusion, that ordinal exponentiation is not the same as cardinal exponentiation. is indeed uncountable, because it's cardinal exponentiation; but is countable by the definition of ordinal exponentiation.


    * Uncountable ordinals.

    Can there possibly be an uncountable ordinal? In fact there is. We sketch the construction as follows.

    We've already noted that the , or union, or least upper bound of a set of ordinals is an ordinal.

    Now onsider the set of all possible countable ordinals; that is, the set of all well-orderings of . We have to prove that this is a set, but that can be done.

    Its union, or , is an ordinal, but it can't be a countable one because then it would be a member of itself; and no ordinal is a member of itself. We call this ordinal , the first uncountable ordinal. Its existence can be proven without the axiom of choice.

    Trying to imagine an uncountable ordinal is mind boggling, but they exist even in ZF. In other words we know that the axiom of choice says that all sets can be well-ordered. But even without choice, some uncountable sets can be well-ordered. Just not all of them.


    * The Alephs.

    Ok time to catch our breath. The ordinals are dizzying to contemplate. Let's take a digression to define the Aleph numbers. These are Cantor's famous cardinalities. What are they, exactly? In the early days of set theory, a cardinal number was the equivalence class of all sets bijectively equivalent to each other. So was the class of all sets bijectively equivalent to the natural numbers, and so forth.

    There is a problem with this definition, which is that the Alephs are not sets. For the same reason that there's no set of all sets, there's also no set of all sets bijectively equivalent to the naturals or any other cardinality. [I'm using cardinality a little circularly there, but you know what I mean].

    John von Neumann, who we'll talk about more in a bit, is responsible for the following modern definition, called the von Neumann cardinality assignment. Although tonight as I was writing this is the first time I ever heard it called that, and learned that von Neumann is responsible for the idea. He showed how to define the cardinality of any well-ordered set as a particular ordinal, so that cardinals are sets and can be manipulated using the rules of set theory. That turns out to be more convenient than the older definition.

    We need the fact that any nonempty collection of ordinals must have a smallest ordinal. In other words the class of ordinals is itself well-ordered.

    (However the class of ordinals is not a set, that's the Burali-Forti paradox).

    Now given any well-ordered set, we define its Aleph number as the least ordinal that's cardinally equivalent to that set. How do we know that there is one? Since the set is well-ordered by hypothesis, it's cardinally equivalent to at least one ordinal. In other words the class of ordinals cardinally equivalent to our set is nonempty; therefore there's a smallest one. That's the one that we define as the set's Aleph.

    And since the Alephs are then a collection of ordinals, there's a smallest one, which is , and a next one, , and so forth.

    That's why there's no for example. Nobody ever asks why the Alephs are indexed by whole numbers, but now it's clear why. Each Aleph is itself an ordinal, and any collection of ordinals is well-ordered. The collection of all the Alephs is not a set, by the way. Again, same reason as that there's no set of all sets.

    In fact the Alephs are indexed not just by natural numbers, but by ordinals. So for each ordinal , there's an . There's an , and an , and so forth. Those are some big sets!

    Let's work out the first few Alephs.

    What is the least of all the ordinals with the same cardinality as ? We've seen that it's . So we define .

    What's next? We define . So now we can visualize . It's the cardinality of the set of all countable ordinals.

    And then is the cardinality of the set of all ordinals of cardinality .

    And since each of the finite numbers 1, 2, 3, ... is itself an ordinal, we see that is just the cardinality of the set of all finite ordinals.

    And now we can concretely visualize all the Alephs. For suitable values of "concretely," anyway. Each Aleph is the cardinality of the set of ordinals one level down. You want to know what is ? It's the cardinality of the set of all well-orders of a set of cardinality .

    Let me say this again to emphasize how simple it is.

    How many different well-orderings are their of finite sets? There are of them, one for each of 0, 1, 2, ... How many well-orderings are there of a set of cardinality ? There are of them. How many well-orderings of a set of cardinality ? There are of them. And so on all the way up.

    One final wrinkle. I said this definition works for any set that is well-orderable. Given a well-ordered set, we find the class of all ordinals cardinally equivalent to it, and define that set's Aleph as the least such ordinal.

    In the presence of the Axiom of Choice, every set can be well-ordered and this definition works for every possible set. But in the absence of choice, there are infinite sets that are not well-ordered, so we can't use this definition. In that case there's a trick, called Scott's trick, that can assign a cardinality to every set, even the non-well-ordered ones. That's a little outside the scope of this exposition but I'm mentioning it for completeness.


    * The von Neumann ordinals.

    We've seen that we ran out of clever ways to visualize well-orders of the natural numbers long before we ran out of countable ordinals. Here's another nice way to visualize the ordinals. In fact this method provides a specific, canonical set to represent each ordinal.

    John von Neumann was a mathematician and pure and applied scientist. He invented mathematical game theory, worked on the hydrogen bomb, made fundamental contributions to functional analysis and quantum mechanics, worked on operator algebras and fluid mechanics and more. In his time he was regarded as the smartest man in the world. And as if all that wasn't enough for one short life -- he died tragically at 53 of cancer, possibly due to radiation exposure contracted at Los Alamos National Laboratory -- he gave us our modern definition of ordinal numbers.

    First, a transitive set is a set each of whose elements is also a subset.

    If is any set, we define its successor as ; that is, unioned with the set containing

    We can then build up all the ordinals as transitive sets, starting from the empty set.

    is vacuously a transitive set, which we call .

    If is the successor of , then:

    .

    ,



    and so on.

    Now if is a set of ordinals, we define , the union of all the ordinals in . We also call that the least upper bound of that set of ordinals.

    If has a largest element, such as for example , then , the largest element. In other words, the union of a set of ordinals having a largest element is just that largest element.

    But if the set of ordinals has no largest element, then its union is a brand new ordinal. So . Such an ordinal is called a limit ordinal. That is, a limit ordinal is an ordinal that's not the successor of any ordinal.

    Once we reach , we keep taking successors till we reach and all the rest of them. The idea is to keep taking successors then limits, successors then limits, without end.

    This gives another way to think of the ordinals.

    The natural numbers are produced by starting with 0, and then repeatedly applying the successor operation.

    The ordinals are just like that, but in addition to the successor operation, we also have the sup operation. We keep taking successors, and every once in a while we accumulate a countably infinite collection of successors into their sup and keep on going.

    One of the virtues of the von Neumann ordinals is that every ordinal is the set of all smaller ordinals.

    And von Neumann's idea allows us to give the standard, official definition of an ordinal number that you'll find in set theory textbooks:

    An ordinal is a transitive set well-ordered by .


    * The class of all ordinals.

    As I mentioned, the collection of all the ordinals is not a set. The class of ordinals is called On or sometimes Ord. It's On that Cantor originally identified with God. Cantor called the class of ordinals , the Absolute infinite. He already knew that the class of all ordinals is not a set. He said:

    The system Ω of all [ordinal] numbers is an inconsistent, absolutely infinite multiplicity. — Georg Cantor

    In modern set theory, On is of great theoretical importance.


    * Ordinal arithmetic

    We can add, multiply, and exponentiate ordinals. The Wiki writeup of ordinal arithmetic is pretty good and I can't add anything to it. One thing to know is that ordinal addition and multiplication are not in general commutative. They are both associative, and multiplication left-distributes but does not right-distribute over addition.



    * Odds and ends about countable ordinals.

    The countable ordinals are very wild and strange. is one mind-boggling countable ordinal we saw.

    A surprising fact is that every countable ordinal can be order-embedded into the rationals. That is, for every countable ordinal, there is a set of rationals in their usual order that's order-isomorphic to that ordinal.

    We've seen that there are uncountably many well-orders of . But there are only countably many Turing machines, or Python or C++ programs if you prefer. So there must exist noncomputable well-orderings of the natural numbers; and if there are any, since they're ordinals, there's a smallest one. The smallest noncomputable countable ordinal is called the Church-Kleene ordinal. From that point on, none of the order types of the natural numbers are computable.

    Here's the Feferman–Schütte ordinal, whose Wiki definition is far from clear to me and about which I know nothing.

    Wikipedia has an article on large countable ordinals that shows just how complicated things can get.

    I'm in too deep, time to stop.
  • jgill
    3.5k
    Well done! Handy reference for an oldtimer, Too. :cool:
  • Banno
    23.1k
    OK, I'm not reading all that... but thank you.
  • tim wood
    8.7k
    and eventually to the coolest number that I know, an ωω-sized exponental tower of ωω's. This number is called ϵ0=ωωω⋰ϵ0=ωωω⋰. Then there's a hierarchy ϵ1ϵ1, ϵ2ϵ2, and on and on. These are the epsilon numbers.

    Now here is the punch line.

    Every one of these ordinal numbers that I've shown so far is a countable set. It represents some well-ordering of NN.
    fishfry

    I have to pause here because you have said explicitly what I thought was an error on a video. An ordering has a first element (yes?). At some point candidates for the second element are exhausted, how then going forward does it remain uniquely orderable? And if it does, then how do you get to ε?
    I'll keep reading.

    Btw, for clarity on a difficult subject, you're hitting it out of the park!
  • fishfry
    2.6k
    I have to pause here because you have said explicitly what I thought was an error on a video.[/url]

    What vid, I'll take a look. Youtube giveth and Youtube taketh away.
    tim wood
    An ordering has a first element (yes?).[/url]

    A well-ordering, yes. Orderings in general need not have first elements, for example the usual < on the integers. But well-orderings always have a first, second, third, ..., element.

    tim wood
    At some point candidates for the second element are exhausted, how then going forward does it remain uniquely orderable?tim wood

    Not sure I understand the question. The ordering is given, we don't have to find it. Like the usual ordering on the natural numbers: 0, 1, 2, 3, ... We are given the ordering, then we observe that it's a well-ordering in which each nonempty subset has a smallest element.

    And if it does, then how do you get to ε?tim wood

    The key point is that the natural numbers start with 0 and are then produced by taking successors. The ordinals start with 0 and are produced by taking successors, and then accumulating successors in the limit, or sup operation. The ordinals are like the naturals, but with two generators -- successor and sup -- rather than just the one successor operation of the naturals.

    So we go 0, 1, 2, 3, ...; and then we slurp up all of those into and then keep on going: 0, 1, 2, 3, ..., , and all the way up to and beyond.

    It's a little dizzying, it honestly takes a long time to get used to. But the basic idea is successors and sups, successors and sups.

    Btw, for clarity on a difficult subject, you're hitting it out of the park!tim wood

    Thanks.

    OK, I'm not reading all that... but thank you.Banno

    I found that shortness and clarity were inversely related. I tried best I could to make it short and clear, and in the end strove for clarity. Readers will have to say whether I succeeded. For what it's worth, ordinals are a little complicated. I've been coming back to this material periodically for years.

    I recommend a book called Infinity and the Mind by Rudy Rucker. It has a fantastic visualization of the countable ordinals.

    ↪fishfry Well done! Handy reference for an oldtimer, Too. :cool:jgill

    Thanks!
  • TonesInDeepFreeze
    2.3k
    Re:

    The question was asked by tim wood: "What is an infinite ordinal?"

    As direct an answer I can provide:

    S is an ordinal if and only if all three: (1) every member of a member S of is a member of S, and (2) for any different members x and y of S, either x is a member of y or y is a member of x, and (3) in every non-empty subset of S there is a member m in the subset such that no member of the subset is a member of m.

    S is infinite if and only if there is no 1-1 correspondence between S and a natural number.

    S is an infinite ordinal if and only if both (1) S is an ordinal, and (2) S is infinite.
  • TonesInDeepFreeze
    2.3k
    An ordering has a first element (yes?)tim wood

    A well ordering of set S provides that every non-empty subset of S has a first element. And S is a subset of S, so if S is non-empty, then S has a first element. The first element of any ordinal is 0 (the empty set).

    But there are orderings other than well orderings.

    At some point candidates for the second element are exhausted,tim wood

    Not if the set is infinite.

    Also, if this is pertinent to your question, bear in mind that some ordinals have no last element and some ordinals do have a last element.

    uniquely orderabletim wood

    What does "uniquely orderable" mean?
  • TonesInDeepFreeze
    2.3k
    Further, in greater generality, a well ordering R of a set S is relation such that both (1) R is a subset of the set of ordered pairs of members of S, and (2) for any different members x and y of S, either Rxy or Ryx, and (3) for any non-empty subset of S there is a member m of the subset such that there is no member x of the subset such that Rxm.

    Then we see that S is an ordinal if and only if both (1) every member of a member of S is a member of S, and (2) the membership relation on S is a well ordering of S.

    Then, along the lines of fishfry's post, it is a theorem of ZF (transifinite induction is used) that for any set S and well ordering R of S, there is a unique ordinal D, such that <S R> is isomorphic with <D membership_relation_on_D>. So D is called 'the order type of <S R>'.
  • tim wood
    8.7k
    Every one of these ordinal numbers that I've shown so far is a countable set. It represents some well-ordering of NN.fishfry
    But now the modulo remainder trick doesn't work; and it's clear that there are going to be a lot more ordinals than there are obvious ways to reorder the naturals to represent them. We need new ideas.fishfry
    The core concept of ordinals is the idea of a well order. A well-order is an order relation on a set such that every nonempty subset has a smallest element.fishfry

    Hmm. New for me: well-ordered does not mean in-order, yes?! Is it correct to think of all the well-orderings to be the same thing as all the permutations? For the natural numbers, that would just be ω! (or maybe better aleph-0!), yes? The image I have - that maybe I have to work through - is of something like a deck of card. Fifty-two of them. With 52! possible arrangements. With the cards, at least, you can't get past 52! arrangements without duplication.

    I suppose similarly there is an upper limit on the arrangements of NN. And I get it that each of those is countable. Why not, they're just arrangements.

    Again how to be brief? Following with your construction above, it seems that ω is the ordinal associated with NN. But it also seems that ω is also associated with every infinite subset of NN. On this basis I (think) I can see where ω+1, ω+ω, ωω,..., come from. That leaves the question, how many infinite subsets of NN are there? (And with each ω as a subset, if well-ordering does not require being in-order, then each of those yielding ω! permutations - yes?) If all of this ends at ε - does it end at ε? - then how do you get beyond ε and still be countable? If it doesn't end, how do you get larger ordinals.

    I'm still reading. I suppose the answer is up ahead. I'll look for it, then, and wait for it.
  • tim wood
    8.7k
    A well ordering of set S provides that every non-empty subset of S has a first element.TonesInDeepFreeze
    First? Or least but not necessarily first?

    What does "uniquely orderable" mean?TonesInDeepFreeze
    I was thinking naively that well-ordering means the set can be and is ordered lexicographically. But with the OP I'm thinking the "and is" isn't part of it. E.g., I thought 1,2,3 is well-ordered when presented as {1,2,3}. But now I'm thinking that 1,2,3 is well ordered in each, and all, of six variations. If the latter is true, then my "uniquely orderable" is just a mistake.
  • fishfry
    2.6k
    Hmm. New for me: well-ordered does not mean in-order, yes?tim wood

    I'm not sure what you mean by in-order. Do you mean in its usual order? No. A well-order is an order in which every nonempty subset has a smallest element. Like the natural numbers in their usual order.

    ! Is it correct to think of all the well-orderings to be the same thing as all the permutations?tim wood

    No, not at all. For example we know from cardinality theory that there is a bijection from the natural numbers to the integers. So we can in fact permute the natural numbers, which are well ordered, to the integers, which aren't.

    It's easier to see this in the other direction. In their usual order, the integers are:

    ..., -4, -3, -2, -1, 0, 1, 2, 3, 4, ...

    which is NOT a well-order, because there is no first element.

    But what if I reorder them like this:

    0, -1, 1, -2, 2, -3, 3, -4, 4, ...

    That IS a well-order, because it has the same order-type as the natural numbers. So clearly we can take a set that's not well-ordered, permute its elements, and make it well-ordered. And we could do the same in reverse.

    For the natural numbers, that would just be ω! (or maybe better aleph-0!), yes? The image I have - that maybe I have to work through - is of something like a deck of card. Fifty-two of them. With 52! possible arrangements. With the cards, at least, you can't get past 52! arrangements without duplication.tim wood

    Every permutation of a finite set is a well-order. All finite sets are well-ordered and every permutation of a finite set has exactly the same order type. If I have a, b, c and then c, b, a, there's clearly an order-isomorphism between those two orders.

    I suppose similarly there is an upper limit on the arrangements of NN. And I get it that each of those is countable. Why not, they're just arrangements.tim wood

    We can rearrange 0,1,2,3,4,... into 1, 2, 3, 4, ..., 0. The former has order type , and the latter has order type . So for infinite sets, permuting does not preserve order type.

    Again how to be brief?tim wood

    I might not be the best person to give advice about that :-)
    Following with your construction above, it seems that ω is the ordinal associated with NN.tim wood

    With in its usual order. But we can rearrange to get very many different well-orders, and we can rearrange it so it's not well-ordered at all, as in the integer example I gave.


    But it also seems that ω is also associated with every infinite subset of NN.

    In its usual order, but not necessarily if we reorder it.


    On this basis I (think) I can see where ω+1, ω+ω, ωω,..., come from.

    is the order 1, 2, 3, ..., 0.

    is the even-odd order 0, 2, 4, 6, 8, ..., 1, 3, 5, 7, ...

    is a tricky one. We need copies of . There's no "obvious" rearrangement of the natural numbers that does that, even though there is one. It's just not obvious. But we can use the rationals.

    Consider, in the rationals, the set 1/2, 3/4, 7/8, 15/16, ... That's an instance of .

    So 1/2, 3/4, 7/8, ..., 1+1/2, 1+3/4, 1+7/8, ..., 2+1/2, 2+3/4, 2+7/8, ..., 3+1/2, 3+3/4, 3+7/8, ...,

    gives us a subset of the rationals in their usual order that's an instance of copies of , or .

    All of the countable ordinals are buried in the rationals in their usual order, so the rationals give a nice class of visualizations.


    That leaves the question, how many infinite subsets of NN are there?tim wood

    , right? That's basic cardinality. Well there are subsets all together, but only countably many infinite subsets, leaving infinite subsets. You know the old song. bottles of beer on the wall, bottles of beer, you take one down, pass it around, bottles of beer on the wall!

    (And with each ω as a subset, if well-ordering does not require being in-order, then each of those yielding ω! permutations - yes?)tim wood

    What do you mean "each" ? There's only one such ordinal. It would be like saying "each 3." There's only one 3.

    By in-order do you mean in its usual order? Well-orders don't require a set being lined up in its usual order. We've seen that some permutations result in well-orders and others don't, like the naturals-to-integers example. And the notation is not defined at all, for the reason that you can't subtract 1 from a limit ordinal. So we couldn't sensibly define that even if we tried.


    If all of this ends at ε - does it end at ε? -tim wood

    Do you mean ? No, there's , , etc. We can always take successors. Remember there are two rules:

    * Given an ordinal, we can always take its successor.

    * Given a set of ordinals, we can always take their sup or least upper bound, in the same way we can aggregate 0, 1, 2, 3, ... into the single ordinal and then keep on going with successors.

    The procession of ordinals never ends.

    then how do you get beyond ε and still be countable?tim wood

    Keep taking successors, and when you accumulate a bunch of those, accumulate them into their sup, or least upper bound.

    If it doesn't end, how do you get larger ordinals.tim wood

    Successors and sups. Successors and sups. Never ends.

    I'm still reading. I suppose the answer is up ahead. I'll look for it, then, and wait for it.tim wood

    Keep asking questions. These are not easy concepts, the ordinals are a deep idea.

    Can you tell me what video you saw? I'm curious to know.

    If you don't mind I'll take a shot at answering your questions to @Tones.

    I was thinking naively that well-ordering means the set can be and is ordered lexicographically.tim wood

    Well-ordering means that every nonempty subset has a least, or first, or smallest, element. Means the same thing. NOT like the integers, which have no first element. Does that make sense?

    {a,b,c} is ordered lexicographically, and {b,c,a} isn't, but they have the same order type and it's a well-order.

    But with the OP I'm thinking the "and is" isn't part of it. E.g., I thought 1,2,3 is well-ordered when presented as {1,2,3}. But now I'm thinking that 1,2,3 is well ordered in each, and all, of six variations. If the latter is true, then my "uniquely orderable" is just a mistake.tim wood

    Every permutation of a FINITE set is well-ordered and is the same order type.
  • TonesInDeepFreeze
    2.3k
    First? Or least but not necessarily first?tim wood

    'first' in the sense that there is no member that precedes it in the ordering. Usually we say 'least' or 'minimal'.

    can be and istim wood

    In ordinary mathematics, other than for colloquial emphasis, there is no difference in meaning between 'can be' and 'is'.

    well-ordering means the set [...] is ordered lexicographically.tim wood

    The definition of 'R is a well ordering of S' is:

    All three hold: (1) R is a subset of the set of ordered pairs of members of S, and (2) for any different members x and y of S, either Rxy or Ryx, and (3) for any non-empty subset of S there is a member m of the subset such that there is no member x of the subset such that Rxm.

    The definition of 'There is a well ordering of S' (or 'S is well ordered') is:

    There exists an R such R is a well ordering of S.

    Lexicographic ordering is something different.

    1,2,3 is well ordered in each, and all, of six variationstim wood

    Every permutation of {1 2 3} "induces" a distinct well ordering of {1 2 3}.

    A permutation of a set is a bijection from the set onto itself. For each permutation f of {1 2 3} there is the well ordering R on {1 2 3} defined by;

    Rxy <-> (x e {1 2 3} & y e {1 2 3} & f(x) < f(y))
  • fishfry
    2.6k
    Every permutation of {1 2 3} "induces" a distinct well ordering of {1 2 3}.TonesInDeepFreeze

    Yes but the same order-type, which is how we define an ordinal. Every possible permutation of a three-element set has the order type of the ordinal 3. Important to note in the present discussion I think.
  • TonesInDeepFreeze
    2.3k
    Is it correct to think of all the well-orderings to be the same thing as all the permutations?tim wood

    No. The set of all permutations of S is the set of all bijections from S onto S. The set of all well orderings of S is something different.

    ω!tim wood

    For a natural number n, we have n! = the cardinality of the set of all permutations of n. But n! is not the set of all permutations of n.

    So I would take 'w!' to mean the cardinality of the set of all permutations of w.

    NNtim wood

    By 'NN' I surmise you mean the set of natural numbers. That's confusing notation. I would just use 'N' or 'w' [read as omega].

    seems that ω is the ordinal associated with NN. But it also seems that ω is also associated with every infinite subset of NN.tim wood

    w = N = card(N) = aleph_0 = the order type of <N standard-ordering-of_N>

    'w', 'N', 'card(N)', 'aleph_0' are all names for the same set.

    If S is an infinite subset of N, then w = card(S)

    how many infinite subsets of NN are there?tim wood

    First, the cardinality of the set of infinite subsets of N is the cardinality of the power set of N (because the set of all finite subsets of N is countable, and the cardinality of the union of a countable set and an uncountable set is the cardinality of the uncountable set).

    So the question is:

    What is the value of x in the following?:

    card(power set of S) = card({f | f is a function from S into {0 1}) = aleph_x

    The answer to that depends on the continuum hypothesis.

    εtim wood

    What does epsilon stand for there? Do you mean epsilon_0?

    how do you get beyond ε and still be countable?tim wood

    epsilon_0 + 1 is countable. There is no greatest countable ordinal.

    /

    To keep in mind:

    There are two different things: (1) a set S and (2) <S R> where R is a well ordering of S. Strictly speaking, it doesn't make sense to say 'S is not well ordered'. Rather, strictly speaking, we would say for a given R that is not a well ordering of S that "S is not well ordered by R'. For example, strictly speaking, we would not say "The integers are not well ordered" but instead, strictly speaking, we would say "The integers are not well ordered by the standard ordering of the integers". In casual contexts, we take it for granted that we are referring to the standard orderings, so "the integers are not well ordered" is okay in that casual context. But sometimes we need to be stricter to avoid misunderstanding.

    Also, strictly speaking, permutations themselves are not usually well orderings, but rather a permutation may "induce" a well ordering. A permutation is a bijection from a set onto itself. That is not usually a well ordering. In casual contexts, we benignly conflate the permutation with an ordering the permutation "induces", but sometmeise we need to be stricter to avoid misunderstanding.

    /

    General suggestion: It is virtually impossible to gain a clear understanding of set theory through back and forth posts. Only a textbook studied systematically starting at page 1 is likely to work.
  • TonesInDeepFreeze
    2.3k
    Here is some of the terminology (not necessarily in logical order) that one must have a very clear understanding of in order to have a clear understanding the matters in this thread. If one is at all unclear about this terminology and the axioms and main theorems, then confusion is virtually inevitable. But a good textbook takes you through it all step by step:

    class
    set
    empty set
    proper class
    subset
    power set
    union
    pair
    ordered pair
    singleton
    relation
    domain
    range
    field
    Cartesian product
    converse relation
    function
    bijection
    into
    onto
    permutation
    reflexive relation
    irreflexive relation
    symmetric relation
    anti-symmetric relation
    asymmetric relation
    transitive relation
    connected
    linear ordering
    well ordering
    epsilon transitive
    ordinal
    successor ordinal
    limit ordinal
    transfinite recursion
    homomorphism
    isomorphism
    order-type
    finite
    natural number
    set of natural numbers
    infinite
    Dedekind infinite
    countable
    uncountable
    cardinal
    cardinal addition
    cardinal multiplication
    cardinal exponentiation
    aleph
    ordinal addition
    ordinal multiplication
    ordinal exponentiation
    recursive ordinal
    epsilon_0
    tuple
    lexicographic ordering
  • jgill
    3.5k
    Having left the profession before remote learning became fashionable, I am impressed with this thread. An ideal arrangement having two highly competent instructors and one focused student. :cool:

    One might expect Metaphysician Undercover (Unknown) to chime in with "inherent order", but he might be out of his depth.
  • Banno
    23.1k
    One might expect Metaphysician Unknown to chime in with "inherent order", but he might be out of his depth.jgill

    As if that would stop him.
  • Pfhorrest
    4.6k
    Seems like every popular leftist finite ordinal is coming out as trans these days. Pretty soon they’ll make it illegal to be a cis finite ordinal at all!
  • fishfry
    2.6k
    Here is some of the terminology (not necessarily in logical order) that one must have a very clear understanding of in order to have a clear understanding the matters in this thread.TonesInDeepFreeze

    I emphatically disagree. I wrote my post so as to not need much background at all; pretty much the basics of infinite cardinalities as vaguely understood by the average reader of this site. Whether I was successful or not, I can't yet say. But one need not be a specialist to get the general idea of the transfinite ordinals.

    Seems like every popular leftist finite ordinal is coming out as trans these days. Pretty soon they’ll make it illegal to be a cis finite ordinal at all!Pfhorrest

    Set-theoretic comedy is harder than it looks :-)
  • TonesInDeepFreeze
    2.3k


    I didn't say one needs to be a specialist. Having an adequate grasp of the basic terminology doesn't require that one be a specialist. And one can get the "general idea" about ordinals, but a clear understanding includes a clear understanding the definitions of the terminology used.
  • fishfry
    2.6k
    And one can get the "general idea" about ordinalsTonesInDeepFreeze

    That's the point.

    a clear understandingTonesInDeepFreeze

    I aspire to clear understanding myself. It's an ongoing process.
  • tim wood
    8.7k
    It is virtually impossible to gain a clear understanding of set theory through back and forth posts. Only a textbook studied systematically starting at page 1 is likely to work.TonesInDeepFreeze

    I accept this as a fair statement. But I will note there are many who consider such books "archives" and that the sine qua non of learning is the good teacher. I myself favor middle ground, finding books to allow triangulation on a topic by one providing illumination where another is dark, while a teacher provides guidance and explains difficulties. And I have some familiarity with most of the terms you listed, but we can both agree that mere familiarity with terms doesn't get a person very far.

    A difficulty of mine lies in asking intelligible questions briefly - or at all!

    We can do the same trick with remainders mod 4, 5, and so on, to represent ω4,ω5,…ω4,ω5,…. Eventually the upward limit of that process is ωω copies of ωω, or ω∗ω=ω2ω∗ω=ω2.

    But now the modulo remainder trick doesn't work; and it's clear that there are going to be a lot more ordinals than there are obvious ways to reorder the naturals to represent them. We need new ideas.
    fishfry

    Hmm. I find this, which seems a model of clarity:
    -------------
    "The version of the paradox above is anachronistic, because it presupposes the definition of the ordinals due to John von Neumann, under which each ordinal is the set of all preceding ordinals, which was not known at the time the paradox was framed by Burali-Forti. Here is an account with fewer presuppositions: suppose that we associate with each well-ordering an object called its order type in an unspecified way (the order types are the ordinal numbers). The order types (ordinal numbers) themselves are well-ordered in a natural way, and this well-ordering must have an order type Omega . It is easily shown in naïve set theory (and remains true in ZFC but not in New Foundations) that the order type of all ordinal numbers less than a fixed alpha is alpha itself. So the order type of all ordinal numbers less than Omega is Omega itself. But this means that Omega , being the order type of a proper initial segment of the ordinals, is strictly less than the order type of all the ordinals, but the latter is Omega itself by definition. This is a contradiction." https://en.wikipedia.org/wiki/Burali-Forti_paradox
    ---------------

    Maybe this way.
    I vaguely remember a comment that "explained" certain large cardinals by saying, "You can't get theah from heah." By which I understood that no ordinary process could get to them, meaning, as best I get it, that no recursion scheme could get to them. The idea was that they were simply defined into existence, and then it was interesting to see what could be done with them. Perhaps analogous to studying the mating habits of Klingons.

    I can "see" the ωs. If each ω were the address of a house on a street, ω-street, it would be a very long street indeed, and I can see a short distance down it. But at some point the name of the street changes from ω-street to ε-street and keeps on going.

    Question: is the change from ω-street to ε-street a "can't get theah from heah" transition? I see the language that says you just add a successor, but what successor would that be? Because it would seem that by the time the εs are got to, all the successors have already been used.

    By "successor" I understand some number, as 3 is the successor to 2, 4 to 3, and so forth.
  • fishfry
    2.6k
    The idea was that they were simply defined into existence,tim wood

    Large cardinals require additional set-theoretic axioms, correct. That's the definition of large cardinals.

    Question: is the change from ω-street to ε-street a "can't get theah from heah" transition?tim wood

    No. Everything we've discussed is provable in ZF. You don't even need the axiom of choice. There are "large ordinals" in the sense that new set-theoretic axioms are needed to prove their existence, but we haven't talked about them.

    The "large countable ordinals" are ordinals for which there aren't notations, which aren't computable, and so forth. They still exist within ZF and in fact they're all countable sets. So perhaps "large countable ordinal" and "large ordinal" is misleading terminology, because they're two very different concepts.

    I see the language that says you just add a successor, but what successor would that be?tim wood

    You keep taking successors and sups, successors and sups. is a limit ordinal, it's not the successor of any ordinal.

    It's not easy to get your mind around , I've been slowly developing intuition for it and still have a ways to go. It's the limit of the ordinals , , , , etc. Not easy to comprehend. These are all countable, no new axioms are required to construct them.

    Even , the first uncountable ordinal, exists in ZF with no choice needed.

    I'm wondering if you feel like you have gotten any of your original questions answered yet, and if this thread has helped put the video you saw into context.
  • tim wood
    8.7k
    and if this thread has helpedfishfry
    Your OP a Disneyland of rides, and I not tall enough for most of them.

    You keep taking successors and sups, successors and sups. ϵ0 is a limit ordinal, it's not the successor of any ordinal.fishfry

    And yet it's countable. That seems strange.

    With zero and 1, I take it a person can get to any number in {0, 1, 2,.., n}, though perhaps not efficiently. The limit of that being ω. Hmm. The only way I can understand ω or ω+1, is simply as the numbers ω and ω+1, which are just larger than any of the {0, 1,.., n}. Maybe I need a bit more care in thinking about what a number is. Transfinite cardinals and ordinals thus not numbers in any naive sense, but in an extended sense, perfectly useful and thus perfectly good.
  • fishfry
    2.6k
    Your OP a Disneyland of rides, and I not tall enough for most of them.tim wood

    To put it into context, it takes a long time to get one's mind around even the basics of the ordinals. If you think of my article as kind of a high-level tourist flight, perhaps that's more helpful. Maybe appreciate a little here and a little there.

    So the main thing is that you originally had some questions about the subject based on video you saw. If you have specific questions, perhaps I can answer them.

    Also I wonder if you can point me to the video. I'm curious if it's a good vid explained badly or a bad vid explained well, and maybe I'll learn something.



    And yet it's countable. That seems strange.tim wood

    It is very strange. The countably ordinals are massively strange, the strangest mathematical structure I know. I looked up proofs that is countable and I'm not sure I understand them. That's the next thing for me to learn. is my own personal favorite number. I still have a very limited understanding of it.

    With zero and 1, I take it a person can get to any number in {0, 1, 2,.., n}, though perhaps not efficiently. The limit of that being ω. Hmm. The only way I can understand ω or ω+1, is simply as the numbers ω and ω+1, which are just larger than any of the {0, 1,.., n}.tim wood

    is in its usual order.

    is in the funny order:

    1, 2, 3, 4, 5, 5, 6, ..., 0. It's the same set of numbers, but 0 comes after everything else.

    Perhaps that's the most important concept to get. The idea that we can rearrange, or permute, the elements of to get a set with the same cardinality -- it's the same set of elements, after all -- that's also well-ordered, but that has a different order type. Because has a largest element, and doesn't.

    I think if we could stay here for a while and understand this one point it would be helpful. It's the heart of the whole matter, your original question of "what is a transfinite ordinal?"

    The key to this whole business is to understand as an alternate ordering of the natural numbers, one that has both a smallest and a largest element yet is the exact same set of numbers. Let's drill down there. You said you don't quite understand so let's work on that if you're open to it. That's the key to the whole enterprise.


    Maybe I need a bit more care in thinking about what a number is. Transfinite cardinals and ordinals thus not numbers in any naive sense, but in an extended sense, perfectly useful and thus perfectly good.tim wood

    They're transfinite numbers. Definitely different than plain old finite numbers or even real or complex numbers. Sort of analogous to how negative numbers were once new, and irrational numbers and then complex numbers were once new and revolutionary, and are now accepted by everyone. Transfinite numbers came out of nowhere from the mind of one person in the 1870's, and that's not very long ago in the scheme of things.
  • TonesInDeepFreeze
    2.3k
    An ordinal number is the order-type of a well-ordered setfishfry

    Yes, 'x is an ordinal iff x is the order-type of a well ordered set' is a theorem. From the definition of 'order-type', every order-type is an ordinal. And with a trivial proof, every ordinal is an order-type. But, just to be clear, 'x is an ordinal iff x is the order-type of a well ordered set' is not a definition of 'is an ordinal', lest we have the circularity of defining 'order-type' with 'ordinal' and 'ordinal' with 'ordinal type'.

    A well-order is an order relation on a set such that every nonempty subset has a smallest element.fishfry

    Not just any order relation such that every nonempty subset has a minimal member. Rather, a connective order such that every nonempty subset has a minimal member. ('connective order' might not be a usual terminology; what I mean is an order R on S such that for every x and y in S, either Rxy or Ryx.)

    Every possble nonempty set of the naturals has a smallest member, so the naturals are well-ordered by <.fishfry

    Yes, but again, also because < is a connective order. Also, merely as a small note, we don't need to mention modality with 'possible'.

    the negative numbers have no smallest element.fishfry

    Yes, but just to be clear (since we are considering contexts in which we mention also other orderings), the set of integers has no minimal element regarding the standard ordering on the integers.

    ω stands for the natural numbers in their usual order.fishfry

    w is the order-type of <w standard-ordering-on_w>, but more basically, w is the set of natural numbers, even irrespective ordering.

    If the usual order 0, 1, 2, 3, ... is called ωfishfry

    w is not an order. w is the order-type of <w standard-ordering-on_w>.

    our funny order (N,≺) is called ω+1fishfry

    w+1 is not an order. w+1 is the order-type of <w ≺>.

    even without choice, some uncountable sets can be well-ordered. Just not all of them.fishfry

    It is not the case that the absence of choice implies that not all sets have a well-ordering. Rather, the absence of choice leaves it undecided whether all sets have a well-ordering.

    in the absence of choice, there are infinite sets that are not well-orderedfishfry

    As above.

    there's also no set of all sets bijectively equivalent to the naturals or any other cardinality.fishfry

    Except the cardinality 0. The set of all sets that have a bijection with 0 is {0}.

    the Alephs are indexed by whole numbersfishfry

    As you mentioned later, for any ordinal, there is the aleph indexed by that ordinal.
  • TonesInDeepFreeze
    2.3k
    Infinity and the Mind by Rudy Rucker.fishfry

    That is an entertaining book, but one might need to take it with a grain of salt regarding certain technical matters (I don't recall the particular matters now).

    Another entertaining book about logic is William Poundstone's 'Labyrinths Of Reason'.
  • TonesInDeepFreeze
    2.3k
    in the limit, or sup operation.fishfry

    We should mention that limits (aka 'sups') in regard to ordinals are unions that are not successors. We need to have a good understanding of both binary union and generalized union to understand ordinals.
  • TonesInDeepFreeze
    2.3k
    Every permutation of a finite set is a well-order.fishfry

    For clarity, I prefer to use 'permutation' in its exact mathematical meaning. A permutation is a bijection from a set onto itself. In that regard, a permutation is not an ordering. A permutation may "induce" (I don't know whether there's a more usual terminology) an ordering:

    Any permutation f of a set (finite or infinite) that has a well ordering R induces a well-ordering R* as follows:

    R*f(x)f(y) <-> Rxy

    A well-order is an order in which every nonempty subset has a smallest element.fishfry

    Again, we need also to include mention that the order is a connective order.

    So for infinite sets, permuting does not preserve order type.fishfry

    With the ordinary mathematical definition of 'permutation', the above is incorrect. As mentioned above:

    Any permutation f of a set (finite or infinite) that has a well ordering R induces a well-ordering R* as follows:

    R*f(x)f(y) <-> Rxy
  • TonesInDeepFreeze
    2.3k
    there are many who consider such books "archives" and that the sine qua non of learning is the good teacher. I myself favor middle ground, finding books to allow triangulation on a topic by one providing illumination where another is dark, while a teacher provides guidance and explains difficulties.tim wood

    Whatever many people may think, such books are key to understanding. But of course, a combination of books and teachers is best. In any case, in mathematics, to have a good understanding, it is crucial that the study is systematic - moving from the most basic concepts, step by step through definitions and proofs, to more complicated material.

    I vaguely remember a comment that "explained" certain large cardinals by saying, "You can't get theah from heah." By which I understood that no ordinary process could get to them, meaning, as best I get it, that no recursion scheme could get to them.tim wood

    I take it you mean 'large cardinal' in the mathematical sense. I don't know enough about the relation of recursion and large cardinals, but I would be careful saying things like "no recursion scheme could get to them" without specifying exactly what you mean by that. In any case, the context at least requires understanding the definitions of 'large cardinal' and 'transfinite recursion'.
  • TonesInDeepFreeze
    2.3k
    The only way I can understand ω or ω+1, is simply as the numbers ω and ω+1, which are just larger than any of the {0, 1,.., n}.tim wood

    You are skipping the definitions:

    w = the set of natural numbers

    w+1 = w u {w}

    Maybe I need a bit more care in thinking about what a number is.tim wood

    Mathematics doesn't have a separate definition of 'number' in general. Only definitions of 'number' with an adjective such as 'natural', 'rational', 'real', 'complex', 'ordinal', 'cardinal', et. al. So don't think of having to understand a concept of "is a number" onto itself.

    When we say 'ordinal number', 'cardinal number', et. al, we could just as well merely say 'ordinal', 'cardinal', etc. The word 'number' is just artifact really. If 'number' is tripping you up, then forget about the word 'number'.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment