Introduction
Scope and variable binding are fundamental concepts in predicate logic that determine how quantifiers interact with variables and formulas. Understanding these concepts is essential for:
- Correctly interpreting logical formulas
- Avoiding logical errors
- Understanding the semantics of quantified statements
- Writing correct logical proofs
In this article, we’ll explore scope, variable binding, free and bound variables, and how to work with them correctly.
What is Scope?
Scope is the range of a formula over which a quantifier applies. It determines which variables are bound by a quantifier and which are free.
Scope Notation
The scope of a quantifier extends from the quantifier to the end of the formula or to the matching closing parenthesis.
Examples:
∀x P(x)
Scope of ∀x: P(x)
∀x (P(x) ∧ Q(x))
Scope of ∀x: (P(x) ∧ Q(x))
∀x (P(x) → ∃y Q(y))
Scope of ∀x: (P(x) → ∃y Q(y))
Scope of ∃y: Q(y)
Scope Hierarchy
When quantifiers are nested, inner quantifiers have narrower scope than outer quantifiers.
Example:
∀x (P(x) → ∃y Q(x, y))
↑ ↑
Outer scope (∀x)
↑ ↑
Inner scope (∃y)
Free and Bound Variables
A variable is bound if it appears within the scope of a quantifier that binds it. A variable is free if it is not bound by any quantifier.
Identifying Bound Variables
A variable is bound if it appears within the scope of a quantifier with the same variable name.
Examples:
∀x P(x)
x is bound (appears in scope of ∀x)
∀x (P(x) ∧ Q(x))
Both x's are bound (appear in scope of ∀x)
∀x P(x, y)
x is bound, y is free (no quantifier for y)
Identifying Free Variables
A variable is free if it appears outside the scope of any quantifier that binds it.
Examples:
P(x)
x is free (no quantifier)
∀x P(x, y)
x is bound, y is free
∀x P(x) ∧ Q(y)
x is bound, y is free (Q(y) is outside scope of ∀x)
Examples with Multiple Variables
∀x ∃y P(x, y)
x is bound by ∀x
y is bound by ∃y
No free variables
∀x (P(x, y) → Q(x))
x is bound by ∀x
y is free (no quantifier for y)
∀x P(x) ∧ Q(y)
x is bound by ∀x
y is free (Q(y) is outside scope of ∀x)
∀x (P(x, y) ∧ ∃y Q(y))
First x is bound by ∀x
First y is free (in P(x, y), outside scope of ∃y)
Second y is bound by ∃y
Scope Ambiguity
Scope ambiguity occurs when it’s unclear which quantifier binds a variable or where a quantifier’s scope ends.
Example 1: Ambiguous Scope
∀x P(x) ∨ Q(x)
Interpretation 1: (∀x P(x)) ∨ Q(x)
Scope of ∀x: P(x)
x in Q(x) is free
Interpretation 2: ∀x (P(x) ∨ Q(x))
Scope of ∀x: (P(x) ∨ Q(x))
Both x's are bound
These have different meanings:
- Interpretation 1: Either all x satisfy P, or some specific x satisfies Q
- Interpretation 2: For all x, either P(x) or Q(x)
Example 2: Multiple Quantifiers
∀x ∃y P(x, y)
Interpretation 1: For every x, there exists a y such that P(x, y)
∀x (∃y P(x, y))
Interpretation 2: There exists a y such that for every x, P(x, y)
∃y (∀x P(x, y))
These have very different meanings:
- Interpretation 1: Each person has a mother (different mothers possible)
- Interpretation 2: There is one person who is everyone’s mother
Resolving Ambiguity
Use parentheses to make scope explicit:
Ambiguous: ∀x P(x) ∨ Q(x)
Clear: (∀x P(x)) ∨ Q(x)
or
Clear: ∀x (P(x) ∨ Q(x))
Variable Binding Rules
Rule 1: A Quantifier Binds All Occurrences in Its Scope
When a quantifier binds a variable, all occurrences of that variable within its scope are bound by that quantifier.
Example:
∀x (P(x) ∧ Q(x) → R(x))
All three x's are bound by ∀x
Rule 2: Inner Quantifiers Override Outer Quantifiers
When a variable is bound by both an inner and outer quantifier, the inner quantifier takes precedence.
Example:
∀x (P(x) ∧ ∃x Q(x))
First x is bound by ∀x
Second x is bound by ∃x (inner quantifier)
The ∃x "shadows" the ∀x for its scope
This is called variable shadowing or variable capture.
Rule 3: Scope Extends to the End or Matching Parenthesis
The scope of a quantifier extends from the quantifier to the end of the formula or to the matching closing parenthesis.
Examples:
∀x P(x) ∧ Q(x)
Scope of ∀x: P(x)
x in Q(x) is free
∀x (P(x) ∧ Q(x))
Scope of ∀x: (P(x) ∧ Q(x))
Both x's are bound
Substitution and Variable Renaming
Substitution
Substitution is the process of replacing a variable with a term throughout a formula.
Example:
Formula: ∀x P(x, y)
Substitute y with a:
Result: ∀x P(x, a)
Formula: ∀x (P(x) → Q(x, y))
Substitute y with f(x):
Result: ∀x (P(x) → Q(x, f(x)))
Variable Renaming
Variable renaming (also called alpha-conversion) is the process of renaming bound variables without changing the meaning of a formula.
Example:
∀x P(x) is equivalent to ∀y P(y)
∃x Q(x) is equivalent to ∃z Q(z)
Key point: Only bound variables can be renamed. Free variables cannot be renamed without changing the formula’s meaning.
∀x P(x, y) is NOT equivalent to ∀x P(x, z)
(y and z are free, so renaming changes meaning)
When to Use Variable Renaming
Variable renaming is useful for:
- Avoiding variable capture
- Making formulas clearer
- Preparing formulas for substitution
Example:
Original: ∀x (P(x) ∧ ∃x Q(x))
Rename inner x to y: ∀x (P(x) ∧ ∃y Q(y))
Now it's clear that the two x's are different
Scope in Natural Language
Translating Scope from English
English sentences often have scope ambiguities that must be resolved when translating to logic.
Example 1:
"Every student has a teacher"
Interpretation 1: Each student has some teacher (possibly different)
∀x (student(x) → ∃y (teacher(y) ∧ teaches(y, x)))
Interpretation 2: There is one teacher for all students
∃y (teacher(y) ∧ ∀x (student(x) → teaches(y, x)))
Example 2:
"A student in every class is smart"
Interpretation 1: For each class, there is a student in that class who is smart
∀x (class(x) → ∃y (student(y) ∧ in(y, x) ∧ smart(y)))
Interpretation 2: There is a student who is in every class and is smart
∃y (student(y) ∧ ∀x (class(x) → in(y, x)) ∧ smart(y))
Context Determines Scope
The intended meaning usually depends on context:
"Every student has a teacher"
Natural interpretation: Each student has their own teacher
∀x (student(x) → ∃y (teacher(y) ∧ teaches(y, x)))
"There is a teacher for every student"
Natural interpretation: One teacher for all students
∃y (teacher(y) ∧ ∀x (student(x) → teaches(y, x)))
Scope in Logical Proofs
Scope in Universal Instantiation
When using universal instantiation, we must respect the scope of the quantifier.
Example:
Given: ∀x P(x)
We can instantiate: P(a)
Given: ∀x (P(x) → Q(x))
We can instantiate: P(a) → Q(a)
Given: ∀x P(x) ∨ Q(x)
We can instantiate: P(a) ∨ Q(x)
(x in Q(x) is free, so it remains free)
Scope in Existential Generalization
When using existential generalization, we must ensure the variable is free.
Example:
Given: P(a)
We can generalize: ∃x P(x)
Given: P(a, b)
We can generalize: ∃x P(x, b)
or: ∃y P(a, y)
Given: ∀x Q(x)
We cannot generalize to: ∃x ∀x Q(x)
(x is already bound)
Common Scope Errors
Error 1: Incorrect Scope of Quantifier
Incorrect: ∀x P(x) ∧ Q(x)
(Intends: ∀x (P(x) ∧ Q(x)))
Correct: ∀x (P(x) ∧ Q(x))
Error 2: Variable Capture
Incorrect: ∀x (P(x) ∧ ∃x Q(x))
(Inner x shadows outer x, confusing)
Better: ∀x (P(x) ∧ ∃y Q(y))
(Clear that x and y are different)
Error 3: Free Variable Treated as Bound
Incorrect: ∀x P(x, y) where y is free
Then claiming: "For all x and y, P(x, y)"
Correct: ∀x ∀y P(x, y)
(If both should be bound)
Error 4: Incorrect Scope in Translation
English: "All students study some subject"
Incorrect: ∀x ∀y (student(x) ∧ subject(y) → studies(x, y))
(This says all students study all subjects)
Correct: ∀x (student(x) → ∃y (subject(y) ∧ studies(x, y)))
(Each student studies some subject)
Glossary
- Scope: The range of a formula over which a quantifier applies
- Bound variable: A variable that appears within the scope of a quantifier
- Free variable: A variable that is not bound by any quantifier
- Variable binding: The process of a quantifier binding variables
- Variable shadowing: When an inner quantifier binds a variable already bound by an outer quantifier
- Substitution: Replacing a variable with a term
- Variable renaming: Renaming bound variables (alpha-conversion)
- Scope ambiguity: Unclear which quantifier binds a variable or where scope ends
- Occurs check: Checking if a variable appears in a term
Practice Problems
Problem 1: Identifying Bound and Free Variables
For each formula, identify which variables are bound and which are free:
- ∀x P(x, y)
- ∀x (P(x) ∧ Q(y))
- ∀x ∃y P(x, y)
- ∀x (P(x) → Q(x, y))
- ∀x P(x) ∧ Q(x)
Solution:
- x bound, y free
- x bound, y free
- x and y both bound
- x bound, y free
- x bound in P(x), x free in Q(x)
Problem 2: Scope Ambiguity
For each ambiguous formula, provide two interpretations:
- ∀x P(x) ∨ Q(x)
- ∀x P(x) → Q(x)
Solution:
-
Interpretation 1: (∀x P(x)) ∨ Q(x) - Either all x satisfy P, or some x satisfies Q Interpretation 2: ∀x (P(x) ∨ Q(x)) - For all x, either P(x) or Q(x)
-
Interpretation 1: (∀x P(x)) → Q(x) - If all x satisfy P, then some x satisfies Q Interpretation 2: ∀x (P(x) → Q(x)) - For all x, if P(x) then Q(x)
Problem 3: Variable Renaming
Rename the bound variables to avoid shadowing:
- ∀x (P(x) ∧ ∃x Q(x))
- ∀x (∀x P(x) → Q(x))
Solution:
- ∀x (P(x) ∧ ∃y Q(y))
- ∀x (∀y P(y) → Q(x))
Problem 4: Translation with Scope
Translate to predicate logic, being careful about scope:
- “Every student studies some subject”
- “Some subject is studied by every student”
- “For every person, there is someone they like”
Solution:
- ∀x (student(x) → ∃y (subject(y) ∧ studies(x, y)))
- ∃y (subject(y) ∧ ∀x (student(x) → studies(x, y)))
- ∀x (person(x) → ∃y (person(y) ∧ likes(x, y)))
Related Resources
Online Platforms
- Stanford Encyclopedia of Philosophy - Logic articles
- Khan Academy Logic - Logic tutorials
- Coursera Logic Courses - Online courses
- MIT OpenCourseWare - University courses
- Brilliant.org Logic - Interactive lessons
Interactive Tools
- Logic Translator - Translate English to logic
- Predicate Logic Visualizer - Visualize formulas
- Scope Visualizer - Visualize variable scope
- Formula Checker - Check formulas
- Quantifier Visualizer - Visualize quantifiers
Recommended Books
- “Language, Proof, and Logic” by Barwise & Etchemendy - Scope and binding
- “Introduction to Logic” by Hurley - Comprehensive coverage
- “Symbolic Logic” by Lewis & Langford - Classic text
- “Logic: The Basics” by Priest - Accessible introduction
- “Formal Semantics” by Heim & Kratzer - Advanced topics
Academic Journals
- Journal of Symbolic Logic - Primary research
- Studia Logica - Logic research
- Linguistics and Philosophy - Language and logic
- Philosophical Logic - Logic applications
- Computational Linguistics - NLP applications
Software Tools
- Prolog - Logic programming
- Coq - Theorem prover
- Isabelle - Proof assistant
- Z3 - SMT solver
- Datalog - Logic database
Conclusion
Scope and variable binding are fundamental concepts that determine how quantifiers interact with variables and formulas:
- Scope defines the range over which a quantifier applies
- Bound variables are within the scope of a quantifier
- Free variables are not bound by any quantifier
- Variable renaming helps avoid confusion and shadowing
- Scope ambiguity must be resolved using parentheses and context
Mastering these concepts is essential for correctly interpreting and writing logical formulas.
In the next article, we’ll explore predicate logic equivalences, which show how different formulas can express the same logical relationships.
Next Article: Predicate Logic Equivalences
Previous Article: Translating English to Predicate Logic
Comments