Deducción natural: $(\neg q \to\neg p)\vdash(p\to q)$ sin Modus Tollens

Question

Puede alguien ayudarme a obtener este resultado en deducción natural, sin utilizar el modus tollens:

$$(\neg q \to \neg p) \vdash ( p \to q)$$

Answer 1

Aquí tienes. He utilizado el modus ponens ( $\rightarrow$ Elim), la ley de no contradicción ( $\bot$ Intro), reductio ad absurdum ( $\lnot$ Intro), y la prueba directa ( $\rightarrow$ Introducción). Dependiendo de tu sistema, probablemente puedas saltarte el 6 e ir directamente al 7.

Answer 2

Utilicé un estilo de prueba de Hilbert del libro "Introduction to Mathematical Logic" de Elliot Mendelson. Es un libro muy bueno:

1. (¬q→¬p) Hipótesis
2. (¬q→¬p)→((¬q→p)→q) Axioma
3. (¬q→p)→q Modus Ponens (1, 2)
4. p→(¬q→p) Axioma
5. p→q Transitividad (3, 4)

Transitividad a→b, b→c ⊢ a→c:

1. a→b Hipótesis
2. b→c Hipótesis
3. (b→c)→(a→(b→c)) Axioma
4. a→(b→c) Modus Ponens (2, 4)
5. (a→(b→c))→((a→b)→(a→c)) Axioma
6. (a→b)→(a→c) Modus Ponens (4, 5)
7. a→c Modus Ponens (1, 6)