Set Theory and First-Order Logic

A genuine puzzle that troubles many newcomers to the foundations as presented here: first-order logic and set theory (ZFC) appear to depend on each other. This remark untangles that relationship.

The apparent circularity

There is a real tension lurking in the foundations as presented here:

• The semantics of first-order logic is set-theoretic. A structure $\mathcal{M}$ is a set (the domain) equipped with sets of tuples (the relations) and functions; satisfaction $\mathcal{M}\models \phi$ is defined by recursion using sets; "valid" means "true in every structure," quantifying over a proper-class-sized collection of sets. Tarski's truth definition lives inside set theory.
• Yet ZFC is a first-order theory — its axioms are first-order sentences in the language $\{\in \}$, and its logic is first-order logic.

So first-order logic is explained using set theory, and set theory is formulated using first-order logic. Which comes first?

Resolution: object theory vs. metatheory

The circle is only apparent, and the standard resolution is the distinction between the object theory and the metatheory. (For the underlying definition of model and structure used throughout, see What is a model? in the model-theory page.)

• When we study a formal system (define its syntax, its models, prove soundness/completeness), we work in an informal or semi-formal metatheory — ordinary mathematical reasoning, which can itself be formalized in some set theory (often a weak fragment, or ZFC, or even just primitive recursive arithmetic for the syntactic parts).
• When ZFC is the object theory, it is the system under the microscope: a set of strings closed under first-order derivation rules. The metatheory talks about those strings.

The two roles use the "same" notions (sets, first-order formulas) but at different levels. Confusing them is the source of the vertigo; keeping them apart dissolves it. This is the same move that resolves Skolem's paradox — "countable" in the model versus "countable" in the metatheory — and that underlies Gödel's incompleteness theorems, where a theory reasons about (a coded copy of) its own syntax.

The status of model and truth talk under this distinction — why "satisfies / true-in" is irreducibly metalinguistic (Tarski's undefinability of truth), and the "two gazes" picture of object vs. metatheory — is developed separately in Models, Truth, and Metalanguage.

How little metatheory is actually needed

A reassuring fact: the syntactic side of logic needs almost no set theory at all. Formulas are finite strings, proofs are finite sequences, and "$⊢$" is a decidable/recursively-enumerable relation on them. All of this is formalizable in a weak arithmetic such as PRA (primitive recursive arithmetic) or even weaker — no infinite sets required. The completeness theorem ($⊢$ ⟺ $\models$) is what drags set theory back in, because $\models$ quantifies over arbitrary structures; its proof (Henkin's) uses a modest amount of infinitary reasoning. The proof-theoretic content of logic is thus foundationally cheap; only the model-theoretic content is foundationally expensive.

Which logic comes "first"?

A defensible ordering of dependencies:

1. Syntax / proof theory of first-order logic — finite combinatorial objects; needs only a weak arithmetic metatheory.
2. A foundational theory (ZFC, or a fragment) — formulated in that first-order syntax, supplying a universe of sets.
3. Model theory / semantics of first-order logic — defined inside that set-theoretic universe, since structures are sets.

On this reading first-order syntax is prior to set theory, and set theory is prior to first-order semantics. The completeness theorem is precisely the bridge certifying that the cheap syntactic notion and the expensive semantic notion coincide. (For exactly how much metatheory each step needs — the reverse-mathematics ledger and the axiom-of-choice subtlety — see What the Metalanguage for First-Order Logic Assumes.)

First-order logic's special status

Why is first-order logic, specifically, the partner of ZFC — rather than second-order logic?

• Lindström's theorem. First-order logic is the maximal logic enjoying both compactness and the downward Löwenheim–Skolem property. Any genuinely stronger logic loses one of them. This is a precise sense in which first-order logic is not an arbitrary choice but a canonical one.
• Second-order set theory hides the question. One can phrase set theory in second-order logic (e.g. second-order ZFC is quasi-categorical — Zermelo's theorem pins down the $V_{\kappa }$ for inaccessible $\kappa$). But second-order consequence is not axiomatizable and smuggles set theory into the logic itself ("set theory in sheep's clothing"). So the apparent gain in determinacy just relocates the set-theoretic commitments from the axioms into the logic. First-order ZFC keeps those commitments explicit, in the axioms, which is exactly why it is preferred as a foundation.

Take-aways

• The set-theory/first-order-logic "circularity" is a level confusion, not a vicious circle: object theory vs. metatheory (the status of model/truth talk under this distinction is covered in Models, Truth, and Metalanguage).
• Syntax of first-order logic is foundationally cheap (weak arithmetic); semantics is expensive (needs set theory). Completeness links the two.
• First-order logic is the canonical foundational logic by Lindström's theorem, and first-order ZFC is preferred precisely because it keeps its set-theoretic commitments in the axioms rather than in the logic.

Related discussions: Skolem's paradox (absoluteness across models), Gödel's incompleteness (a theory reasoning about its own syntax), and category-theoretic foundations (an alternative that relocates the primitives entirely).