Franklin's Notes


Consistency and Satisfiability

A set of sentences $\Sigma$ is inconsistent if $\Sigma\vdash\varphi$ for all sentences $\varphi$, and consistent otherwise. We say that $\Sigma$ is maximal consistent if $\Sigma$ is not a proper subset of any other consistent set of sentences.

Proposition 1. $\Sigma$ is inconsistent if and only if $(\varphi\land(\neg\varphi))$ is deducible from $\Sigma$ for some sentence symbol $\varphi$.

Proof. The "only if" direction follows directly from the definition of inconsistency. For the "if" direction, suppose that $(\varphi\land(\neg\varphi))$ is deducible from $\Sigma$ for some sentence symbol $\varphi$. The sentence $\neg(\varphi\land(\neg\varphi))$ is a tautology, meaning that $(\varphi\land(\neg\varphi))\to \psi$ is also a tautology for any sentence $\psi$. However, this means that $\psi$ is deducible from $\Sigma$ by modus ponens, and $\psi$ was arbitrary. $\blacksquare$

The above is sometimes known as the principle of explosion: from a contradiction, anything follows. The above proof applies to sentential logic with a set of sentence symbols $\mathscr{S}$, but it can also be applied to first-order logic by replacing the word "sentence symbol" with "formula".

Proposition 2. If $\Sigma$ is consistent and $\Gamma$ is the set of sentences deducible from $\Sigma$, then $\Gamma$ is consistent.

Proof. This follows easily from Proposition 1. If $\Sigma$ is inconsistent, then $(\varphi\land(\neg\varphi))$ is deducible from $\Sigma$ for some sentence symbol $\varphi$, meaning that $(\varphi\land(\neg\varphi))$ is in $\Gamma$ and is hence deducible from $\Gamma$. On the other hand, if $\Gamma$ is inconsistent, then $(\varphi\land(\neg\varphi))$ is deducible from $\Gamma$ and hence an element of $\Gamma$ (since $\Gamma$ is closed under deductive consequences), meaning that $(\varphi\land(\neg\varphi))$ is deducible from $\Sigma$, making it inconsistent. $\blacksquare$

Proposition 3. (Deduction Theorem) If $\Sigma\cup{\psi}\vdash \varphi$, then $\Sigma\vdash (\psi\rightarrow\varphi)$.

Proposition 4. (Lindenbaum's Theorem) Any consistent set of sentences $\Sigma$ can be enlarged to a maximal consistent set of sentences $\Gamma$.

The above proposition can be proven using transfinite induction, by considering a sequence of extensions of a set of sentences $\Sigma$ indexed by ordinal numbers .

A set of sentences $\Sigma$ is satisfiable if it has at least one model.

Theorem 1. (Extended Completeness Theorem) A set of sentences $\Sigma$ of $\mathscr{S}$ is consistent if and only if it is satisfiable.

Theorem 2. (Compactness Theorem) A set of sentences $\Sigma$ is satisfiable if and only if it is finitely satisfiable.

Proof. The "only if" direction follows directly from definitions. The "if" direction follows from the fact that at most finitely many sentence symbols of $\mathscr{S}$ can be involved in any deductive proof of the consequences of $\Sigma$, meaning that any contradiction deducible from $\Sigma$ is deducible from finitely many sentences of $\Sigma$. $\blacksquare$


Exercise 1. (Chang and Kiesler 2.1.13) If $T_1,T_2$ are two theories such that $T_1\cup T_2$ has no models, prove that there is a sentence $\varphi$ such that $T_1\vDash \varphi$ and $T_2\vDash\neg\varphi$. If $T_1,T_2$ are two theories such that $\mathfrak{A}$ is a model of $T_1$ iff it is not a model of $T_2$, then $T_1,T_2$ are finitely axiomatizable.

Proof. For the first part, suppose that $T_1,T_2$ are theories such that $T_1\cup T_2$ has no models, so that (by completeness ) $T_1\cup T_2\vDash \varphi\land\neg\varphi$ for some sentence $\varphi$. It follows by compactness that there is some finite set of sentences $\Sigma={\sigma_1,\cdots,\sigma_k}\subset T_1$ and $\Phi={\phi_1,\cdots,\phi_l}\subset T_2$ such that $\Sigma\cup\Phi\vDash \varphi\land\neg\varphi$. Thus, if we let we clearly have that $\Sigma\vDash \sigma$ since each $\sigma_i\in\Sigma$, whereas we also have that $\Phi\vDash\neg\sigma$ using a proof by contradiction. Hence, since $\Sigma\subset T_1$ and $\Phi\subset T_2$, we have $T_1\vDash\sigma$ and $T_2\vDash\neg\sigma$, as desired.

For the second part, suppose $T_1,T_2$ are two theories such that every model is a model of exactly one of $T_1,T_2$. This means that $T_1\cup T_2$ has no models, and therefore by the previous part, there exists a sentence $\sigma$ such that $T_1\vDash\sigma$ but $T_2\vDash\neg\sigma$. We can show that $\sigma$ entails all of $T_1$, for if it did not, there would exist (by completeness ) a model of $\sigma$ that is not a model of $T_1$, but such a model would have to be a model of $T_2$ and therefore a model of $\neg\sigma$, which is a contradiction. Similarly, we have that $\neg\sigma$ entails all of $T_2$, so that $\sigma$ is a finite axiomatization of $T_1$ and $\neg\sigma$ is a finite axiomatization of $T_2$.

As an aside: the philosophical significance of this statement is that it says the only way of "partitioning the class of possible universes" into two possibilities is with a single sentence. $\blacksquare$

model-theory

consistency

satisfiability

sentential-logic

first-order-logic

back to home page