# Model theory substitution notation

Let $$\mathcal M$$ be a structure in language $$\mathcal L$$ and let expanded language $$\mathcal L_\mathcal M$$ be the language with added constants $$c_a$$ for $$a \in \mathcal M$$.

I thought I understood notation but I keep finding myself questioning if my understanding is actually accurate. We write $$\phi(a_1, \dots, a_n)$$ as shorthand notation for the substitutions $$\phi[x_1 / c_{a_1}, \dots, x_n / c_{a_n}]$$. Now if we write $$\mathcal M \models \phi (a_1, \dots, a_n)$$, what does this precisely mean? It was my understanding that for satisfaction, ex. $$\mathcal M \models \psi$$, $$\psi$$ is a sentence so all variables are bound and none can be substituted. Does this mean before the substitution $$\phi$$ has free variables $$x_1, \dots, x_n$$ and after the substition $$\phi(a_1, \dots, a_n)$$ is a sentence?

On a related note, what does $$\phi(c_{a_1}, \dots, c_{a_n})$$ in the expanded language mean? Is it the same result as $$\phi(a_1, \dots, a_n)$$, that is a sentence with constants $$c_{a_1}, \dots, c_{a_n}$$?

• You are right: $a$ is an "object", i.e. an element of the domain, and $c_a$ is a constant, i.e. a term of the language. Maybe the author want to stress the "subtle" difference between substituting a variable with a constant, i.e. an operation in the language, where the constant denote an object, i.e. a relation between language and "reality". – Mauro ALLEGRANZA Apr 27 '20 at 6:08

There is a subtle difference between constant symbols in a language and the elements of a structure.

Let's start with a language, the language of groups. So we have a binary function symbol $$m(x,y)$$ for multiplication and a constant $$e$$ for the identity element. Any structure in this language should assign an element to this constant (and an operation to the function symbol). For example, in the additive group $$\mathbb{Z}$$ the element $$0$$ is assigned to $$e$$, but in the multiplicative group $$\mathbb{Q} - \{0\}$$ the element $$1$$ is assigned.

Now jump to satisfaction of sentences. If $$\mathcal{M}$$ is an $$\mathcal{L}$$-structure and $$\varphi(x_1, \ldots, x_n)$$ is an $$\mathcal{L}$$-formula, then of course it would not really make sense to write $$\mathcal{M} \models \varphi(x_1, \ldots, x_n)$$ (see also footnote). In our example of the language of groups we could take the formula $$m(x_1, x_2) = e$$, what would $$\mathcal{M} \models m(x_1, x_2) = e$$ mean? Of course, this makes sense once we plug in elements from $$\mathcal{M}$$ for the free variables $$x_1$$ and $$x_2$$.

For example, for the multiplicative group $$\mathbb{Q}$$, asking whether or not $$\mathbb{Q} \models m(1/3, 3) = e$$ makes perfect sense. But we have to replace the symbols in our language by their interpretations first to give a final answer to this question. Doing that we arrive at "$$1/3 \cdot 3 = 1$$", which is true, so indeed $$\mathbb{Q} \models m(1/3, 3) = e$$. Note that "$$m(1/3, 3) = e$$" is no longer a formula (or sentence) in our language, so it will generally not make sense in any other structure (e.g. it does not make sense in $$\mathbb{Z}$$). But when replacing free variables by elements, and replacing all symbols by their interpretations, we can turn a formula in a statement that can be true or false in our structure. This is what $$\mathbb{Q} \models m(1/3, 3) = e$$ means, or more generally $$\mathcal{M} \models \varphi(a_1, \ldots, a_n)$$.

What often happens in model theory, is that we wish to fix some elements of a structure as parameters and act as if they were in the language in the first place. Formally what happens is this. Let $$\mathcal{M}$$ be an $$\mathcal{L}$$-structure.

