Category Archives: Math

Prev TOC Next

In post 13 I sketched proof by transfinite induction, and definition by transfinite recursion. Let’s take a closer look at that. By definition, < means ∈ for ordinals—treat that also as vernacular. Sometimes one symbol or the other makes the meaning clearer. We must keep in mind though that we have not shown that < is a well-ordering on Ω, or even a simple ordering.

Let Ω(x) be the formula for “x is an ordinal”, thus:

The first line says x is transitive, the next four lines say that < simply-orders x, and the last line says that < is a well-ordering on x. (Quite a bit of vernacular, but by now you should know how to deal with “u∈v∈x’’, for example.)

The clauses are not as economical as possible: for example, Foundation implies the third and last line, and a transitive irreflexive relation is automatically asymmetric, so even without Foundation we don’t need the fourth line. For the moment, we proceed without using Foundation.

Within an ordinal, ∈ well-orders; we want to bootstrap this to all of Ω. First an easy observation. Given a formula φ(x), if any β∈α satisfy φ, then there is a least such β. We need only invoke Separation to provide us with the set of all β∈α satisfying φ, and then appeal to the last clause in the definition of an ordinal.

How about smallest elements over all of Ω? That is,

∃αφ(α)→∃α(φ(α) ∧ ∀β(¬(β<α∧φ(β))))

(By vernacular convention, α and β are ordinals. Formally one begins “∃x(Ω(x)∧φ(x))…’’.)

Suppose ∃γφ(γ). If none of γ’s predecessors satisfy φ, then we’re done. Otherwise suppose φ(α) with α∈γ. Because γ is well-ordered, there is is an element of γ—let’s still call it α—such that α is the smallest element of the set {β∈γ:φ(β)}. We need to know that there are no ordinals, period, that satisfy φ and precede α. But if β was such an ordinal, we’d have β∈α∈γ. Since γ is transitive, we’d have β∈γ, and we’ve already ruled that out.

The contrapositive is transfinite induction. Letting ψ be ¬φ,

∀α((∀β<α)ψ(β)→ψ(α)) → ∀αψ(α)

With transfinite induction, we can show that Ω is simply-ordered. Only trichotomy presents any wrinkles. We induct on the property, “α is comparable with every ordinal.” Suppose this is true for all β<α. Let γ be an arbitrary ordinal. If γ<β or γ=β for some β∈α, then γ<α, since α is transitive (and < means ∈). Suppose then that β∈γ for all β∈α. That is, α⊆γ. If α=γ, we’re done. Suppose α⊂γ. Let δ be the smallest element of γ∖α. We will now show that α=δ, proving α∈γ, i.e., α<γ.

The key point: both α and δ are subsets of γ, and within γ, ∈ is a simple ordering. Extensionality kicks in: we have to prove x∈α↔x∈δ, or turned around, x∉δ↔x∉α. Now, α is an initial segment of γ because α is transitive. Therefore δ>x for all x∈α because δ∉α. So x∉δ implies x≥δ implies x∉α. On the other hand, x∉α implies x>y for all y∈α, again because α is an initial segment. Since δ is the least element of γ∖α, it follows that x≥δ, i.e., ¬x<δ, i.e., x∉δ. We’re done.

So < is a well-ordering on Ω, and we can trust our intuition about it (mostly).

Next consider transfinite recursion. The discussion in post 13 applies, with a few remarks. As before, we have a “rule” ρ(α,f,s) that assigns a value s to an ordinal α given as input a function f:α→···. Our rule is a formula, and may even include parameters. Thus: ρ(α,f,s,p̄).

Suppose that for the parameter values p̄=c̄ this formula is “function-like”; then we’re in business. One proves in ZF that the following condition

∀α,f  ∃s  ρ(α,f,s,c̄)
∧ ∀α,f,s,t (ρ(α,f,s,c̄)∧ρ(α,f,t,c̄)→s=t)

implies, for all α, the existence of a unique function g_α:α+1→··· “obeying the recursion”. The proof uses transfinite induction, of course; also the set-existence axioms, especially Replacement. I won’t comb out all the hair, but essentially: if we have an “obedient” g_β for all β<α, Replacement plus Union plus the uniqueness allow you to combine all these g_β’s into one f_α with domain α. Then you use ρ to assign a value to α, extending f_α to g_α.

The conclusion, even leavened with vernacular, is more than I’m prepared to write. But you get a theorem—technically, a different theorem for each formula ρ. (So it’s a theorem schema.) It has the form ∀p̄(A→B), where A is the above condition and B asserts the existence of g.

