I'm studying basic first order logic right now and I'm confused about one concept that I can't get any clarification on.
If you have a formula like $\forall x\exists z((P(x)\rightarrow Q(x,z))\land R(z,b,c))$, is $((P(i)\rightarrow Q(i,k))\land R(i,b,d))$ a valid substitution instance? More specifically, is it okay to replace the variable "$z$" with two different names once you strip off the quantifiers, since the new main operator is now "$\land $"? If not, can you ever replace the same variable with different names, or not?
Thank you in advance!
You write:
No. You need to consistently use the same name when eliminating/instantiating a quantifier.
In the comments, Mauro gives the following example. Consider the formula $$\forall x \ x = x$$. Clearly this is a statement that is always true, no matter what we are talking about. But if you were allowed to instantiate the same variable with two different names, we could get $$0 = 1$$
which is clearly not true.
OK, but your particular statement is a bit more complicated, you say. So maybe there are special cases where it actually is ok (in the sense that the result is indeed a logical consequence of the original)? In particular you say that maybe there is something about the $\land$ that makes you wonder if maybe in this case it is ok... I am actually not sure why you think so, but let me say this: Yes, I am sure there are special cases where the result of substituting the same variable with two different names is actually logically implied by the original statement, but they would be highly exceptional. So as a general rule we will never allow it.
I want to note one more thing though about your question. When going from
$$\forall x\exists z((P(x)\rightarrow Q(x,z))\land R(z,b,c))$$
to
$$((P(i)\rightarrow Q(i,k))\land R(i,b,d))$$
you are not only substituing different names for the sa,me variable $z$, but you are also substituting both the $x$ and the last $z$ with the same name $i$. But because of the $\forall x \exists z$ construction in the original, that is cause for trouble. Consider the statement $$\forall x \exists z \ x \neq z$$
In any domain with more than one object, this is obviously true: for any object $x$ I can pick some other object $z$ that is different from $x$. But if I were allowed to use the same name for both $x$ and $z$, I could get
$$0 \neq 0$$
which is clearly not true.
OK, so how do things work correctly? Well, when you have a universal quantifier, you can substitute anything you want, including names that are already in use, though you do need to use the same name for every (free) instance of that variable. So, you can go from your
$$\forall x\exists z((P(x)\rightarrow Q(x,z))\land R(z,b,c))$$
to something like
$$\exists z((P(i)\rightarrow Q(i,z))\land R(z,b,c))$$
but you could also go to
$$\exists z((P(b)\rightarrow Q(b,z))\land R(z,b,c))$$
With an existential, you can only instantiate a new name, because we don;t know if that 'something' is one of the things you are already referring to. And again, you need to consistently use the same name throughout for all the (free) variable substitutions. So, you could go from
$$\exists z((P(i)\rightarrow Q(i,z))\land R(z,b,c))$$
to
$$(P(i)\rightarrow Q(i,k))\land R(k,b,c))$$
but you cannot go to
$$(P(i)\rightarrow Q(i,b))\land R(b,b,c))$$
and certainly not to
$$(P(i)\rightarrow Q(i,k))\land R(i,b,d))$$
for now you are making three mistakes:
you did not use the same substitution consistently throughout: the first $z$ got substituted with $k$ and the second with $i$
You did not (always) introduce a new name: you substituted thew last $z$ with an $i$ that was laready in the formula
You substituted $d$ for $c$??? Obviously you can't just change names ... I assume that was just a typo :P