I have been reading Kleene "Introduction to Metamathematics" and found out that, even though he has been using a notion of "substituting simultaneously", he has never defined it.
On page 78 he says "The substitution of term $t$ for a variable $x$ in a term or formula $A$ shall consist in replacing simultaneously each free occurrence of $x$ in $A$ by an occurrence of $t$."
On page 79 he says "Similarly, we define substitution performed simultaneously for a number of distinct variables."
So, what does "substitution performed simultaneously" actually means?
My thoughts:
if we are given formula $A(x)$ and we want to replace $t$ for a variable $x$ in it then, first of all, we find all places in $A(x)$ (which is a finite string of symbols) where $x$ is. Then, we go from left to right through the string $A(x)$ and write $t$ in each place where we identified the $x$ is.
One then might define substitution in $A(x_1, ... , x_n)$ for $t_1, ..., t_n$ recursively but then I guess one runs into problem that $t_2$ for example might be $x_3$. Then, the recursive mechanism is not the same as one would intuitively think as "simultaneous substitution", at least I think so.
So, probably, one could define simultaneous substitution in the case of many variables as, first of all, because $A(x_1, ..., x_n)$ is still a finite string, we find all occurences of $x_1, ... x_n$. Then, we go from the left to right in a given string and whenever we have occurence of some $x_i$ we replace it by $t_i$. Then, we continue until the string ends. Is this how it is supposed to be defined?
Yes, that is what 'simultaneously' means here.
As a concrete example, take the formula $A(x,y)$ to be $x=y$.
Substituting $x+y$ for $x$ and $x-y$ for $y$ simultaneously in $A$ yields $$x+y = x-y$$ Substituting $x+y$ for $x$ and then substituting $x-y$ for $y$ in $A$ yields $$x+(x-y)=x-y$$ These are evidently not the same formula!