1
$\begingroup$

I am a little confused with the Existential Instantiation. If the domain = {a,b}, and the hypothesis is ∃xP(x) for some predicate P, why can we claim that both P(a) and P(b) are true via P(a)∧(a is in the domain) and WLOG for the case with b. What is the intuition behind this? My interpretation is that "there exists an x" corresponds to "at least one", so why would this be true if we aren't using the universal quantifier?

Edit: Here is some context:

I am trying to show the following argument is invalid over the domain {a,b}:

$$h_{1}:\forall x (P(x) \rightarrow Q(x))$$ $$h_{2}:\exists x \neg P(x) $$ $$ \therefore \neg Q(x)$$

The source says that $h_{1}$ is true because P(x) is false for both inputs. I am not sure how one can deduce that P(a) and P(b) are false for $\exists x \neg P(x)$

Edit 2: I misunderstood the exercise - I was supposed to give values to each predicate so that the argument holds invalid. This clarifies a lot here.

$\endgroup$
5
  • $\begingroup$ Not clear... Yes, "there exists an x" corresponds to "at least one". "At least one x is P" is not in contradiction with "All x are P". It is in contradiction with "No x is P". $\endgroup$ Jan 17 at 19:19
  • $\begingroup$ Having said that, the Existential Instantiation has some restriction for its use. Obviously, if the domain is finite and we know that $P(a)$ holds, the correct rule to be used is Existential Introduction: from $P(a)$ derive $\exists x Px$ $\endgroup$ Jan 17 at 19:24
  • $\begingroup$ Who says that you can claim all those things? Are you getting this from some textbook? Course notes? $\endgroup$
    – Bram28
    Jan 17 at 22:31
  • $\begingroup$ @Bram28 See edit for clarification $\endgroup$ Jan 17 at 22:31
  • 1
    $\begingroup$ @ilikemath3.14 Ah! OK, so that was it then: they provided a counterexample ... that is completely different from inferring anything from the existential. $\endgroup$
    – Bram28
    Jan 18 at 13:41
1
$\begingroup$

Existential instantiation says that you can remove an outermost existential quantifier and replace the variable that it introduced with a fresh constant that doesn't appear earlier in the proof.

A fresh constant is not the same thing as an element of your domain. It is a new constant symbol that stands for a specific element element of your domain (but an arbitrary one).

For instance, suppose $ \exists x \mathop. \varphi$ is true and the constant symbol $c$ has not been used so far in the proof. You can then conclude the following.

$$ \varphi[x := c] $$

This means $\varphi$, but with free occurences of $x$ replaced with $c$. For example

$$ \exists x \mathop. P(x) \to Q(x) $$ $$ P(c) \to Q(c) $$

Quoting Wikipedia briefly,

The rule has the restrictions that the constant $c$ introduced by the rule must be a new term that has not occurred earlier in the proof, and it also must not occur in the conclusion of the proof.

The reason for freshness constraint is to prevent us from concluding that $\exists x \mathop. \varphi$ and $\exists x \mathop. \psi$ implies $\exists x \mathop. \varphi \land \psi$. The reason to prohibit $c$ from appearing in the conclusion is its arbitrariness. We don't know anything about $c$ other than that it's an element of the domain of discourse and it satisfies the properties specified in the statement it's taken from ($\varphi$ and $P(x) \to Q(x)$ in the above examples).

$\endgroup$

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.