Paradoxes and Competing Foundations

A successful mathematical construction does not establish that every superficially similar construction is legitimate. The previous note illustrated Cantor's formation of a diagonal subset inside an existing set. Around the turn of the twentieth century, closely related arguments exposed the danger of allowing unrestricted collections.

The resulting problems affected several foundational projects, but they did not all have the same source. Set-theoretic paradoxes concern principles for forming collections. Semantic paradoxes concern truth, reference, or definability. Frege's contradiction arose within a particular logical system involving value-ranges. Distinguishing these settings is necessary to understand the different repairs.

Unrestricted comprehension

Suppose that every condition $\varphi(x)$ determines a set consisting of exactly the objects satisfying it:

Choose the condition $x\notin x$. The proposed set is

Its defining property applies to every object, including $R$ itself. We therefore obtain

If $R\in R$, its defining condition implies $R\notin R$. If $R\notin R$, that same condition implies $R\in R$. The inconsistency follows from the unrestricted formation principle together with ordinary reasoning.

The problem is not that a peculiar set has been found and should be removed from an otherwise unchanged universe. The proposed principle itself authorizes an impossible object. A replacement must say which formations are legitimate and explain how enough mathematics remains available.

Russell discovered the contradiction in 1901 and communicated it to Frege in 1902. Related difficulties involving the totality of ordinals or the idea of a largest cardinal had already shown that unrestricted totalities required care. These discoveries formed an overlapping history rather than one isolated surprise.

Why the contradiction affected Frege

Frege's goal was to derive arithmetic from logical principles. His system distinguished concepts from objects, but also associated objects called extensions or value-ranges with functions and concepts.

For concepts, the content of Basic Law V can be presented schematically as

The law identifies extensions precisely when the corresponding concepts agree on every object. Together with the surrounding expressive and comprehension resources, it allows the construction behind Russell's contradiction.

It would therefore be inaccurate to say only that Frege assumed naive set theory. His formal organization and philosophical account differed. The relevant connection is that his system permitted a sufficiently unrestricted passage from concepts to extension objects.

The contradiction struck a foundational principle on which his derivation of arithmetic depended. Frege discussed the difficulty in an appendix to the second volume of Grundgesetze, whose publication was approaching when Russell's letter arrived. His attempted repair did not provide the intended successful foundation.

This episode also illustrates a distinction that persists throughout the series. The expressive innovations of Frege's logical language survived the failure of a principle adopted within his foundational project. A defective axiom does not make every technique used to state that axiom defective.

Russell's types and the vicious-circle concern

One response is to restrict which expressions can meaningfully apply to which objects. If individuals occupy one logical type and predicates of individuals another, applying a predicate to itself is not a well-formed operation.

In a simple typed setting, an expression

may be allowed because $P$ expects an argument of the type occupied by $a$. The expression $P(P)$ is rejected because $P$ does not have its own argument type.

Russell's historical theory went further. His ramified theory of types imposed levels associated with definitions and quantification, reflecting a concern about definitions that presuppose a totality to which the defined item would itself belong. This was an attempt to address a broader family of vicious circles.

The difficulty was that restrictive formation rules could obstruct ordinary mathematics. In Principia Mathematica, Whitehead and Russell used the axiom of reducibility to recover needed expressive resources. Roughly, it supplied suitably low-order predicates extensionally equivalent to predicates of higher order.

The axiom's role was technically important and philosophically controversial. If a foundation is intended to derive mathematics from principles that are purely logical, one must explain why an additional existence principle of this strength counts as logic.

Frank Ramsey's 1920s work distinguished different sources of paradox and helped clarify a route toward simpler type systems. Later simple type theory, including Church's 1940 formulation, should not be treated as a verbatim continuation of every commitment in Russell's ramified system.

Predicativity as a different restriction

Henri Poincaré criticized definitions that appeared to depend on an illegitimate circularity. A common way to introduce the issue is to consider a definition that quantifies over a totality containing the very object being defined.

For example, defining a set of natural numbers by a condition that quantifies over all sets of natural numbers raises a predicative question: is that totality already available independently of the definition?

