A step in the completeness proof of first-order logic

Question

In Enderton's Mathematical Logic, in presenting the completeness proof for first-order logic he constructs a maximally consistent set of sentences $\Delta$ and then a structure from this. He writes:

We now make from $\Delta$ a structure $\mathfrak{A}$ for the new language, but with the equality symbol (if any) replaced by a new two-place predicate symbol $E$. $\mathfrak{A}$ will not itself be the structure in which $\Gamma$ will be satisfied but will be a preliminary structure.

He then writes the following after constructing the structure:

If our original language did not include the equality symbol, then we are done. For we need only restrict $\mathfrak{A}$ to the original language to obtain a structure that satisfies every member of $\Gamma$ with the identity function.

But now assume that the equality symbol is in the language. Then $\mathfrak{A}$ will no longer serve. For example, if $\Gamma$ contains the sentence $c=d$ (where $c$ and $d$ are distinct constant symbols), then we need a structure $\mathfrak{B}$ in which $c^{\mathfrak{B}} = d^{\mathfrak{B}}$. We obtain $\mathfrak{B}/E$ as the quotient structure $\mathfrak{A}/E$ of $\mathfrak{A}$ modulo $E$.

Firstly, what is meant by ''a structure that satisfies every member of $\Gamma$ with the identity function?''. I don't really understand what he means by this first quotation.

Secondly, why is a quotient structure chosen, as opposed to some other structure which is not a quotient structure?

Answer 1

I'm going to address your questions directly by paraphrasing the explanations given in https://builds.openlogicproject.org/courses/enderton/open-logic-enderton.pdf on pages 121 and 127-129.

To answer your first question: a structure that satisfies every member of Γ with the identity function describes a model that satisfies (makes true) all sentences in $\Gamma$ containing the predicate (identity) symbol =. The point is that the term models used hitherto in the completeness proof for languages without identity will not suffice for that task. Why not? This is explained as part of the answer to your second question (below).

To answer your second question: the predicate symbol = has a fixed interpretation: $\vDash_{\mathfrak A} t=t'$ iff $t^{\mathfrak A}=t'^{\mathfrak A}$. Now, since the term model $\mathfrak A$ has been set up in a way so that the value of a term $t$ is $t$ itself, then $\mathfrak A$ will make no sentence of the form $t = t′$ true unless $t$ and $t′$ are one and the same term. For instance, consider a theory of arithmetic and the provable formula $(0 + 0) = 0$. This is not going to be true in $\mathfrak A$ since $(0 + 0)$ and $0$ are distinct objects in the domain of $\mathfrak A$.

To solve this problem, we change the domain of $\mathfrak A$ as follows. Instead of using terms as the objects in the domain of $\mathfrak A$, we use sets of terms, and each set is fashioned in a way as to contain all those terms which the sentences in $\Gamma$ require to be equal. So, for instance, if $\Gamma$ is a theory of arithmetic, one of these sets will contain: $0, (0 + 0), (0 × 0)$, etc. This will be the set we assign to $0$, and it will turn out that this set is also the value of all the terms in it, e.g., also of $(0+0)$. Therefore, the sentence $(0+0) = 0$ will be true in this revised structure $\mathfrak B$.

That revised structure will be much like $\mathfrak A$ with the addition of a predicate $E$ that is an equivalence relation, partitioning the domain of $\mathfrak A$ into equivalence classes of objects stipulated as identical in $\Gamma$, i.e. $E(t,t')$ iff $t=t' \in \Gamma$. That is, $\mathfrak B = \mathfrak A /E$. Now, $\mathfrak A /E$ is just the structure $\mathfrak B$ stipulated by the statement you wished explained in the first question. This is because even for distinct terms $t$ and $t'$, such that $t=t' \in \Gamma$, now we have $[t]_E = [t']_E$, i.e. $t^{\mathfrak A /E} = t'^{\mathfrak A /E}$. That is, we have $t=t' \in \Gamma$ iff $t^{\mathfrak B} = t'^{\mathfrak B}$ iff $\vDash_{\mathfrak B} t=t'$, as required.

A quotient stucture is used here since it offers plenty with little effort. That is, it's the least amount of change in the featured Henkin (term model) approach that succesfully makes the required amendments for identity, whilst preserving the results for languages without identity.

Answer 2

I don't have a copy of Enderton. I can see what those two quotations mean in isolation, but I don't know their overall role within the proof of completeness in that book.

There are two approaches to defining the semantics of $=$.

One is to say that $M, \vec{v} \models x = y$ where $\vec{v}$ is a mapping from variables including $x$ and $y$ to their interpretations, is true if and only if $\vec{v}_x$ is the same as $\vec{v}_y$, i.e. the variable mapping $\vec{v}$ sends both $x$ the symbol and $y$ the symbol to the same element of the domain.

Let's call this semantics equality is real sameness.

Another interpretation is to treat $=$ just like any other binary predicate, with some additional rules it has to satisfy, namely:

• $=$ is symmetric, transitive, and reflexive.
• For all relations $R$, $\vec{x} = \vec{y}$ and $R(\vec{x})$ imply $R(\vec{y})$.
• For all functions $f$, $\vec{x} = \vec{y}$ and $f(\vec{x}) = z$ imply $f(\vec{y}) = z$.

Here I'm treating a constant symbol as a nullary function.

Intuitively, this means that $=$ is an equivalence relation and no functions or relations in the vocabulary can distinguish two elements $p$ and $q$ if it holds that $p = q$.

Let's call this semantics equal elements are indistinguishable.

Enderton uses the real sameness semantics, like all modern books.

However, in this step, they're building a structure with a new predicate $E$ that satisfies the same rules that $=$ does in the indistinguishable semantics.

They are then quotienting by $E$ to produce a model in which $E$ has the same truth conditions as real equality.

Here's an example:

Suppose we are interested in the integers mod 3, $\mathbb{Z}/3\mathbb{Z}$.

In the real sameness semantics, we might pick $\{0, 1, 2\}$ as our model and define addition, negation, and multiplication using a table.

In the indistinguishable semantics, we can pick $\mathbb{Z}$ as our domain and say that $a = b$ holds when $a - b$ is divisible by $3$ in $\mathbb{Z}$.

So, if we wanted to compute $1 + 1 + 1 + 2 + 1$ in the indistinguishable semantics, we can do

$$ 1 + 1 + 1 + 2 + 1 \\ 2 + 1 + 2 + 1 \\ 3 + 3 \\ 6 \\ 0 $$

$0, 3, 6$ are not the same in the underlying domain, but $0 = 3$, $0 = 6$, $3 = 6$, and so on are true in the structure $\mathbb{Z}/3\mathbb{Z}$.

Arguably the indistinguishable semantics is kind of confusing and unnecessary, hence why it isn't used anymore in textbooks.

1. It makes $=$ different from real sameness in a way that's subtle and hard to describe.
2. You can always quotient by $=$ anyway if you're using the indistinguishable semantics.