Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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). – Arturo Magidin Jun 19 '11 at 20:38
up vote 8 down vote accepted

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.

share|cite|improve this answer

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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