| Version 10 |
Version 9 |
| In what follows, references to sentences and sets of sentences are |
In what follows, references to sentences and sets of sentences are |
| all relative to some fixed first-order language.\\ |
all relative to some fixed first-order language.\\ |
|
|
| \textbf{Definition.} A \textbf{theory} $T$ is a \emph{deductively |
\textbf{Definition.} A \textbf{theory} $T$ is a \emph{deductively |
| closed} set of sentences; that is, a set $T$ such that for each |
closed} set of sentences; that is, a set $T$ such that for each |
| sentence $\varphi$, $T \models \varphi$ only if $\varphi \in |
sentence $\varphi$, $T \models \varphi$ only if $\varphi \in |
| T$.\\ |
T$.\\ |
|
|
| \textbf{Definition.} A theory $T$ is \emph{consistent} if and only |
\textbf{Definition.} A theory $T$ is \emph{consistent} if and only |
| if for some sentence $\varphi$, $T \not \models \varphi$. |
if for some sentence $\varphi$, $T \not \models \varphi$. |
| Otherwise, $T$ is \emph{inconsistent}. A sentence |
Otherwise, $T$ is \emph{inconsistent}. A sentence |
| $\varphi$ is \emph{consistent with $T$} if and only if the |
$\varphi$ is \emph{consistent with $T$} if and only if the |
| theory $T \cup \lbrace \varphi \rbrace$ is consistent.\\ |
theory $T \cup \lbrace \varphi \rbrace$ is consistent.\\ |
|
|
| \textbf{Definition.} A theory $T$ is \emph{complete} if and only |
\textbf{Definition.} A theory $T$ is \emph{complete} if and only |
| if for each sentence $\varphi$, either $\varphi \in T$ |
if for each sentence $\varphi$, either $\varphi \in T$ |
| or $\neg \varphi \in T$.\\ |
or $\neg \varphi \in T$.\\ |
|
|
| \textbf{Lemma.} A theory $T$ is complete if and only if $T$ is |
\textbf{Lemma.} A theory $T$ is complete if and only if $T$ is |
| maximally consistent. That is, $T$ is complete if and only if for |
maximally consistent. That is, $T$ is complete if and only if for |
| each sentence $\varphi$, $\varphi \not \in T$ only if |
each sentence $\varphi$, $\varphi \not \in T$ only if |
| $T \cup \lbrace \varphi \rbrace$ is inconsistent.\\ |
$T \cup \lbrace \varphi \rbrace$ is inconsistent.\\ |
|
|
| \textbf{Theorem. (Tarski)} Every consistent theory $T$ is included |
\textbf{Theorem. (Tarski)} Every consistent theory $T$ is included |
| in a complete theory. |
in a complete theory. |
|
|
| \textbf{Proof :} Use Zorn's lemma on the set of consistent |
\textbf{Proof :} Use Zorn's lemma on the set of consistent |
| theories that include $T$.\\ |
theories that include $T$.\\ |
|
|
| \textbf{Remark}. A theory $T$ is \emph{axiomatizable} if and only |
\textbf{Remark}. A theory $T$ is \emph{axiomatizable} if and only |
|
if $T$ includes a \PMlinkname{decidable}{DecidableSet} subset $\Delta$ such that $\Delta
|
if $T$ includes a decidable subset $\Delta$ such that $\Delta
|
| \models T$ (every sentence of $T$ is a logical consequence of |
\models T$ (every sentence of $T$ is a logical consequence of |
| $\Delta$). Every complete axiomatizable theory $T$ is decidable; |
$\Delta$). Every complete axiomatizable theory $T$ is decidable; |
| that is, there is an algorithm that given a sentence $\varphi$ as |
that is, there is an algorithm that given a sentence $\varphi$ as |
| input yields $0$ if $\varphi \in T$, and $1$ otherwise. |
input yields $0$ if $\varphi \in T$, and $1$ otherwise. |
