The only congruence is the identity congruence [From Algebraic Methods in Philosophical Logic, Dunn and Hardegree]

congruence-relationslogicuniversal-algebra

In the book "Algebraic Methods in Philosophical Logic" by Dunn and Hardegree I was very much confused by the remark 2.6.7 on page 22.

In this book a relational structure $\mathbf{A}$ is defined as a set $A$, together with a family $\langle R_i\rangle$ of relations on $A$.

Then the following definition is given for a congruence relation:

Let $\mathbf{A}$ be any relational structure with relations $\langle R_i\rangle$, and let $\equiv$ be any equivalence relation on $A$. Then $\equiv$ is said to be a congruence relation on $\mathbf{A}$ if it satisfies the following condition, for all $i$:

(RP*) If $a_1 \equiv b_1$ and $\ldots$ and $a_n \equiv b_n$, and $\langle a_1, \ldots, a_n, x\rangle \in R_i$, then there exists $y$ such that $x \equiv y$ and $\langle b_1, \ldots, b_n, y\rangle \in R_i$.

The remark 2.6.7 is then the following:

It is best to think of the above fact [about complex replacement being equivalent to atomic replacement] as applying to first-order logic without identity. The reason to exclude identity is that otherwise the following is an instance of (RP*): if $a\equiv b$ and $a=x$, then $b = x$.
From this we get as an instance: if $a\equiv b$ and $a=a$, then $b=a$. From which it can immediately be concluded: if $a\equiv b$, then $b = a$. So the only congruence is the identity congruence on the algebra.

My confusion is as follows:

  • Why is the instance of (RP*) not "if $a\equiv b$ and $a=x$, then $x\equiv y$ and $b = y$"? If this is the case then surely there is no problem in considering first-order logic with identity?

Additional, maybe related, maybe irrelevant, confusions are

  • Why do they talk about the "identity congruence on the algebra"? (RP*) was defined for relational structures, not algebras (i.e. operational structures), so why the use of the word algebra?
  • Why talk about first-order logic without identity? So far in the book not much has been said about logics past the introduction. Do they just mean "operational structure without indentity"?

Many thanks for any help or pointers!

Best Answer

I think you're right and you've found a confusion in the book.

The usual definition of a congruence on a relational structure would not have the condition (RP*) that you quoted but rather (RP#): If $a_1\equiv b_1,\dots,a_n\equiv b_n$ and $R_i(a_1,\dots,a_n)$ then $R_1(b_1,\dots,b_n)$. (Here $n$ is the number of argument places of $R_i$.) This (RP#) would indeed have the claimed, undesirable consequence if equality were one of the relations $R_i$. Indeed, using (RP#) with equality as $R_i$, we'd be able to infer from $x\equiv y$ (taking $a_1,b_1,a_2$ all to be $x$ and taking $b_2$ to be $y$) that $x=y$. So the equivalence relation $\equiv$ could only be equality.

The book's unusual requirement (RP*) seems to be designed specifically for the situation where each $R_i$ (now having $n+1$ argument places) is intended to represent an $n$-place function. As far as I can see, it does not cause any problem when the equality relation is among the relations $R_i$.

Also, "intended to represent an $n$-place function" might explain the use of the word "algebra". It looks to me as if the authors were sometimes thinking of algebras and sometimes of relational structures, and the two topics got mixed together confusingly.

Related Question