1
$\begingroup$

How can I proove in Propositional Logic (using only the basic axioms of P.L. and not a valuation function like it's used in Propositional Calculus) that :

$\vdash$ ((($\phi$ $\to$ $\psi$ )$\to$ $\phi$)$\to$ $\phi$)

where $\phi$,$\psi$ are given formulas ?

$\endgroup$
  • $\begingroup$ excuse my bad writing.. i don't know how to make the symbols apear, if any one can correct this it woulb be lovely. $\endgroup$ – Lena Pappa Jan 19 '16 at 22:29
  • $\begingroup$ Just enclose them between $ signs. Also, use \phi and \psi. Btw, exactly what 'basic axioms' do you refer here? $\endgroup$ – Berci Jan 19 '16 at 22:33
  • $\begingroup$ This, or all substitution instances of it, just might be one of the "basic axioms". It's Peirce's Law. That link may give you ideas about how to prove it, depending upon what formalism you have in mind... which is unclear. So, same question as @Berci asked: what "basic axioms" do you have in mind? $\endgroup$ – BrianO Jan 19 '16 at 22:57
  • $\begingroup$ You mean $\phi\to(\psi\to\phi)$? as one axiom? (this can't be the only one, I expect a 2), ...) So, A Hilbert-style system. $\endgroup$ – BrianO Jan 19 '16 at 23:04
  • 1
    $\begingroup$ basically: 1) $\phi$ $\to$ ($\psi$ $\to$ $\phi$ ) 2) ($\phi$ $\to$ ($\psi$ $\to$ $\omega$ ) ) $\to$ ( ($\phi$ $\to$ $\psi$ ) $\to$ ($\phi$ $\to$ $\omega$)) 3)($\lont$ $\phi$ $\to$ $\lont$ $\psi$) $\to$ (($\lont$ $\phi$ $\to$ $\psi$)$\to$ $\phi$ ) those are what our professor gave us and a couple of lemmas $\endgroup$ – Lena Pappa Jan 19 '16 at 23:11
1
$\begingroup$

Axioms :

(A1) $\phi\to (\psi \to \phi)$

(A2) $(\phi → (ψ → ω)) → ((ϕ → ψ) → (ϕ → ω))$

(A3) $(\lnot ϕ → \lnot ψ) → ((\lnot ϕ → ψ) → ϕ)$.


With (A1) and (A2) we can prove :

Lemma 1 : $\vdash (\phi\to \phi)$.

With (A1), (A2) and Lemma 1 we can prove the:

Deduction Th : If $\Gamma$ is a set of formulae and $\phi, \psi$ are formulae, and $\Gamma , \phi \vdash \psi$, then $\Gamma \vdash \phi \to \psi$.

Finally, we have to prove :

Lemma 2 : $\vdash \lnot \phi \to (\phi \to \psi)$

1) $\lnot \phi$ --- premise

2) $\phi$ --- premise

3) $\vdash \phi \to (\lnot \psi \to \phi)$ --- (A1)

4) $\vdash \lnot \phi \to (\lnot \psi \to \lnot \phi)$ --- (A1)

5) $\lnot \psi \to \phi$ --- from 2) and 3) by modus ponens

6) $\lnot \psi \to \lnot \phi$ --- from 1) and 4) by mp

7) $\psi$ --- from 5), 6) and (A3)

8) $\lnot \phi, \phi \vdash \psi$ --- 1), 2) and 7)

$\vdash \lnot \phi \to (\phi \to \psi)$ --- from 8) by Ded.Th twice.


Now for the main proof :

1) $(ϕ → ψ) → ϕ$ --- premise

2) $\lnot \phi$ --- premise

3) $\vdash \lnot \phi \to (\phi \to \psi)$ --- Lemma 2

4) $\phi \to \psi$ --- from 2) and 3) by mp

5) $\phi$ --- from 1) and 4) by mp

6) $(ϕ → ψ) → ϕ \vdash \lnot \phi \to \phi$ --- from 2) and 5) by Ded.Th

7) $\vdash \lnot \phi \to \lnot \phi$ --- Lemma 1

8) $(ϕ → ψ) → ϕ \vdash \phi$ --- from 6), 7) and (A3) by mp twice

$\vdash ((ϕ → ψ ) → ϕ) → ϕ$ --- from 8) by Ded.Th.

$\endgroup$
  • 1
    $\begingroup$ thank you! but how can you use in the main proof step 2) as a premise? we are suppose to use only the formula you type in step 1) as given and all the tautologies.. $\endgroup$ – Lena Pappa Jan 20 '16 at 20:44
  • $\begingroup$ @LenaPappa - it is an applcation of Ded.Th; from 1)-5) : $(ϕ→ψ)→ϕ, ¬ϕ \vdash ϕ$, I've derived 6) $(ϕ→ψ)→ϕ \vdash ¬ϕ→ϕ$ $\endgroup$ – Mauro ALLEGRANZA Jan 20 '16 at 20:55
  • 1
    $\begingroup$ in 4) you use mp on 2) and 3)... but u can't have 2) in the first place... it's not given how can you use it? and its not proven by the axioms! sorry but it seems to me like you are proving { ($(\phi \to \psi) \to \phi)$ , $\lnot\phi$ } $\vdash$ $\phi$ instead of { ($(\phi \to \psi) \to \phi)$ } $\vdash$ $\phi$ $\endgroup$ – Lena Pappa Jan 20 '16 at 21:29
  • 2
    $\begingroup$ I don't see how you got to step 8. $\endgroup$ – Doug Spoonwood Jan 21 '16 at 22:59
  • $\begingroup$ @LenaPappa - except for parentheses, it exactly what I've written in my comment above : 1)-5) proves : $(ϕ→ψ)→ϕ,¬ϕ⊢ϕ$ which is $\{ (ϕ→ψ)→ϕ), ¬ϕ \} ⊢ ϕ$. Then applying Ded.Th : "if $Γ, \alpha ⊢ \beta$, then $Γ ⊢ \alpha → \beta$, with as $Γ$ the single formula $(ϕ→ψ)→ϕ$, I've derived in step 6) : $(ϕ→ψ)→ϕ ⊢ ¬ϕ → ϕ$. $\endgroup$ – Mauro ALLEGRANZA Jan 22 '16 at 8:09

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.