8
$\begingroup$

Why does one need valuations in order to define the semantics of first-order logic? Why not just define it for sentences and also define formula substitutions (in he expected way). That should be enough:

$$M \models \forall x. \phi \iff \text{for all }d\in \mathrm{dom}(M),\ M \models \phi[x\mapsto d]$$

instead of

$$M,v \models \forall x. \phi \iff \text{for all }d\in \mathrm{dom}(M),\ M, v[x\mapsto d] \models \phi$$

$\endgroup$
13
$\begingroup$

It is perfectly possible to define satisfaction using just sentences as you suggest, and in fact, it used to be the standard approach for quite some time.

The drawback of this method is that it requires to mix semantic objects into syntax: in order to make an inductive definition of satisfaction of sentences in a model $M$, it is not sufficient to define it for sentences of the original language of $M$. You need to first expand the language with individual constants for all elements of the domain of $M$, and then you can define satisfaction for sentences in the expanded language. This is, I believe, the main reason why this approach went into disuse; if you use valuations, you can maintain a clear conceptual distinction between syntactic formulas of the original language and semantic entities that are used to model them.

$\endgroup$
  • 3
    $\begingroup$ I think it depends somewhat on whether the author is approaching things from a proof theory side or a model theory side. In the case of proof theory, the original language is of interest for studying provability of sentences, but in the case of model theory the expanded language is more useful for studying definability. So for example Marker's model theory book defines satisfaction via the extended language, but Enderton's intro logic book uses valuations. $\endgroup$ – Carl Mummert May 3 '12 at 21:50
5
$\begingroup$

The meaning of a closed formula is a truth value $\bot$ or $\top$. The meaning of a formula containing a free variable $x$ ranging over a set $A$ is a function from $A$ to truth values. Functions $A \to \lbrace \bot, \top \rbrace$ form a complete Boolean algebra, so we can interpet first-order logic in it.

Similarly, a closed term $t$ denotes an element of some domain $D$, while a term with a free variable denotes a function $D \to D$ because the element depends on the value of the variable.

It is therefore natural to interpret a formula $\phi(x_1, \ldots, x_n)$ with free variables $x_1, \ldots, x_n$ in the complete Boolean algebra $D^n \to \lbrace{\bot, \top\rbrace}$ where $D$ is the domain of range of the variables. Whether you phrase the interpretation in this complete Boolean algebra in terms of valuations or otherwise is a technical matter.

Mathematicians seem to be generally confused about free variables. They think they are implicitly universally quantified or some such. The cause of this is a meta-theorem stating that $\phi(x)$ is provable if and only if its universal closure $\forall x . \phi(x)$ is provable. But there is more to formulas than their provability. For example, $\phi(x)$ is not generally equivalent to $\forall x . \phi(x)$, so we certainly cannot pretend that these two formulas are interchangable.

To summarize:

  • formulas with free variables are unavoidable, at least in the usual first-order logic,
  • the meaning of a formula with a free variable is a truth function,
  • therefore in semantics we are forced to consider complete Boolean algebras $D^n \to \lbrace\bot, \top\rbrace$, which is where valuations come from,
  • the universal closure of a formula is not equivalent to the original formula,
  • it is a mistake to equate the meaning of a formula with the meaning of its universal closure, just as it is a mistake to equate a function with its codomain.
$\endgroup$
  • $\begingroup$ Cool. Clear and simple answser! I wonder what the logicians have to say about this? $\endgroup$ – Uday Reddy May 6 '12 at 12:29
  • 2
    $\begingroup$ I am one of "the logicians", it's written on my certificate of PhD. $\endgroup$ – Andrej Bauer May 6 '12 at 16:39
3
$\begingroup$

Simply because it's more natural to say "$x > 2$ is true when $x$ is $\pi$" (that is, on a valuation which sends $x$ to $\pi$) than "$x > 2$ is true when we substitute $\pi$ (the number itself, not the Greek letter) for $x$". Technically the approaches are equivalent.

$\endgroup$
2
$\begingroup$

I want to strengthen Alexey's answer, and claim that the reason is that the first definition suffers from technical difficulties, and not just that the second (standard) way is more natural.

Alexy's point is that the first approach, i.e.:

$M \models \forall x . \phi \iff$ for all $d \in M$: $M \models \phi[x\mapsto d]$

mixes syntax and semantics.

For example, let's take Alexey's example:

${(0,\infty)} \models x > 2$

Then in order to show that, one of the things we have to show is: $(0,\infty) \models \pi > 2$

The entity $\pi > 2$ is not a formula, unless our language includes the symbol $\pi$, that is interpreted in the model $M$ as the mathematical constant $\pi \approx 3.141\ldots$.

A more extreme case would be to show that $M\models\sqrt[15]{15,000,000} > 2$, and again, the right hand side is a valid formula only if our language contains a binary radical symbol $\sqrt{}$, that is interpreted as the radical, and number constants $15$ and $15,000,000$.

To ram the point home, consider what happens when the model we present has a more complicated structure. For example, instead of taking real numbers, take Dedekind cuts (a particular implementation of the real numbers).

Then the elements of your model are not just "numbers". They are pairs of sets of rational numbers $(A,B)$ that form a Dedkind cut.

Now, look at the object $({q \in \mathbb Q | q < 0 \vee q^2 < 5}, {q \in \mathbb Q | 0 \leq q \wedge q^2 > 5}) > 2$" (which is what we get when we "substitute" the Dedekind cut describing $\sqrt{5}$ in the formula $x > 2$. What is this object? It's not a formula --- it has sets, and pairs and who knows what in it. It's potentially infinite.

So in order for this approach to work well, you need to extend your notion of "formula" to include such mixed entities of semantic and syntactic objects. Then you need to define operations such as substitutions on them. But now substitutions would no longer be syntactic functions: $[ x \mapsto t]: Terms \to Terms$. They would be operations on very very large collections of these generalised, semantically mixed terms.

It's possible you will be able to overcome these technicalities, but I guess you will have to work very hard.

The standard approach keeps the distinction between syntax and semantics. What we change is the valuation, a semantic entity, and keep formulae syntactic.

$\endgroup$
  • 6
    $\begingroup$ The key point to the first approach is that given a model $M$ in a language $L$ you first expand to a language $L(M)$ in which there is a new constant symbol for every element in $M$. Then you can just substitute these constant symbols into formulas in the usual way. There are no actual technical difficulties. $\endgroup$ – Carl Mummert May 3 '12 at 21:45

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.