Franklin's Notes

Free variables

Chang and Kiesler do not define the notion of a free variable and they leave it up to the reader's preexisting knowledge of First-order logic . I thought it would be a good idea to include a quick description of what this means, and attempt to define it recursively as an exercise.

Intuitively, a "free variable" $v$ of a formula $\varphi$ is one which is not prefaced by $(\forall v)$ or $(\exists v)$. This means that the truth value of $\varphi$ is not (necessarily) determined unless some particular value of $v$ is specified, whereas a formula with no free variables is more "completely determined". This is why a formula $\varphi$ with a free variable $v$ is denoted $\varphi(v)$ according to our notational conventions , as if it were a function of $v$.

We may define a free variable recursively as follows.
1. All variables used in an atomic formula are free variables.
2. If $v$ is a free variable in either $\varphi$ or $\psi$, then it is a free variable in $(\neg\varphi)$ and $(\varphi\land\psi)$.
3. $v$ is a free variable in $\varphi$ if and only if it can be shown to be a free variable by applying rules $(1)$ and $(2)$ finitely many times.

Note that $v$ is never a free variable in $(\forall v)\varphi$, even though the $\forall$ symbol is not mentioned anywhere in the above rules, simply because they cannot ever be used to deduce that $(\forall v)\varphi$ has $v$ as a free variable.

Exercise 1. Even though formulas of the form $(\forall v)\varphi$ never have $v$ as a free variable, there are formulas containing the substring $(\forall v)$ which have $v$ as a free variable. Find one in the language $\mathscr{L}={P}$, where $P$ is a unary relation.

Solution. An example is the formula $P(v)\land(\forall v)P(v)$.