# Quotient of an Interpretation under a Congruence

## Example: quotient on pairs of natural numbers

Let . Consider a structure with domain , with functions (plus and minus):  Relation defined by is a congruence with respect to operations and . Indded, we can check that, for example, if and then Congruence is an equivalence relation. What are equivalence classes for elements:   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 define operations and such that the following holds: This construction is an algebraic approach to construct from natural numbers one well-known structure. Which one?

Note: this construction can be applied whenever we have an associative and commutative operation satisfying the cancelation law . It allows us to construct a structure where operation has an inverse. What do we obtain if we apply this construction to multiplication of strictly positive integers?

## Definition of Quotient of an Interpretation

(Recall notation in First-Order Logic Semantics.)

Let be an interpretation of language with for which Axioms for Equality hold, that is, is a congruence relation for . We will construct a new model .

For each element , define Let The constructed model will be where In particular, when is we have Functions are special case of relations: Interpretation of variables is analogous to interpretation of constants: Lemma 0: For all , Lemma 1: For each function symbol with , the relation is a total function and for all , Lemma 2: For each term we have .

Theorem: For each formula that contains no '=' symbol, we have where is result of replacing 'eq' with '=' in .