first-order theory

In what follows, references to sentences and sets of sentences areall relative to some fixed first-order language $L$.

Definition. A theory $T$ is a deductivelyclosed set of sentences in $L$; that is, a set $T$ such that for eachsentence $\phi$, $T⊢\phi$ only if $\phi \in T$.

Remark. Some authors do not require that a theory be deductively closed. Therefore, a theory is simply a set of sentences. This is not a cause for alarm, since every theory $T$ under this definition can be “extended” to a deductively closed theory $T^{⊢}:=\{\phi \in L\mid T⊢\phi \}$. Furthermore, $T^{⊢}$ is unique (it is the smallest deductively closed theory including $T$), and any structure $M$ is a model of $T$ iff it is a model of $T^{⊢}$.

Definition. A theory $T$ is consistent if and onlyif for some sentence $\phi$, $T⊬\phi$.Otherwise, $T$ is inconsistent. A sentence$\phi$ is consistent with $T$ if and only if thetheory $T\cup \{\phi \}$ is consistent.

Definition. A theory $T$ is complete if and onlyif $T$ is consistent and for each sentence $\phi$, either $\phi \in T$or $\mathrm{\neg }\phi \in T$.

Lemma. A consistent theory $T$ is complete if and only if $T$ ismaximally consistent. That is, $T$ is complete if and only if foreach sentence $\phi$, $\phi \notin T$ only if$T\cup \{\phi \}$ is inconsistent. See this entry (http://planetmath.org/MaximallyConsistent) for a proof.

Theorem. (Tarski) Every consistent theory $T$ is includedin a complete theory.

Proof : Use Zorn’s lemma on the set of consistenttheories that include $T$.

Remark. A theory $T$ is axiomatizable if and onlyif $T$ includes a decidable (http://planetmath.org/DecidableSet) subset $\mathrm{\Delta }$ such that $\mathrm{\Delta }⊢T$ (every sentence of $T$ is a logical consequence of$\mathrm{\Delta }$), and finitely axiomatizable if $\mathrm{\Delta }$ can be made finite. Every complete axiomatizable theory $T$ is decidable;that is, there is an algorithm that given a sentence $\phi$ asinput yields $0$ if $\phi \in T$, and $1$ otherwise.