You are here
Homeequivalent formulation of substitutability
Primary tabs
equivalent formulation of substitutability
Proposition 1.
Suppose a variable $x$ occurs free in a wff $A$. A term $t$ is free for $x$ in $A$ iff no variables in $t$ are bound by a quantifier in $A[t/x]$.
Proof.
We do induction on the complexity of $A$.

If $A$ is atomic, then any $t$ is free for $x$ in $A$, and clearly $A[t/x]$ is just $A$, which has no bound variables.

Finally, suppose $A$ is of the form $\exists yB$. Since $x$ is free in $A$, $x$ is not $y$, and $t$ is free for $x$ in $A$ iff $y$ is not in $t$ and $t$ is free for $x$ in $B$ iff, by induction, $y$ is not in $t$ and no variables of $t$ are bound in $B[t/x]$ iff no variables of $t$ are bound in $\exists yB[t/x]$, which is just $A[t/x]$ (since $x\neq y$).
∎
If $x$ does not occur free in $A$ (either $x$ occurs bound in $A$ or not at all in $A$), then $t$ is obviously free for $x$ in $A$, but $A[t/x]$ is just $A$, and there is no guarantee that variables in $t$ are bound in $A$ or not.
In the special case where $t$ is a variable $y$, we see that $y$ is free for $x$ in $A$ iff $y$ is not bound in $A[y/x]$, provided that $x$ occurs free in $A$. In other words, $y$ is free for $x$ in $A$ iff no free occurrences of $x$ in $A$ are in the scope of $Qy$, where $Q$ is either $\exists$ or $\forall$. So if $y$ is not bound in $A$, $y$ is free for $x$ in $A$, regardless of whether $x$ is free or bound in $A$. Also, $x$ is always free for $x$ in $A$.
Mathematics Subject Classification
03B05 no label found03B10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections