29 April, 2005

Infinite numbers

This is a follow-up for those who asked questions about infinite numbers on the previous mathematical post. The following discussion is based on pages 52-61 of Azriel Levy's Set Theory, and agrees substantially with my (vague) memories of Jech's Set Theory (the text from which I studied set theory 10 years ago).

Modern set theory was born from a serious crisis in mathematics: the realization that we didn't really understand the details of the most fundamental objects in mathematics: numbers, sets, etc. I'm not a historian of mathematics, but I know enough to say that this crisis was probably influenced by the discovery of non-Euclidean geometries during the 19th century and the subsequent attempt at a formalization of mathematics by David Hilbert at the beginning of the 20th.

The problem is a very basic one: how do we define numbers as "simply" as possible? The result may not seem simple, but from a mathematical and logical perspective, it is.

Here we will concern ourselves with ordinal numbers. I won't discuss cardinal numbers, but I can if anyone wants.

We will define numbers as a special kind of set. Here you have to know what a set is in mathematics: a collection of objects. This definition actually leads to curious problems (does the set of all sets have itself as a member?) but it turns out that any beginning leads, sooner or later, to curious problems: the axiom of choice, the infinite sphere of finite radius, etc. That's the fun (if you can call it that) of set theory.

First concept: we say that a set X is ordinal if:

  • it is transitive, which is to say:
    • for every A that is a member of X, and
    • for every B that is a member of A,
    • B is also a member of X.
  • it is well-ordered by ∈ ("is an member of"), which is to say:
    • if x∈X and y∈X, either x∈y or y∈x;
    • there is a "smallest" element z∈X such that z∈x for any other x∈X.
Thus, if X={1,{2,3}}, X is not transitive (B=2 and A={2,3} do not satisfy the definition) while Y={1,2,{1,2}} is. However, Y is not ordinal because it is not well-ordered: both 1∈Y and 2∈Y, but 1∈2 and 2∈1 are both false.

The easiest ordinal to imagine is the empty set, ∅. This is the set that has no members, also written {}. Since ∅ has no members, it "vacuously" satisfies the rules for an ordinal.

The successor of an ordinal a is b={a∪{a}}. Notice that this satisfies both the transitive property and the requirement of well-ordering by ∈:
  • {a} is an element of b, and a is an element of both {a} and b, so b is transitive;
  • a∈{a}, so b is well-ordered by ∈.
Thus an ordinal's successor is also an ordinal. (I'm skipping some details for the sake of readability, but it works.)

Since we know that ∅ is an ordinal (which we ordinarily call 0), we can build an infinite number of ordinals by applying succession repeatedly:
  • 0: ∅
  • 1: {∅,{∅}}
  • 2: {∅,{∅},{∅,{∅}}}
  • ...
We can also define ordinary arithmetic using set operations on these sets, obtaining the results that you would expect to obtain but I won't go into those details.

What about the set of all these ordinals? Let ω={0,1,2,...}. Clearly ω has no largest member: for any member a of ω, we know that {a,{a}} is also a member of ω. Also, it isn't hard to see that ω is not the successor of any of the ordinals 0,1,2,.... It's a rather unique object, especially since ω also satisfies all the rules for an ordinal (proposition 3.17 in the text).

However: whereas all the other ordinals had a finite number of elements, ω is an infinite ordinal: it has an infinite number of elements. I haven't definite "finite" or "infinite", so we're "hand-waving" here; nevertheless, we can define it rigorously: an ordinal α is finite if α=∅ or if α is the successor of a finite ordinal. (Hence 0, 1, 2, ... are easily shown to be finite.)

Thus, an infinite ordinal is an ordinal that is not finite: it is neither ∅, nor the successor of a finite ordinal. Since ω is not the successor of any finite ordinal, &omega is an infinite ordinal.

Since our definition of numbers is that of ordinal numbers, "infinite numbers" exist — and, it turns out, there are infinitely many of them!

If you then talk about the size of these sets, you get cardinal numbers, and thus inifinite numbers of another sort. Either way, you have "infinite numbers".

No comments: