5
$\begingroup$

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?

  • 0
    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.2011-06-16
  • 0
    FOM = foundations of mathematics2011-06-16
  • 0
    aha: now it seems rather obvious! thanks!2011-06-16
  • 0
    @Hans: *Is* the theory of topological spaces first order?2011-06-16
  • 0
    @Zhen: *This* is a question that bothered me ever since. I guess, it depends on its formulation. And, yes, I guess, you can formulate it in first order. (At least inside set theory!)2011-06-16
  • 1
    @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.2011-06-16
  • 1
    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.2011-06-16
  • 1
    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.2011-06-16
  • 0
    @Andres: Can't I talk about the subsets of X only and identify the elements of X with the singletons of P(X)?2011-06-17
  • 0
    @Hans: The main problem with your suggestion is that the language you use to talk about a given class of structures should be fixed from the beginning. With your suggestion, you need a different language for each cardinality.2011-06-17
  • 0
    @Andres: I try to make sense of what you said in the light of the answer and comments to this question http://math.stackexchange.com/questions/46656/why-is-topology-nonfirstorderizable, but I didn't succeed.2011-06-21

2 Answers 2

11

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.

  • 0
    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?2011-06-16
  • 1
    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.2011-06-16
  • 0
    @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."2011-06-16
  • 0
    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.2011-06-16
  • 0
    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?2011-06-16
  • 0
    Yes, I take the claim that the completeness theorem is provable in set theory in the same way that one might understand set theory as a foundation for any mathematical argument.2011-06-16
  • 0
    @Qiaochu: I believed to understand these definitions - from the point of view of model theory. But I find it hard to see model theory merely as a branch of set theory.2011-06-16
  • 0
    @Joel, "Your proposed schema...": Is this really the point? Cannot I mimick every theory in every language of every signature by a set-theoretic formula, just by an ordered tupel of relations and functions?2011-06-16
  • 0
    Yes, but the completeness theorem is about the original theory, not about your set-theoretically enhanced modified theory. We want to know that when a statement purely in the language of group theory is true in all groups, then we can prove it directly from the group axioms.2011-06-17
  • 0
    What status then has the fact, that for (almost) all set theoretic predicates $\phi(x)$ like the ones above (x is a graph, x is a group, and so on) it can be proved that $(\exists x)\phi(x)$? Doesn't this tell something about set theory, too? And cannot this be rephrased that every consistent theory$_2$ has a model$_2$?2011-06-17
2

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
    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,...?2011-06-16
  • 1
    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.2011-06-17