Satisfiability and Truth in First Order Model Theory

Question

In Mendelson's book An Introduction to Mathematical Logic he introduces the use of denumerable sequences in the following section:

Near the end of this passage he states: "Let $\Sigma$ be the set of all denumerable sequences of elements of D". How do we visual these denumerable sequences? I don't quite understand their purpose here. They're clearly more than an ordered representation of the free variables; are they infinite?

Answer 1

Suppose I have a structure $M$ and a formula $\varphi$ - possibly with free variables. Since $\varphi$ might have free variables, it's not a priori clear that the truth value of $\varphi$ in $M$ is well-defined. For example, is "$x_1$ is even" true in $(\mathbb{N};+,\cdot)$?

For each specific formula $\mathcal{B}$, there's a canonical "type of object" needed to make $\varphi$ "unambiguous" in $M$: namely, a map $$v: FreeVar(\mathcal{B})\rightarrow M$$ assigning a value to each free variable in $M$. However, we could also go for overkill: what sort of object makes every formula "unambiguous" in $\mathcal{M}$?

The answer is simply an assignment of values to all variables. Note that such an $s$ really is overkill: for any specific formula $\mathcal{B}$, $FreeVar(\mathcal{B})$ will be finite but $s$ tells us infinitely many facts.

• In particular, addressing the cardinality question we have $$\vert\Sigma\vert=\vert M\vert^{\aleph_0}$$ (and hence as long as $M$ has more than one element, the corresponding $\Sigma$ will be uncountable!).

---

Now let's look at your final comment above. We need to distinguish valuations in the sense above with instantiations of quantifiers. The latter is not relevant here; we're only looking at the former. For example, when looking at the (very silly) formula $\forall x_1\exists x_3(x_2=x_4)$, only the second and fourth values of a sequence $s$ will be "used" when we ask whether $s$ makes that formula true in $M$.

It may help to think about an $s\in\Sigma$ as "acting on" a formula $\mathcal{B}$ to produce a new formula $s(\mathcal{B})$ with parameters from $M$ - namely, the formula gotten from $\mathcal{}$ by replacing each free variable in $\mathcal{B}$ by the corresponding value given by $s$. Looking at your example, thinking about the valuation $s=(c,d,c,d,...)$ we have

• $s(\forall x_1(x_1=x_2)$ is $\forall x_1(x_1=d)$ since $s(2)=d$.

• $s(\forall x_1(A_1(x_1))$ is just $\forall x_1(A_1(x_1))$ again, since there aren't any free variables for $s$ to do anything to.

• $s(A_1(x_1))=A_1(c)$ since $s(1)=c$.

Note that at no point does $s$ touch the quantifiers of the formula it acts on. In particular, if $\mathcal{B}$ has no free variables then $s(\mathcal{B})=\mathcal{B}$.