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:axioms_for_equality [2008/04/02 00:42] vkuncak |
sav08:axioms_for_equality [2008/04/02 14:28] 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 \}$++ |
- | $[(10,1)] = $ ++| $\{ (x,y) \mid x=y+9 \}$ | + | $[(10,1)] = $ ++| $\{ (x,y) \mid x=y+9 \}$++ |
- | $[(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} | ||
\] | \] | ||
- | 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 consutrction to multiplication of strictly positive integers? | ||
===== References ===== | ===== References ===== | ||
* [[Calculus of Computation Textbook]], Section 3.1 | * [[Calculus of Computation Textbook]], Section 3.1 | ||