Differences

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

--- sav08:axioms_for_equality [2008/04/02 21:27]
vkuncak
+++ sav08:axioms_for_equality [2009/05/06 09:52]
vkuncak
@@ Line 1: / Line 1: @@
 ====== Axioms for Equality ======
+The following definitions are useful when axiomatizing equality in a logic that does not have equality built in. It is also useful when discussing algorithms that automate reasoning about equality.
 For language ${\cal L}$ and a relation symbol $eq \notin {\cal L}$, the theory of equality, denoted AxEq, is the following set of formulas:
@@ Line 18: / Line 20: @@
 **Definition:** if an interpretation $I = (D,\alpha)$ the axioms $AxEq$ are true, then we call $\alpha(eq)$ (the interpretation of eq) a //congruence// relation for interpretation $I$.
-**A terminological note:** in algebra, an interpretation is often called a //structure//. Instead of using $\alpha$ mapping language ${\cal L} = \{ f_1,\ldots,f_n, R_1,\ldots,R_m\}$ to interpretation of its symbols, the structure is denoted by a tuple $(D,\alpha(f_1),\ldots,\alpha(f_n),\alpha(R_1),\ldots,\alpha(R_n))$.  For example, an interpretation with domain ${\can N}$, with one binary operation whose interpretation is $+$ and one binary relation whose interpretation is $\leq$ can be written as $({\cal N},+,\leq)$.  This way we avoid writing $\alpha$ all the time, but it becomes more cumbersome to describe correspondence between structures.
+**Side remark:** Functions are relations.  However, the condition above for function symbols is weaker than the condition for relation symbols.  If $f$ is a function, then the relation $\{(x_1,\ldots,x_n,f(x_1,\ldots,x_n)) \mid x_1,\ldots,x_n \in D \}$ does not satisfy the congruence condition because it only has one result, namely $f(x_1,\ldots,x_n)$, and not all the results that are in relation eq with $f(x_1,\ldots,x_n)$. However, if we start from the condition for functions and treat relations as functions that return true or false, we obtain the condition for relations. So, it makes sense here to treat relations as a special case of functions.
-=== 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 contruct a structure where operation $*$ has an inverse.  What do we obtain if we apply this construction to multiplication of strictly positive integers?
 ===== References =====
   * [[Calculus of Computation Textbook]], Section 3.1