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

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)$ .

References

Calculus of Computation Textbook, Section 3.1