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]$

We can start with:

$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.

enter image description here

  • $\begingroup$ 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$. $\endgroup$ Jun 29 at 17:25
  • $\begingroup$ The conclusion follows from it and 6 by MP. $\endgroup$ Jun 29 at 17:32
  • $\begingroup$ That makes sense, thank you. $\endgroup$
    – Malzahar
    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)$.

  • $\begingroup$ Sorry but how did we obtain $P(a,b,b)$? Was it valid to use b as a Skolem constant? $\endgroup$
    – Malzahar
    Jun 29 at 15:02
  • $\begingroup$ @Malzahar - not clear... you have obtained $P(a,b,b)$ in your proof above. $\endgroup$ Jun 29 at 15:07
  • $\begingroup$ 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"? $\endgroup$
    – Malzahar
    Jun 29 at 15:27
  • 1
    $\begingroup$ 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)}$$ $\endgroup$ Sep 8 at 1:36
  • $\begingroup$ This makes perfect sense. Thank you. $\endgroup$
    – Malzahar
    Sep 9 at 16:43

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.