I'm trying to prove the statement ~(a->~b) => a in a Hilbert style system. Unfortunately it seems like it is impossible to come up with a general algorithm to find a proof, but I'm looking for a brute force type strategy. Any ideas on how to attack this are welcome.
R – Hilbert System – Automate Proof
If You like "programming" in combinatory logic, then
The possibility of this translation in ensured by Curry-Howard correspondence.
Unfortunately, the situation is so simple only for a subset of (propositional) logic: restricted using conditionals. Negation is a complication, I know nothing about that. Thus I cannot answer this concrete question:
¬ (α ⊃ ¬β) ⊢ α
But in cases where negation is not part of the question, the mentioned automatic translation (and back-translation) can be a help, provided that You have already practice in functional programming or combinatory logic.
Of course, there are other helps, too, where we can remain inside the realm of logic:
As for theorem provers, as far as I know, the capabilities of some of them are extended so that they can harness interactive human assistance. E.g. Coq is such.
Let us see an example. How to prove α ⊃ α?
Let us prove theorem: α ⊃ α is deducible for any α proposition.
Let us introduce the following notations and abbreviations, developing a "proof calculus":
A tree diagram notation:
Axiom scheme — Verum ex quolibet:
⊢ α ⊃ β ⊃ α
Axiom scheme — chain rule:
⊢ (α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ
Rule of inference — modus ponens:
⊢ α ⊃ β ⊢ α
Let us see a tree diagram representation of the proof:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━ [CRα, α⊃α, α] ━━━━━━━━━━━━━━━ [VEQα, α⊃α]
⊢ [α⊃(α⊃α)⊃α]⊃(α⊃α⊃α)⊃α⊃α ⊢ α ⊃ (α ⊃ α) ⊃ α
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ [MP] ━━━━━━━━━━━ [VEQα,α]
⊢ (α ⊃ α ⊃ α) ⊃ α ⊃ α ⊢ α ⊃ α ⊃ α
⊢ α ⊃ α
Let us see an even conciser (algebraic? calculus?) representation of the proof:
(CRα,α⊃α,α VEQα,α ⊃ α) VEQα,α: ⊢ α⊃ α
so, we can represent the proof tree by a single formula:
It is worth of keep record about the concrete instantiation, that' is typeset here with subindexical parameters.
As it will be seen from the series of examples below, we can develop a proof calculus, where axioms are notated as sort of base combinators, and modus ponens is notated as a mere application of its "premise" subproofs:
VEQα,β: ⊢ α ⊃ β ⊃ α
Verum ex quolibet axiom scheme instantiated with α,β provides a proof for the statement, that α ⊃ β ⊃ α is deducible.
VEQα,α: ⊢ α ⊃ α ⊃ α
Verum ex quolibet axiom scheme instantiated with α,α provides a proof for the statement, that α ⊃ α ⊃ α is deducible.
VEQα, α⊃α: ⊢ α ⊃ (α ⊃ α) ⊃ α
Verum ex quolibet axiom scheme instantiated with α, α⊃α provides a proof for the statement, that α ⊃ (α ⊃ α) ⊃ α is deducible.
CRα,β,γ: ⊢ (α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ
Chain rule axiom scheme instantiated with α,β,γ provides a proof for the statement, that (α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ is deducible.
CRα,α⊃α,α: ⊢ [α ⊃ (α⊃α) ⊃ α] ⊃ (α ⊃ α⊃α) ⊃ α⊃ α
Chain rule axiom scheme instantiated with α,α⊃α,α provides a proof for the statement, that [α ⊃ (α⊃α) ⊃ α] ⊃ (α ⊃ α⊃α) ⊃ α⊃ α is deducible.
CRα,α⊃α,α VEQα,α ⊃ α: ⊢ (α ⊃ α⊃α) ⊃ α⊃ α
If we combine CRα,α⊃α,α and VEQα,α ⊃ α together via modus ponens, then we get a proof that proves the following statement: (α ⊃ α⊃α) ⊃ α⊃ α is deducible.
(CRα,α⊃α,α VEQα,α ⊃ α) VEQα,α: ⊢ α⊃ α
If we combine the compund proof (CRα,α⊃α,α) together with VEQα,α ⊃ α (via modus ponens), then we get an even more compund proof. This proves the following statement: α⊃ α is deducible.
Although all this above has indeed provided a proof for the expected theorem, but it seems very unintuitive. It cannot be seen how people can "find out" the proof.
Let us see another field, where similar problems are investigated.
Untyped combinatory logic
Combinatory logic can be regarded also as an extremely minimalistic functional programming language. Despite of its minimalism, it entirely Turing complete, but evenmore, one can write quite intuitive and complex programs even in this seemingly obfuscated language, in a modular and reusable way, with some practice gained from "normal" functional programming and some algebraic insights, .
Adding typing rules
Combinatory logic also has typed variants. Syntax is augmented with types, and evenmore, in addition to reduction rules, also typing rules are added.
For base combinators:
Typing rule of application:
Notations and abbreviations
It can be seen that the "patterns" are isomorphic in the proof calculus and in this typed combinatory logic.
But what is the gain? Why should we translate problems to combinatory logic? I, personally, find it sometimes useful, because functional programming is a thing which has a large literature and is applied in practical problems. People can get used to it, when forced to use it in erveryday programming tasks ans pracice. And some tricks and hints of functional programming practice can be exploited very well in combinatory logic reductions. And if a "transferred" practice develops in combinatory logic, then it can be harnessed also in finding proofs in Hilbert system.
Links how types in functional programming (lambda calculus, combinatory logic) can be translated into logical proofs and theorems:
Links (or books) how to learn methods and practice to program directly in combinatory logic: