# 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:

Let . Let us answer the following:

• Is consistent?
• Is complete?