5

In model theory, the satisfaction relation ⊧ relates a first-order theory with a collection of sets, functions and relations. The collection of elements those sets, functions and relations respectively take values in can be called the domain of discourse or universe.

Does this make every first-order theory implicitly an extension of set theory?

The signature of ZFC can be conservatively extended with the subset symbol ⊆, and the theory of ZFC conservatively extended with the formula ∀xy [ x ⊆ y ↔ ∀z [z ∈ x → z ∈ y] ]. Let’s call that theory ZFC ∪ ⊆.

One common theory is the theory of groups:

For signature Σ := {e0, i1, ×2}:

  • ∀xyz [x × (y × z) ≡ (x × y) × z]
  • ∀x [i(x) × x ≡ e]
  • ∀x [e × x ≡ x]

One model of this theory can be given as:

  • J(e) = 0
  • J(i) = {(0,0), (1,1)}
  • J(×) = {(0,0,0), (0,1,1), (1,0,1), (1,1,0)}

where 0 := ∅ and 1 := {∅}.

Because the model is a collection of sets, they already carry the structure of set theory. Therefore, if I extended the above theory of groups with the axioms of ZFC, the group part of the model would not change or be affected.

Doesn’t this mean that when we say a theory doesn’t have a model, we mean there is no set in a model of ZFC that models that theory? Since there are other set theories than ZFC, for example, ZF+CH, we know the theory of ZF+CH has a model, just not a model that is also contained in ZFC.

So does this mean that when we talk about a model of a theory, we are actually taking some model of some theory that gives us our semantics (for example, ZFC), and then extending it with the specific theory in focus (for example, the theory of groups)?

Julius Hamilton
  • 4,678
  • 2
  • 11
  • 48

4 Answers4

4

Your question is about models and semantics. Since none of the three other answers deals with models, it may be worth pointing out that when one talks about models of theories (even those much weaker than ZFC), one traditionally works in a model (assumed to exist) of a background set theory. However, this does not mean that the first-order theory itself is an extension of the theory ZFC; indeed, Presburger Arithmetic, Peano Arithmetic, etc. are far weaker than ZFC.

When working with Pi_1 or Sigma_1 statements, one does not need infinitary notions implicit in traditional set theory. However, once the statements involve an alternation of quantifiers, the corresponding semantics (the scope of the quantifiers) is usually considered not to be finitist anymore. Even such a simple purely arithmetic statement as the twin prime conjecture (TPC) involves an alternation of quantifiers and therefore possesses a non-finitary aspect as far as semantics is concerned (in principle TPC could even be independent of ZFC).

Mikhail Katz
  • 4,754
  • 10
  • 32
4

Not at all. You simply need a meta-system MS that is strong enough to cater for your desired reasoning about models of FOL. As described in this brief sketch, if you only really care about countable FOL theories, then you can very well make do with ACA (PA for ℕ plus arithmetical comprehension for subsets of ℕ plus the full induction schema), which is strong enough to prove a lot of key facts about FOL including the compactness theorem and the semantic-completeness theorem for your favourite deductive system.

Furthermore, ACA is very well justified ontologically because the intended model of ACA is just ℕ plus its arithmetical subsets, and those subsets directly correspond to arithmetical properties on ℕ, which are syntactic objects and hence are beyond ontological doubt unless you reject even the notion of ℕ.

Not only that, PA (and hence ACA too) proves many things about set theories including ZFC, such as Con(ZFC)⇒Con(ZFC+CH)∧Con(ZFC+¬CH). This is despite ACA being unable to talk about an uncountable model of ZFC. But it does not need to. It knows that if Con(ZFC) then ZFC has a (countable) model M, and can construct the L inside M and prove that L satisfies ZFC+CH. Similarly it can prove Con(ZFC) implies Con(ZFC+¬CH).

user21820
  • 820
  • 1
  • 9
  • 27
3

This presupposes that set theory is a first order theory. There are arguments against this: Quine remarked that higher order logic is "set theory in sheep's clothing". We can turn this around and say that set theory is higher order logic in sheep's clothing. Which stance you take depends upon your philosophical presuppositions. Personally, I think both higher order logic and set theory to be natural.

What do we mean by saying set theory is higher order logic in sheep's clothing? I mean by this, it's formal description is as a first order theory but ontologically speaking, it is a higher order logic which is disguised by its formal description. One way of noting is that ZFC can formalise Peano Arithmetic and whilst this arithmetic is a first order theory the we can see that the axiom of induction is actually an axiom schema and is more naturally expressed as a second order axiom.

if models of first order logics are defined by set theory, is every first order theory an exyension of set theory.

No, first order Pressburger Arithmetic, which formalises only addition and equality, is not an extension of set theory in any sense as it is a decidable theory whilst ZFC, since it can encode Peano Arithmetic, is undecidable.

Mozibur Ullah
  • 49,540
  • 15
  • 101
  • 267
1

Picking up on Double Knot's comment, talking of sets when studying logic is convenient, but it is not an essential prerequisite. All we need is some primitive pre-theoretic notion of a collection of things. We can even eliminate that by using the language of plurals. Logic does not presuppose any formal set theory.

Peter Smith states it like this:

Up to now, we have avoided talk of sets - so, for example, we preferred to talk of some wffs, plural, tautologically entailing a conclusion rather than of a set of wffs entailing the conclusion (which is the more usual idiom). Still - partly for convenience, partly to align ourselves with other treatments - we will start occasionally talking of sets or collections. However, unless explicitly signalled, this is to be interpreted in the non-committal lightweight way that can in principle be paraphrased away into plural talk. (When apparent reference to some objects can be paraphrased away, some philosophers talk of these as being merely virtual objects: in this sense, unless otherwise indicated, our sets can be treated as virtual sets.)

  • Peter Smith, Introduction to Formal Logic (Cambridge, 2nd edition, 2020), section 25.5, page 236.
Bumble
  • 35,899
  • 4
  • 37
  • 97