Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:interpretation_quotient_under_congruence [2008/04/16 09:22] maysam |
sav08:interpretation_quotient_under_congruence [2012/05/01 16:03] vkuncak |
||
---|---|---|---|
Line 4: | Line 4: | ||
===== Example: quotient on pairs of natural numbers ===== | ===== Example: quotient on pairs of natural numbers ===== | ||
- | Let ${\cal N} = \{0,1,2,\ldots, \}$. Consider a structure with domain $N^2$, with functions | + | Let ${\cal N} = \{0,1,2,\ldots, \}$. Consider a structure with domain $N^2$, with functions (plus and minus): |
\[ | \[ | ||
p((x_1,y_1),(x_2,y_2)) = (x_1 + x_2, y_1 + y_2) | p((x_1,y_1),(x_2,y_2)) = (x_1 + x_2, y_1 + y_2) | ||
Line 15: | Line 15: | ||
r = \{((x_1,y_1),(x_2,y_2)) \mid x_1 + y_2 = x_2 + y_1 \} | r = \{((x_1,y_1),(x_2,y_2)) \mid x_1 + y_2 = x_2 + y_1 \} | ||
\] | \] | ||
- | is a congruence with respect to operations $p$ and $m$. | + | is a congruence with respect to operations $p$ and $m$. Indded, we can check that, for example, if $r((x_1,y_1),(x'_1,y'_1))$ and |
+ | $r((x_2,y_2),(x'_2,y'_2))$ then | ||
+ | \[ | ||
+ | r(p((x_1,y_1),(x_2,y_2)), p((x'_1,y'_1),(x'_2,y'_2))) | ||
+ | \] | ||
Congruence is an equivalence relation. What are equivalence classes for elements: | Congruence is an equivalence relation. What are equivalence classes for elements: | ||
Line 37: | Line 41: | ||
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? | 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 42: | Line 47: | ||
(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 |