LARA

Differences

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

Link to this comparison view

sav08:interpretation_quotient_under_congruence [2009/05/14 14:06]
vkuncak
sav08:interpretation_quotient_under_congruence [2015/04/21 17:30]
Line 1: Line 1:
-====== Quotient of an Interpretation under a Congruence ====== 
- 
- 
-===== Example: quotient on pairs of natural numbers ===== 
- 
-Let ${\cal N} = \{0,​1,​2,​\ldots,​ \}$.  Consider a structure with domain $N^2$, with functions 
-\[ 
-    p((x_1,​y_1),​(x_2,​y_2)) = (x_1 + x_2, y_1 + y_2) 
-\] 
-\[ 
-    m((x_1,​y_1),​(x_2,​y_2)) = (x_1 + y_2, y_1 + x_2) 
-\] 
-Relation $r$ defined by 
-\[ 
-   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$.  ​ 
- 
-Congruence is an equivalence relation. ​ What are equivalence classes for elements: 
- 
-$[(1,1)] = $ ++| $\{ (x,y) \mid x=y \}$++ 
- 
-$[(10,1)] = $ ++| $\{ (x,y) \mid x=y+9 \}$++ 
- 
-$[(1,10)] = $ ++| $\{ (x,y) \mid x+9=y \}$++ 
- 
-Whenever we have a congruence in an interpretation,​ we can shrink the structure to a smaller one by merging elements that are in congruence.  ​ 
- 
-In the resulting structure $([N^2], I_Q)$ we define operations $p$ and $m$ such that the following holds: 
-\[ 
-\begin{array}{l} 
-   ​I_Q(p)( [(x_1,y_1)] , [(x_2,y_2)] ) = [(x_1 + x_2, y_1 + y_2)] \\ 
-   ​I_Q(m)( [(x_1,y_1)] , [(x_2,y_2)] ) = [(x_1 + y_2, y_1 + x_2)]  
-\end{array} 
-\] 
-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 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 ===== 
- 
-(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$. We will construct a new model $I_Q$. 
- 
-For each element $x \in D$, define 
-\[ 
-    [x] = \{ y \mid (x,y) \in \alpha(eq) \} 
-\] 
-Let 
-\[ 
-    [D] = \{ [x] \mid x \in D \} 
-\] 
-The constructed model will be $I_Q = ([D],​\alpha_Q)$ where  
-\[ 
-    \alpha_Q(R) = \{ ([x_1],​\ldots,​[x_n]) \mid (x_1,​\ldots,​x_n) \in \alpha(R) \} 
-\] 
-In particular, when $R$ is $eq$ we have 
- 
-$\alpha_Q(eq) = $ ++| $\{ ([x_1],​[x_2]) \mid (x_1,x_2) \in \alpha(eq) \} = \{ (a,a) \mid a \in D \}$ 
- 
-that is, the interpretation of eq in $([D],I_Q)$ is diagonal relation - equality. 
-++ 
- 
-Functions are special case of relations: 
-\[ 
-    \alpha_Q(f) = \{ ([x_1],​\ldots,​[x_n],​[x_{n+1}]) \mid (x_1,​\ldots,​x_n,​x_{n+1}) \in \alpha(f) \} 
-\] 
- 
-Interpretation of variables is analogous to interpretation of constants: 
-\[ 
-   ​\alpha_Q(x) = [\alpha(x)] 
-\] 
- 
-**Lemma 0:** For all $x_1,​\ldots,​x_n \in D$, 
-\[ 
-    ([x_1],​\ldots,​[x_n]) \in \alpha_Q(R) \mbox{ iff }  (x_1,​\ldots,​x_n) \in \alpha(R) 
-\] 
- 
-**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$, 
-\[ 
-    \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)]$. 
- 
-**Theorem:​** For each formula $F$ that contains no '​='​ symbol, we have $e_F(F)(I) = e_F(F)(I_Q) = e_F(F_0)(I_Q)$ where $F_0$ is result of replacing '​eq'​ with '​='​ in $F$.