This is an old revision of the document!
Axioms for Equality
For language and a relation symbol
, the theory of equality, denoted AxEq, is the following set of formulas:
Note: if an interpretation satisfies
, then we call
(the interpretation of eq) a congruence relation for
.
Example: quotient on pairs of natural numbers
Let . Consider a structure with domain
, 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 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 and
.
Congruence is an equivalence relation. What is the equivalence class for element ?
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? | where
is the set of integers.$
References
- Calculus of Computation Textbook, Section 3.1