patternMinor
P, Q, ((P→Q)→R) ⊢ R using only modus ponens
Viewed 0 times
modusonlyusingponens
Problem
Can $R$ be inferred from $P$, $Q$, and $(P \to Q) \to R$ using only modus ponens?
My understanding is that it can, as shown below, but I was told this was incorrect.
Proof of ${P, Q, (P \to Q) \to R} \vdash R$ using modus ponens:
My understanding is that it can, as shown below, but I was told this was incorrect.
Proof of ${P, Q, (P \to Q) \to R} \vdash R$ using modus ponens:
P, Q, (P->Q)->R : Given
Q, (Q)->R : By Modus Ponens
R : By Modus PonensSolution
Given $P$, $Q$ and $(P \to Q) \to R$, there is no way to apply modus ponens. You would need to have $(P \to Q)$. If you had $P$, $Q$ and $P \to (Q \to R)$, then you could apply modus ponens twice the way you did, but $P \to (Q \to R)$ and $(P \to Q) \to R$ are different.
$P \to (Q \to R)$ says “if I have P, then if I have Q, then I can get R”.
$(P \to Q) \to R$ says “if I can get Q given P, then I can get R”. It requires a method of getting from P to Q.
It is true that given $P$, $Q$ and $(P \to Q) \to R$, you can deduce $R$. You can see that with truth tables, for example. However this requires logical rules that go beyond modus ponens. This has a mathematical consequence: this deduction is only valid in logics where those extra rules are available (such as classical logic).
There is a computational interpretation of these deductions. $P \to Q$ can be interpreted as a function that produces a $Q$ given a $P$. Modus ponens then comes down to applying a function. Given a function $f : P \to (Q \to R)$, you can apply $f$ to a $P$, which produces a new function $Q \to R$; when you apply this function to a $Q$, you get an $R$. Given a function $g : (P \to Q) \to R$, the situation is different: you need a function from $P$ to $Q$ to get started. Given a $Q$, it's easy: you can use a constant function that returns this $Q$. But that first step of constructing the constant function is not modus ponens.
$P \to (Q \to R)$ says “if I have P, then if I have Q, then I can get R”.
$(P \to Q) \to R$ says “if I can get Q given P, then I can get R”. It requires a method of getting from P to Q.
It is true that given $P$, $Q$ and $(P \to Q) \to R$, you can deduce $R$. You can see that with truth tables, for example. However this requires logical rules that go beyond modus ponens. This has a mathematical consequence: this deduction is only valid in logics where those extra rules are available (such as classical logic).
There is a computational interpretation of these deductions. $P \to Q$ can be interpreted as a function that produces a $Q$ given a $P$. Modus ponens then comes down to applying a function. Given a function $f : P \to (Q \to R)$, you can apply $f$ to a $P$, which produces a new function $Q \to R$; when you apply this function to a $Q$, you get an $R$. Given a function $g : (P \to Q) \to R$, the situation is different: you need a function from $P$ to $Q$ to get started. Given a $Q$, it's easy: you can use a constant function that returns this $Q$. But that first step of constructing the constant function is not modus ponens.
Context
StackExchange Computer Science Q#22514, answer score: 5
Revisions (0)
No revisions yet.