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