Generated equivalence relations in logics

64 Views Asked by At

Let $L$ be some logic (FO or stronger which is not important for this purpose). Given a $\tau$-structure $A$ and a formula $\varphi(x_1, \dots x_n) \in L[\tau]$ with free variables $x_1, \dots, x_n$. We introduce the following notation

$$ \varphi[A,x_1, \dots x_n] := \{ (x_1, \dots,x_n) \in V(A)^n \mid (A,x_1, \dots x_n) \models \varphi \}$$

where $V(A)$ is the universe of $A$. This is basically the set of all assignments for variables $x_1, \dots, x_n$ which satisfy the formula.

Now consider the a formula $\psi(x,y) \in L[\tau]$ and $\tau$-structure $A$.

$\psi[A, x, y]$ defines a binary relation on $V(A)$.

The following part is a definition I am not sure I understand:

We denote the symmetric, reflexive, transitive closure of $\psi[A,x,y]$ by $\equiv_\psi$. We say $\equiv_\psi$ is the equivalence relation generated by $\psi[A,x,y]$.

Okay given $V(A):=\{1,2,3\}$ and $\tau=\{S\}$ where $S$ is the successor relation and $\psi(x,y) = x < y$.

I can see that e.g. $1 \equiv_\psi 3$. However, I don't think that $\equiv_\psi$ is a equivalence relation since $1 \not \equiv 1$... Where is the mistake? Is the definition not well-defined? Does it only refer to those $\psi$ where $\equiv_\psi$ is in fact a equivalence relation? Any ideas?

1

There are 1 best solutions below

0
On BEST ANSWER

Note that it is required that $\equiv_\psi$ is the symmetric, REFLEXIVE, transitive closure of $\psi$. So even if $\psi$ is not reflexive, $\equiv_\psi$ is. In particular, even if $\psi$ is the less-than relation (not reflexive), we will still have $1 \equiv_\psi 1$.