# Definition:Occurrence (Predicate Logic)

## Contents

## 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$.

Let $y$ be another variable such that $y$ does not occur in $\mathbf C$.

Let $\mathbf C'$ be the WFF resulting from replacing all free occurrences of $x$ in $\mathbf C$ with $y$.

Then to all intents and purposes, the WFFs:

- $Q x: \mathbf C$
- $Q y: \mathbf C'$

will have the same interpretation.

Thus we may change the free occurrences of any variable for another variable symbol.

This change is called **alphabetic substitution**.

## Also see

## Sources

- 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*: $\S 2.3$