Author Archives: Michael Weiss

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

Prev TOC Next

“An Axiom, you know, is a thing that you accept without contradiction. For instance, if I were to say ‘Here we are!’ that would be accepted without any contradiction, and it’s a nice sort of remark to begin a conversation with. So it would be an Axiom. Or again, supposing I were to say, ‘Here we are not!’, that would be—”

“—a fib!” cried Bruno.

“that would be accepted, if people were civil”, continued the Professor; “so it would be another Axiom.”

“It might be an Axledum”, Bruno said: “but it wouldn’t be true!”

—Lewis Carroll, Sylvie and Bruno Concluded

To get to the “good stuff” in math, you almost always need some set theory. Zermelo-Fraenkel set theory (ZF), plus the axiom of choice (AC; ZF+AC=ZFC) has become the standard first-order axiom system for set theory.

Before diving into the details, some generalities on axiom systems. Nowadays we’re pretty chill about them; you can take any collection you like (hopefully consistent) for a theory, and then you can start writing your thesis. Not, perhaps, an interesting thesis, but at any rate Bruno won’t complain that your axioms aren’t true!

For the Greeks, the axioms and postulates were true, in some sense. Idealized, sure, but descriptive of reality. This tie began to fray with the discovery of non-Euclidean geometries. Algebraic axiom systems, like those for groups and for fields, appear by the end of the 19th century.

For roughly two thousand years after Euclid, most math developed without axioms. Take calculus as an example. You have the rules of calculus, but you don’t see anything like the Euclidean treatment of geometry. This remained true even as people subjected its foundations to stricter and stricter scrutiny. Mathematical intuition reigned supreme.

Hilbert’s Grundlagen der Geometrie (Foundations of Geometry, 1899) pushed towards a more formalist attitude. A celebrated quote of his, from years earlier, sums it up nicely:

One must be able to say at all times, instead of points, lines, and planes: tables, chairs, and beer mugs.

At times Cantor seemed to endorse this perspective:

Mathematics is entirely free in its development, and its concepts are only bound by the necessity of being consistent, and being related to the concepts introduced previously by means of precise definitions.

—Grundlagen einer allgemeinen Mannigfaltigkeitslehre (Foundations of a general theory of sets)

But he held strong opinions on what’s true in mathematics:

I entertain no doubts as to the truths of the tranfinites, which I recognized with God’s help and which, in their diversity, I have studied for more than twenty years; every year, and almost every day brings me further in this science.

—Letter from Cantor to Jeiler, quoted in Dauben (p.147).

On the other hand, he referred to the “Cholera-Bacillus of infinitesimals”, and called them “nothing but paper numbers!” (Dauben, p.131). The Continuum Hypothesis was for him a question of fact.

Two other themes run through this period: mathematics as a mental activity, and as logic.

Recall that Boole titled his famous treatise An Investigation of the Laws of Thought: on Which are Founded the Mathematical Theories of Logic and Probabilities. Cantor’s definition of “set” in his last major work reads

By a set we are to understand any collection into a whole M of definite and separate objects m of our intuition or our thought.

Here is the first sentence of Dedekind’s Was sind und sollen die Zahlen?: “In what follows I understand by thing every object of our thought.” His proof of the existence of an infinite set relies on this ontology:

Theorem: There exist infinite systems.

Proof: My own realm of thoughts, i.e., the totality S of all things which can be objects of my thought, is infinite. For if s signifies an element of S, then the thought s′, that s can be an element of my thought, is itself an element of S…

[Dedekind then appeals to his definition of infinite as having a bijection with a proper subset.]

Frege severely criticized this injection of psychology into mathematics. Cantor’s “proof” of the Well-Ordering Theorem suffers from it, as it consists of successively choosing elements of the set to be well-ordered. If we take this literally, then the choices must take place at an increasing sequence of times t₁<t₂<…. This limits us to ordinals that are “realizable in ℝ’’, and thus to countable ordinals (see post 4). Yet Cantor claimed that every set can be well-ordered, in particular ℝ.

This is why Zermelo was at pains to say in his second proof of the Well-Ordering Theorem, “…the ‘general principle of choice’ can be reduced to the following axiom, whose purely objective character is immediately evident.” (My emphasis.)

Both Frege and Russell held that the truths of mathematics are logical facts. Thus we find debates on whether Zermelo’s axiom of choice is logically valid. Not surprising, historically. Aristotle’s logic dealt with propositions. From “proposition” we obtain “propositional function”, that is, a proposition with a free variable, like “x is mortal”. It becomes a proposition if we assign a value to the variable (“Socrates is mortal”), or quantify over it (“All men are mortal”). The class of all things satisfying a propositional function went by the name, “extension of a concept”.

Zooming out from these specifics, logic and mathematics both lay claim to necessary truth. This is elaborated in Kantian philosophy. Kant classified mathematical facts as synthetic a priori: necessary truths that go beyond analytic truth, which are true by definition. Poincaré classified the Axiom of Choice as a synthetic a priori judgment, just like the principle of induction.

The rise of formal logic and axiomatic set theory resulted in a sharply drawn boundary between logic and set theory. We have the axioms and rules of inference of first-order logic; then we have the axioms of ZFC or similar systems, which are particular first-order theories. Things weren’t so clear at the dawn of the 20th century.

Prev TOC Next