Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:interpretation_quotient_under_congruence [2008/04/02 22:20] vkuncak |
sav08:interpretation_quotient_under_congruence [2009/05/14 14:06] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Quotient of an Interpretation under a Congruence ====== | ====== Quotient of an Interpretation under a Congruence ====== | ||
+ | |||
===== Example: quotient on pairs of natural numbers ===== | ===== Example: quotient on pairs of natural numbers ===== | ||
Line 35: | Line 36: | ||
This construction is an algebraic approach to construct from natural numbers one well-known structure. Which one? ++| $({\cal Z}, + , -)$ where ${\cal Z}$ is the set of integers. ++ | This construction is an algebraic approach to construct from natural numbers one well-known structure. Which one? ++| $({\cal Z}, + , -)$ where ${\cal Z}$ is the set of integers. ++ | ||
- | Note: this construction can be applied whenever we have an associative and commutative operation $*$ satisfying the cancelation law $x * z = y * z \rightarrow x=y$. It allows us to contruct a structure where operation $*$ has an inverse. What do we obtain if we apply this construction to multiplication of strictly positive integers? | + | Note: this construction can be applied whenever we have an associative and commutative operation $*$ satisfying the cancelation law $x * z = y * z \rightarrow x=y$. It allows us to construct a structure where operation $*$ has an inverse. What do we obtain if we apply this construction to multiplication of strictly positive integers? |
===== Definition of Quotient of an Interpretation ===== | ===== Definition of Quotient of an Interpretation ===== | ||
Line 41: | Line 43: | ||
(Recall notation in [[First-Order Logic Semantics]].) | (Recall notation in [[First-Order Logic Semantics]].) | ||
- | Let $I = (D,\alpha)$ be an interpretation of language ${\cal L}$ with $eq \in {\cal L}$ for which [[Axioms for Equality]] hold, that is, $\alpha(eq)$ is a congruence relation for $I$. | + | Let $I = (D,\alpha)$ be an interpretation of language ${\cal L}$ with $eq \in {\cal L}$ for which [[Axioms for Equality]] hold, that is, $\alpha(eq)$ is a congruence relation for $I$. We will construct a new model $I_Q$. |
For each element $x \in D$, define | For each element $x \in D$, define | ||
Line 77: | Line 79: | ||
\] | \] | ||
- | **Lemma 1:** $I_Q = ([D],I_Q)$ is a well-defined interpretation, that is, | + | **Lemma 1:** For each function symbol $f$ with $ar(f)=n$, the relation $\alpha_Q(f)$ is a total function $[D]^n \to [D]$ and for all $x_1,\ldots,x_n \in D$, |
- | * $[D]$ is non-empty; | + | \[ |
- | * for each function symbol $f$ with $ar(f)=n$, the relation $\alpha_Q(f)$ is a total function $[D]^n \to [D]$. | + | \alpha_Q(f)([x_1],\ldots,[x_n]) = [\alpha(f)(x_1,\ldots,x_n)] |
+ | \] | ||
**Lemma 2:** For each term $t$ we have $e_T(t)(I_Q) = [e_T(t)(I)]$. | **Lemma 2:** For each term $t$ we have $e_T(t)(I_Q) = [e_T(t)(I)]$. |