We don’t need to prove that the condition holds; rather, the theorem says that whenever it holds (perhaps only for some values of the parameters), then the conclusion holds. The proof does not require Choice: the ordinals are already well-ordered. As before, we also have a formula G(α,c̄,s); if the condition holds for some c, then G(α,c̄,s) assigns a unique s to every ordinal—a “function-like” thingy with “domain” Ω.

As a bonus, we can rehabilitate Cantor’s “proof” of the Well-Ordering Theorem. Let M be a set, and let c be a choice function for M. Our rule ρ says that the s assigned to α is c(M∖{f(β):β<α}), provided that the difference set is not empty. Otherwise we assign M to α. (We choose M simply because it is not an element of M.) We define G by transfinite recursion; informally, we can write Ĝ(α) for the value assigned to α. (I have left the parameters M and c̄ implicit.) If we never have Ĝ(α)=M, that means that G defines an injection of Ω into M, and inverting this gives us a map from M onto Ω. Replacement then says that Ω is a set. The Largest Ordinal paradox however proves this is not so. (The formal statement: ¬∃S ∀x(Ω(x)↔x∈S).) Therefore for some α, g_α maps α+1 1–1 onto M, and we’ve well-ordered M.

I’ve made a full meal of this argument. Typically, one would condense this discussion into a couple of sentences: “Given a choice function c, use it to define (by transfinite recursion) an injective function from an initial segment of Ω into M. As this function cannot be defined for all ordinals, it must map the ordinals less than some α onto M, and so M is well-orderable.”

While this proof resembles Cantor’s demonstration, it borrows essential features from Zermelo’s. Gone are the successive choices with their psychological aspect, replaced with a choice function. And the “union of partial well-orderings” in Zermelo’s 1904 proof lies buried inside the transfinite recursion.

Prev TOC Next

Prev TOC Next

The Axioms of ZFC

The language of ZF (ℒ(ZF)) consists of basic first-order syntax, with a single binary predicate symbol ∈. Here is a list of the axioms, with a tag-line (an imprecise description) for each.

Extensionality:

Every set is determined by its elements.

Foundation:

All sets are built up in levels by starting with the empty set.

Pairs:

There is a set whose elements are any two given sets. (Or any one set.)

Union:

For every set, there is a set consisting of the union of its elements.

Power Set:

For every set, there is a set consisting of all its subsets.

Infinity:

There is an infinite set.

Replacement:

Given a set and a rule for replacing its elements, there is a set consisting of all these replacements.

Choice:

Given a set of pairwise disjoint nonempty sets, there is a set containing exactly one element from each of them.

Two more axioms:

Null Set:

There is a set with no elements.

Separation:

Given a set and a property, there is a set consisting of all the elements satisfying the property.

These are redundant. The version of Replacement we adopt implies Separation; Null Set follows from Pairs plus Separation. But they are historically important, and help understand ZFC.

Now for the formal, or at least more formal, statements. (I discussed “vernacular” in post 15. Recall that t̄ stands for stands for a list (t₁,…,t_n).)

Extensionality:

∀z(z∈x↔z∈y)→x=y

Using the defined symbol ⊆ (defined as ∀z(z∈x→z∈y)), we could also write this as “x⊆y∧y⊆x→x=y’’.

Foundation:

∀x(∃y∈x)(y∩x=∅)

Of course, ∩ and ∅ are defined terms, and (∃y∈x) is vernacular. Here is Foundation without using them:

∀x∃y(y∈x∧∀u(¬(u∈x∧u∈y)))

People sometimes call this Regularity. Foundation says there is an ∈-minimal element of x, that is, a y∈x none of whose elements belong to x. If that were false, we’d have an infinite descending chain x∋y₁∋y₂∋…. (Possibly it could end in a loop, i.e., y_m=y_n for some m<n.) But such an x is not “built up from ∅’’.

Foundation has an equivalent statement: There are no infinite descending ∈-chains. To prove this equivalence, you need Choice. The version above (due to von Neumann) avoids this issue, and is simpler to express.

Pairs:

∀x ∀y ∃z(z={x,y})

or without the defined term {x,y}:

∀x ∀y ∃z∀u(u∈z ↔(u=x∨u=y))

Since x=y is not excluded, this also covers singletons.

Null Set:

∃x∀y(¬y∈x)

Union:

∀x ∃u(u=⋃_y∈xy)

or without the defined term ⋃

∀x ∃u ∀z(z∈u ↔∃y(z∈y∧y∈x))

In other words, the elements of the union are the elements of the elements of the original set.

Power Set:

∀x∃p∀s(s∈p↔s⊆x)

