# What is substitution simultaneously?

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?

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!