What is the difference between an Ordinal number and a Cardinal number?

Question

I'm trying to understand the real difference between an Ordinal and a Cardinal, especially in relation with transfinite cardinals. The stuff on Wiki is a bit too complicated. Can anyone make it simple for me?

Answer 1

They are two different approaches towards understanding the notion of the infinite. (They can be used for finite quantities as well, but they coincide in that case, so it's a bit boring.) There are other approaches as well, but they tend to be derivative concepts of at least one of cardinality or ordinality.

These two concepts are different when it comes to infinite collections, and illustrates why it is important to consider what structures you wish to be recognised as different, so that those differences are preserved throughout your analysis, when you wish to consider concepts such as infinity in mathematics.

About cardinals and ordinals

Cardinals describe a notion of size. That is: how many of some type of object are there? In this respect, cardinals are a generalization of the whole numbers: 0, 1, 2, etc. They are an appropriate way to describe the size of a set. As Mozibur indicates, we do this by matching up elements of the set we wish to measure, with another set. (This is exactly what we do when we count: when you recite "one", "two", "three", "four", and so forth, you are giving each of the items you count a temporary name, matching an item with the name of a number to find out what cardinal describes the size of the set. For infinite sets, we also apply this idea of matching the elements of a set with those of a cardinal number.)

Ordinals describe a notion of sequence: not just size, but order. They describe a very specific kind of ordering, known as a well-order: the defining property of which is that for any collection of items, they can be put into a strict ordering, with one of them being the first. — Note that this property does not hold for all orderable sets: for example, there is no smallest real number in the interval (0,1], or among the negative integers {..., -3, -2, -1}; but well-orders are a very natural way to think of ordering discrete sets for many applications and tends to appeal to people's notion of ordering of events, with causes and effects.

If you order the finite whole numbers, what you get is a well-order. So, those who like to explore foundations of mathematics through set theory usually use the same construction to build both the finite ordinals and the finite cardinals. You may see some people describing cardinals by 1, 2, 3, ... and distinguishing them from ordinals by writing the ordinals as 1^st, 2^nd, 3^rd, etc.; however, the usual mathematical construction for both is to define

• 0 := ∅, that is the empty set;

• 1 := {0} = {∅} = 0 ∪ {0};

• 2 := {0,1} = {∅,{∅}} = 1 ∪ {1};

• 3 := {0,1,2} = 2 ∪ {2};

and so forth. For every ordinal α, we define α+1 := α ∪ {α}. Where cardinals express the size of a set, such as {a,b,c}, the ordinals describe the order type of a sequence, such as (a,b,c). This only becomes important when you have infinitely long sequences, however.

About the first several-infinite ordinals

To illustrate what the purpose of the ordinals are in the study of the infinite, first I have to introduce you to a few-infinite number of them.

We order the ordinals by saying that α < β if and only if α ∈ β. This is important when we start talking about infinite ordinals. The first infinite ordinal is what comes from considering the set of all of the finite ordinals. It describes a sequence of elements which are well-ordered, but which has no final element: (0,1,2,...). We call this ordinal ω. We then define the next largest ordinal by ω+1 := ω ∪ {ω}, as before: this describes an ordering (0,1,2,...,ω), where there are an infinite number of elements hiding in the ellipses, but where there is no "item that comes just before ω"; any consecutive collection of items which contains ω and some items which come before it must have infinitely many elements. This is just a result of the way that ω was defined. It's what is known as a limit ordinal: it comes at the end of an infinite sequence of elements which lead up to it, putting a cap on top of an infinite subsequence. We get other limit ordinals by piling infinitely many other ordinals on top of it: we have ω+2 := (ω+1) ∪ {ω+1}, and we can define ω+3, ω+4, etc. the same way until we can define

      2ω := {0,1,2,3...,ω,ω+1,ω+2,ω+3,...} = 0 ∪ 1 ∪ 2 ∪ ... ∪ ω ∪ (ω+1) ∪ (ω+2) ∪ ...

as being the collection of all of the ordinals up to ω, and then gotten from ω again by increments. Then we may define 2ω+1, 2ω+2, and so forth up to 3ω; and so forth ad infinitum. We then get another limit ordinal,

      ω² := 0 ∪ ω ∪ 2ω ∪ 3ω ∪ 4ω ∪ ...

in a similar way to how the limit ordinals ω, 2ω, and so forth are defined. (We would normally also include 1, 2, 3, ω+1, ω+2, 2ω+1, and so forth in the union; but I'm trying to just sketch the construction.) This would allow us ultimately to define ordinals such as ω²+3ω+7 by repeating the same process as before for the ordinals 2ω, 3ω, etc..

We then proceed to define 2ω² as the limit of all ordinals obtained by adding combinations of ω and finite integers to ω²; and then we may come to define 3ω² and 4ω²; and eventually we may come up with the idea of defining ω³ as the limit of all of the ordinals involving combinations of ω², ω, and finite integers. We may go about defining ω⁴, and ω⁵, until eventually after infinitely many iterations we are moved to define ω^ω, and ω^ω+1, ω^ω+2, ω^2ω, and the process never really stops.

What all of these ordinals are doing is capturing notions of ordering. Each new ordinal that we define extends the ones which came before.

The reason why this is important is that they aren't capturing any difference of size at all — after ω, all of the ordinals that I've described to you thus far have exactly the same number of elements, when we describe the size of a set by cardinality. The ordinal numbers are clearly capturing a lot of information about structure, in that there are many limit ordinals which only come after infinitely long sequences of successive iterations, e.g. as 8ω²+3ω comes only after the entire sequence 8ω²+2ω+1, 8ω²+2ω+2, 8ω²+2ω+3, ... but if you allow yourself to consider ways of matching up elements in a way which does not preserve the order of the elements, you can match the elements of all of these "polynomials" of ω with each other.

• For instance, you can match ω = {0,1,2,...} with ω+1 = {0,1,2,...,ω} by the matching 0 ⇒ ω, 1 ⇒ 0, 2 ⇒ 1, and so forth.

• You can match up the elements of ω² with those of ω by the formula aω+b ⇒ a+(a+b)(a+b+1)/2.

More complicated formulas allow you to produce a one-to-one matching of any of these first several infinite ordinals with ω; but at the same time they give a notion of size in which it feels as though they should be different from one another. That is, the ordinals provide a notion of additional structure. They describe many different ways in which the same number of elements can be put into different kinds of order, described by the structure of the limits within that ordering — the ways in which infinite stretches of increments cumulate to an element which caps off those increments.

What we mean by the size depends on what we want from structure

Infinities in mathematics are a notorious source of counter-intuitive results. The reason why is because our intuitions are built upon structure; and cardinality — the most primitive notion of the "size" of a collection — ignores many forms of structure which we consider important.

• Galileo revolted at the notion that the perimeter of a larger circle had the same number of points as that of a smaller circle. (He is also perhaps the first European to remark on the fact that infinte sets of integers can be brought into one-to-one correspondance with proper subsets.) His objection can ultimately be boiled down to the fact that he was interested in measure; where line-segments had lengths, and discrete items in a set added a finite (but non-negligeable) degree to the size of a set, whereas one-to-one correspondances do not preserve such notions of the measure of system or the additivity of parts. (The infamous Banach-Tarski paradox is an example of just such a result arising from the lack of preservation of the measure of subsystems.)

• Most people initially balk at the idea that there are as many points in the plane, as there are points on a line. (The one-to-one correspondance between the rational numbers and the integers, or between ω² and ω as described above, is of the same type.) This is because of an intuitive notion of dimension; the plane simply has more dimensions than the line, so that not only does the line fit into the plane, it does so infinitely many times. This geometric sort of information, however, is also something that a one-to-one matching does not have to respect.

This goes to show that when considering infinity — as well as many other sorts of mathematical concepts — what structure you consider important, that is what structure you require to be preserved by the transformations you wish to consider (such as matching from one set to another), will determine whether or not two objects are equivalent, or distinct. If you care about concepts such as dimension or measure, and demand that they be preserved by any functions you consider, then you can never bring a short line segment into one-to-one correspondance with a long one, or with a square. However, if you allow arbitrary functions, which may completely ignore the structural notions that you cherish, then you may obtain results which you find surprising, or even revolting to your intuition. This would ultimately be because there is a conflict between the ideas that you wish to consider, and the way in which you are considering it.

Answer 2

Actually, the difference cal already be seen for finite numbers, although they get really manifest only in the infinite numbers.

Cardinals are about the question "how many". For example, there are ten athletes at the competition. Ordinals are about the order. There's the winner, then there is the second one, then the third one, and so on.

Now for finite sets (like the ten athletes above), there is essentially only one way to arrange them (ignoring the selection who gets first etc.). However, as soon as we get infinite sets, this changes dramatically.

Consider the natural numbers. There's a certain amount of them, which is called ℵ₀ (spoken "aleph 0"). This amount of course doesn't depend on how we arrange them.

But now there are many substantially different ways to arrange them; indeed, even more such ways than there are natural numbers. However not all possible ways to arrange them correspond to an ordinal number; the ordinal numbers correspond to so-called well-orders, that is, orders where from any subset you can still say which one came first. This is for example not the case for the integers ordered by size; if you look at the negative numbers, there is no first one, as there's always one preceding it.

For the natural numbers, the most obvious well-ordering is the usual ordering: You can easily say e.g. what is the first prime number (2), the first common multiple of 12 and 15 (0 — that clearly comes before 60), the first number that has three digits in decimal notation (100), and so on.

The order of the natural numbers is called ω (spoken "omega").

Note that this is the same order type you get when you e.g. exchange each even number with the following odd number, that is,

1, 0, 2, 1, 3, 2, …

While the exact ordering is different, you can get the original back by just renaming the individual numbers to the one appropriate for its position. Therefore this ordering is also described by the ordinal number ω.

But now consider the alternative arrangement of the natural numbers where you first take all odd numbers, and then all even numbers. That is, your ordering now looks like

1, 3, 5, 7, …, 0, 2, 4, 6, …

This is substantially different from the usual ordering: While in the usual ordering, starting from 0 you can reach any specific natural number in a finite number of steps, now this is only true for the odd numbers; to reach an even number, you first have to go past the infinitely many even numbers, and then possibly a finite number of further steps. And you cannot remove that difference by renaming the numbers; the fact remains that there are numbers that are preceded by infinitely many other numbers.

However this is still a well order. You can still ask what is, in this order, about the first prime number (3), the first common multiple of 12 and 15 (still 0), and the first three-digit number (101).

This ordering is called ω+ω (because it's basically two copies of the natural number put besides each other; ordinal "+" basically means concatenation).

But you can also just move one element to the right, for example, just the 0, to get

1, 2, 3, 4, 5, …, 0

That is, you have the order of the natural numbers, and then one extra; this is described by the ordinal number ω+1.

And it is indeed again a well order, where now the first prime is 2, the first common multiple of 12 and 15 is 60 (because 0 comes way later, at the ω-th position), and the first three-digit number is 100.

Now you may ask what is 1+ω? Well, just put the 0 on the left of the 1,2,3, …, instead of the right. What do you get? Well, exactly the usual order of the natural numbers! So indeed, 1+ω = ω ≠ ω+1. So you have the unusual property that addition of ordinal numbers is not commutative.

Note that all those examples used the natural numbers, therefore all of them have the same number of elements, that is the same cardinality.

Answer 3

The difference is between matching (cardinality) and ordering (Ordinals):

Two sets such as {a,b,c} and {A,B,C} can be matched. The alphabetical ordering isn't important. Although you can count the elements in each set - they both have three - this isn't what should be done. First take any element from the first set, say 'b' and match it to one of the second set, say 'B'; carry on doing this until either set is empty (or both). If the first set is empty before the second then it is smaller in cardinality etc. In this sense matching is more fundamental than counting. In fact the cardinal of these two sets is 3. The reason why matching is more important than counting is that it can deal with infinite sets.

Ordinals refer to how you order a set. THe two sets above have the same alphabetical order, and have an ordinal also called 3.

The set {1,2,3,...} is usually called the greek lowercase omega, which i'll call w.

then {1,2,3,...;1,2}=w+2 and {1,2,3,...;1,2,3,...;1,2}=w+w+3=2w+3

The cardinals are sparsely populated amongst the ordinals. For example there are many orderings (ordinals) that refer to aleph-1 the first uncountable cardinal.