This is an old revision of the document!
First-Order Theories
Definition: A first-order theory is a set of 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 sentences that are true in all interepretations of
, 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?