Bounded and Free Variables

Learn about bounded and free variables in quantified logical statements.

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)P(x) and Q(x)Q(x).

xP(x)Q(x)x(P(x)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)P(x) is quantified, while on the right-hand side, both P(x)P(x) and Q(x)Q(x) are quantified.


Consider the following sets:

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

Now, we look at the following proposition:

xXyYP(x,y).\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.

xXyYP(x,y)=xX(P(x,a)P(x,b)P(x,c))\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.

xXyYP(x,y)=(P(1,a)P(1,b)P(1,c))(P(2,a)P(2,b)P(2,c))(P(3,a)P(3,b)P(3,c)).\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.

xXyYP(x,y)=(yYP(1,y))(yYP(2,y))(yYP(3,y)).\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.

xXyYP(x,y)=(P(1,a)P(1,b)P(1,c))(P(2,a)P(2,b)P(2,c))(P(3,a)P(3,b)P(3,c)).\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:

yYxXP(x,y)=yY(P(1,y)P(2,y)P(3,y)).\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)).

xXyYP(x,y)=(P(1,a)P(2,a)P(3,a))(P(1,b)P(2,b)P(3,b))(P(1,c)P(2,c)P(3,c)).\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,

xXyYP(x,y)=yYxXP(x,y).\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.

xXyYP(x,y)=yYxXP(x,y).\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. xP(x)Q(x).\forall x P(x) \Rightarrow Q(x).

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

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

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

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

    The variable xx, both in PP and SS, is in the scope of the outer existential quantifier. The variable yy in PP is not in the scope of any quantifier, while in SS, 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. xP(x)Q(x).\forall x P(x) \Rightarrow Q(x).

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

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

    There are three variables in this statement. The variable yy in predicate SS is bounded by the existential quantifier. The variable xx is free and it is not bounded by any quantifier. The variable zz is bounded by the universal quantifier.

  3. xy(3x2+2y<z3)jk(7j2+5k<p3).\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 xx and yy are bounded by universal quantifiers. The variables jj and kk are bounded by existential quantifiers. The variables zz and pp are not bounded by any quantifier, therefore, they are free.

Quiz

Test your understanding of bounded and free variables.

1

Which option has a free variable?

A)

xyz(x2+y2=z2).\forall x \forall y \exists z (x^2 + y^2 = z^2).

B)

xyz(x2+y2=z2)(x2+z2=y2).\forall x \forall y \exists z (x^2 + y^2 = z^2) \lor (x^2 + z^2 = y^2).

C)

xyz(x2y2=z2).\exists x \exists y \exists z (x^2 - y^2 = z^2).

D)

xyz(3x2+5y231z2=0).\forall x \exists y \exists z (3x^2 + 5y^2 - 31z^2 = 0).

Question 1 of 20 attempted