0
$\begingroup$

To properly ask my question, I need to set up some definitions of whose I don't know, if I use the words in the usual sense:

  1. Let $\mathcal{L}$ be a formal language of first-order predicate logic with equality. With the word theory, I mean a collection of formulas in that language, that is

    • closed under the usual rules of inference, so every formula, that can be derived from the theory is already a member of it.
    • consistent, so the formula $\top \leftrightarrow \bot$ is no member of it.
  2. I will call a theory $T$ in the language $\mathcal{L}$ complete iff for any sentence $A$, that can be formed in the language $\mathcal{L}$, one of the two sentences $$ A \leftrightarrow \top \qquad \text{or} \qquad A\leftrightarrow \bot$$ is a member of $T$.

Note that a complete theory contains a formula like $\exists x : A(x)$, if and only if there is a term $t$, such that it contains the formula $A(t)$ (so the $\exists$-quanitifier has its intended "meaning").

  1. For some theory $T$ in the language $\mathcal{L}$, a syntactic model for $T$ consists of

    • a language $\mathcal{L}'$, that contains the same function symbols, relation symbols and variables as the language $\mathcal{L}$, contains every constant symbol of $\mathcal{L}$ but may contain even more constant symbols.
    • and a complete theory $T'$ in the language $\mathcal{L}$', that contains every sentence of $T$, when interpreted as a sentence in the language $\mathcal{L}'$.
  2. For some theory $T$ in the languahe $\mathcal{L}$, a set model for $T$ is an $\mathcal{L}$-structure, satisfying each formula of $T$, interpreted in standard semantics (just the usual definition of a model here).

