LARA

Quotient of an Interpretation under a Congruence

Example: quotient on pairs of natural numbers

Let ${\cal N} = \{0,1,2,\ldots, \}$. Consider a structure with domain $N^2$, with functions (plus and minus):

\begin{equation*}
    p((x_1,y_1),(x_2,y_2)) = (x_1 + x_2, y_1 + y_2)
\end{equation*}

\begin{equation*}
    m((x_1,y_1),(x_2,y_2)) = (x_1 + y_2, y_1 + x_2)
\end{equation*}

Relation $r$ defined by

\begin{equation*}
   r = \{((x_1,y_1),(x_2,y_2)) \mid x_1 + y_2 = x_2 + y_1  \}
\end{equation*}

is a congruence with respect to operations $p$ and $m$. Indded, we can check that, for example, if $r((x_1,y_1),(x'_1,y'_1))$ and $r((x_2,y_2),(x'_2,y'_2))$ then

\begin{equation*}
     r(p((x_1,y_1),(x_2,y_2)), p((x'_1,y'_1),(x'_2,y'_2)))
\end{equation*}

Congruence is an equivalence relation. What are equivalence classes for elements:

$[(1,1)] = $

$[(10,1)] = $

$[(1,10)] = $

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{equation*}
\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}
\end{equation*}

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 $x * z = y * z \rightarrow x=y$. 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 $I = (D,\alpha)$ be an interpretation of language ${\cal L}$ with $eq \in {\cal L}$ for which Axioms for Equality hold, that is, $\alpha(eq)$ is a congruence relation for $I$. We will construct a new model $I_Q$.

For each element $x \in D$, define

\begin{equation*}
    [x] = \{ y \mid (x,y) \in \alpha(eq) \}
\end{equation*}

Let

\begin{equation*}
    [D] = \{ [x] \mid x \in D \}
\end{equation*}

The constructed model will be $I_Q = ([D],\alpha_Q)$ where

\begin{equation*}
    \alpha_Q(R) = \{ ([x_1],\ldots,[x_n]) \mid (x_1,\ldots,x_n) \in \alpha(R) \}
\end{equation*}

In particular, when $R$ is $eq$ we have

$\alpha_Q(eq) = $

Functions are special case of relations:

\begin{equation*}
    \alpha_Q(f) = \{ ([x_1],\ldots,[x_n],[x_{n+1}]) \mid (x_1,\ldots,x_n,x_{n+1}) \in \alpha(f) \}
\end{equation*}

Interpretation of variables is analogous to interpretation of constants:

\begin{equation*}
   \alpha_Q(x) = [\alpha(x)]
\end{equation*}

Lemma 0: For all $x_1,\ldots,x_n \in D$,

\begin{equation*}
    ([x_1],\ldots,[x_n]) \in \alpha_Q(R) \mbox{ iff }  (x_1,\ldots,x_n) \in \alpha(R)
\end{equation*}

Lemma 1: For each function symbol $f$ with $ar(f)=n$, the relation $\alpha_Q(f)$ is a total function $[D]^n \to [D]$ and for all $x_1,\ldots,x_n \in D$,

\begin{equation*}
    \alpha_Q(f)([x_1],\ldots,[x_n]) = [\alpha(f)(x_1,\ldots,x_n)]
\end{equation*}

Lemma 2: For each term $t$ we have $e_T(t)(I_Q) = [e_T(t)(I)]$.

Theorem: For each formula $F$ that contains no '=' symbol, we have $e_F(F)(I) = e_F(F)(I_Q) = e_F(F_0)(I_Q)$ where $F_0$ is result of replacing 'eq' with '=' in $F$.