4
$\begingroup$

In order to prove the completeness theorem we obviously need a framework such as ZFC (I'm aware that ZFC isn't the only possibility) so that we can talk about a language $\mathcal{L}$ and also about models of $\mathcal{L}$.

Now the completeness theorem makes perfect sense to me in so far as the language which we study has a model like first order logic ($\mathcal{L_=}$), ordered fields, groups, etc.

But then I hand a thought. By the completeness theorem if $\mathbf{ZFC} \models \varphi$ then $\mathbf{ZFC} \vdash \varphi$ (by $\mathbf{ZFC}$ I mean the axioms of ZFC). However $\mathbf{ZFC} \models \varphi$ means that any model $\mathfrak{U}$ for which $\mathfrak{U} \models \mathbf{ZFC}$ it is true that $\mathfrak{U} \models \varphi$. But how do we know that any model of ZFC exists? Since we can't construct a model of ZFC within ZFC, how can we interpret what the completeness theorem is saying?

So does the completeness theorem just not say anything about ZFC itself? Or is it the case that even though we don't know anything about models of ZFC inside ZFC we can still talk about them and because of this the completeness theorem does hold.

$\endgroup$
3
  • 2
    $\begingroup$ Not necessarily $\mathsf {ZFC}$... Gödel's original proof of the basic result: " Every valid (true in all structures) formula $\varphi$ is provable (in the specified proof system)" considered the equivalent formulation: "Every formula $\varphi$ is either refutable or satisfiable in some structure" used an arihmetical model to show that the non-refutable formula is satisfiable. $\endgroup$ Mar 28 at 9:42
  • $\begingroup$ If no model of the theory exists, “every model satisfies $\psi$” is vacuously true for all $\psi$. The completeness theorem is saying that is the case if and only if the theory proves every sentence $\psi$. This is of course the “has a model iff consistent” formulation discussed in Z.A.K.’s answer. $\endgroup$ Mar 28 at 14:14
  • $\begingroup$ It doesn't matter whether $\text{PA}$ or $\text{ZFC}$ or any other theory is inconsistent unless we find a proof of a contradiction from it. Contradictions are disdained because of 'ex falso quodlibet' - every sentence is derivable from a contradiction. Now suppose hypothetically that $\text{ZFC}$ is inconsistent but the shortest proof of a contradiction is $10^{1000}$ pages long. We have no hope of ever finding it. So we can't use this hypothetical contradiction to 'prove everything'. In the meantime we're busy finding out what sentences can be proved in less than a 1000 pages. $\endgroup$
    – Chad K
    Mar 28 at 16:10

2 Answers 2

9
$\begingroup$

Welcome to Math.SE!

The completeness theorem is a theorem of ZFC Set Theory. It says that if a first-order theory $T$ is consistent, then $T$ has a model (and vice versa).

This is a conditional statement: you can use the completeness theorem to get a model of the theory only if you know that said theory is consistent. Similarly, if you know that a theory has a model, you can be sure that theory is consistent.

The following is a particular instance of the theorem, obtained by taking ZFC as the theory $T$:

ZFC is consistent precisely if it has a model.

This theorem of ZFC leaves open two possibilities,

  • I. ZFC is inconsistent, and it does not have a model;
  • II. ZFC is consistent, and it has a model;

while ruling out the following others:

  • III. ZFC is inconsistent, but it has a model;
  • IV. ZFC is consistent, but it does not have a model.

If ZFC really is free of contradictions, then it can't prove its own consistency or come up with its own model, so the axioms of ZFC do not pin down which of I or II hold.

Nevertheless, certain ZFC extensions might lean towards one outcome. E.g. the theory ZFC+$\neg \mathrm{Con}(ZFC)$ proves that ZFC is inconsistent, and by the completeness theorem also proves that ZFC has no model (I). Similarly, Tarski-Grothendieck set theory proves both that ZFC has a model and that ZFC is consistent (II).

But ZFC has no consistent extension which proves that ZFC is consistent but not that it has a model (III), nor a consistent extension which proves that ZFC has a model but not that it is consistent (IV): this is the meaning of the completeness theorem when applied to ZFC itself.

$\endgroup$
5
  • 1
    $\begingroup$ Thank you very much for your answer. My problem was that I didn't fully understand what the completeness theorem was actually saying. It now makes perfect sense. $\endgroup$ Mar 28 at 16:40
  • $\begingroup$ To clarify for future readers: $\mathrm{ZFC}+\neg\mathrm{Con}(\mathrm{ZFC})$ "proves" that ZFC has no model, but what that actually means is that there is no object which that extension of ZFC thinks is a model of ZFC. It does not necessarily mean that there really is no model of ZFC. $\endgroup$
    – Kevin
    Mar 28 at 22:45
  • $\begingroup$ @Kevin: You might as well make it clearer by saying that ZFC is just a formal system and the theorems it proves are analogous to the chess games that the chess rules permit. There is no meaning to any of the theorems of ZFC unless we interpret them somehow. So if we cannot interpret ZFC+¬Con(ZFC) meaningfully, then we should never expect what it says (e.g. that ZFC is not consistent and that ZFC has no model) to be meaningful, not to say correct. And even ZFC itself is not free from suspicion. $\endgroup$
    – user21820
    Mar 29 at 2:15
  • $\begingroup$ @user21820: Yes, I know. I'm trying to make this question easier to read for someone who is just getting into model theory for the first time. $\endgroup$
    – Kevin
    Mar 29 at 16:27
  • $\begingroup$ @Kevin: I get what you're saying, but it's still not clear enough. The reason is that you use the words "think" and "model", but "think" is vague and "model" is subjective. What does "really is no model" mean? And in "that extension of ZFC thinks is a model of ZFC" your "model" here is merely some syntactically defined notion. I don't really think model theory helps much to beginners, unless you explicitly make clear to work within a sufficiently weak meta-system, but most model theory textbooks use full ZFC. $\endgroup$
    – user21820
    Mar 30 at 7:28
4
$\begingroup$

"But how do we know that any model of ZFC exists?"

We don't. The usual way out is to assume that such a base model exists, and refer to it as "the intended model/interpretation". There are many questions here and at MO about this; you could consult for example this MO question: Looking for a source for intended interpretation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .