Bound and Free Variables

Mathematical Logic · Axiom Academy

LESSON Bound and Free Variables Understanding the crucial distinction between variables under the control of quantifiers and those that remain independent in predicate logic formulas. 1. Free Variables: Independent and Unbound Consider the formula P(x) which states "x has property P". The variable x is free because no quantifier controls it. The truth value of this formula depends on what value we assign to x . 2. Bound Variables: Under Quantifier Control In the formula ∀x P(x) , the variable x is bound by the universal quantifier ∀. This formula makes a complete statement: "for all x, P(x) holds". We don't need to supply a value for x —the quantifier already specifies we're talking about all possible values. The scope is typically indicated by parentheses or extends to the end of the current subformula. Understanding scope is crucial for determining which variables are free and which are bound. ∀x (P(x) → Q(x)) — scope extends over (P(x) → Q(x)) ∀x P(x) ∧ Q(y) — ∀x only scopes over P(x); y is free ∀x (P(x) ∧ ∃y R(x,y)) — x bound by ∀, y bound by ∃ 4. Sentences vs. Open Formulas 5. Identifying Free and Bound Variables Let's analyze several formulas to identify free and bound variables. Remember: a variable occurrence is bound if there's a quantifier for that variable whose scope includes the occurrence. ∀x (P(x) ∧ Q(y)) x: bound , y: free ∃x P(x, y) ∧ ∀y Q(y) First x: bound by ∃x , first y: free , second y: bound by ∀y

This is the written version of the interactive lesson above. See the full Mathematical Logic course.