Existential Instantiation

From ProofWiki
Jump to navigation Jump to search

Theorem

$\exists x: P \left({x}\right), P \left({\mathbf a}\right) \implies y \vdash y$


Suppose we have the following:

From our universe of discourse, any arbitrarily selected object $\mathbf a$ which has the property $P$ implies a conclusion $y$
$\mathbf a$ is not free in $y$
It is known that there does actually exists an object that has $P$.

Then we may infer $y$.


This is called the Rule of Existential Instantiation and often appears in a proof with its abbreviation EI.


When using this rule of existential instantiation:

$\exists x: P \left({x}\right), P \left({\mathbf a}\right) \implies y \vdash y$

the instance of $P \left({\mathbf a}\right)$ is referred to as the typical disjunct.


Proof

This is an extension of Proof by Cases.


The propositional expansion of $\exists x: P \left({x}\right)$ is:

$P \left({\mathbf X_1}\right) \lor P \left({\mathbf X_2}\right) \lor P \left({\mathbf X_3}\right) \lor \ldots$

We know that any arbitrarily selected $\mathbf a$ with the property $P$ implies $y$.

From this we can infer that all such $\mathbf a$ which have that property imply $y$.

This is equivalent to the step in Proof by Cases in which we need to prove that both disjuncts lead to the same conclusion.

The fact that we only need one of them in fact to be true is quite enough to draw the conclusion that $y$ is true.

In this context, we are assured by the statement $\exists x: P \left({x}\right)$ that at least one such disjunct in the above propositional expansion is true.

Thus the conclusion follows, and the result is proved.

$\blacksquare$


Also known as

Some authors call this the Rule of Existential Elimination and it is then abbreviated EE.


Sources