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}$?

  • $\begingroup$ 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". $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – qwr Apr 27 '20 at 3:24
  • $\begingroup$ 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. $\endgroup$ – Ted Apr 27 '20 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.