From the FOM newsgroup I learned:

It's a theorem of (first-order) set theory that every consistent first-order theory has a model.

What's the exact formulation of this theorem in purely set-theoretic terms? (Reference?)

Is the following a sensible point of view?

Given a definition for "defining a consistent first-order theory" for formulas $\phi(x)$ in the language of set theory, including conditions that make $\phi(x)$ a "theory" and "consistent". Think of formulas $\phi(x)$ that say $x$ is a graph or $x$ is a group or $x$ is a topological space.

Can the model existence theorem then be seen as a theorem scheme such that for every formula $\phi(x)$ defining a consistent first-order theory (in the sense above) the sentence $(\exists x)\phi(x)$ is provable from the axioms of set theory?

  • $\begingroup$ Pardon my ignorance, here, but what does the "F" in FOM stand for...and is the full acronym F____ of Math(ematics)? I'm aware (and a member of) the MAA's SIGMAA (special interest group of MAA) POM (Philosophy of Math), which has a listserv of sorts, but haven't come across FOM. $\endgroup$ – Namaste Jun 16 '11 at 19:48
  • $\begingroup$ FOM = foundations of mathematics $\endgroup$ – Hans-Peter Stricker Jun 16 '11 at 19:49
  • 1
    $\begingroup$ @Hans: The theory of topological spaces is not first order. "First-order" is with respect to the universe of the structures you consider. To formulate "$(X,\tau)$ is a topological space", you need to refer to arbitrary unions of the elements of $\tau$, that are themselves subsets of $X$, and you also need to talk about arbitrary subsets of $X$. This is not first order, even if you allow a two-sorted structure to talk about both $X$ and its power-set. Of course, the statement is first-order in set theory, but that's a different issue. $\endgroup$ – Andrés E. Caicedo Jun 16 '11 at 23:41
  • 1
    $\begingroup$ To be more explicit: To say that a class $S$ of structures is first order, means that, in an appropriate language, there is a collection $C$ of first-order sentences such that, given a structure $M$ in that language, $M\models C$ iff $M\in S$. To say that "the theory of topological spaces" is first-order means that the class $T$ of topological spaces is first-order in the sense just described. $\endgroup$ – Andrés E. Caicedo Jun 16 '11 at 23:46
  • 1
    $\begingroup$ This is rather different from saying that there is a first-order formula $\phi(x)$ in the language of set theory such that $T$ is definable by $\phi$, i.e., for any set $M$, $M\in T$ iff $\phi(M)$, which is the sense in which I think you are saying that "inside set theory", the theory is first-order. $\endgroup$ – Andrés E. Caicedo Jun 16 '11 at 23:46

You are asking for the completeness theorem of first-order logic, proved by Kurt Gödel in 1929.

There are various ways to state the completeness theorem, and among them are the following two assertions:

  • Whenever a statement $\varphi$ is true in every model of a theory $T$, then it is derivable from $T$.

  • Whenever a theory $T$ is consistent, then it has a model.

These assertions are easily seen to be equivalent, by the following argument. If the first holds, and a theory $T$ has no model, then false holds (vacuously) in every model of $T$, and so $T$ derives a contradiction; so the second holds. If the second holds, and $\varphi$ holds in every model of $T$, then $T+\neg\varphi$ has no models and so is inconsistent by 2, so by elementary logic, $T$ derives $\varphi$; so the first statement holds.

  • $\begingroup$ Not immediately. My main question is: What's the formulation (of one of these equivalent(?) theorems) in purely set-theoretic terms? And does my "point of view" make sense? $\endgroup$ – Hans-Peter Stricker Jun 16 '11 at 20:11
  • 1
    $\begingroup$ You don't need very much set theory to formalize the completeness theorem---just enough to speak about models of a theory and whether they exist, and enough to carry out the Henkin construction. To formalize the theorem in set theory amounts just to being precise about what sentences are, etc., as in any mathematical enterprise, which can be viewed as founded ultimately in set theory. $\endgroup$ – JDH Jun 16 '11 at 20:16
  • $\begingroup$ @Hans: you should be able to do this yourself once you understand the definitions of "a statement is true," "a statement is derivable," "a theory is consistent," and "a theory has a model." $\endgroup$ – Qiaochu Yuan Jun 16 '11 at 20:17
  • $\begingroup$ Your proposed schema is not correct, since we want to apply the theorem to $\varphi$ that may not be in the language of set theory. We want to consider theories in the language of graph theory, arithmetic etc. The completeness theorem shows that the first-order deductive system with which it is concerned is complete, so that it guarrantees the existence of models of any theory in which we cannot derive a contradiction. It follows from this, for example, that any statement in the language of graph theory that happens to be true in all graphs, is derivable from the graph axioms. $\endgroup$ – JDH Jun 16 '11 at 20:20
  • $\begingroup$ Where is all of this spelled out? Or does it really depend only on a definition what a formula/sentence is in set-theoretic terms: a tupel of elements of a set called "alphabet", obeying some conditions? $\endgroup$ – Hans-Peter Stricker Jun 16 '11 at 20:22

That's Gödel's Completeness theorem. The formulation in set theory is: "Every consistent first order theory has a model". An equivalent formulation is "Every logical consequence of a theory is provable from said theory".

This is not a scheme of theorems. It is a single theorem. Keep in mind though that this theorem doesn't speak about the metalanguage (in this case that of set theory), but rather about the sentences of various languages as seen inside set theory.The theorem now states that if a set of sentences is consistent, then there exists a set that is a model of these sentences. The standard definition of a model is a set equipped with various functions, relations etc. and a map between these and the objects of the language.

  • 1
    $\begingroup$ So all I have to do is to keep in mind that signatures are sets, sentences are sets, languages are sets, theories are sets, being consistent is a property of sets, being a model of a set of sentences (= sets) is a relation between sets, the interpretion map is a set,...? $\endgroup$ – Hans-Peter Stricker Jun 16 '11 at 22:34
  • 1
    $\begingroup$ Hans, yes, this is the sense in which the completeness theorem can be viewed as a theorem of set theory. This is all the person meant in your original quote. $\endgroup$ – JDH Jun 17 '11 at 0:08

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.