Or in other words, p={s : s⊆x}, just the kind of set-builder definition that was uncritically accepted before the paradoxes. The power set of x is denoted 𝒫(x). Without the defined term s⊆x:

∀x∃p∀s(s∈p↔∀y(y∈s →y∈x))

Infinity:

∃w(∅∈w∧∀x(x∈w→x∪{x}∈w))

We mentioned earlier the von Neumann representation for natural numbers: 0={∅}, 1={0}, 2={0,1}, etc. This axiom insures the existence of a set containing all the von Neumann natural numbers. I leave the vernacular-free expression of Infinity as an exercise for the fastidious.

Separation (sometimes called Subset) isn’t a single axiom, but an axiom schema. We have an instance of the schema for each formula φ(y,t̄). For any set x and any choice of values c̄ for t̄, the instance says there is a set of all elements y of x satisfying φ(y,c̄).

Separation:

∀t̄ ∀x ∃s∀y(y∈s↔y∈x∧φ(y,t̄))

Separation justifies the use of the set-builder notation s={y∈x:φ(y,t̄)}.

Replacement (sometimes called Substitution) is also an axiom schema, with an instance for each formula φ(y,z,t̄). Suppose for some particular choice t̄=c̄, the formula φ(y,z,t̄) defines z as a partial function φ° of y: Given y, there is at most one z making φ(y,z,c̄) true. Then the range of φ° on any set x is a set.
Replacement:

∀t̄∀x(∀y ∃_≤1z φ(y,z,t̄) →∃w(w={φ°(y):y∈x}))

But the set-builder term is not justifiable by Separation. Eliminating it gives:

And we can eliminate ∃_≤1z and ∃y∈x. We replace ∃_≤1z with this:

∀u∀v(φ(y,u,t̄)∧φ(y,v,t̄)→u=v)

and (∃y∈x)φ(y,z,t̄) with

∃y(y∈x ∧φ(y,z,t̄))

This version of Replacement demands only that φ° be a partial function, not necessarily total. You can derive Separation from it. If φ(y,t̄) is the separating property, then let ψ(y,z,t̄) (for a particular t̄=c̄) define the partial function ψ°(y)=y when φ(y,c̄) is true, and undefined when φ(y,c̄) is false. Then applying ψ° to x gives the subset we want. Some authors use the “total” version of Replacement, and include Separation in their list of axioms.

Choice (AC) was the scene for major philosophical combat early in the 20th century, as we’ve seen. It’s easier to express than Replacement.

Choice:

Eliminating some vernacular should be routine by now: y≠∅, y∩z=∅. As for #(c∩y)=1, this becomes

∃u(u∈c∩y∧∀v(v∈c∩y→v=u))

where of course u∈c∩y is formally u∈c∧u∈y, likewise for v.

Another version of Choice does not require disjointness. It’s easy to express formally once you have the machinery of ordered pairs, and thus functions as sets of ordered pairs. It says: for every set x whose elements are all nonempty sets, there is a so-called choice function c such that c(y)∈y for all y∈x.

Unlike every other “set existence” axiom of ZFC, we can’t define c with set-builder notation, or indeed give any other explicit description of the choice function. We’ve seen how this lead to much distrust of AC. In 1938, Gödel showed if ZF is consistent, then ZFC is too. That calmed things down somewhat. I’ve cited Moore’s book before on the history of the Axiom of Choice.

Prev TOC Next

Prev TOC Next

The Role of Formal Logic

In Zermelo’s original system, the Separation Axiom refers to a “definite property”. The Replacement Axiom refers to a “rule”. In 1922, Skolem proposed interpreting “definite” as “first-order definable”. So properties and rules are just formulas in the language of ZF, ℒ(ZF). With this clarification, ZFC assumes its modern form as a first-order theory.

ZF boasts a spartan vocabulary: just ∈ plus the basic symbols of first-order logic. Writing things out formally, with no abbreviations or short-cuts, rapidly snows us under unreadable expressions. We handle this (like everyone else) with semi-formal expressions; I like to call these “vernacular”. Copious hand-waving suggests how a masochist could write these out in the formal language ℒ(ZF).

Example: here’s how we say p=〈x,y〉={{x},{x,y}}, partially expanded:

∃a,b(p={a,b}∧a={x}∧b={x,y})

“∃a,b’’ is vernacular for “∃a∃b’’. Next we expand p={a,b} into

∀u(u∈p↔(u=a∨u=b))

and likewise for a={x} and b={x,y}.

A relation r is a set of ordered pairs, so more formally

(∀p∈r)∃a,b(p=(a,b))

which still has some vernacular. (∀p∈r)… more formally is ∀p(p∈r→…). Likewise, (∃x∈z)… in formal dress is ∃x(x∈z∧…).

To say f is a function with domain D, we start with the vernacular

f is a relation
∧ (∀(a,b)∈f)a∈D
∧ (∀a∈D) ∃!b((a,b)∈f)

“∀(a,b)∈f’’ expands to “(∀p∈f)∀a,b(p=(a,b)→…)’’. ∃!bφ(b), “exists a unique b satisfying φ’’, expands to ∃bφ(b)∧∀b,c(φ(b)∧φ(c)→b=c).

The vernacular f(x)=y becomes 〈x,y〉∈f. These should be enough to give you the flavor.

Often we have lists of variables, like x₁,…x_n. We write x̄ to reduce clutter; ∀x̄ and ∃x̄ have the obvious meanings.

When we get to the formal versions of Separation and Replacement, we’ll see how “property” and “rule” are made precise.

Coda

We’ve seen the informal use of “class” in ZF. This proved so convenient that NBG, a theory developed in succession by von Neumann, Bernays, and Gödel, gave a home to it. It turns out that NBG is a so-called conservative extension of ZFC: any formula of NBG that “talks only about sets” is provable in NBG iff it is provable in ZF.

In NBG, we still have only the symbol ∈ plus the basic logical symbols. However, certain members of the “universe” have the left-hand side of ∈ barred to them. If x∈y, then we say x is a set; anything that’s not a set is a proper class. So proper classes can have sets as elements, but cannot themselves be elements. The term class encompasses both sets and proper classes; in NBG, the variables range over classes.

Here’s how NBG skirts around Russell’s paradox. We can still write the formal expression R={x:x∉x}. This defines the class R, which is the class of all sets that are not elements of themselves. Is R∈R? No, because if it were, it would have to be a set that was not an element of itself. OK, if R∉R, doesn’t that mean that R satisfies the condition to be an element of R? No, not if R is a proper class—R contains only sets, no proper classes allowed!

Zermelo’s original system did not include Replacement and Foundation, although it did include Choice. Somewhat ahistorically, people use Z to refer to ZF minus Replacement, but including Separation. ZC is Z plus Choice.

ZF is a theory of “pure sets”. ZFA is “ZF with atoms”. An atom is an object that is not the null set but has no elements. The axioms of ZF can be modified to allow for this. Before the invention of forcing, Mostowski used ZFA to investigate theories without Choice.

Prev TOC Next

Prev TOC Next

Replacement and Foundation

Thirteen years after Zermelo published his axioms, Fraenkel pointed out that they weren’t quite strong enough. For example, you couldn’t prove the existence of the set ⋃_n∈ω𝒫ⁿ(0).

Fraenkel suggest the Axiom of Replacement (aka Substitution): If we have a way of “associating” with every element m of a set M a set X_m, then {X_m:m∈M} is a set. In other words, if you go through a set, replacing each element with another set, you get a set. The intuition: {X_m:m∈M} is “no bigger” than M, and so ought to be a set also.

Combined with Axiom of Unions, this is the gateway to big sets. Replacement gives us {𝒫ⁿ(0):n∈ω}, and then Union gives us Fraenkel’s set.

Zermelo agreed with Fraenkel for this addition to the axioms. Skolem also pointed out the need.

Using transfinite recursion, we now define the Cumulative Hierarchy:

Fraenkel’s set is V_ω.

(Two variations: it turns out that “V_α∪’’ isn’t neeeded in the second line, you get the same sets with “V_α+1=𝒫(V_α)’’. Some authors modify the definition so that their V_λ is the same as our V_λ+1.)

Power Set plus Replacement plus Union shows that all the V_α are sets. The rank of a set is where it first appears in the cumulative hierarchy, or more precisely: rk(X) is the least α with X∈V_α+1. The “+1’’ is so that α has rank α.

How do we know that every set appears somewhere in the cumulative hierarchy? That brings us to our second additional axiom: Foundation.

Skolem noticed the need to exclude “pathological” sets, such as A={A} or infinite descending chains A₁∋A₂∋…. Such sets will never appear in any of the V_α’s. The Foundation Axiom does the trick.

von Neumann gave the most elegant version of Foundation: Every nonempty set contains an element disjoint from it. That is, for any set A, there is an a∈A with a∩A=∅. This a is minimal in the ∈ ordering of the elements of M. That’s another way to phrase it: Every nonempty set A has a minimal element in its ∈-ordering.

Foundation is equivalent to every set having a rank. Writing this the classy way, V=⋃_α∈ΩV_α. The proof of this takes a few steps; I’ll save it for the end of this post.

For so-called “ordinary mathematics”, you usually don’t need to go any higher than rank ω2. Example: the complex Hilbert space L²(ℝ³), beloved by analysts and physicists alike. We build up to this by contructing all the natural numbers, then the integers, rational numbers, and reals, ordered pairs and ordered triples of reals, then functions from the ordered triples to ordered pairs, and finally equivalence classes of these functions. (Recall that two L² functions are identified if they agree except for a set of measure zero; hence, the actual elements of L²(ℝ³) are equivalence classes.) We have all the natural numbers by the time we get to V_ω. If x,y∈V_α, then the ordered pair 〈x,y〉∈V_α+2. So if A∈V_α, then any subset of A×A is in V_α+3. Integers are often defined as sets of ordered pairs of natural numbers, rational numbers as sets of ordered pairs of integers, and real numbers as sets of rational numbers (Dedekind cuts). If I counted right, that puts all the elements of ℝ in V_ω+7 and any subset of ℝ in V_ω+8. The Hilbert space in question should belong to V_ω+15, again if I haven’t miscounted.

Although sets of high rank aren’t “needed” by most mathematicians, it would be quite strange to impose a “rank ceiling” limitation on the power set axiom. Just maybe if V_ω+1 were adequate—but it isn’t.

Without Choice, we cannot use von Neumann’s definition of card(M) as the least ordinal equivalent to M. An alternative is Scott’s trick: card(M) is the set of all sets of least rank equivalent to M. In other words, S∈card(M) iff S≡M and for all T≡M, rk(T)≥rk(S). This lacks the simplicity of von Neumann’s definition, but it’s the best we’ve got. Scott’s trick can be used for other purposes, e.g., to define the order type of a simply-ordered set.

Okay, let’s look at the equivalence of Foundation with V=⋃_α∈ΩV_α. We’ll need some machinery: transitive closures, ∈-induction, and the suprenum of a set of ordinals.

Recall that a set A is transitive if b∈a∈A implies b∈A, i.e., a∈A implies a⊆A. Every set A is contained in a transitive set called its transitive closure, tc(A). First we set f(A)=⋃_a∈Aa. Then set tc(A)=⋃_n∈ωfⁿ(A), where f⁰(A)=A. The transitive closure is the smallest transitive set containing A: A⊆tc(A), and if A⊆B with B transitive, then tc(A)⊆B.

Suppose φ is a property where the following implication holds: If every element of A satisfies φ, then so does A. Then ∈-induction says that φ holds for all sets. Foundation justifies this. Suppose on the contrary that A is a non-φ set. Then some element of A is non-φ. Consider the subset S of tc(A) consisting of all non-φ elements. This is nonempty by hypothesis, so let s∈S be ∈-minimal in S. All the elements of s belong to tc(A) because tc(A) is transitive, so therefore all of s’s elements must satisfy φ (otherwise s wouldn’t be ∈-minimal). But then s must also satisfy φ, contradiction.

Lemma: If S is a set of ordinals, then ⋃_α∈Sα is an ordinal. This is a set by the Union Axiom. That S is simply-ordered under ∈ is easy as pie. Foundation makes the proof of the well-ordering property trivial, though it’s not hard to prove without it. For ordinals, α⊆β is equivalent to α≤β (we’ll prove this in a later post), so S is an upper bound to all its elements. As usual, we call the least uppper bound to S its suprenum, denoted sup S.

Now suppose X is a set, and we associate an ordinal α_x with each x∈X. Replacement says that {α_x:x∈X} is a set; we denote its suprenum by sup_x∈Xα_x.

Time to prove that every set has a rank. We use ∈-induction. Suppose all the elements of A have ranks. Set α=sup_a∈A(rk(a)+1). As a∈A belongs to V_rk(a)+1 and V_β⊆V_α whenever β≤α, all the elements of A belong to V_α. Therefore A belongs to V_α+1.

The reverse implication is straightforward, given this fact about rank: a∈b implies rk(a)<rk(b). (Proof: transfinite induction.) It follows that an element of A of lowest rank is ∈-minimal in A.

Prev TOC Next

Prev TOC Next

Zermelo’s 1908 system differs from ZFC in three respects. (1) ZFC is a “pure” set theory, without atoms. (2) ZFC includes two additional axioms, Replacement and Foundation. (3) ZFC is a first-order theory. Zermelo’s axioms are not formalized in this way. In this and the next two posts I will go into details.

Everything’s a Set!

In Zermelo’s original conception, we begin with a foundation of so-called atoms (aka urelements), things like the natural numbers. We then build up the universe by forming sets of atoms, sets of sets, etc. Later people realized that with various “coding tricks”, you don’t need any atoms. We’ve already encountered the von Neumann finite ordinals: 0=∅, 1={0}, 2={0,1}, etc. So these can serve for the natural numbers.

Zermelo had no ordered pairs. Kuratowski came up with this trick: define the ordered pair 〈x,y〉 to be the set {{x},{x,y}}. We can extract x and y from p=〈x,y〉={a,b} by noting that x is the only element of a∩b, and then y is the other element of a∪b, if a∪b has two elements. If a∪b has only one element, then of course y is that element. With Kuratowki’s ordered pairs on hand, we can deal with relations and functions without Zermelo’s awkward workarounds.

von Neumann defined ordinals by two properties. First:

A set X is transitive if b∈a∈X implies b∈X. Equivalently, if a∈X implies a⊆X.

Then:

An ordinal is a transitive set that is well-ordered under ∈.

We need transitivity, otherwise (for example) {5} would compete with {0} for the title of “1”.

I won’t go through the development of the ordinals in detail, but here are the first few steps. The precedessors of an ordinal are its elements: β<α iff β∈α. The successor of an ordinal α (denoted α⁺ in this post) is α∪{α}. If α is neither 0 nor a successor, it is a limit ordinal. By standard convention, λ always denotes a limit ordinal.

A finite ordinal (aka natural number) is defined as a non-limit ordinal (i.e., either a successor or 0), all of whose elements are also non-limit ordinals. If an ordinal is finite, so is its successor. The Axiom of Infinity says there is a set, say w, closed under α↦α⁺ and containing 0. Separation now says there is set, denoted ω, of all the finite ordinals in w. One proves that ω is the set of all finite ordinals.

Ω denotes the class of all ordinals. (Some authors use “On”.) Classes are not a formal part of ZFC, but we permit them as a “manner of speaking”. If φ(x) is a property of sets, we might talk about the class φ of all sets x satisfying φ(x), and write x∈φ to mean φ(x). For example, α∈Ω is just another way to say that α satisfies von Neumann’s two properties. We write V for the class of all sets, corresponding to the property x=x. Any set x is a class, corresponding to the property y∈x. A non-set class is called a proper class. After a fashion, proper classes are the descendents of Cantor’s “absolutely infinite multitudes”.

It is almost trivial to prove transfinite induction on Ω. Say φ(α) is a property of ordinals, and say we have this implication: If φ holds for all β<α, then it holds for α. Then φ holds for all ordinals. (Proof: If it doesn’t hold for α, then it doesn’t hold for some β<α. Since α is well-ordered, there is a least β<α for which it doesn’t hold. But then it holds for all γ<β, and hence for β.)

While Ω isn’t a well-ordered set, it shares enough properties to call it (informally) a well-ordered class. Namely, the ordinals are simply ordered: we will prove this in a later post. Any property φ of ordinals has a least ordinal satisfying it.

Definitions by transfinite recursion take a bit more fussing. I’ll leave the details to the textbooks, but basically: we have a “rule” determining a value s_α whenever we are given all the values s_β with β<α. How are we given all these values? By a function f_α with domain α, so f_α(β)=s_β for all β<α. The “rule” is a predicate with two free variables, say ρ(x,y); we want ρ(f_α,s_α) to hold. The rule ρ should be “function-like”, i.e., for every x there is a unique y such that ρ(x,y) holds. You drop the function f_α into the input hopper of ρ, and out pops a value s_α. (If you’re wondering how s₀ gets assigned, for α=0 the function is the empty function f₀=∅.)

Using transfinite induction, one can show that for every α∈Ω there is a unique function g_α with domain α⁺=α∪{α} that “obeys the recursion”. That is, for every β≤α, if f_β is the restriction of g_α to β, then ρ(f_β,g_α(β)). We say that we’ve defined g_α by transfinite recursion up to and including the ordinal α.

Thus we have a function g_α, with domain α⁺, for every ordinal α. For any β<α, g_β is the restriction of g_α to β′. We can’t formally define a function with domain Ω, but we do have a “function-like” predicate γ(x,y) with “domain” Ω: γ(α,s_α) holds if and only if g_α(α)=s_α.

Now that we have pairs, functions, and ordinals, we can populate our universe with all the usual flora and fauna. ℕ is the same as ω. The standard rigamarole then constructs integers, rationals, reals, Hilbert spaces,…

What about cardinalities? Frege and Russell both proposed “The cardinality of M is the set of all sets equivalent to M.” But a more elaborate version of Russell’s paradox kills this approach. Informally, we can talk about the class of all sets equivalent to M. We need to pick a representative from each such class.

von Neumann proposed: the first ordinal in the class. ℵ₀ is just ω. ℵ₁ is the first uncountable ordinal. 2^ℵ₀ is whichever ordinal is the first one with cardinality c. The cardinality of M is thus the unique smallest ordinal μ such that M is equivalent to μ.

All this assumes that for any M, there is an ordinal equivalent to it. That follows from the well-ordering theorem, which uses the Axiom of Choice. If AC isn’t around, then you need a different idea. We’ll see one later.

Prev TOC Next

Prev TOC Next

In 1908 Zermelo published his paper “Investigations in the foundations of set theory”. This contained the axiom system that eventually led to ZFC. Zermelo opens the paper with this rationale:

Set theory is that branch of mathematics whose task is to investigate mathematically the fundamental notions “number”, “order”, and “function” … At present, however, the very existence of this discipline seems to be threatened by certain contradictions, or “antinomies” [such as the Russell paradox]. …it no longer seems admissible today to assign to an arbitrary logically definable notion a “set”, or “class”, as its “extension”. Cantor’s original definition of a “set” as “a collection, gathered into a whole, of certain well-distinguished objects of our perception or our thought” therefore certainly requires some restriction … Under these circumstances there is at this point nothing left for us to do but to proceed in the opposite direction and, starting from “set theory” as it is historically given, to seek out the principles required for establishing the foundations of this mathematical discipline. In solving the problem we must, on the one hand, restrict these principles sufficiently to exclude all contradictions and, on the other, take them sufficiently wide to retain all that is valuable in this theory.¹

Zermelo’s motivation is pragmatic, unlike the philosophical approach of Russell and Whitehead’s Principia Mathematica.

Axiomatization was “in the air” at this time, with people throwing out various suggestions. Moore (p.151) offers some examples. Julius König proposed two axioms: (1) There are mental processes satisfying the formal laws of logic. (2) The continuum ℝ, treated as the totality of all sequences of natural numbers, does not lead to a contradiction. Schoenflies opted for the Trichotomy of Cardinals, and wanted to hold on to the Principle of Comprehension. Cantor sent a letter to Hilbert with some principles that look a lot like Zermelo’s axioms, but this letter didn’t come to light until decades later.

Zermelo’s article stands out as the first published proposal with a full set of axioms, demonstrating that it could save some of Cantor’s Paradise, and recognizing that the Principle of Comprehension was kaput.

Zermelo’s eschews philosophy:

The further, more philosophical, question about the origin of these principles and the extent to which they are valid will not be discussed here. I have not yet even been able to prove rigorously that my axioms are “consistent”, though this is certainly very essential…

The paper, he says, develops the theory of equivalence in a manner “that avoids the formal use of cardinal numbers.” He promises a second part, dealing with well-ordering, but this never appeared.

After the introduction, Zermelo begins:

1. Set theory is concerned with a “domain” 𝔅 of individuals, which we shall call simply “objects” and among which are the “sets”. …
2. Certain “fundamental relations” of the form aεb obtain between the objects of the domain 𝔅. …An object b may be called a set if and—with a single exception (Axiom II)—only if it contains another object, a, as an element. [I will use the modern ∈ in place of Zermelo’s ε from now on.]
3. [Definition of subset and disjoint]
4. A question or assertion 𝔈 is said to be “definite” if the fundamental relations of the domain, by means of the axioms and the universally valid laws of logic, determine without arbitrariness whether it holds or not. Likewise a “propositional function” 𝔈(x), in which the variable term x ranges over all individuals of a class 𝔎, is said to be “definite” if it is definite for each single individual x of the class 𝔎. Thus the question whether a∈b or not is always definite, as is the question whether M⊆N or not.

Note that item (1) allows for so-called urelements or atoms—things like integers. ZFC is a so-called “pure” set theory, without atoms.

Next come seven axioms, interlarded with extensive discussion.

Extensionality:

“Every set is determined by its elements.” In other words, if M⊆N and N⊆M, then M=N.

Elementary Sets:

The null set exists. Given any elements a and b of the domain, the sets {a} and {a,b} exist.

Separation:

To quote Zermelo: “Whenever the propositional function 𝔈(x) is definite for all elements of a set M, M possesses a subset M_𝔈 containing as elements precisely those elements x of M for which 𝔈(x) is true.”

Zermelo notes that “sets may never be independently defined by means of this axiom but must always be separated as subsets from sets already given”, and that this prevents the Russell paradox and the like. Indeed, the Russell paradox is turned into a theorem: for any set M there is a subset M₀ such that M₀∉M. He also notes that “definiteness” precludes some semantic paradoxes, e.g., Richard’s paradox (see post 5).

