# Definition of Ordinals in Set Theory in Layman Terms

I've taken a huge interest in the mathematical concept of infinity and often been contemplating the same over years. But the fundamental concept of set theory ordinals continues to evade my understanding. The questions below comprise (more or less) the gaps in my comprehension of the mathematical infinite:

1. Ordinal numbers in general (1st, 2nd, 3rd, 4th...) are entirely different from ordinal numbers in set theory, correct?
2. I understand that set theory ordinals are basically sets that contain a least element by definition. But, is it necessary for the elements of an ordinal to be strictly in order? For example, must the ordinal 4 be represented as {∅, {∅}, {∅,{∅}}, {∅, {∅}, {∅,{∅}}}....} and not as {{∅,{∅}}, ∅, {∅}, {∅, {∅}, {∅,{∅}}}....}?
3. The cardinality of ω is א‎0 (please correct me if I'm wrong), but where exactly is the position of ω along the number line. Is it א‎0th position (so to speak)?

I apologize for the naivety of the questions above (honestly, I really don't find a layman explanation of ordinals anywhere on the web. I saw a very good YouTube video though). The objective is to understand the core concept of set theory ordinals (well enough to be able to explain the same to a layman) rather than memorizing formal, mathematical definitions with little to no true comprehension of the same. Thanks in advance!

• I'm 99% confident that the video of which you speak is riddled with mathematical holes, which of course lay people cannot see. Better to leave it unmentioned... – user21820 Jul 16 '16 at 4:26
• Yes, I was kind of having the same thought myself :) – Hemnath Prabagaran Jul 16 '16 at 6:04
• I'm writing an explanation now that rigorously explains the intuition behind ordinals, but it will take a while. – user21820 Jul 16 '16 at 6:13
• Please, please do!! Mathematics is not my favourite subject, but when I came across Georg Cantor's perspective of infinity, it blew my mind! I've been a ardent follower of the set theory representation of infinity since. At this juncture, I find it extremely disappointing that virtually nowhere on the web I'm able to find a simple, core explanation for infinite ordinals. Your explanation, I'm sure, will be a huge contribution to existing, online information on transfinite ordinals. You have my utmost gratitude. – Hemnath Prabagaran Jul 16 '16 at 6:52
• When you say $n$th position, you are talking about an ordinal number $n$. Since $\aleph_0$ is not an ordinal, but rather a cardinal, talking about the $\aleph_0$th position along the ordinal line makes no sense. However $\omega$ is the $\omega$th ordinal. – Asaf Karagila Jul 16 '16 at 14:08

## 4 Answers

Counting has two purposes, namely for specifying sizes and indices. These are directly related for finite quantities, because the number of natural numbers (including $0$) less than $n$ (before the position $n$) is $n$. But in set theory, when generalizing to infinite sets these two notions become different. $\def\nn{\mathbb{N}}$ $\def\zz{\mathbb{Z}}$ $\def\qq{\mathbb{Q}}$ $\def\rr{\mathbb{R}}$ $\def\eq{\leftrightarrow}$ $\def\less{\smallsetminus}$ $\def\none{\varnothing}$

The notion of size is extended to infinite sets in the following way. Take any two sets $X,Y$. We say that $X$ is no larger than $Y$ if we can label each element of $X$ with a unique element of $Y$, in the sense that no two elements of $X$ are given the same label. Mathematically this labelling is called an injection from $X$ into $Y$, and we write $\def\inj{\hookrightarrow}$$X \inj Y. We say that X is of the same size as Y iff there is a bijection (1-to-1 correspondence) between elements of X and elements of Y, and we write X \approx Y. It turns out that if X \inj Y and Y \inj X then X \approx Y. Notice that \nn_{>0} \inj \nn via the identity labelling, and \nn \inj \nn_{>0} by labelling each element n of \nn by n+1. So \nn_{>0} \approx \nn, meaning that they cannot be distinguished in terms of size as defined above. There is no other elegant way to define size comparison to distinguish them, because we want it to be independent of labelling, meaning that we want X \approx \{ f(x) : x \in X \} for any set X and function f on X. ## Indices The notion of indexing, on the other hand, can be extended in the following way. Indexing is used for a sequence, where order is important. Note that a sequence is nothing more than a function on its indices, where the indices are totally ordered. But if we want to define a sequence recursively by defining each element in terms of all the previous ones, then it is in general not enough for indices to be ordered. Specifically, a recursive definition on I is a function E such that, for every i in I and function f on I_{<i}, E(f) is a function on I_{\le i}, and we want to build a function f on I such that f \restriction I_{\le i} = E(f \restriction I_{<i}) for any i \in I ("f \restriction D" denotes "f restricted to the domain D"). We cannot always do this if I has a strictly decreasing infinite sequence. For a concrete example, there is no function f on \zz such that f(r) = \cases{0 & if \exists s \in \zz_{<r}\ ( f(s)=1 ) \\ 1 & otherwise}, despite it looking like a recursive definition. (Exercise: Prove that no such f exists!) Notice that this counter-example can be easily adapted to any I that has some strictly decreasing infinite sequence. It turns out that, if I has no strictly decreasing infinite sequence, then every recursive definition on I not only will have some sequence satisfying it (in the above sense) but also that sequence is in fact unique! We say that a total order is well-ordered iff if every non-empty set of elements in it has a minimum. Now given any such I and any set S of elements in I, if S has no minimum then we can iteratively pick a (countable) strictly decreasing sequence of elements in S [by the axiom of dependent choice]. Therefore I is well-ordered. Now take any recursive definition E on I. If E does not 'work', namely it does not uniquely define a sequence on I, then let S be the set of all elements i in I such that there is no unique function f on I_{\le i} such that f agrees E(f \restriction I_{<i}), and let m be the minimum of S in I. Then for every i \in I_{<m} there is a unique function on I_{\le i} satisfying E, and all these functions agree, and hence combining them gives a unique function on I_{<m} that satisfies E. By definition of E there is a unique function on I_{\le m} that satisfies E, contradicting the definition of m. Therefore E does 'work', namely there is a unique sequence on I that satisfies E. [Note: If you do not want to use the axiom of dependent choice, then you can still have recursive definitions for well-orders.] The above is why we use well-orders for indexing, since every well-order has no strictly decreasing infinite sequence. In textbooks E is also called an extender function because it essentially allows us to extend the partial sequence of all previous terms to the current term. [Technically E is not an object in most set theories, but we always use E as a function and so we can still apply the above argument to any specific defining formula for E without constructing E.] Also, the above proof technique generalizes to transfinite induction, which is that for any well-order I and statement P we can prove \forall i \in I\ ( \forall j \in I_{<i}\ ( P(j) ) \to P(i) ) \to \forall i \in I\ ( P(i) ). ## Ordinals Given any two total orders X,Y, we say that X embeds into Y if there is an injection φ from X into Y that preserves the ordering, meaning that a < b \eq φ(a) < φ(b) for every a,b in X. Also, we say that X is isomorphic to Y if there is a bijection from X to Y that preserves the ordering. It is not too hard to prove that, for any two non-isomorphic well-orders, one of them embeds into the other, and not the other way around. Therefore well-orders are themselves totally ordered up to isomorphism, meaning that they satisfy the conditions for a total order except that equality is replaced by isomorphism. Now the next natural step is to find a canonical form for well-orders, which we shall call ordinals. Take any well-order X. Recursively define the sequence f on X by f(i) = \{ f(j) : j \in X_{<i} \} for each i \in X. Then its range \{ f(i) : i \in X \} ordered under set membership \in is isomorphic to X! (Exercise: Prove this by using transfinite induction to prove simultaneously that \{ f(j) : j \in X_{\le i} \} and f(i) are well-ordered under \in for every i in X.) We use this well-ordering as the (canonical) ordinal for X, which we shall denote by ord(X). We will also order ordinals by \in unless otherwise stated. This also can motivate the von Neumann definition of ordinals as sets that are transitive (every element is a subset) and well-ordered under \in. It turns out that every (canonical) ordinal is also a von Neumann ordinal, and every von Neumann ordinal is its own (canonical) ordinal. (Exercise: Prove this. For the first part, first prove by transfinite induction that f(i) is a von Neumann ordinal for every i in X.) Note that no ordinal is an element of itself, otherwise it will have a strictly decreasing infinite sequence. Consequently, there cannot be a set of ordinals ORD in most set theories, because ORD would be a von Neumann ordinal and hence ORD \in ORD. ## Cardinals Now we go back to the notion of size. It turns out that we can use some of the ordinals to represent the sizes of infinite sets. Take any set X. Let W be the set of all well-orders with elements in X, and let A = \{ ord(w) : w \in W \}. Then we can prove that A is a von Neumann ordinal. Also there cannot be an injection f from A into X, otherwise we can define a well-order < on S = \{ f(a) : a \in A \} by f(a) < f(b) \eq a \in b, and then A = ord(S,<) \in A. Given the full axiom of choice, we can prove that X \approx A_{<i} for some i \in A as follows. Recursively define f(i) to be some element in X \less \{ f(j) : j \in A_{<i} \} if there is one and \none otherwise, for each i \in A. By definition of A, f is not an injection from A into X, and hence there is a least i \in A such that X \less \{ f(j) : j \in A_{<i} \} is empty, which implies that f \restriction A_{<i} is an bijection between A_{<i} and X. By the well-ordering of ordinals we can define \#(X), the cardinality of X, to be the least ordinal such that there is a bijection between X and it. [Without the axiom of choice, we cannot define f and so this definition of cardinality fails, but by the well-ordering of ordinals there is a least ordinal H, called a Hartogs number, such that there is no injection from H into X, which is also a sort of measure of size.] The size condition allows us to define recursive sequences on X by ordering its elements according to this well-order. The minimality condition ensures that the partial sequence that we have to extend in the recursive definition is strictly smaller than X, which condition may be needed by the recursive definition itself. For instance we can prove that \#(S^2) = \#(S) for any infinite set S by transfinite induction. Let k = \#(S). Then it suffices to prove that \#(k^2) = k. Order the elements of k^2 by maximum and then lexicographic order, which can be easily shown to be a well-order. Let m be the ordinal for this well-order, and let f be the isomorphism from m to k^2. If k < m, then let a,b \in k such that f(k) = (a,b), and let d = \#(\max(a,b)) \le \max(a,b) < k. Then k is isomorphic to \{ f(i) : i \in k \} \subseteq \{ (x,y) : x,y \in k \land x,y \le d \} \approx \#((d⊕1)^2) = \#(d^2⊕d⊕d⊕1) = \#(d⊕d⊕d⊕1) < k, where "p⊕q" denotes a disjoint union of p and q, namely \{ (0,x) : x \in p \} \cup \{ (1,x) : x \in q \}. The last inequality is because k is infinite, and either d is finite and so d⊕d⊕d⊕1 is also finite, or d is infinite and so \#(d⊕d⊕d⊕1) = d. Thus \#(k) < k, contradicting the definition of k. Therefore k \ge m \ge \#(k^2) \ge \#(k) = k, and hence \#(k^2) = k. (Exercise: Prove that there is a set S of points in the plane such that every line passes through exactly two points in S. Sketch: Let c = \#(\rr). Then there are \#(\rr^2⊕\rr) = c many lines in the plane. We start with S = \none and iterate through the lines indexed by c. We maintain the invariance that at each step i \in c there are at most 2i many points added so far, which means that there are at most (2i)^2 points on the current line L that cannot be added to S without violating the desired property. But (2i)^2+2 < c and L passes through c many points, so we can add (up to two) points to S such that L passes through exactly two points without violating the desired property.) • Anyway to answer your questions: (1) It turns out that the von Neumann construction of a model of Peano Arithmetic in ZFC is the ordinal ω, which is the set of all finite ordinals, with addition and multiplication defined on it by induction. So in that sense the 'ordinary' numerical ordinals are indeed set-theoretic ordinals too! (2) A set has elements but no order. It so happens that the elements of an ordinal are ordered under \in, but that does not mean that the set has order to its elements by itself! – user21820 Jul 16 '16 at 14:28 • (3) There is no number line in set theory. But imagine ω as a set of dots going off to the right, itself denoted by a dot after them all. The position of an ordinal in ORD is itself. – user21820 Jul 16 '16 at 14:30 • If that's as simple as you can put it, thank you. I'm beginning to feel I should've first brushed up on set theory language and symbolic representations (which I hardly remember any more as I first learned them way back in elementary school) before I troubled the good folks here with layman-level questioning. – Hemnath Prabagaran Jul 17 '16 at 0:56 • @HemnathPrabagaran: Yes it is difficult to understand the need for ordinals unless you need such kind of (transfinite) recursion/induction. If all you want to deal with is natural numbers and sets of them, then almost always you don't need anything more than ordinary induction. I think it's fine if you don't get the technical details (especially those in square-brackets, which are meant for advanced readers). However, perhaps the key idea that you can take away is that strong induction expressed using only ordering extends to 'longer' sequences only if the indices are well-ordered. – user21820 Jul 17 '16 at 4:53 • @HemnathPrabagaran: In any case, I did intend my answer to be as useful as possible for readers at all levels, partly because I myself was never taught the motivation for ordinals and had to figure it out myself. Your question prompted me to try to find the most intuitive motivation I could come up with. Anyway you can come back here in the future to read this again, and feel free to ask me questions you have then. =) – user21820 Jul 17 '16 at 4:59 To understand ordinals you first need to understand what is a well-order. Well-orders are a type of strict partial orders which satisfy the following axiom: Every non-empty set has a minimum. This implies that well-orders are linear orders, and that they look kinda like the natural numbers. The most important property of well-orders is that we can use them for inductive constructions and proofs, much like the natural numbers. Now, when we want to do something by induction and use some well-ordered set, the specific set does not matter. What matters is how does the set "looks like". In mathematical terms we care about its order type, rather than its actual elements. Two partially ordered sets have the same order type if there is an order isomorphism between them: a bijection between the two sets which preserves the order attached to each set. Let's consider a quick example: \Bbb N and \Bbb N\cup\{-42\}, both ordered by the usual order of the integers, are isomorphic, they have the same order type. The isomorphism can be even given explicitly,$$f(x)=\begin{cases}0 & x=-42\\ x+1 & x\in\Bbb N\end{cases}$$I will let you check and see that this is an isomorphism. Two important theorems about well-ordered sets are these: 1. If$A$and$B$are two well-ordered sets, and there is an order isomorphism from$A$into some$B'\subseteq B$and from$B$into some$A'\subseteq A$, then in fact there is an isomorphism between$A$and$B$. Moreover, this isomorphism is unique. This is a non-trivial fact. Take a look at$\Bbb Q$and$\Bbb Q\cap[0,1]$. We can embed each into the other, but they are not isomorphic: one of them has a minimum and maximum and the other does not. And even if we consider a simpler example,$\Bbb Z$and$\Bbb Z$itself, there are many ways to move the elements around while preserving the order. 1. If$A$and$B$are two well-ordered sets, then either$A$is isomorphic to an initial segment of$B$or$B$is isomorphic to an initial segment of$A$. (And this isomorphism is unique, as a consequence of the previous theorem.) Again, this is nontrivial. Consider$\Bbb Z$and$\Bbb Q$. Neither one is isomorphic to the other, and neither one is isomorphic to an initial segment of the other. So what do these two theorems tell us? They us that well-orders are very robust, they have great comparability properties, and so if we only consider equivalence classes of well-orders under isomorphism, this induces a natural ordering between the classes, which itself happens to be a well-ordering. That's great! But now we have a mild problem. Other than the empty order, there is a proper class of well-ordered sets from each order type. Just note that for the order type of "one element", every singleton can be a candidate for the well-ordered set, and there is a proper class of those. This is not a huge problem, but wouldn't it be nice if we could replace these proper classes by sets? At some point in the early years of set theory, von Neumann suggested that instead of thinking in terms of abstract well-ordering, since they are so nice, we pick canonical representatives from each isomorphism class. And he proved that you can find a unique set which is transitive and well-ordered by$\in$inside each class. (Here we say that$A$is a transitive set if whenever$a\in A$, it follows that$a\subseteq A$.) And this is the von Neumann ordinal assignment. It picks from each order type, the unique transitive set which is well-ordered by$\in$. Then, a magical thing happens, it turns out that$0=\varnothing$, and the successor of$\alpha$is$\alpha\cup\{\alpha\}$, and that if$\{\alpha_i\mid i\in I\}$were defined, and$I$is a well-ordering without a maximal element, then$\bigcup\{\alpha_i\mid i\in I\}$is the limit of the$\alpha_i$'s. And that gives us a very robust structure for the von Neumann ordinals:$\alpha=\{\beta\mid\beta<\alpha\}$, where$<$here indicates "isomorphic to a proper initial segment". Let me digress now, and since you brought$\aleph_0$into the discussion, talk about cardinals for a moment. Cardinals are also isomorphism classes, like order type, only here we use just plain ol' bijections without requiring they preserve any structure. In the days of yore cardinals were also proper classes (except that of the empty set). We would say that$A$has cardinality$\aleph_0$if it has a bijection with the natural numbers, for example. As set theory grew, we realized that if$A$can be well-ordered, then there is a smallest order type of such a well-ordering (because the order types of well-ordered sets have a well-ordering themselves). This meant that we can assign to a set that can be well-ordered the least ordinal that can be put in bijection with that set. And after you have the von Neumann ordinals, this points at a specific set, too. Of course, assuming the axiom of choice every set can be well-ordered and that's fine, but not assuming choice, we need to find a better solution, and I won't discuss it here. We have since come to confuse cardinals with ordinals on a regular basis. This is fine if all parties involved are well-aware of the differences and the implicit contexts and types. But I would generally advise against it (and I try my best to discern in my work between the cardinal and the ordinal, whenever possible). The two systems are equipped with addition, multiplication and exponentiation. And they often disagree.$\aleph_0+\aleph_0=\aleph_0$as cardinal addition, but$\omega+\omega\neq\omega$as ordinal addition. So talking about$\aleph_0$as if it was an ordinal is technically not a mistake, but it can lead others to mistaken conclusions (I recall several occasions that I had struggled with such notation; and historically we can find examples of people who didn't understand implicit contexts and made mistakes.) Now, you asked whether or not ordinals denote "first" and "second" and "$\alpha$th". And the answer is yes. An ordinal is the answer to "how long is the queue to the bathroom". Cardinals, however, are the question "how many people are in the queue to the bathroom". As long as the queue is finite, the answers are the same. But if the queue has order type$\omega$, then every person has to wait only a finite time before using the facilities; but if you join at the end of the queue, we didn't increase the "how many" answer, but you clearly have to wait an infinite time before you can get to the bathroom. So using$\aleph_0$to denote a location in the queue is not ideal, as I remarked. Sure, you can insist that$\aleph_0$and$\omega$are both designated by the same set, therefore you can talk about the$\aleph_0$th ordinal being$\omega$. But it is much better to separate in your mind the two notions of cardinals and ordinals, at least until you have a better grasp of the two. • That ended up longer than I expected, and it took longer than I thought it would take. – Asaf Karagila Jul 17 '16 at 5:21 • It's heartening to see the amount of time you guys invest in your responses (without expecting so much as a penny in return). I'll better put some time in refreshing myself with some basic set theory stuff, like symbolic representations and perhaps take some "crash courses" on some must-know set theory principles before I can expect to be able to fully comprehend set theory ordinals. And thank you so much your detailed response. I'll take my time contemplating the same and get back for any further queries. – Hemnath Prabagaran Jul 17 '16 at 6:57 • The idea, in a nutshell, is that ordinals is an abstract representation of a length of a queue. Preferably to the bathroom. The queue gets longer when you add someone at the end; but it might not be longer if someone cuts in line. This gives rise to a natural structure of ordinals. Then we implement them with some technical construction via canonical sets. But the sets don't matter. It's the idea that matters. – Asaf Karagila Jul 17 '16 at 9:28 • On reading your answer, I'm curious about a few things: (1) How did von Neumann discover his definition? In my answer I constructed the ordinal representing a well-order via transfinite recursion on the well-order itself. But was that how von Neumann came up with it? (2) Is there a totally ordered notion of size that does not depend on the axiom of choice? (3) I'm not convinced by the "queue" analogy. To get a queue of length$ω$we already need a process of length$ω$. Even if we have that, to get a queue of length$ω_1$we need a process of length$ω_1$. We seem stuck at regular cardinals. – user21820 Jul 17 '16 at 12:25 • @user21820: It was part of his Ph.D. dissertation, how did he come up with it exactly I don't know. But it was probably related to the fact the axiom of regularity played an important role in his work, as did replacement. Any total order of the cardinals imply the axiom of choice, so I'm not sure what you could mean by this. And finally, the queue analogy is for an intuition. If you talk about any set you sort of assume it exists in the first place (in this context). So you can't escape the axioms and the proofs. But you can carry the intuition of what ordinals represent. – Asaf Karagila Jul 17 '16 at 12:39 You need to distinguish between the ordinal numbers and a particular representation in set theory, which is akin to the distinction between a number and a numeral in arithmetic. In arithmetic there is a number which is the result of applying the successor function twenty-five times to$0$. In base$10$we use the numeral$25$to represent this number. In base$2$we use the numeral$11001_2$to represent this number. For your point 1, the ordinals of set theory are intended to capture all we mean by first, second, third,$\dots$and then extend the concept in a well-defined way into the infinite. For point 2, the von Neumann ordinals are akin to numerals. They are a particular way of representing the ordinals which is rather convenient, but the important thing about the ordinals is the way they are related by the successor function and taking limits. Another way to represent$4$is$\{\{\{\{\emptyset\}\}\}\}$As we can make a bijection between this style and the one you cite, we can translate proofs between them if we want and use this version. It would be similar to writing proofs using base$9$. The proofs would work fine, but others would find them harder to follow because we were using nonstandard notation. For point 3, yes, the cardinality of$\omega$is$\aleph_0$. The standard number line does not include$\omega$. It includes all the finite ordinals.$\omega$is then the limit of all those ordinals and in the von Neumann formulation is the union of all of them. • Your response is both quick and generous (honestly, I'm pleasantly surprised by the prompt responses in this page). I'll take my time comprehending your answer before I post any more doubts, if I'm allowed to trouble you again at no cost :) – Hemnath Prabagaran Jul 16 '16 at 6:11 1. A binary relation$R$on a set$S$is any subset of the Cartesian product$S\times S.$And We write$xRy$to mean$(x,y)\in R.$2. A well-order is a binary relation$R$on a set$S$such that whenever$\emptyset \ne U\subset S,$there is a unique$x\in U$such that$xRu$for all$u\in U\backslash \{x\}$. Exercise. A well-order$R$on a set is a linear order. 1. DEF'N. A set$S$is transitive iff every$x\in S$is a subset of$S.$2. DEF'N. A set$S$is an ordinal iff$S$is transitive and$\epsilon$(membership) is a well-order on$S.$(That is, the relation$R=\{x,y)\in S\times S :x\epsilon y\}$is a well-order.) 3. When a set is presented, described, or defined by brace brackets it means that its members are all, and only, those thing specified within the braces.It does not matter what order the things appear within the braces. 6.There are several ways to define a finite ordinal. One way is that an ordinal$S$is finite iff$\epsilon^*$is also a well-order on$S,$where$x\epsilon^*y \iff y\epsilon x.$1. One basic fact about ordinals is that if$S_1,S_2$are ordinals then exactly one of the following holds : (i)$S_1=S_2 $. (ii)$S_1\epsilon S_2 .$(iii)$S_2\epsilon S_1$..... It is customary to write$S_1<S_2$to mean$S_1\epsilon S_2$for ordinals$S_1,S_2$. Exercise . For ordinal$S,$define$S+1=s\cup \{s\}.$Show that if ordinal$T$satisfies$S<T$then$S+1=T$or$S+1<T.$1. The ordinal$\omega\$ is the set of all finite ordinals. It does not belong to the real-number line. ... I suggest a modern textbook on introductory set-theory.
• You should state that your definition is for von Neumann ordinals. See Ross' answer for the distinction between the interface and implementation. – user21820 Jul 16 '16 at 5:48
• Also, I'm doubtful that your answer addresses the question, since it implicitly asks for an intuitive explanation, not a symbolic definition. – user21820 Jul 16 '16 at 5:50
• True. I'm expecting a layman explanation. I'm sorry that I'm not one for symbolic language. – Hemnath Prabagaran Jul 16 '16 at 6:07
• I really have no idea how to give an intuitive definition . An intutive motivational essay,perhaps, but not a definition. – DanielWainfleet Jul 16 '16 at 14:48
• That's alright. You took the time to respond to my query, and I appreciate that. – Hemnath Prabagaran Jul 17 '16 at 0:34