Basic question concerning free variables

Question

I - First doubt : free variables on open formulas .

I'm having a hard time discovering what different kinds of variables in an open formula of fol are refering to., For example, lets take some open formulas :

1: $"x+2=5"$
2: $"x=x"$
3: $"x+y = y+x"$
4: $"x+2 = 5 -> x=3 "$ .

So let's suppose we have a domain D of a structure which is interpreting that fol language. Even tho all those formulas are open formulas variables occuring free, i think the variables refer to different kind of sets ( obviously all sets with the same type of objects, be it numbers, or whatever ) depending on the kind of formula... to what exactly, in each case ?

The formula 1 would be refering to a fixed element on the domain (whatever kind of elements it has ) ? Would that be it ? Or would it be an arbitrary one ?

Should we always use the word "refering to" in open formula, instead of "ranging through" ?

The free variable on the formula 2 would be refering to a bunch of elements of the domain ? Or would it be ranging through a bunch of elements of the domain ? How does the truth-set ( set of individuals that satisfy the open sentence " of each formula enter in picture ?

II - Second doubt : When to close a formula, and what does it provide us ?

The second point i'm having a hard time with is how to differentiate, and how to know the difference between the uses and the reasons of choosing to use either the formula
$"x+2 =5 -> x = 3 "$ or $\forall x (x+2 = 5 -> x = 3 )$ .

And also between the difference of using ( and choosing to use ) the open formula $"x+y = y+x"$ or the closed formula $"\forall x \forall y ( x + y = y + x ) "$.

Same thing about $"x = x$ and $"\forall x (x = x) "$.

Answer 1

Question n°1 :

let's suppose we have a domain $D$ of a structure which is interpreting that fol language. [...] the I think the variables refer to different kind of things depending on the kind of formula... to what exactly, in each case ?

The answer is : NO.

If you are working in FOL, the domain $D$ contains only one "sort" of thing; if you "apply" (as in the example) first-order language to "speak of" numbers, the domain will be, for example, $\mathbb N$, the set of natural numbers and all individual variables will "get value" from the domain $\mathbb N$.

Question n°2 :

how to interpret a formula like : $x+2=5$, with a free variable ?

One way (there are more than one, all producing the same result) is by considering an object $a \in D$ (an object in the domain) and enlarging the language with a "name" for it : call it $\overline a$.

If $\mathcal A(x)$ is a formula with only one free var $x$, we consider an instance of it : $\mathcal A(x/\overline a)$, i.e.the formula (without free vars) obtained from $\mathcal A(x)$ by substitution of all occurrences of $x$ with $\overline a$.

Now the formula $\mathcal A(x/\overline a)$ is closed (i.e. without free vars), and we call it a sentence, and we are able to evaluate its truth-value.

Consider the formula of your example (I omit the overline for simplicity) :

$x+2=5$;

if we substitute to $x$ the (name for the) number $3$, we obtain a true sentence (i.e. $3+2=5$).

If instead we substitute to $x$ the (name for the) number $4$, we obtain a false sentence (i.e. $4+2=5$).

A formula with free var is called open because it has no (fixed) meaning : it is "open to" different interpretations; in order to give it meaning, you have to transform it into a sentence (i.e. a closed formula).

We have two ways to do this :

• either use quantifiers; thus, from $x+2=5$, we can obtain $\forall x(x+2=5)$, which is plainly false;

• or instantiate it (as above); of course, for different instances of the same formula, we will obtain different sentences with different truth-values.

Question n°3 :

In the case of $x = x$, the two ways above will give as results :

• $\forall x (x = x)$, wich is clearly true (and more: it is valid, i.e.true in every domain)

• in the domain $\mathbb N$, we can instantiate it as, e.g. $1=1$, $2=2$, and so on; all will be true instances. Of course the $x$ must be instantiated to the same objects in both occurrences of it into $x=x$.

Question n°4 :

When we have to use formulae with free vars or closed one ?

It depends...

Consider : $x+2=5 \rightarrow x=3$

What happens with $3$ in place of $x$ ?

We get : $3+2=5$, which is true, and $3=3$, also true; thus, by truth-table for $\rightarrow$ :

$(x+2=5 \rightarrow x=3)[3/x]$, i.e. $3+2=5 \rightarrow 3=3$, that reduces to True $\rightarrow$ True, which is True.

And with $4$ in place of $x$ ? We can easily check that we will have False $\rightarrow$ False, which is again True.

Thus, we have showed that $∀x(x+2=5 \rightarrow x=3)$ is true in $\mathbb N$.

But this is not always so : $\forall x (2 \times x = 4)$ is not true in $\mathbb N$.

Answer 2

I don't know if this will help, but here's the formalism I use.

Let a first-order language $L$ be given, an open formula $\varphi(x,y)$ in the language of $L$, with only free variables $x$ and $y$, and an $L$-structure $M$. Let $X$ be the collection of all variables you are using.

There is no way to determine whether $M \models \varphi(x,y)$ without knowing what $x$ and $y$ are. A valuation is a function $\sigma\colon X \to M$ that gives a value $\sigma(x)$ to each $x \in X$. Then, if $\varphi$ holds in $M$ with the constant $\sigma(x)$ plugged in for $x$ and $\sigma(y)$ plugged in for $y$, one can write $M \models_\sigma \varphi(x,y)$. We say $M \models \exists x\ \exists y \ \varphi(x,y)$ if there is some valuation $\sigma$ such that $M \models_\sigma \varphi(x,y)$, and $M \models \forall x\ \forall y\ \varphi(x,y)$ if for every valuation $\sigma$, it is the case $M \models_\sigma \varphi(x,y)$.

Some people use $M \models \varphi(x,y)$ interchangeably for $M \models \forall x\ \forall y\ \varphi(x,y)$. If that's your convention, of course one gains nothing from closing. Otherwise, you need to close to have a truth-value independently of valuation. A sentence is true or false in a structure, whereas an open formula is only true or false under a given valuation in a given structure.

In the sort of language you seem to be using, $x$ and $y$ all range over the same sorts of things, namely, individuals in (the underlying set of) $M$.

Answer 3

Quite often, quantifiers are are left out of statements in informal discussions. When we talk about the commutativity of addition on the natural numbers, for example, some authors may simply write $x+y=y+x$. To be more precise, they should write $\forall x,y\in N: x+y=y+x.$

In a statement in a formal proof, free variables are those that are not quantified within that statement. If we have a statement in formal proof like $y=x+1$ (with no quantifiers), it is best to think of it as referring to a single pair of numbers $x$ and $y$ even if we are later able to generalize for infinitely many cases using quantifiers.