LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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