Differences

This shows you the differences between two versions of the page.

--- sav08:substitutions_for_first-order_logic [2008/03/19 16:04]
vkuncak
+++ sav08:substitutions_for_first-order_logic [2015/04/21 17:30]
@@ Line 1: / Line 1: @@
-====== Substitutions for First-Order Logic ======
-(Recall [[Substitution Theorems for Propositional Logic]].)
-===== Motivating Example =====
-It is important to be precise about substitutions in first-order logic.  For example, we would like to derive from formula $\forall x.F(x)$ formula $F(t)$, denoted $subst(\{x \mapsto t\})(F)$ that results from substituting a term $t$ instead of $x$.  For example, from $\forall x. x < x + 5$ we would like to derive $y - 1 < (y - 1) + 5$.  Consider, however formula
-\[
-    \forall x. \exists y. x < y
-\]
-Consider an interpretation in integers.  This formula is true in this domain.  Now substitute instead of x the term y+1.  We obtain
-\[
-    \exists y. y + 1 < y
-\]
-This formula is false.  We say that the variable $y$ in term $y+1$ was captured during substitution.  When doing substitution in first-order logic we must avoid variable capture.  One way to do this is to rename bound variables.  Suppose we want to instantiate the formula  $\forall x. \exists y. x<y$ with $y+1$.  Then we first rename variables in the formula, obtaining
-\[
-    \forall x_1. \exists y_1. x_1 < y_1
-\]
-and then after substitution $\{x_1 \mapsto y+1\}$ we obtain $\exists y_1. y + 1 < y_1$, which is a correct consequence of $\forall x. \exists y. x < y$.
-===== Naive and Safe Substitutions =====
-Let $U$ be a set of variables (that is, $U \subseteq V$).  A //variable substitution// is a function $\sigma : U \to T$ where $T$ is the set of [[First-Order Logic Syntax|terms first-order logic]].
-We define naive substitution recursively, first for terms:
-\[\begin{array}{rcl}
-subst(\sigma)( x ) &=& \sigma( x ),\ \sigma \mbox{ d{}efined at } x \\
-subst(\sigma)( x ) &=& x,\ \sigma \mbox{ not d{}efined at } x \\
-subst(\sigma)(f(t_1,\ldots,t_n)) &=& f(subst(\sigma)(t_1),\ldots,subst(\sigma)(t_n))
-\end{array}\]
-and then for formulas:
-\[\begin{array}{rcl}
-  nsubst(\sigma)(R(t_1,\ldots,t_n)) &=& R(nsubst(\sigma)(t_1),\ldots,nsubst(\sigma)(t_n)) \\
-  nsubst(\sigma)(t_1 = t_2) &=& (nsubst(\sigma)(t_1) = nsubst(\sigma)(t_n)) \\
-  nsubst(\sigma)(\lnot F) &=& \\
-  nsubst(\sigma)(F_1 \land F_2) &=& \\
-  nsubst(\sigma)(\forall x.F) &=&  \\
-  nsubst(\sigma)(\exists x.F) &=&
-\end{array}
-\]
-**Lemma:** Let $\sigma = \{x_1 \mapsto t_1,\ldots,x_n \mapsto t_n\}$ be a variable substitution and $t$ a term.  Then for every interpretation $I$,
-\[
-    e_T(nsubst(\sigma)(t))(I) = e_T(t)(I[x_1 \mapsto e_T(t_1)(I),\ldots, x_n \mapsto e_T(t_n)(I)])
-\]
-To avoid variable capture, we introduce in addition to $subst$ a safe substitution, $ssubst$.
-\[
-\begin{array}{rcl}
-  sfsubst(\sigma)(R(t_1,\ldots,t_n)) &=& R(nsubst(\sigma)(t_1),\ldots,nsubst(\sigma)(t_n)) \\
-  sfsubst(\sigma)(t_1 = t_2) &=& (nsubst(\sigma)(t_1) = nsubst(\sigma)(t_n)) \\
-  sfsubst(\sigma)(\lnot F) &=& \\
-  sfsubst(\sigma)(F_1 \land F_2) &=& \\
-  sfsubst(\sigma)(\forall x.F) &=& \\
-  sfsubst(\sigma)(\exists x.F) &=&
-\end{array}
-\]
-**Lemma:** Let $\sigma = \{x_1 \mapsto t_1,\ldots,x_n \mapsto t_n\}$ be a variable substitution and $t$ a term.  Then for every interpretation $I$,
-\[
-    e_F(sfsubst(\sigma)(F))(I) = e_F(F)(I[x_1 \mapsto e_T(t_1)(I),\ldots, x_n \mapsto e_T(t_n)(I)])
-\]
-**Lemma:** $(\forall x.F) \models sfsubst(\{x \mapsto t\}(F)$.