1. Extend our language to $$\mathcal{L}_\mathcal{M}$$ by adding a constant symbol $$c_a$$ for each $$a \in \mathcal{M}$$. Note that formally $$c_a$$ and $$a$$ are different objects: the first one is a constant symbol in the new language $$\mathcal{L}_\mathcal{M}$$ and the second one is an element in $$\mathcal{M}$$.
2. The structure $$\mathcal{M}$$ was just an $$\mathcal{L}$$-structure, but we can naturally make it into an $$\mathcal{L}_\mathcal{M}$$-structure by interpreting every new constant symbol $$c_a$$ as $$a$$. This makes sense, because by construction we had that $$a$$ is an element in $$\mathcal{M}$$.

Now comes the magic of this construction, which tells us why $$c_a$$ and $$a$$ are often used interchangeably. Even though they technically are different things! So read carefully were everything lives.

Let $$\varphi(x_1, \ldots, x_n)$$ be an $$\mathcal{L}$$-formula and let $$a_1, \ldots, a_n \in \mathcal{M}$$ be elements. As argued before, the question whether or not $$\mathcal{M} \models \varphi(a_1, \ldots, a_n)$$ now makes sense. By the construction above, we also have constant symbols $$c_{a_1}, \ldots, c_{a_n} \in \mathcal{L}_\mathcal{M}$$, so we could also form the $$\mathcal{L}_\mathcal{M}$$-sentence $$\varphi(c_{a_1}, \ldots, c_{a_n})$$. Note that I say sentence now, because this has no free variables. Since we naturally view $$\mathcal{M}$$ as an $$\mathcal{L}_\mathcal{M}$$-structure, we can also ask whether or not $$\mathcal{M} \models \varphi(c_{a_1}, \ldots, c_{a_n})$$. To answer that question, we have to replace each constant symbol by their interpretation and we arrive at the same question we had before, namely $$\mathcal{M} \models \varphi(a_1, \ldots, a_n)$$.

What the above shows is that, viewing $$\mathcal{M}$$ as an $$\mathcal{L}_\mathcal{M}$$-structure, we have $$\mathcal{M} \models \varphi(c_{a_1}, \ldots, c_{a_n}) \quad \Longleftrightarrow \quad \mathcal{M} \models \varphi(a_1, \ldots, a_n).$$ So the subtle difference between elements and constant symbols disappears in this way. Which is why many authors will not distinguish between them.

Footnote: some authors use $$\mathcal{M} \models \varphi(x_1, \ldots, x_n)$$ as an abbreviation for $$\mathcal{M} \models \forall x_1 \ldots x_n \varphi(x_1, \ldots, x_n)$$, which does make sense since then there are no longer free variables.

• Thank you for your detailed answer. As someone who is learning the basics, the element $a$ and constant $c_a$ seem quite different to me. I think of $c_a$ as purely a syntactic term that interprets as $a$. But I hope as I become more comfortable with working with model theory, I will be able to understand from context what is meant. – qwr Apr 27 '20 at 20:05

Does this mean before the substitution $$\phi$$ has free variables $$x_1, x_2, \ldots, x_n$$ and after the substitution $$\phi(a_1, \ldots, a_n)$$ is a sentence?

Yes, that's precisely what it means.

On a related note, what does $$\phi(c_{a_1}, \dots, c_{a_n})$$ in the expanded language mean? Is it just indicating that $$\phi$$ has constants $$c_{a_1}, \dots, c_{a_n}$$ ?

That notation is kind of confusing. I would have assumed that $$a_i$$ are constants themselves, not indices to constants.

• The $a_i$ are elements of the underlying set of $\mathcal M$. Then $c_{a_i}$ are constants added to the language based on $a_i$. Here is an example: "The complete diagram of $\mathcal M$ is the set of sentences in the expanded language $\mathcal L_\mathcal M$ which are true in $\mathcal M$, that is the set of sentences $\phi(c_{a_1}, \dots, c_{a_n})$ such that $\mathcal M \models \phi(a_1, \dots, a_n)$. " I don't know if the notation is standard. – qwr Apr 27 '20 at 3:24
• Okay, sort of. In your example, I still don't see why the author would write $c_{a_1}$ in one case but $a_1$ in other. They are both the same type of expression. – Ted Apr 27 '20 at 4:39