Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:first-order_theories [2008/03/19 15:13] vkuncak |
sav08:first-order_theories [2008/04/15 13:46] vkuncak |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| (Building on [[First-Order Logic Semantics]].) | (Building on [[First-Order Logic Semantics]].) | ||
| - | **Definition:** A //first-order theory// is a set $T$ of [[First-Order Logic Syntax|sentences]]. | + | **Definition:** A //first-order theory// is a set $T$ of [[First-Order Logic Syntax|first-order logic sentences]]. |
| **Definition:** A theory $T$ is //consistent// if it is satisfiable. | **Definition:** A theory $T$ is //consistent// if it is satisfiable. | ||
| Line 11: | Line 11: | ||
| 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. | 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 ${\cal I}$ is a set of interpretations, then the theory of ${\cal I}$ is the set of sentences that are true in all interepretations of ${\cal I}$, that is $Th({\cal I}) = \{ F \mid \forall I \in {\cal I}. e_F(F)(I)\}$. | + | **Definition:** If ${\cal I}$ is a set of interpretations, then the theory of ${\cal I}$ is the set of formulas that are true in all interepretations from ${\cal I}$, that is $Th({\cal I}) = \{ F \mid \forall I \in {\cal I}. e_F(F)(I)\}$. |
| Note that $F \in Th(\{I\})$ is equivalent to $e_F(F)(I)$. | Note that $F \in Th(\{I\})$ is equivalent to $e_F(F)(I)$. | ||
| Line 30: | Line 30: | ||
| Let $T = Conseq(\{Ref,Sym,Tra\})$. Let us answer the following: | Let $T = Conseq(\{Ref,Sym,Tra\})$. Let us answer the following: | ||
| * Is $T$ ++consistent?|Yes, take, for example, ordering on integers.++ | * Is $T$ ++consistent?|Yes, take, for example, ordering on integers.++ | ||
| - | * Is $T$ ++complete?|No, take, for example, $\exists x. \forall y. x \le y$.++ | + | * Is $T$ ++complete?|No, take, for example, $\exists x. \forall y. x \le y$. It is true with the ordering on $\mathbb{N}$, but false with the ordering on $\mathbb{Z}$.++ |