This is an old revision of the document!
First-Order Theories
(Building on First-Order Logic Semantics.)
Definition: A first-order theory is a set of first-order logic sentences.
Definition: A theory is consistent if it is satisfiable.
Definition: A theory is complete if for every closed first-order formula , either or .
We have two main ways of defining theories: by taking a specific set of structures and looking at sentences true in these structures, or by looking at a set of axioms and looking at their consequences.
Definition: If is a set of interpretations, then the theory of is the set of formulas that are true in all interepretations from , that is .
Note that is equivalent to .
Lemma: For any interpretation , the theory is complete.
Definition (axiomatization of a theory): We say that is an axiomatization of iff . Axiomatization is finite if is a finite set. Axiomatization is recursive if it is a recursive set.
Example: Theory of Partial Orders
Consider the language where is a binary relation. Consider the following three sentences: \[\begin{array}{rcl}
Ref & \equiv & \forall x. x \le x \\ Sym & \equiv & \forall x.\ x \le y \land y \le x \rightarrow x=y \\ Tra & \equiv & \forall x. \forall y.\ \forall z. x \le y \land y \le z \rightarrow x \le z
\end{array} \] Let . Let us answer the following:
- Is consistent?
- Is complete?