Scope (logic)

☆ Save On Wikipedia ↗

In logic, the scope of a quantifier or connective is the shortest formula in which it occurs,[1] determining the range in the formula to which the quantifier or connective is applied.[2][3][4] The notions of a free variable and bound variable are defined in terms of whether that formula is within the scope of a quantifier,[2][5] and the notions of a dominant connective and subordinate connective are defined in terms of whether a connective includes another within its scope.[6][7]

Connectives

The scope of a logical connective occurring within a formula is the smallest well-formed formula that contains the connective in question.[2][6][8] The connective with the largest scope in a formula is called its dominant connective,[9][10] main connective,[6][8][7] main operator,[2] major connective,[4] or principal connective;[4] a connective within the scope of another connective is said to be subordinate to it.[6]

For instance, in the formula ( ( ( P → Q ) ∨ ¬ Q ) ↔ ( ¬ ¬ P ∧ Q ) ) {\displaystyle (\left(\left(P\rightarrow Q\right)\lor \lnot Q\right)\leftrightarrow \left(\lnot \lnot P\land Q\right))} {\displaystyle (\left(\left(P\rightarrow Q\right)\lor \lnot Q\right)\leftrightarrow \left(\lnot \lnot P\land Q\right))}, the dominant connective is ↔, and all other connectives are subordinate to it; the → is subordinate to the ∨, but not to the ∧; the first ¬ is also subordinate to the ∨, but not to the →; the second ¬ is subordinate to the ∧, but not to the ∨ or the →; and the third ¬ is subordinate to the second ¬, as well as to the ∧, but not to the ∨ or the →.[6] If an order of precedence is adopted for the connectives, viz., with ¬ applying first, then ∧ and ∨, then →, and finally ↔, this formula may be written in the less parenthesized form ( P → Q ) ∨ ¬ Q ↔ ¬ ¬ P ∧ Q {\displaystyle \left(P\rightarrow Q\right)\lor \lnot Q\leftrightarrow \lnot \lnot P\land Q} {\displaystyle \left(P\rightarrow Q\right)\lor \lnot Q\leftrightarrow \lnot \lnot P\land Q}, which some may find easier to read.[6]

Quantifiers

The scope of a quantifier is the part of a logical expression over which the quantifier exerts control.[3] It is the shortest full sentence[5] written right after the quantifier,[3][5] often in parentheses;[3] some authors[11] describe this as including the variable written right after the universal or existential quantifier. In the formula ∀xP, for example, P[5] (or xP)[11] is the scope of the quantifier ∀x[5] (or ∀).[11]

This gives rise to the following definitions:[a]

  • An occurrence of a quantifier ∀ {\displaystyle \forall } {\displaystyle \forall } or ∃ {\displaystyle \exists } {\displaystyle \exists }, immediately followed by an occurrence of the variable ξ {\displaystyle \xi } {\displaystyle \xi }, as in ∀ ξ {\displaystyle \forall \xi } {\displaystyle \forall \xi } or ∃ ξ {\displaystyle \exists \xi } {\displaystyle \exists \xi }, is said to be ξ {\displaystyle \xi } {\displaystyle \xi }-binding.[1][5]
  • An occurrence of a variable ξ {\displaystyle \xi } {\displaystyle \xi } in a formula ϕ {\displaystyle \phi } {\displaystyle \phi } is free in ϕ {\displaystyle \phi } {\displaystyle \phi } if, and only if, it is not in the scope of any ξ {\displaystyle \xi } {\displaystyle \xi }-binding quantifier in ϕ {\displaystyle \phi } {\displaystyle \phi }; otherwise it is bound in ϕ {\displaystyle \phi } {\displaystyle \phi }.[1][5]
  • A closed formula is one in which no variable occurs free; a formula which is not closed is open.[12][1]
  • An occurrence of a quantifier ∀ ξ {\displaystyle \forall \xi } {\displaystyle \forall \xi } or ∃ ξ {\displaystyle \exists \xi } {\displaystyle \exists \xi } is vacuous if, and only if, its scope is ∀ ξ ψ {\displaystyle \forall \xi \psi } {\displaystyle \forall \xi \psi } or ∃ ξ ψ {\displaystyle \exists \xi \psi } {\displaystyle \exists \xi \psi }, and the variable ξ {\displaystyle \xi } {\displaystyle \xi } does not occur free in ψ {\displaystyle \psi } {\displaystyle \psi }.[1]
  • A variable ζ {\displaystyle \zeta } {\displaystyle \zeta } is free for a variable ξ {\displaystyle \xi } {\displaystyle \xi } if, and only if, no free occurrences of ξ {\displaystyle \xi } {\displaystyle \xi } lie within the scope of a quantification on ζ {\displaystyle \zeta } {\displaystyle \zeta }.[12]
  • A quantifier whose scope contains another quantifier is said to have wider scope than the second, which, in turn, is said to have narrower scope than the first.[13]

