1
$\begingroup$

I want to show that:

$\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$

I started my deduction as follows:

  1. $\vdash\forall x(\alpha\to\beta)\to(\forall x\alpha\to\forall x\beta)$ ---------------------------------- Axiom $3$
  2. $\vdash\forall x\alpha\to\alpha$ --------------------------------------------------------- Axiom $2$
  3. $\vdash\forall x\neg\alpha\to\neg\alpha$ ----------------------------------------------------- Axiom $2$
  4. $\vdash(\forall x\alpha\to\alpha)\to\big((\forall x\neg\alpha\to\neg\alpha)\to(\forall x\alpha\to\neg\forall x\neg\alpha)\big)$ ------ Axiom $1$
  5. $\vdash(\forall x\neg\alpha\to\neg\alpha)\to(\forall x\alpha\to\neg\forall x\neg\alpha)$ -------------------------- Modus Ponens $2,4$
  6. $\vdash\forall x\alpha\to\neg\forall x\neg\alpha$ -------------------------------------------------- Modus Ponens $3,5$
  7. $\vdash\forall x\alpha\to\exists x\alpha$ ------------------------------------------------------ Definition $\exists$

What is the shortest way to complete this deduction? Having shown that $\vdash\forall x\alpha\to\exists x\alpha$, how do I formally explain that $\vdash\forall x\beta\to\exists x\beta$ ? When I have these two statements, can I apply Rule T to $(1)$ to yield the desired proposition?

$\endgroup$
  • $\begingroup$ Can you do $\forall x\beta\vdash \beta$ and $\beta\vdash\exists x\beta$? $\endgroup$ – Hagen von Eitzen May 23 '15 at 15:58
  • $\begingroup$ @HagenvonEitzen Technically not, if I am to stick to the logical axioms listed page 112 in Enderton's A Mathematical Introduction to Logic (2nd edition). So the lines $2$ to $7$ in my deduction are essentially a work-around that. My question is, since I have proved it for some wff $\alpha$, is there a way to justify that the same holds for some wff $\beta$ in one line, or do I have to do the same derivation twice? $\endgroup$ – Demosthene May 23 '15 at 16:07
2
$\begingroup$

You have to note that in Enderton's system $\exists$ is not primitive; thus, there are no rules for "managing" it.

We have use contraposition :

1) $∀x(α→β)$ --- assumed

2) $α→β$ --- from 1) and Ax.2 by mp

3) $\lnot \beta \to \lnot \alpha$ --- from 2) and Rule T

4) $∀x(\lnot \beta \to \lnot \alpha)$ --- from 3) and Gen Th

5) $∀x\lnot \beta \to ∀x\lnot \alpha$ --- from 4) and Ax.3 by mp

6) $\lnot ∀x\lnot \alpha \to \lnot ∀x\lnot \beta$ --- from 5) "contraposing" again (i.e. by Rule T)

7) $\exists x \alpha \to \exists x \beta$ --- abbreviation.

Thus, from 1) and 7) we conclude by Deduction Th with :

$\vdash ∀x(α→β) → (∃xα→∃xβ)$.

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