Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can you help me with my approach to the following task:

Define simultaneous substitution $\phi[\psi_1,...,\psi_k/p_1,...,p_k]$ recursively.

Usually we have recursive definitions about formulas, but I think here I have to define it rekursively on k?

base case - $k=1$.

$\phi[\psi_1/p_1] = \phi[\psi_1/p_1]$

recursive case - $k > 1$.

Let $p^'_k$ be a variable not in $\psi_i$ for all $i \in \{1,...,k-1\}$ and not in $\phi$.

$\phi[\psi_1,...,\psi_k/p_1,...,p_k] = \left(\left(\phi[p^'_k/p_k]\right)[\psi_1,...,\psi_{k-1}]\right)[p_k/p^'_k]$

share|cite|improve this question
No ... since you want to have simultaneous substitution (and not one after the other as in recursion on $k$), I think you have to do it by recursion on $\phi$. – martini May 14 '12 at 19:25
@martini: But how to do it by recursion on $\phi$? Aim is to define simultaneous substitution so I can't use a simultaneous substitution e. g. in the recursive case $\phi = \phi_1 \circ \phi_2$ as $\phi[\psi_1,...,\psi_k/p_1,...,p_k] = \phi_1[\psi_1,...,\psi_k/p_1,...,p_k] \circ \phi_2[\psi_1,...,\psi_k/p_1,...,p_k]$ since simultaneous recursion isn't defined at this moment! – steltjen May 14 '12 at 20:26
When you use resursion on formulas, you start with basic formulas. So in you recursive step above, you haven't defined substitution for $\phi$, but for $\phi_1$ and $\phi_2$. – martini May 15 '12 at 4:33

For substitution, it helps to think of $\varphi$ as a tree (connectives = internal nodes, variables = leaves).

The substitution is essentially replacing the leaves $p_i$ with trees for the $\psi_i$.

If you want to do the recursion on the number of variables, you have to do it in three steps to make sure the later substitution doesn't effect the former ones. You can do this by using new names for variables in $\psi_i$s (i.e. use $q_i$ in place of $p_i$) so no $p_j$ appears in any $\psi_i$. Then after you have done step by step substitution you can change the new names back to the old ones. The goal here is to avoid a variable $p_j$ in a $\psi_i$ being replaced by $\psi_j$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.