Complex formulas and quantifiers

So far so good. Now comes the more confusing part. When we are forming more complex formulas in $\mathcal{L}_1$, we can not only use connectives, but also quantifiers. And quantifiers work nothing like the connectives! Moreover, quantifiers and variables have an important relation to each other.

Let’s start with the formulas of $\mathcal{L}_1$. It is not hard to define what it means for something to be a formula of our new language. We already know what the atomic formulas are, we still have our connectives as usual, and we add two other symbols, $\forall$ (‘for all’, ‘for every’) for the universal quantifier, and $\exists$ (‘for some’, ‘there exists’) for the existential quantifier. Thus:

How the quantifiers show up in our formulas is as follows. In each case, for a formula $X$, you can form a quantified formula by adding the quantifier with a specific variable in front of the formula. So again, if $X$ is any formula of $\mathcal{L}_1$, then for example, $\forall \mathbf{x}_{1} X$ is also a formula of $\mathcal{L}_1$. And so is $\exists \mathbf{x}_{1} X$. And so is $\exists \mathbf{x}_{45967} X$. But of course, since $X$ can be any formula of $\mathcal{L}_1$, $X$ might already be a quantified formula (that is, it might already have quantifiers), and it might even be a complex formula with quantifiers and connectives (or just connectives). So this new rule of ours gets us infinitely many new formulas in a very strong sense. For example, it gets us infinitely many new formulas even if we fix a quantifier and a variable.

Thus, we have the definition:

So far, not very complicated. But here’s the rub. In first-order logic, we are not (at least currently) interested in all formulas. Instead, we are interested in a special subset of them: those that are called ‘closed formulas’. The formulas that are not closed are called ‘open’. So there are open and closed formulas, and we want the closed ones. These closed formulas are also sometimes called ‘sentences’. Again, this way, sentences are just a special subset of all formulas – the closed ones.

Here is the basic idea behind what makes a formula closed or its opposite, open. Note that the quantifiers $\forall$ and $\exists$ always come with some specific variable after them. They also have a scope, which is just the formula which they flank from the left. In other words, the scope of $\exists x Y$ is $Y$, and the scope of $\forall x Y$ is, again, $Y$, and in either case, the variable is $x$. This is important for the following reason.

If a certain variable that occurs after the quantifier also occurs in the scope of the quantifier (and is not already bound), then we say that the variable’s occurrence is bound by that quantifier. If an occurrence of a variable is bound, it is not free, and it is free if it is not bound.

Let’s look at some examples:

1. $\mathfrak{P}^{1}_{1}(\mathbf{x}_{1}) \wedge \mathfrak{P}^{1}_{1}(\mathbf{x}_{2})$

2. $\forall \mathbf{x}_{1} (\mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{1}}) \wedge \mathfrak{P}^{1}_{1}(\mathbf{x}_{2}))$

3. $\forall \mathbf{x}_{1} (\mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{1}}) \wedge \mathfrak{P}^{1}_{1}(\mathbf{x}_{2})) \wedge \mathfrak{P}^{1}_{1}(\mathbf{x}_{1})$

4. $\exists \mathbf{x}_{2} \forall \mathbf{x}_{1}(\mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{1}}) \wedge \mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{2}}))$

5. $\forall \mathbf{x}_{1}(\mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{1}}) \wedge \exists \mathbf{x}_{2} \mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{2}}))$

6. $\forall \mathbf{x}_{1} \exists \mathbf{x}_{1} \mathfrak{P}^{1}_{1}(\overline{\mathbf{x}_{1}})$

To have a visual representation, I put a horizontal line over each of the bound occurrences of the variables. Every other occurrence of a variable occurs free.

First, with formula (1), there are no quantifiers, so none of the occurrences of the variables are bound. In other words, all the variables occur free. In formula (2), $\mathbf{x}_{1}$ is in the scope of the quantifier $\forall$ with $\mathbf{x}_{1}$, so it gets bound by it. But there is no quantifier for $\mathbf{x}_{2}$, so that remains open.

