Author Archives: Michael Weiss

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:

(∀u,v)(u∈v∈x → u∈x)

∧(∀u,v∈x)(u<v ∨ v<u ∨ u=v)

∧(∀u∈x)(¬u<u)

∧(∀u,v∈x)(¬(u<v ∧ v<u))

∧(∀u,v,w∈x)(u<v<w → u<w)

∧(∀y⊆x)(y≠∅ → ∃u(u∈y ∧ ∀v(¬(v<u ∧ v∈y))))

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:

	∀t̄∀x[∀y∃≤1zφ(y,z,t̄)
	→∃w∀z(z∈w↔(∃y∈x)φ(y,z,t̄))]

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:

	∀x[(∀y∈x)y≠∅∧ (∀y∈x)(∀z∈x)(y≠z→y∩z=∅)
	→∃c(∀y∈x)#(c∩y)=1]

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:

V0	= ∅
Vα+1	= Vα∪𝒫(Vα)
Vλ	= ⋃α<λ Vα

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