Zermelo shows that Separation implies the existence of set differences M∖M₁ (denoted M−M₁) and intersections M∩N (denoted [M,N]), and even ⋂_X∈TX for a set of sets (which he denotes 𝔇T, for “Durchschnitt”).

Power Set:

For any set T, there is a set whose elements are precisely all of T’s subsets. He denotes the power set of T by 𝔘T (for “Untermengen”).

Union:

For any set T, there is a set whose elements are precisely the elements of the elements of T. In modern notation, ⋃_X∈TX. Denoted 𝔖T, for “Summe”. He writes M+N for our M∪N.

Choice:

Given any set T of mutually disjoint nonempty sets, the union ⋃_X∈TX contains a subset S such that S∩X is a singleton for each X∈T.

Zermelo adds, “We can also express this axiom by saying that it is always possible to choose a single element from each element M,N,R,… of T and to combine all the chosen elements, m,n,r,…, into a set” S.

The set of all S’s satisfying this condition (card(S∩X)=1 for all X∈T) Zermelo calls the product of the elements of T, denoted 𝔓T, or just MN for a pair of disjoint sets M and N.

Infinity:

There is a set Z containing the null set 0, and for each of its elements a, it also contains {a}.

This leads to the so-called “Zermelo finite ordinals”, 0, {0}, {{0}}, {{{0}}}, etc. Z contains all these, and using Separation, we can assume Z contains exactly these. The Zermelo finite ordinals have two drawbacks: (1) They don’t extend naturally into the infinite ordinals; (2) Each of them, except 0, contains exactly one element. The von Neumann ordinals removed both of these blemishes.

The rest of the paper develops the theory of equivalence from the axioms. I noted that Zermelo allows atoms. On the other hand, he does not have ordered pairs, and thus neither relations nor functions. This lack calls for some gymnastics. When M and N are disjoint, the set of all unordered pairs MN={{m,n}:m∈M, n∈N} substitutes for our M×N.

To define equivalence between sets M and N, he assumes first that M and N are disjoint. Using MN instead of M×N, he can define “bijection between M and N’’. If one exists, then M and N are “immediately equivalent”. Dropping the disjointness condition, he says M and N are “mediately equivalent” if there exists a third set that is disjoint from both and “immediately equivalent” to both. It takes a couple of pages to show that this definition makes sense.

Zermelo proves the Equivalence Theorem, that is the “(Cantor-Dedekind-Schröder)-Bernstein Theorem”. (A couple of decades later, he discovered that Dedekind had basically the same proof.) He gives detailed proofs of the basic facts about equivalence. He defines “M has lower cardinality than N’’ in the usual fashion (M injects into N but not vice versa) but avoids defining “cardinal number”, as he promised in the introduction. The paper crescendoes in a proof of J. König’s inequality, a generalization of Cantor’s 𝔪<2^𝔪. Expressed using cardinal numbers, this says that if 𝔪_k<𝔫_k for all k in some index set K, then ∑_k𝔪_k<∏_k𝔫_k. Zermelo, of course, phrases this without mentioning cardinal numbers.

Zermelo spills a fair amount of ink on the question of “definiteness”. He initially claims that a∈b and M⊆N are definite questions, as we’ve seen. When defining 𝔇T, he notes that for any object a, the set T_a={X∈T: a∈X} exists by Separation (because a∈X is definite). But the question whether T_a=T is also definite. So using Separation again, 𝔇T={a∈A: T_a=T}, where A is any element of T. A similar discussion accompanies his definition of “immediately equivalent” showing that it is definite whether a given subset of MN defines a bijection.

Nonetheless, a certain nimbus of indefiniteness surrounds Zermelo’s “definite”. Twenty-one years later, Zermelo published a paper, “On the concept of definiteness in axiomatics”. By this time, people had suggested replacing “definite” with “definable in first-order logic”. Zermelo did not accept this, and his proposal had no influence on ZFC.

[1] Despite this clear statement from Zermelo, Moore argues that “his axiomatization was primarily motivated by a desire to secure his demonstration of the Well-Ordering Theorem and, in particular, to save his Axiom of Choice” (Moore (p.159)). He notes that Zermelo composed the two 1908 papers—the axiomatization, and the second well-ordering proof—together, and that “there are numerous internal links connecting the two papers” (Moore). Zermelo’s biographer takes an intermediate view: “Above all, however, one has to take into consideration how deeply Zermelo’s axiomatic work was entwined with Hilbert’s programme of axiomatization and the influence of the programme’s ‘philosophical turn’ which was triggered by the publication of the paradoxes in 1903” (Ebbinghaus (p.81)).

Prev TOC Next