Questions: Variable Binding and Scope

Question 1

In the formula P(x) ∧ ∀x Q(x), what is the status of the two occurrences of x?

• A. Both occurrences are bound — the ∀x quantifier applies to the entire conjunction
• B. The x in P(x) is free; the x in Q(x) is bound by the ∀x quantifier
• C. Both occurrences are free because the quantifier only takes effect after the ∧ connective
• D. The x in P(x) is bound and the x in Q(x) is free — quantifiers bind leftward

Answer: (B)

The scope of ∀x is only the subformula immediately following it — Q(x). The x in P(x) comes before the quantifier and lies outside its scope, so it is a free occurrence. This formula legally has the same variable name appearing both free (in P(x)) and bound (in Q(x)). It is grammatically valid but stylistically poor — experienced logicians would immediately rename the bound variable to avoid confusion.

Question 2

You want to rename the bound variable in ∀x ∃y (x ≠ y) to ∀y ∃y (y ≠ y). Why is this renaming problematic?

• A. Alpha-renaming is never legal in first-order logic — bound variable names are fixed
• B. The outer ∀y would capture the y that was formerly free in the inner formula, changing 'every x has a different element y' into a self-contradictory claim
• C. Only existential quantifiers can be alpha-renamed; universal quantifiers bind their variables permanently
• D. The renaming is fine logically, but stylistically y should be renamed to z to avoid reuse

Answer: (B)

Alpha-renaming is legal only when the new name does not appear free within the scope being renamed. In ∀x ∃y (x ≠ y), the variable y is already used (bound by ∃y). Renaming ∀x to ∀y creates ∀y ∃y (y ≠ y) — the outer ∀y captures the free positions of y in the original inner formula, turning a coherent statement about two different elements into a statement about self-inequality, which is always false. Variable capture completely changes the formula's meaning.

Question 3

Alpha-equivalence means ∀x P(x) and ∀z P(z) express the same logical content — the name of a bound variable is an arbitrary label that can be changed without altering meaning, provided no free variable is captured.

• T. True
• F. False

Answer: True

Bound variable names are implementation details. 'For all x, P(x)' and 'For all z, P(z)' make the same claim: every element in the domain satisfies P. The choice of dummy variable is arbitrary, like the choice of loop variable name in code. What matters is the structure of quantifier scope, not the specific labels. This is alpha-equivalence, and it's the theoretical basis for safe variable renaming during substitution.

Question 4

In a first-order logic formula, a variable is either free throughout the entire formula or bound throughout — it cannot be simultaneously free in one part and bound in another.

• T. True
• F. False

Answer: False

The same variable name can have both free and bound occurrences in the same formula. In P(x) ∧ ∀x Q(x), x appears free in P(x) and bound in Q(x). These are technically different 'slots' that happen to share a label. A variable occurrence is free or bound based on whether it falls within the scope of a matching quantifier — it is a property of each occurrence, not of the variable name as a whole.

Question 5

Why must you check for 'variable capture' when alpha-renaming a bound variable, and what goes wrong if capture occurs?

Model answer: Variable capture occurs when you rename a bound variable to a name that already appears free within the scope of the quantifier being renamed. The newly renamed quantifier then binds those formerly-free occurrences, which were independent variables in the original formula. For example, in ∀x ∃y (x ≠ y), renaming ∀x to ∀y produces ∀y ∃y (y ≠ y) — the outer ∀y inadvertently binds what were free y's in the inner formula, turning a statement about two different elements into a claim about self-inequality. Capture silently transforms the formula's meaning while appearing to be a harmless renaming.

This is why the alpha-renaming rule specifies: rename a bound variable only to a fresh name that doesn't appear free in the scope. The safety condition is not bureaucratic — capture is exactly the error that would make substitution rules (like universal instantiation) unsound if not carefully controlled.