This is an old revision of the document!

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 x_i = y_i) \rightarrow 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 x_i = y_i) \rightarrow (R(x_1,\ldots,x_n) \leftrightarrow R(y_1,\ldots,y_n))

Note: if an interpretation $(D,I)$ satisfies $AxEq$ , then we call $e_F(I)(eq)$ (the interpretation of eq) a congruence relation for $(D,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 is the equivalence class for element $(1,1)$ ?

$[(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 we can define operations $p$ and $m$ such that the following holds: \[ \begin{array}{l}

 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)]

\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.

References

Calculus of Computation Textbook, Section 3.1