2
$\begingroup$

In a previous part of the question I have proved that $((\phi \rightarrow \psi) \rightarrow ((\psi \rightarrow \chi) \rightarrow (\phi \rightarrow \chi))$ is a theorem of L.

Using the previous part of the question, show that (($¬n) \rightarrow (n \rightarrow \theta))$ is a theorem of L, whenever $n, \theta$ are propositional formulas.

I am not really sure how to use the previous part of the question to do this, or do it at all really. Thanks

$\endgroup$
2
$\begingroup$

We have to use the theorem :

$\vdash (ϕ→ψ)→((ψ→χ)→(ϕ→χ))$,

call it Syll, in addition to the axioms (A1), (A2), (A3) amd modus ponens.

Recall that :

(A1) $ϕ→(ψ→ϕ)$

(A2) $(ϕ→(ψ→χ))→((ϕ→ψ)→(ϕ→χ))$

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

Now for the proof :

(1) $\vdash \lnot \phi \rightarrow (\lnot \psi \rightarrow \lnot \phi)$ --- (A1)

(2) $\vdash (\lnot \psi \rightarrow \lnot \phi) \rightarrow (\phi \rightarrow \psi)$ --- (A3)

(3) $\vdash \lnot \phi \rightarrow (\phi \rightarrow \psi)$ --- from 1, 2 and Syll, by modus ponens twice.

$\endgroup$
1
$\begingroup$

I use Polish notation and condensed detachment.

Given your previous post, I'm guessing that your axiom set is

A1 CpCqp recursive variable prefixing
A2 CCpCqrCCpqCpr self-distribution
A3 CCNpNqCqp strong transposition

Now given condensed detachment we can see if, omitting the "A" in "Ax", D1.1, D1.2, D1.3, D2.1, D2.2, D2.3, D3.1, D3.2, and D3.3 exist and get them as the next theorem. Which one might we pick?

Well, let's say we instead made a derivation which started with a hypothesis h and derived a sequence of well-formed formulas (s1, s2, ... s). How would we get to Chs?

The deduction meta-theorem tells us that we would first need to get Chh, Ch-s1, Ch-s2, ..., Ch(s-1), and then we can get to Chs. Where s1, s2, ..., sn is an axiom or assumption in the derivation we can use axiom 1 as the major premise with the axiom or assumption as the minor premise and then detach Cx-s1 where x is any variable. Where s2, ..., sn is obtain via detachment, we can obtain Ch-s2 by first applying axiom 2 to Ch-m where m is the major premise used when detachment got used in the derivation obtaining z, and then using z as the major premise with Ch-n as the minor premise, where n is the minor premise from the step when detachment got used in the derivation. This yields Ch-sx where sx got obtained using detachment with m as the major premise and n a the minor premise. In other words, distribute Ch-m (the hypothesis implying the major premise) to get z, then use z as the new major with Ch-n (the hypothesis implying the minor) as the new minor.

For example let's say we have the following derivation...

hypothesis 1 |   Cpq
hypothesis 2 ||  Cqr
hypothesis 3 ||| p
D1.3       4 ||| q
D2.4       5 ||| r

Now to get to step 4 from step 3 we first need C3-1, and C3-3. Then we'll distribute C3-1 (i. e. find D[axiom 2].[C3-1]). Then we'll use that result as the major and C3-3 as the minor premise. We'd first get CaCpq (let's suppose that the {a, b, c, d, e} belong to a different class of variables than all other lower case letters). Then we'd distribute CaCpq obtaining CCapCaq. Now C3-3 is Cpp. With CCapCaq as the major premise and Cpp as the minor premise we can detach Cpq, given that we can substitute for variables {a, b, c, d, e}. Then to get to Cpr, we first obtain CpCqr. Then we distribute it obtaining CCpqCpr. And then using CCpqCpr as the major premise and Cpq as the minor premise we obtain Cpr. We can write this up as follows:

hypothesis 1 |  Cpq  this is C3-4 where the numerals refer to the above
hypothesis 2 || Cqr
D[A1].2    3 || CaCqr (we have CCqrCaCqr, Cqr also) this is C3-2
D[A2].3    4 || CCaqCar (we had CaCqr and CCaCqrCCaqCar also)
D4.1       5 || Cpr  (substituting only "a" with "p" here)

Now, the proof works similarly in a certain sense. Let's relabel the axioms

1 CpCqp
2 CCpCqrCCpqCpr
3 CCNpNqCqp

Suppose that CCNpNqCqp was the major premise in some detachment, and Cqp was the minor premise. We would take D1.3 obtaining 4 CpCCNqNrCrq effectively giving us Ch-m. Then distributing CpCCNqNrCrq or equivalently taking D2.4 we obtain 5 CCpCNqNrCpCrq giving us z. Now since Cqp is the supposed minor premise of the original derivation we can use axiom 1 to detach CpCqp giving us Ch-n. But of course the last step probably seems silly, since we already had CpCqp, I've just made a comparison here. Then taking D5.1 yields CNpCpq or CNrCrq however you want to write it. Or more compactly:

axiom 1 CpCqp
axiom 2 CCpCqrCCpqCpr
axiom 3 CCNpNqCqp
D1.3  4 CpCCNqNrCrq
D2.4  5 CCpCNqNrCpCrq
D5.1  6 CNrCrq.
$\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.