I observe now, that there is an "almost-bijection" between syntactic models and set models for a theory:

  • Let $M$ be a set model for the theory $T$. For any member $x \in M$, add a constant symbol $\mathsf{c}_x$ to the language of $T$ and let $T'$ be the collection of all sentences in the enhanced language, that are true in $M$ (interpreted via standard semantics).
  • Let $(\mathcal{L}',T')$ be a syntactic model for the theory $T$ in the language $\mathcal{L}$. Define an $\mathcal{L}$-structure $M$ by building equivalence classes of $\mathcal{L}'$-terms containing no variables, where two terms $t,s$ are equivalent, if the equation $s=t$ is a member of $T'$. Interpret the function symbols in the obvious way. Now for every $n$-ary relation symbol $R$, define the coresponding set theoretical relation as $$ \{ (t_1, \dots , t_n) \in M^n \mid ( R(t_1, \dots ,t_n) \leftrightarrow \top) \in T' \} $$ Thus, we get a set model for $T$.

These two operations are almost inverse, but the operation $\{\text{syntactic models}\} \to \{\text{set models}\} \to \{\text{syntactic models}\}$ adds a constant symbol for each equivalence class of constant terms.

It seems to me that the notion of syntactic model can fully replace set models. Also every prove of Gödel's completeness theorem, that I have seen, goes on to construct a syntactic model first and then transform it into the set model. It follows that the completeness theorem still holds, if we replace set models by syntactic models.

Now comes my question: Why do we even go that detour around set theory, when defining semantics? Why don't we only work with syntactic models?

The advantage of syntactic models is, that they don't stress the ontology more than necessary. If you believe in strings and the notion of formal derivability, it's not hard for you to belive in syntactic models as well. You don't need to belive in or even think of general power sets, functions being defined as sets of Kuratowski pairs, uncountable infinities or the notion of cardinality at all.

$\endgroup$
  • 1
    $\begingroup$ There is no reason to write something like $A\leftrightarrow \top$; that is always equivalent to just $A$. Similarly $A\leftrightarrow\bot$ is just $\neg A$. $\endgroup$ – Eric Wofsey Sep 28 '19 at 22:46
  • 2
    $\begingroup$ Your sentence starting "Note that a complete theory contains..." is also totally wrong. You can have a complete theory in a language with no function symbols at all, so there are no closed terms. $\endgroup$ – Eric Wofsey Sep 28 '19 at 22:48
  • 2
    $\begingroup$ Note in particular that normally a theory is only allowed to contain sentences, not formulas with free variables. If you allow free variables then free variables are not really variables at all but are effectively constant symbols. (And, you need to be very careful about what kind of inferences you allow, if you don't want pretty much every theory to trivially be inconsistent.) $\endgroup$ – Eric Wofsey Sep 28 '19 at 22:52
  • 2
    $\begingroup$ Based on this question and your previous question, it sounds like you have some major misunderstandings about the role of variables in first-order logic. I might suggest reading the first couple chapters of an introductory text in model theory to get a better understanding. $\endgroup$ – Eric Wofsey Sep 28 '19 at 23:09
  • $\begingroup$ Thanks for the advice! I already read some chapters of logic books. But I am now trying to find my own interpretation of first-order calculus. Every albgebraic structure is isomorphic to a factor structure of some term algebra (the freely generated one), that can be described via generators and equations. The same seems to hold for models of first order theory, but if every model is characterised by the syntactic porperties of generating symbols and equations, why should we consider more than that? $\endgroup$ – Lucina Sep 30 '19 at 14:15
5
$\begingroup$

As Eric Wofsey points out, there are some errors implicit in your question which have to be addressed before it can be answered. The issues around variables are a side issue which I'll ignore. The important error is the claim

Note that a complete theory contains a formula like $\exists x : A(x)$, if and only if there is a term $t$, such that it contains the formula $A(t)$ (so the $\exists$-quanitifier has its intended "meaning").

which is quite false. One easy way to see that this fails even for complete theories is by thinking about models (in the usual semantic sense): for any structure $\mathcal{M}$ the theory $Th(\mathcal{M}):=\{\varphi: \mathcal{M}\models\varphi\}$ is complete (this is a trivial consequence of the negation clause in the Tarski definition of truth), so the theory of any structure in a language with only relation symbols is a counterexample to your claim.

However, this does isolate a key property of theories. Say that a theory $T$ has the strong witness property if for every formula $\varphi(x_1,...,x_n)$ there are constant symbols $c_1,...,c_n$ in the language of $T$ such that $$T\vdash[\exists x_1,...,x_n\varphi(x_1,...,x_n)\implies\varphi(c_1,...,c_n)].$$ The right notion of "syntactic model of $T$" then is just consistent complete extension of $T$ with the strong witness property.


Having said that, you're quite right that we can rephrase everything in terms of syntactic models (once we've redefined them properly per the above). But this has the drawback of making the interaction between logic and the rest of math more cumbersome: mathematicians outside logic care about mathematical structures more than sets of formal sentences. That is, the language of (semantic) models isn't something logicians introduce, it's something we abstract from existing mathematical discourse (and indeed it only captures part of the picture - think of, say, topological spaces). Similarly, students coming into logic tend to already have "semantic mathematics" in the background. So it's genereally more natural.

Moreover, as you yourself observed syntactic models and semantic models are more-or-less equivalent, so we actually don't buy any more philosophical tameness by focusing only on the latter: "a language" is no less complicated than "a set," and restricting attention to countable languages is no less complicated than restricting attention to countable models in the usual sense.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry about the mistake. I thougt, that from the formula $A(x)\leftrightarrow \bot$ we can induce $(\exists x : A(x)) \leftrightarrow \bot$ so by completenes and consistency, my claim holds. It seems that I confused constant terms with variables. $\endgroup$ – Lucina Sep 30 '19 at 13:52
  • $\begingroup$ I have the impression that the classical theory of first-order semantics ultimately boils down to syntactic derivability: What makes you sure, that in a model, there is no formula both true and wrong? The assumed consistency of the set thory you are using to define models. What makes you sure, that in a model, each formula is either true or wrong. Your assumption of tertium non datur in set theory. How can you tell, if some concrete formula is true? By syntactically deriving it in set theory. $\endgroup$ – Lucina Sep 30 '19 at 13:56
  • $\begingroup$ So, the theory of truth seems like outsourcing the object language's notion of derivability to that of the meta-theory you're using to talk about models. But accepting that point of view, the notion of syntactic models is quite more "honest" about this, than the more sophisticated approach of set models. Finally, assume you are using a set theory $T$ to formalize model theory and the axioms of $T$ itself. The in-$T$-provable sentence "T has a model iff it is consistent" has no onthological substance then. (or has it?) $\endgroup$ – Lucina Sep 30 '19 at 14:06
  • $\begingroup$ @Lucina Sorry, I just saw these. "the classical theory of first-order semantics ultimately boils down to syntactic derivability" You can indeed embed all of mathematics in formal systems - this is why formalism is a tenable philosophy (and indeed one I hold). But you seem to take the further stance that we should therefore ignore semantic ideas. First of all, this is incompatible with some philosophies of mathematics, and there's a general principle (which I approve of) that mathematics should accommodate as much variety of foundational stance as possible. (continued) $\endgroup$ – Noah Schweber Oct 2 '19 at 16:56
  • $\begingroup$ When you say "boils down," you're talking about what necessarily is, not what there might be - but not everybody's on board with "philosophical minimization." (Indeed, I'm a formalist and I'm not on board with that!) More relevantly to you I suspect is the fact that those ideas are useful even from a formalist viewpoint (cont'd): if, for example, you want to prove in ZFC that Con(ZFC) implies Con(ZFC+CH), the easiest way to do so is via formalizing model-theoretic ideas inside ZFC. Even if you only want to talk about formal deductions, semantic ideas are invaluable. (continued) $\endgroup$ – Noah Schweber Oct 2 '19 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.