Are Sets Buildable and Provable in First-Order Logic?

The Short Answer: Yes, But With Profound Limitations

Sets are indeed formalizable in first-order logic through axiomatic set theories like ZFC, but this foundation comes with deep limitations revealed by fundamental metamathematical results.

How Sets Are Built in First-Order Logic

Zermelo-Fraenkel Set Theory with Choice (ZFC)

ZFC is a first-order theory with one binary relation symbol ∈ (membership).

Language: {∈} (first-order logic with equality)
Domain: All sets
Intended interpretation: ∈ represents set membership

Basic Axioms

• Extensionality: Sets with same members are equal
• Empty Set: ∃x∀y(y ∉ x)
• Pairing: For any a,b, {a,b} exists
• Union: For any set A, ∪A exists
• Power Set: For any set A, 𝒫(A) exists

Construction Axioms

• Infinity: An infinite set exists
• Separation: {x∈A : φ(x)} exists for any formula φ
• Replacement: Image of a set under a definable function is a set
• Foundation: No infinite descending ∈-chains
• Choice: Every family of nonempty sets has a choice function

Building Mathematics from ZFC

Von Neumann Ordinals:
0 = ∅
1 = {∅}
2 = {∅, {∅}}
ω = {0, 1, 2, ...} (first infinite ordinal)

Construction of ℕ: The set of finite ordinals
Construction of ℤ: Equivalence classes of pairs of naturals
Construction of ℚ: Equivalence classes of pairs of integers
Construction of ℝ: Dedekind cuts or Cauchy sequences

The Profound Limitations: Metamathematical Results

Gödel's First Incompleteness Theorem (1931)

Any consistent formal system F that is strong enough to contain elementary arithmetic is incomplete—there are statements in F that can neither be proved nor disproved in F.

For ZFC (if consistent):
∃ sentence G such that ZFC ⊬ G and ZFC ⊬ ¬G

This means there are set-theoretic statements that are true but unprovable in ZFC.

Gödel's Second Incompleteness Theorem

A consistent formal system F cannot prove its own consistency.

If ZFC is consistent, then ZFC ⊬ Con(ZFC)

We can never prove within ZFC itself that ZFC is consistent.
We must either assume consistency or use a stronger system.

The Continuum Hypothesis is Independent

Gödel (1938) and Cohen (1963) proved:

If ZFC is consistent, then:
ZFC ⊬ CH and ZFC ⊬ ¬CH
where CH is: 2^ℵ₀ = ℵ₁

This means the cardinality of the real numbers is not determined by ZFC axioms.

What Can and Cannot Be Proven

Provable in ZFC

• Basic set operations
• Existence of various number systems
• Cantor's theorem: |A| < |𝒫(A)|
• Most "ordinary" mathematics
• Well-ordering theorem (equivalent to AC)

Independent of ZFC

• Continuum Hypothesis
• Axiom of Constructibility (V=L)
• Various large cardinal axioms
• Many statements in infinitary combinatorics
• Whitehead problem in group theory

The Multiverse Perspective

Due to independence results, some mathematicians advocate for a "multiverse" view:

There are different set-theoretic universes satisfying ZFC
but making different decisions about independent statements like CH.

This suggests that first-order ZFC doesn't determine a unique mathematical reality, but rather a family of possible set-theoretic universes.

First-Order Logic vs. Second-Order Logic

First-Order ZFC

• Advantages: Complete proof system, well-understood metatheory
• Disadvantages: Cannot capture "all subsets" directly, many independence results
• Axiom Schemas: Separation and Replacement are infinite schemas of axioms

Second-Order Set Theory

• Advantages: Can quantify over all subsets, might determine CH
• Disadvantages: No complete proof system, complicated metatheory
• Categoricity: Second-order ZFC might be quasi-categorical

Important: First-order ZFC uses first-order logic, but its axioms (Separation, Replacement) are schemas that essentially quantify over all first-order formulas, which is a form of metatheoretic second-order quantification.

Practical Implications for Mathematics

The "Safe" Core of Mathematics

Most ordinary mathematics falls within what's provable in ZFC:

• Elementary number theory
• Calculus and real analysis
• Basic algebra and geometry
• Most of functional analysis
• Probability and statistics
• Computer science foundations

It's primarily at the frontiers of set theory and certain advanced topics where independence appears.

Working with the Limitations

Mathematicians have developed ways to work with these limitations:

• Relative consistency proofs: Show that if System A is consistent, then so is System B
• Forcing: A method for building models of set theory with different properties
• Inner model theory: Studying submodels of set-theoretic universes
• Large cardinal axioms: Stronger axioms that resolve some independent questions

Synthesis: Buildable But Fundamentally Limited

Yes, sets are buildable in first-order logic through ZFC, and this foundation successfully supports the vast majority of mathematics. The construction is rigorous and well-understood.

But there are profound limitations:

• Incompleteness: Some set-theoretic truths are unprovable in ZFC
• Consistency unprovable: We cannot prove ZFC is consistent within ZFC
• Independence: Important questions like CH are independent of ZFC
• Non-categoricity: ZFC has non-isomorphic models with different properties

The Philosophical Implications:
First-order ZFC gives us a powerful but incomplete picture of the set-theoretic universe.
It successfully captures most mathematical practice but leaves fundamental questions open.

The Current Consensus:

• For practical mathematics: ZFC is entirely adequate
• For set-theoretic foundations: We must acknowledge the limitations
• For philosophical foundations: The situation is more complex and debated

So while sets are indeed "buildable and provable" in first-order logic in a practical sense, the metamathematical results show that this foundation cannot give us complete knowledge of the set-theoretic universe. The success of ZFC as a foundation for mathematics is one of the great achievements of modern logic, but its limitations remind us that mathematical truth extends beyond what can be captured in any fixed formal system.