Bounded and Free Variables

Precedence of quantifiers

The precedence of quantifiers is higher than all the logical operators. This means the quantifier takes immediate effect unless specified by using brackets.

Example

Assume two predicates, $P(x)$ and $Q(x)$.

$$\forall x P(x) \land Q(x) \ne \forall x \left(P(x) \land Q(x)\right).$$

On the left-hand side of the above inequality, only $P(x)$ is quantified, while on the right-hand side, both $P(x)$ and $Q(x)$ are quantified.

---

Consider the following sets:

• $X=\{1,2,3\}$ and $Y=\{a,b,c\}$.

---

Now, we look at the following proposition:

$$\forall_{x\in X} \forall_{y \in Y} P(x,y).$$

Which quantifier should be applied first? Let’s try it both ways. First, use the internal quantifier.

$$\forall_{x\in X} \forall_{y \in Y} P(x,y) = \forall_{x\in X} (P(x,a)\land P(x,b)\land P(x,c))$$

Now, apply the outer quantifier.

$$\forall_{x\in X} \forall_{y \in Y} P(x,y) = (P(1,a)\land P(1,b)\land P(1,c))\land (P(2,a)\land P(2,b)\land P(2,c)) \land (P(3,a)\land P(3,b)\land P(3,c)).$$

Let’s see what happens when we apply the quantifiers in reverse order. First, use the outer quantifier.

$$\forall_{x\in X} \forall_{y \in Y} P(x,y) = (\forall_{y \in Y} P(1,y)) \land (\forall_{y \in Y} P(2,y)) \land (\forall_{y \in Y} P(3,y)).$$

Now, apply the inner quantifier.

$$\forall_{x\in X} \forall_{y \in Y} P(x,y) = (P(1,a) \land P(1,b) \land P(1,c)) \land ( P(2,a) \land P(2,b) \land P(2,c)) \land (P(3,a) \land P(3,b) \land P(3,c)).$$

There is no difference. We can think it either way. Conventionally, we first apply the outer quantifier, which helps us when all the quantifiers are not identical.

Let’s look at the following case now:

$$\forall_{y\in Y} \forall_{x \in X} P(x,y) = \forall_{y \in Y}(P(1,y)\land P(2,y) \land P(3,y)).$$

$$\forall_{x\in X} \forall_{y \in Y} P(x,y) = (P(1,a)\land P(2,a) \land P(3,a))\land (P(1,b)\land P(2,b) \land P(3,b)) \land (P(1,c)\land P(2,c) \land P(3,c)).$$

Due to the commutativity and associativity of conjunction operation,

$$\forall_{x\in X} \forall_{y \in Y} P(x,y) = \forall_{y\in Y} \forall_{x \in X} P(x,y).$$

Similarly, we can write the following due to the commutativity and associativity of disjunction operation.

$$\exists_{x\in X} \exists_{y \in Y} P(x,y) = \exists_{y\in Y} \exists_{x \in X} P(x,y).$$

Be cautious that both the quantifiers are universal quantifiers. Do not assume anything about mixing different kinds of quantifiers.

Scope of a quantifier

The scope of a quantifier is the segment of the logical expression under its effect. This effect is only for the variable attached to the quantifier. We use brackets to specify the scope of a quantifier.

Examples

Consider the following statements:

1. $\forall x P(x) \Rightarrow Q(x).$

   The scope of the universal quantifier is only $P(x)$, and $Q(x)$ is not in its scope.

2. $\forall x (P(x) \Rightarrow Q(x)).$

   Both $P(x)$ and $Q(x)$ are in the scope of the universal quantifier.

3. $\exists x(P(x,y)\lor \exists y S(x,y)).$

   The variable $x$, both in $P$ and $S$, is in the scope of the outer existential quantifier. The variable $y$ in $P$ is not in the scope of any quantifier, while in $S$, it is in the scope of the quantifier just preceding it.

Bounded variables

A variable is bounded if it is in the scope of a quantifier quantifying it. To make a proposition from a predicate, we either quantify or set a constant value for each variable in it. For a variable to be bounded, it has to be in the scope of some quantifier.

Free variables

A variable that is not in the scope of any quantifier and does not have a fixed value is free. In other words, a free variable is one that is not bounded, and no constant value is assigned to it.

Examples

Consider the following statements. Assume the domain is integers.

1. $\forall x P(x) \Rightarrow Q(x).$

   The scope of the universal quantifier is only up to $P(x)$. Therefore, the variable $x$ in $Q(x)$ is a free variable. The variable $x$ in $P(x)$ is a bounded variable.

2. $\exists y S(x,y)\land \forall z T(z).$

   There are three variables in this statement. The variable $y$ in predicate $S$ is bounded by the existential quantifier. The variable $x$ is free and it is not bounded by any quantifier. The variable $z$ is bounded by the universal quantifier.

3. $\forall x \forall y(3x^2+2y<z^3)\lor \exists j \exists k(7j^2+5k<p^3).$

   In this statement, there are six variables. The variables $x$ and $y$ are bounded by universal quantifiers. The variables $j$ and $k$ are bounded by existential quantifiers. The variables $z$ and $p$ are not bounded by any quantifier, therefore, they are free.