Definition:Occurrence (Predicate Logic)
Definition
Let $\mathbf A$ be a WFF of predicate logic.
Let $S$ be a string in the alphabet of predicate logic.
Each place where $S$ appears in $\mathbf A$ is called an occurrence of $S$ in $\mathbf A$.
Note that $S$ may consist of a single symbol, but may not be null.
Scope
Let $\mathbf A$ be a WFF of the language of predicate logic.
Let $Q$ be an occurrence of a quantifier in $\mathbf A$.
Let $\mathbf B$ be a well-formed part of $\mathbf A$ such that $\mathbf B$ begins (omitting outer parentheses) with $Q x$.
That is, such that $\mathbf B = \paren {Q x: \mathbf C}$ for some WFF $\mathbf C$.
$\mathbf B$ is called the scope of the quantifier $Q$.
Bound Occurrence
Let $Q x$ be an occurrence of a quantifier in $\mathbf A$.
Any occurrence of the variable $x$ in the scope of $Q$ is called a bound occurrence.
Free Occurrence
An occurrence of a variable $x$ in $\mathbf A$ is said to be a free occurrence if and only if it is not bound.
Alphabetic Substitution
Consider the (abbreviated) WFF $Q x: \mathbf C$ where $Q$ is a quantifier.
Let $y$ be another variable such that:
- $y$ is freely substitutable for $x$ in $\mathbf C$
- $y$ does not occur freely in $\mathbf C$.
Let $\mathbf C'$ be the WFF resulting from substituting $y$ for all free occurrences of $x$ in $\mathbf C$.
The change from $Q x: \mathbf C$ to $Q y: \mathbf C'$ is called alphabetic substitution.
Also see
Sources
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability: $\S 2.3$