Differences

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

--- sav08:axioms_for_equality [2008/04/02 21:28]
vkuncak moved terminological note to semantics of FOL
+++ sav08:axioms_for_equality [2015/04/21 17:30]
@@ Line 1: / Line 1: @@
-====== Axioms for 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:
-  * Reflexivity: ++| $\forall x. eq(x,x)$ ++
-  * Symmetry: ++| $\forall x. \forall y.\ eq(x,y) \rightarrow eq(y,x)$ ++
-  * Transitivity: ++| $\forall x. \forall y. \forall z.\ eq(x,y) \land eq(y,z) \rightarrow eq(x,z)$ ++
-  * Congruence for function symbols: for $f \in {\cal L}$ function symbol with $ar(f)=n$, ++ |
-\[
-   \forall x_1,\ldots,x_n, y_1,\ldots,y_n.\ (\bigwedge_{i=1}^n eq(x_i,y_i)) \rightarrow eq(f(x_1,\ldots,x_n),f(y_1,\ldots,y_n))
-\]
-++
-  * Congruence for relation symbols: for $R \in {\cal L}$ relation symbol with $ar(R)=n$, ++ |
-\[
-   \forall x_1,\ldots,x_n, y_1,\ldots,y_n.\ (\bigwedge_{i=1}^n eq(x_i,y_i)) \rightarrow (R(x_1,\ldots,x_n) \leftrightarrow R(y_1,\ldots,y_n))
-\]
-++
-**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$.
-=== 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