# Using existential generalization repeatedly.

The statement I'm trying to prove:

$$\exists x\left[R\left(x,\:x\right)\right]\:^{\:}\wedge \:\left[\forall x\exists y\left[R\left(x,\:x\right)\rightarrow P\left(x,y,y\right)\right]\right]\rightarrow \exists x\exists y\exists z\left[P\left(x,y,z\right)\right]$$

$$1. \exists \:x\left[R\left(x,\:x\right)\right] (Premise)$$

$$2. \forall \:x\exists \:y\left[R\left(x,\:x\right)\rightarrow \:P\left(x,\:y,\:y\right)\right] (Premise)$$

$$3. R(a,a)$$ $$(1, Existential Instantiation)$$

$$4. \exists \:y\left[R\left(a,\:a\right)\rightarrow \:P\left(a,\:y,\:y\right)\right]$$ (2, Universal Instantiation)

$$5. R\left(a,\:a\right)\rightarrow \:P\left(a,\:b,\:b\right)$$ (4, Existential Instantiation)

$$6. P(a,b,b) (3,5,Modus Ponens)$$

And from this point I'm not sure how I should carry on, I assume that if I'll be using existential generalization then I'll have to replace all free occurrences of the constant with the variable (As mentioned in Wikipedia) which doesn't make it possible for me to reach the conclusion.

• 4 has a typo: form 2 we get $∃y[R(a,a)→P(a,y,y)]$. After 6 you need the axiom $P(a,b,b) \to \exists z P(a,b,z)$ where $P(a,b,b)$ is obtained from $P(a,b,z)$ replacing every free occurrences of $z$ with $b$. Jun 29 at 17:25
• The conclusion follows from it and 6 by MP. Jun 29 at 17:32
• That makes sense, thank you. Jul 13 at 12:22

Consider the formula $$\exists z P(a,b,z)$$.

Here we have that $$Q(z)$$ is $$P(a,b,z)$$ and $$P(a,b,b)$$ is obtained replacing all free instances of $$z$$ in $$P(a,b,z)$$.

Thus, applying the rule, we get:

$$P(a,b,b) \to \exists z P(a,b,z)$$.

The rule does not say that you have to replace all occurrences of $$a$$ in $$Q(a)$$ with $$x$$ to get $$Q(x)$$, but says that you have to start for (the suitable) $$Q(x)$$ and get $$Q(a)$$.

• Sorry but how did we obtain $P(a,b,b)$? Was it valid to use b as a Skolem constant? Jun 29 at 15:02
• @Malzahar - not clear... you have obtained $P(a,b,b)$ in your proof above. Jun 29 at 15:07
• It seemed to me that you didn't get $P(a,b,b)$ without starting with $\exists z P(a,b,z)$ that's why I mentioned the fact. Now I'm confused about what the rule actually says, so it does allow only replacing some of the instances of the variable with the constant? In other words, it's not necessary that "all free instance of the variable are replaced"? Jun 29 at 15:27
• That is correct, @Malzahar . You may replace as many or few free occurrences as you wish. If you can show that $~f(a,b,b)~$ holds, then there does exist some instance of fresh variable $z$ where $~f(a,b,z)~$ holds (for example, $z=b$ is clearly such an instance).$$\dfrac{f(a,b,b)}{\exists z~f(a,b,z)}$$ Sep 8 at 1:36
• This makes perfect sense. Thank you. Sep 9 at 16:43