Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:axioms_for_equality [2008/04/02 00:44] vkuncak |
sav08:axioms_for_equality [2008/04/02 00:47] vkuncak |
||
|---|---|---|---|
| Line 33: | Line 33: | ||
| is a congruence with respect to operations $p$ and $m$. | is a congruence with respect to operations $p$ and $m$. | ||
| - | Congruence is an equivalence relation. What is the equivalence class for element $(1,1)$? | + | Congruence is an equivalence relation. What are equivalence classes for elements: |
| $[(1,1)] = $ ++| $\{ (x,y) \mid x=y \}$++ | $[(1,1)] = $ ++| $\{ (x,y) \mid x=y \}$++ | ||
| Line 41: | Line 41: | ||
| $[(1,10)] = $ ++| $\{ (x,y) \mid x+9=y \}$++ | $[(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 we can define operations $p$ and $m$ such that the following holds: | + | 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} | \begin{array}{l} | ||
| - | p( [(x_1,y_1)] , [(x_2,y_2)] ) = [(x_1 + x_2, y_1 + y_2)] \\ | + | I_Q(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)] | + | I_Q(m)( [(x_1,y_1)] , [(x_2,y_2)] ) = [(x_1 + y_2, y_1 + x_2)] |
| \end{array} | \end{array} | ||
| \] | \] | ||