((())()) is a theorem of PR?

211 Views Asked by At

If we have the following formal system, called PR whose formulas are strings of well-formed parentheses. The language has two symbols '(' and ')'. Any expression is a formula. The only axiom is (). Let $\phi$ and $\psi$ be two formulas of PR; there are three rules of inference:

$$ \frac{\phi}{(\phi)} \ \text{ADD} \quad \quad \frac{\phi}{\phi \phi} \ \text{DOUBLE} \quad \quad \frac{\phi ( \ ) \psi}{\phi \psi} \ \text{OMIT} $$

((())()) is a theorem of PR?

1

There are 1 best solutions below

2
On BEST ANSWER

Here's a hint:

Recall that any expression is a formula. In particular, $\phi = {(())(}$ and $\psi = {)}$ are both formulas, so that one instance of OMIT is

$$ \frac{\phi (\ ) \psi}{\phi \psi} = \frac{(())( \ \ ( \ ) \ \ )}{(())()} $$

This is counterintuitive, since you have to work with expressions with unmatched parentheses in the middle of your derivation, but is completely allowable from the rules you've stated. Do you see how to finish from here?

(As an aside, I suspect if you require $\phi$ and $\psi$ to be theorems at every intermediate stage, then $((())())$ will not be a theorem, but I don't have time to work on a proof right now.)


I hope this helps ^_^