Existential Generalisation

From ProofWiki
Jump to navigation Jump to search

Theorem

Informal Statement

$\map P {\mathbf a} \vdash \exists x: \map P x$


Suppose we have the following:

We can find an arbitrary object $\mathbf a$ in our universe of discourse which has the property $P$.

Then we may infer that:

there exists in that universe at least one object $x$ which has that property $P$.


This is called the Rule of Existential Generalisation and often appears in a proof with its abbreviation $\text {EG}$.


Existential Generalisation in Models

Let $\map {\mathbf A} x$ be a WFF of predicate logic.

Let $\tau$ be a term which is freely substitutable for $x$ in $\mathbf A$.


Then $\map {\mathbf A} \tau \implies \exists x: \map {\mathbf A} x$ is a tautology.


Existential Generalisation in Proof Systems

Let $\map {\mathbf A} x$ be a WFF of predicate Logic of $\LL$.

Let $\tau$ be a term which is freely substitutable for $x$ in $\mathbf A$.

Let $\mathscr H$ be Hilbert proof system instance 1 for predicate logic.


Then:

$\map {\mathbf A} \tau \vdash_{\mathscr H} \exists x: \map {\mathbf A} x$

is a provable consequence in $\mathscr H$.


Also known as

Some authors call this the Rule of Existential Introduction and it is then abbreviated $\text {EI}$.

However, beware the fact that other authors use $\text {EI}$ to abbreviate the Rule of Existential Instantiation which is the antithesis of this one.

So make sure you know exactly what terminology is specified.