I know that formulas contains free variables and sentences only contains bounded variables. Am I right to say that sentences are equivalent to the properties that structures may have or have not. As sentences have a definite truth value. for example if M = (|M|,<) ,where |M| is set of natural numbers.Then it is not the property of the structure M that 'forall x , therexist a number y less than x' . Because for x = 1 there is no number y<1 so this is not a property of M. And clearly it is a sentence that expresses a property of structure. So am I right to believe that all sentences expresses some property of a structure. What about formulas? How shall i think of them? what are they needed for?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
migrated from cstheory.stackexchange.com Jul 2 '11 at 4:37
This question came from our site for theoretical computer scientists and researchers in related fields.
It is true that sentences only contain bound occurrences of variables, while formulas ordinarily contain free occurrences of variables. I am being fussy here: a sentence is a special kind of formula, just like an equilateral triangle is a special type of isosceles triangle. When we call a triangle isosceles, we do not necessarily preclude the possibility that it is equilateral.
If we are only going to talk only about a specific interpretation (model) $M$, sentences can be viewed as expressing properties of the structure. However, sentences can be viewed purely syntactically, and there can be analysis, for example, of provability or refutability, not truth in a specific $M$. In reality, logic is often about the interplay between syntax and semantics. So the syntactic description of sentences (no free occurrences of variables) and your semantic description (definite truth value in a model) embody two complementary views of the subject.
Semantic interpretation of formulas goes along the lines that you described for sentences. For example, let $L$ be the language that has function symbols $+$ and $\times$, and constant symbols $0$ and $1$. Let $M$ be the structure whose underlying set is the reals, with $+$, $\times$, $0$, and $1$ interpreted in the usual way.
We consider a specific formula $F(x)$, say $$\exists z (z \times z=x).$$ This formula is true if the variable $x$ is interpreted, for example, as the real number $\pi$, and false if the variable $x$ is interpreted as the real number $-17$. "Interpreted" needs to be defined precisely, the usual technical term you will see is valuation. The details are not hard, but we have to be careful not to confuse syntax and semantics. The definition, in particular, has to deal with what it means to "substitute" an element $m$ of $M$ for $x$ in a formula. After all, $m$ is not a symbol of $L$.
Enough of formality! Informally, a formula $F(x)$ is typically true for some values of $x$ (interpretations of $x$ in $M$,) and false at other values of $x$.
The formula could very well be true at all values of $x$. For the structure $M$ we have been discussing, an example is $$\exists z (((z\times z)\times z)=x)$$ since every real number has a cube root.
We turn to a familiar syntactically very simple example of a formula $F(x,y)$ with two free variables, $$x +(y+y)=1+1.$$ Here again, if $x$ and $y$ are interpreted as specific real numbers $c$ and $d$, then the formula $F(x,y)$ is true in $M$ under that interpretation if the point $(c,d)$ lies on the line with ordinary equation $x+2y=2$, and false if $(c,d)$ does not lie on the line.
More generally, a formula is interpreted in a model $M$ as a relation. For example, a formula $F(x,y)$ with two free variables $x$ and $y$ is interpreted as a binary relation, which may hold when $x$ and $y$ are interpreted as being certain elements of $M$, and false in other cases.
But do remember that at the syntactic level, a formula is a formula merely because of its shape, period. But the semantic interpretation of formulas as relations is the main reason we are interested in them.
Added: In many areas, there is a tradition of presenting the axioms as what looks superficially like formulas, and not sentences. For example, the commutativity axiom for abelian groups is usually written as something like $$x\times y=y \times x.$$ This should be thought of as an abbreviation for $$\forall x\forall y (x\times y=y \times x).$$ This tradition does not marry well with the usual interpretation of formulas $F(x,y)$ in logic, but the tradition is well-established, and nothing much can be done about it.
Some presentations of logic allow formulas that are not sentences to be provable, by making $F(x_1, \dots, x_n)$ provable iff the sentence obtained by universally quantifying all the free variables of $F(x_1, \dots, x_n)$ is provable.
It is unfortunately sometimes not obvious whether in a formula $F(x)$, the variable symbol $x$ should be considered as being implicitly universally quantified. In mathematical writing, it is not uncommon to leave out some universal quantifiers, to avoid quantifier overload. This tends to blur the important distinction between formulas and sentences.