4
$\begingroup$

I have a question about a gap in lemma. First how things were defined in the course I'm taking (I'm sorry to be making the readers going through this list of definitions, but I don't know how to make it shorter):

Let $\sigma $ be a signature and $T$ a $\sigma $-theory. We have defined this theory to be satisfiable if there is a model $M$ such that for every sentence of the theory $M$ satisfies the sentences. We have defined sentences to be provable if they belong to the smallest set satisfying a list of properties and universal if for every model $M$ they are satisfied. Further on, we have defined the theory to be contradiction free if there are no sentences $\alpha_1,\ldots,\alpha_n \in T$ such that $\neg ( \alpha_1 \wedge \ldots \wedge \alpha_n)$ is provable.

Then we proved that every provable sentence is universal and then it was mentioned (without a full proof) that by the previous proposition every satisfiable theory is contradictions free. My question is: How can the proposition that every provable sentence is universal be used to prove that ?

  • 3
    If $T$ is not contradiction free, then you have sentences $\alpha_1,\ldots,\alpha_n\in T$ such that $\neg(\alpha_1\land\cdots\land\alpha_n)$ is provable. But since $T$ is satisfiable, it has a model $M$; since $M$ is a model, $\alpha_1,\ldots,\alpha_n$ are satisfied in $M$. Since $\neg(\alpha_1\land\cdots\land\alpha_n)$ is provable, it is universal, hence it is satisfied in $M$. So $M$ satisfies each of $\alpha_i$, and satisfies at least on $\neg\alpha_j$, which is impossible ($M$ is a model).2011-06-19

2 Answers 2

9

Suppose $T$ is a satisfiable theory. Pick some model $M$ for it. If $C$ is a contradiction provable in $T$, then by your proposition $C$ must hold for $M$. However, $C$ is not logically valid, and in particular the recursive definition of validity shows that it cannot hold. So $C$ must not have been provable in $T$ after all.

In other words, $M$ is a proof that $T$ is a "reasonable" theory. It witnesses the consistency of $T$ - indeed, it is an example of it! - and so shows that $T$ cannot contain "inherent" contradictions.

4

Another way of saying the same thing: let $T$ be your theory and let $M$ be a model of $T$. Let $S$ be the set of all sentences that are true in $M$ (symbolically, $S = \{ \phi : M \vDash \phi\}$). Then:

  • $S$ extends $T$, because $M \vDash T$.
  • $S$ is closed under provability: if $\psi_1, \ldots, \psi_k \in S$ and $\psi_1, \ldots, \psi_k \vdash \phi$ then $\phi \in S$. This follows from the soundness of the proof system.
  • $S$ is consistent: for no sentence $\phi$ does $S $ contain $\phi \land \lnot \phi$. This follows from the definition of the $\vDash$ relation.

These three bullets together imply $T$ is consistent.

As a bonus, $S$ is also complete: for any $\phi$, either $\phi \in S$ or $\lnot \phi \in S$, again because of the definition of the $\vDash$ relation. So the existence of a model is, in a certain sense, a very strong proof that the theory is consistent: it not only proves the consistency of $T$, it also provides a consistent completion of $T$.