The next formula, formula (3) shows something important. Sometimes, some occurrences of variables are bound, but some other occurrences remain free. As you can see, the first occurrence of $\mathbf{x}_{1}$ gets bound by the universal quantifier with $\mathbf{x}_{1}$, but the second occurrence does not. Why? Because that occurrence of $\mathbf{x}_{1}$ is not in the scope of the quantifier. If you made a syntax tree for the formula, that specific occurrence of the variable would not be underneath the quantifier, it would be on a different branch altogether, while the first occurrence would be. This is why we talk of occurrences of variables, and not simply variables.

Formulas (4) and (5) show two ways in which both variables can be bound. Note that though $\exists \mathbf{x}_{2}$ takes a different place in the second, it still manages to have the sole occurrence of $\mathbf{x}_{2}$ be in its scope, so it binds it either way.

Finally, (6) shows something unfortunate. As our syntax is defined, there can be overlapping quantifiers with identical variables. In such cases, we need a rule to determine which quantifier binds the variable. In this case, that quantifier is $\exists$. Why? Because in $\mathfrak{P}^{1}_{1}(\mathbf{x}_{1})$, $\mathbf{x}_{1}$ occurs free. In $\exists \mathbf{x}_{1} \mathfrak{P}^{1}_{1}(\mathbf{x}_{1})$, $\mathbf{x}_{1}$ no longer occurs free, it gets bound by $\exists \mathbf{x}_{1}$. So when $\forall \mathbf{x}_{1}$ arrives to the party late, it has no free occurrences of variables to bind anymore. Thus $\forall \mathbf{x}_{1}$ does nothing – it binds no variables because there are no free variables to bind.

As mentioned above, formulas in which all the occurrences of the variables are bound are closed, and they are sentences. Formulas in which there is at least one unbound (free) occurrence of a variable are called open, and they are not sentences.

So above, (4), (5), and (6) are closed formulas, and are therefore sentences. On the other hand, (1), (2), (3) are open formulas, and are therefore not sentences.

Now there is a clever way to define what it means to be a sentence of $\mathcal{L}_1$, by keeping count at each turn of forming a formula which variables have at least one free occurrence. It is as follows:

Some further conventions

As before, we shall make some simplifications to our notation to make our formulas more readable, and our claims more general. We already know that we can refer to any predicate $\mathfrak{P}^{n}_{k}$ (for some $n, k \in \mathbb{N})$ by the metavariables $P$, $Q$, $R$, $…$, and we can refer to any constant $\mathfrak{c}_{n}$ ($n \in \mathbb{N}$) by the metavariables $a$, $b$, $c$, $…$. We also had that formulas can be referred to by the metavariables $X$, $Y$, $Z$, $…$. We can now further add that for each variable $\mathbf{x}_{n}$ ($n \in \mathbb{N}$), we can use the metavariables $x$, $y$, $z$, $…$.

It’s important here to understand the distinction between metavariables and variables. Previously, we had less of a problem distinguishing between the two because we were using a language, $\mathcal{L}_0$, without variables. But now that we are using $\mathcal{L}_1$, with variables, we need to distinguish between the two types. We shall see how the variables of $\mathcal{L}_1$ function once we get to its semantics. But we can already say how its metavariables function. In particular, metavariables ‘range over’ the symbols of the language. In other words, if we write something like $P(x)$, it means some formula of the language of form $\mathfrak{P}^{1}_{n}(\mathbf{x}_{k})$ for some $n, k \in \mathbb{N}$. Given this, $P(x)$ could be any one of infinitely many formulas of the language, of that form. In context, we may use this to mean one particular formula of that form, without specifying which one exactly we mean (e.g., in an exercise). Or we can talk about all of them at once, like when we specify that $(X \rightarrow Y) \rightarrow (\neg X \vee Y)$ is a tautology, meaning all formulas of this form are tautologies.