Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: mathematics

Topic: The Coincidence Lemma

Julius Hamilton (May 11 2024 at 21:03):

I was hoping for a small amount of supporting discussion about the significance of the Coincidence Lemma; what it’s “getting at”.

1C05EE2A-7CE7-407B-ACF2-B206E41FF2DB.png

5BC3D77E-9D65-40C0-B3E0-6C377887C054.png

As I understand it:

$S_1$ and $S_2$ are two distinct sets of symbols. Specifically, they are the function, relation, and constant symbols, from two alphabets $A_1$ and $A_2$. (The alphabets contain more symbols, like punctuation, variables, logical symbols, and quantifiers). I wonder if there is a term for these $S$-symbol sets - they are the symbols that “characterize” a given first-order language, since they are what varies from language to language. Since a “structure” is a mapping from these symbols to actual functions, relations, and values in a semantic domain, perhaps the elements of $S$ could be called “the structural symbols”?

$J_1$ and $J_2$ are 2 interpretations. An interpretation is defined as a tuple consisting of a structure $U$, and a variable assignment $B$. (I am curious why by convention we use the letter J for interpretations, U for structures, and B for variable assignments. Perhaps U stands for “universe”?)

As is given as a premise, $J_1 = (U_1, B_1)$ and $J_2 = (U_2, B_2)$ map into the same semantic domain $A$.

$S$ is defined as $S_1 \cap S_2$. It is not intuitively clear to me why we would want to define $S$. I think the coincidence lemma says, “Interpretations are identified with their symbol mappings; if they map symbols the same way, they are identical interpretations.” My guess is that this presentation leaves open the possibility that $S_1 \neq S_2$, and the lemma applies to terms and formula whose symbols are common to both. Still, I don’t feel I understand. The lemma doesn’t apply for when $S_1 \cap S_2 = \emptyset$. But it should apply if there is a certain isomorphism between $S_1$ and $S_2$. I don’t see why the emphasis on the symbols actually being the same.

The lemma then says:

(a) If $J_1$ and $J_2$ agree on the $S$-symbols occurring in an $S$-term $t$, and on the variables occurring in $t$, then $J_1(t) = J_2(t)$.

Since an interpretation is identified with a mapping of symbols, why is (a) not true by definition?

I think the point of the lemma is to establish a notation where you do not have to specify the variable assignment when expressing that something is a model of a formula. You can state that a structure is a model, instead of an interpretation.

But I don’t intuitively grasp why this proof was necessary.

John Baez (May 11 2024 at 21:10):

It's saying that if you have two interpretations that interpret a certain set of symbols and a certain set of variables the same way, they

i) give the same interpretation to terms that only involve the symbols and variables in the aforementioned sets, and

ii) agree on whether they entail a formula if that formula only involves the symbols and variables in the aforementioned sets.

I'm using the word "entail" for $\models$. I don't know what word your book uses.

John Baez (May 11 2024 at 21:12):

I agree with the book that this result is "intuitively clear". It's saying the interpretation of a term or formula only depends on the interpretation of those symbols and variables that are actually in that term or formula.

John Baez (May 11 2024 at 21:13):

I'd expect it to be proved inductively, and that's how they prove it.

Julius Hamilton (May 12 2024 at 15:33):

Thank you. I’ll reflect on your answer and respond when I feel more confident in my understanding.