The Iterative Conception of Sets

Hello! Welcome to the first lesson in our module on the modern foundations of mathematics.

In the previous module, we surveyed the three major foundational programs of the early 20th century: Logicism, Formalism, and Intuitionism. We ended by exploring the practical implications of Intuitionism through constructive proofs. While these programs offered competing visions for mathematics, the framework that ultimately won the day as the standard working foundation is Zermelo-Fraenkel set theory, or ZFC.

Today, we will investigate the conceptual heart of this framework. Your learning outcome is to describe the iterative conception of the set-theoretic universe underlying ZFC. This is the intuitive picture of the world of sets that motivates the formal axioms of ZFC. For someone with your interest in the philosophy of mathematics, understanding this "ontology" is fundamental—it's the story mathematicians tell themselves about the objects they study.

1. The Paradise Lost: Naive Set Theory and its Contradiction

The most intuitive idea of a set is simply a collection of objects that share a certain property. This idea can be formalized as the General Comprehension Principle: for any property you can define, there exists a set of all and only those objects that have that property. This principle was central to the early work on logical foundations, particularly that of Gottlob Frege.

However, as attractive as this principle is, it leads directly to a contradiction. This was famously discovered by Bertrand Russell.

As the video explains, Russell considered the property of a set not being a member of itself. According to the General Comprehension Principle, there should be a set of all such sets. Let's call it $R$:
$R=\{x\mid x\text{ is a set and }x\notin x\}$
Russell then asked: is $R$ a member of itself?

• If $R\in R$, then by the definition of $R$, it must satisfy the property of not being a member of itself, so $R\notin R$. Contradiction.
• If $R\notin R$, then it satisfies the property for membership in $R$, so it should be a member of $R$, meaning $R\in R$. Contradiction.

Since we have $R\in R⟺R\notin R$, the existence of such a set $R$ is a logical impossibility. This demonstrated that the General Comprehension Principle is false, and it devastated Frege's project, which was built upon it. Mathematics needed a more robust, contradiction-free conception of what a set is.

2. The Iterative Conception of Set

The solution that emerged was to abandon the idea that sets are formed all at once by properties. Instead, sets are seen as being formed in a cumulative, hierarchical process of stages. This is the iterative conception of set.

The classic and most lucid explanation of this idea comes from the philosopher and logician George Boolos.

The key insight, as Boolos describes, is that a set can only be formed at a stage after all of its members have been formed at earlier stages.

This simple-sounding rule completely avoids Russell's paradox:

• For a set $x$ to be a member of itself ($x\in x$), it would have to be formed at a stage before it is formed. This is impossible.
• The Russell collection $R=\{x\mid x\notin x\}$ cannot be formed into a set. Why? Because its potential members (all non-self-membered sets) are being created at every stage of the hierarchy. There is no single stage where you can gather them all together to form a new set, because new ones are always appearing at later stages. The collection is "unbounded" in the hierarchy.

This iterative picture gives us a universe of sets that is well-founded and orderly.

3. Formalizing the Hierarchy: The Von Neumann Universe $V$

This informal story of "stages" can be made precise using the mathematical tool of transfinite recursion over the ordinals. This formal structure is called the cumulative hierarchy or the Von Neumann universe, denoted by $V$.

As explained in the video, the hierarchy is built as follows:

• Stage 0: Start with the empty set.
  $V_0=\varnothing$
• Successor Stage: To get to the next stage, take the power set of the previous stage (the set of all its subsets).
  $V_{\alpha +1}=\mathcal{P}(V_{\alpha })$
  So, $V_1=\mathcal{P}(V_0)=\{\varnothing \}$, $V_2=\mathcal{P}(V_1)=\{\varnothing ,\{\varnothing \}\}$, and so on.
• Limit Stage: At a limit ordinal (like $\omega$, the first infinite ordinal), take the union of all the stages that came before.
  $V_{\lambda }={\bigcup }_{\beta <\lambda }{V}_{\beta }$

The entire universe of sets, $V$, is the union of all these stages: $V={\bigcup }_{\alpha }{V}_{\alpha }$. A crucial theorem of ZFC states that every set exists at some stage $V_{\alpha }$.

This structure is beautifully captured in the following diagram:

4. How the Axioms of ZFC Embody this Conception

The real power of the iterative conception is that it provides a compelling, non-arbitrary justification for the axioms of ZFC. The axioms aren't just a random list designed to block paradoxes; they are principles that seem naturally true of this hierarchical universe.

Let's look at the axioms listed in these notes and see how they connect.

Here's how key axioms correspond to the iterative picture:

• Axiom of Foundation (or Regularity): This axiom states that every non-empty set $x$ contains an element $y$ such that $x$ and $y$ are disjoint ($x\cap y=\varnothing$). This directly formalizes the "well-founded" nature of the hierarchy, explicitly ruling out infinite descending membership chains ($...\in x_2\in x_1\in x_0$) and self-membership ($x\in x$), which were already forbidden by the informal story.
• Power Set Axiom: This is the "engine" of the hierarchy, guaranteeing that we can always form the next successor stage $V_{\alpha +1}$ from $V_{\alpha }$.
• Axiom of Union: This axiom allows us to collect together all the sets formed before a limit ordinal to create the limit stage $V_{\lambda }$.
• Axiom of Infinity: This ensures the process doesn't halt with the finite sets. It guarantees the existence of at least one infinite stage, $V_{\omega }$, which contains the set of natural numbers.
• Axiom of Separation: This is the safe replacement for the failed General Comprehension Principle. It says we can't form a set from an arbitrary property out of thin air. We must start with an existing set (which has already been formed at some stage) and then "separate" the elements within it that have a certain property.

Conclusion

Today we explored the intuitive and formal basis for ZFC, the standard foundation of modern mathematics. You've seen how a catastrophic failure in logic led to a powerful and elegant new vision of the mathematical universe.

Key takeaways from this lesson are:

• The intuitive General Comprehension Principle leads to Russell's Paradox, showing that not every property can define a set.
• The iterative conception resolves this by proposing that the universe of sets is built up in well-founded stages, where a set is formed only after its elements exist.
• This conceptual picture is formalized by the Von Neumann cumulative hierarchy ($V$), which is constructed using transfinite recursion with the power set and union operations.
• The axioms of ZFC are not an ad-hoc list but are justified as descriptions of the structure of this iterative universe.

Preview of the Next Lesson:
We've seen that most axioms of ZFC are strongly motivated by the iterative conception. However, one axiom stands apart: the Axiom of Choice. It doesn't seem to follow as directly from the iterative story, and its non-constructive nature has made it a subject of intense debate. In our next lesson, we will focus on this crucial axiom, aiming to explain its statement and give an example of its use.