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

Definition. A theory $T$ is a deductively closed set of sentences in $L$ ; that is, a set $T$ such that for each sentence $\varphi$ , $T \vdash \varphi$ only if $\varphi \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^{\vdash}:=\lbrace \varphi \in L\mid T\vdash \varphi\rbrace$ . Furthermore, $T^{\vdash}$ 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^{\vdash}$ .

Definition. A theory $T$ is consistent if and only if for some sentence $\varphi$ , $T \not \vdash \varphi$ . Otherwise, $T$ is inconsistent. A sentence $\varphi$ is consistent with $T$ if and only if the theory $T \cup \lbrace \varphi \rbrace$ is consistent.

Definition. A theory $T$ is complete if and only if $T$ is consistent and for each sentence $\varphi$ , either $\varphi \in T$ or $\neg \varphi \in T$ .

Lemma. A consistent theory $T$ is complete if and only if $T$ is maximally consistent. That is, $T$ is complete if and only if for each sentence $\varphi$ , $\varphi \not \in T$ only if $T \cup \lbrace \varphi \rbrace$ is inconsistent.

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

Proof : Use Zorn's lemma on the set of consistent theories that include $T$ .

Remark. A theory $T$ is axiomatizable if and only if $T$ includes a decidable subset $\Delta$ such that $\Delta \vdash T$ (every sentence of $T$ is a logical consequence of $\Delta$ ), and finitely axiomatizable if $\Delta$ can be made finite. Every complete axiomatizable theory $T$ is decidable; that is, there is an algorithm that given a sentence $\varphi$ as input yields $0$ if $\varphi \in T$ , and $1$ otherwise.