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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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