Classical mathematicians may regard the definition as harmless because they assume a fixed domain of sets over which the quantifier ranges. A predicativist may require a construction or justification that does not presuppose that whole domain. The disagreement concerns the resources a definition may use.

Predicativity is therefore not simply the syntactic prohibition of self-membership. A set can fail to belong to itself while its definition still uses an impredicative quantifier. Conversely, the absence of a literal self-referential sentence does not remove every question about circular dependence.

Later work by Weyl, and subsequently by proof theorists including Feferman and Schütte, investigated the mathematical reach of predicative methods. Their results belong to a continuing program of measuring justified strength, rather than merely to the history of avoiding a single contradiction.

Zermelo: form subsets inside sets

Ernst Zermelo's 1908 axiomatization adopted a different strategy. It specified operations that produce sets and restricted comprehension to separation within an already given set.

For any set $A$, separation permits

The membership condition is

Apply this to $\varphi(x)\equiv x\notin x$:

There is no contradiction. Instead, we can prove that $R_A\notin A$. If $R_A\in A$, the defining biconditional would yield

The conclusion is that no set $A$ contains every set. The diagonal argument has become a theorem limiting sets rather than a derivation of inconsistency.

The separate note on separation examines this argument in more detail. Its essential point is that the initial set $A$ is part of the formation rule. Omitting that restriction recreates the original problem.

More than a list of prohibitions

Separation alone does not supply all the objects mathematics needs. Zermelo's system also included principles for elementary sets, unions, power sets, infinity, and choice, together with extensionality. Each contributes a positive construction or structural condition.

The axiom of choice had already played a prominent role in Zermelo's well-ordering theorem. It asserts a simultaneous selection from a family of nonempty sets, even when no explicit uniform rule for choosing the elements is supplied. Debate about it concerned mathematical existence and acceptable proof, not just avoidance of contradiction.

In 1922, Fraenkel and Skolem independently developed the replacement principle. In modern form, it says that the image of a set under a definable functional relation is a set. This makes possible constructions whose values need not lie inside a previously supplied bounding set.

The modern ZF axioms emerged through these and further developments. Foundation contributes a well-foundedness condition on membership. In the surrounding theory, it supports the cumulative-hierarchy account in which sets appear at successive stages. That account also uses ordinals, transfinite recursion, power sets, and replacement; Foundation alone is not its complete justification.

Modern ZFC is therefore a developed axiomatic theory, not simply Zermelo's original list with one additional letter. Its history includes changing formulations, expanding mathematical requirements, and continuing debate about the intended universe.

What a repair establishes

The different responses can now be compared more precisely.

Type restrictions control admissible applications and expressions. Predicative restrictions control the resources used in definitions. Axiomatic set theory controls which set constructions are licensed. Logicism is a broader ambition to explain mathematics through logic, and may employ a particular choice among these devices.

Preventing the derivation of Russell's contradiction does not prove that a system is consistent. There could be another contradiction produced by a different combination of principles. Nor does consistency, if established, automatically show that the system captures the intended mathematics.

The central question therefore changed. It was no longer enough to propose axioms that looked plausible and escaped known paradoxes. Mathematicians needed methods for investigating entire formal systems and the strength of their rules.

Hilbert's proof-theoretic program made that investigation explicit. The next note examines the attempt to justify powerful mathematics through a carefully controlled study of finite proofs.

Sources and further reading

• Frege's Grundgesetze der Arithmetik (1893, 1903), including the appendix to volume II, and the Frege–Russell correspondence of 1902.
• Bertrand Russell, “Mathematical Logic as Based on the Theory of Types” (1908); Whitehead and Russell, Principia Mathematica (1910–1913).
• Henri Poincaré, “Les mathématiques et la logique” (1905–1906); Frank Ramsey, “The Foundations of Mathematics” (1926).
• Ernst Zermelo, “Untersuchungen über die Grundlagen der Mengenlehre I” (1908); Abraham Fraenkel's and Thoralf Skolem's 1922 foundational papers.
• Zermelo's Axiomatization of Set Theory, for the formulation and context of the original axioms.