See also

Notes

  1. These definitions follow the common practice of using Greek letters as metalogical symbols which may stand for symbols in a formal language for propositional or predicate logic. In particular, ϕ {\displaystyle \phi } {\displaystyle \phi } and ψ {\displaystyle \psi } {\displaystyle \psi } are used to stand for any formulae whatsoever, whereas ξ {\displaystyle \xi } {\displaystyle \xi } and ζ {\displaystyle \zeta } {\displaystyle \zeta } are used to stand for propositional variables.[1]

References

  1. Bostock, David (1997). Intermediate logic. Oxford : New York: Clarendon Press; Oxford University Press. pp. 8, 79. ISBN 978-0-19-875141-0.
  2. Cook, Roy T. (March 20, 2009). Dictionary of Philosophical Logic. Edinburgh University Press. pp. 99, 180, 254. ISBN 978-0-7486-3197-1.
  3. Rich, Elaine; Cline, Alan Kaylor. Quantifier Scope.
  4. Makridis, Odysseus (February 21, 2022). Symbolic Logic. Springer Nature. pp. 93–95. ISBN 978-3-030-67396-3.
  5. "3.3.2: Quantifier Scope, Bound Variables, and Free Variables". Humanities LibreTexts. January 21, 2017. Retrieved June 10, 2024.
  6. Lemmon, Edward John (1998). Beginning logic. Boca Raton, FL: Chapman & Hall/CRC. pp. 45–48. ISBN 978-0-412-38090-7.
  7. Gillon, Brendan S. (March 12, 2019). Natural Language Semantics: Formation and Valuation. MIT Press. pp. 250–253. ISBN 978-0-262-03920-8.
  8. "Examples | Logic Notes - ANU". users.cecs.anu.edu.au. Retrieved June 10, 2024.
  9. Suppes, Patrick; Hill, Shirley (April 30, 2012). First Course in Mathematical Logic. Courier Corporation. pp. 23–26. ISBN 978-0-486-15094-9.
  10. Kirk, Donna (March 22, 2023). "2.2. Compound Statements". Contemporary Mathematics. OpenStax.
  11. Bell, John L.; Machover, Moshé (April 15, 2007). "Chapter 1. Beginning mathematical logic". A Course in Mathematical Logic. Elsevier Science Ltd. p. 17. ISBN 978-0-7204-2844-5.
  12. Uzquiano, Gabriel (2022), "Quantifiers and Quantification", in Zalta, Edward N.; Nodelman, Uri (eds.), The Stanford Encyclopedia of Philosophy (Winter 2022 ed.), Metaphysics Research Lab, Stanford University, retrieved June 10, 2024
  13. Allen, Colin; Hand, Michael (2001). Logic primer (2nd ed.). Cambridge, Mass: MIT Press. p. 66. ISBN 978-0-262-51126-1.