Hilbert-style deduction system

From Wikipedia, the free encyclopedia

Notepad
 To comply with Wikipedia's quality standards, this article may need to be rewritten.
Please help improve this article. The discussion page may contain suggestions.

In logic, especially mathematical logic, a Hilbert-style deduction system is a type of system of formal deduction attributed to Gottlob Frege[1] and David Hilbert. These deductive systems are most often studied for first-order logic, but are of interest for other logics as well.

Most variants of Hilbert-style deductions systems take a characteristic tack the way they balance a trade-off between logical axioms and rules of inference.[1] Hilbert-style deduction systems can be characterized by the choice of a large number of schemes of logical axioms and a small set of rules of inference. The most commonly studied Hilbert-style deduction system has just one rule of inference – modus ponens – and several infinite axiom schemes.

A characteristic feature of the various variants of Hilbert-style deduction systems is that the context is not changed in any of their rules of inference, while both natural deduction and sequent calculus contain some context-changing rules. Thus, if we are interested only in the derivability of tautologies, no hypothetical judgments, then we can formalize the Hilbert-style deduction system in such a way that its rules of inference contain only judgments of a rather simple form. The same cannot be done with the other two deductions systems: as context is changed in some of their rules of inferences, they cannot be formalized so that hypothetical judgments could be avoided — not even if we want to use them just for proving derivability of tautologies.

Systems of natural deduction take the opposite tack, including many deduction rules but very few or no axiom schemes.

Contents

[edit] Formal deductions

A graphic representation of the deduction system

In a Hilbert-style deduction system, a formal deduction is a finite sequence of formulas in which each formula is either an axiom or is obtained from previous formulas by a rule of inferences. These formal deductions are meant to mirror natural-language proofs, although they are far more detailed.

Suppose Γ is a set of formulas, considered as hypotheses. For example Γ could be a set of axioms for group theory or set theory. The notation \Gamma \vdash \phi means that there is a deduction that ends with φ using as axioms only logical axioms and elements of Γ. Thus, informally, \Gamma \vdash \phi means that φ is provable assuming all the formulas in Γ.

Hilbert-style deduction systems are characterized by the use of numerous schemes of logical axioms. An axiom scheme is an infinite set of axioms obtained by substituting all formulas of some form into a specific pattern. Not only are the axioms generated from this pattern, but also any generalization of one of these axioms, is included in the set of logical axioms. A generalization of a formula is obtained by prefixing zero or more universal quantifiers on the formula; thus

\forall y ( \forall x Pxy \to Pty)

is a generalization of \forall x Pxt \to Pty.

[edit] Logical axioms

A common Hilbert-style system has six infinite axiom schemes and one additional axiom. In order to reduce the number of axiom schemes, this system assumes all formulas have been rewritten to use only the connectives \lnot and \to and only the quantifier \forall. As discussed below, it is possible to extend the system to include additional logical connectives, such as \land and \lor, without enlarging the class of deducible formulas.

The first three logical axiom schemes allow (together with modus ponens) for the manipulation of logical connectives.

1. \phi \to \left( \psi \to \phi \right)
2. \left ( \phi \to ( \psi \rightarrow \xi \right)) \to \left( \left( \phi \to \psi \right) \to \left( \phi \to \xi \right) \right)
3. \left ( \lnot \phi \to \lnot \psi \right) \to \left( \psi \to \phi \right)

The fourth, fifth, and sixth logical axiom schemes provide ways to add, manipulate, and remove universal quantifiers.

4. \forall x \left( \phi \right) \to \phi[x:=t] where t may be substituted for xin φ
5. \forall x \left( \phi \to \psi \right) \to \left( \forall x \left( \phi \right) \to \forall x \left( \psi \right) \right)
6. \phi \to \forall x \left( \phi \right) where x is not a free variable of φ.

The final axiom schemes are required to work with formulas involving the equality symbol.

7. x = x for every variable x.
8. \left( x = y \right) \to \left( \phi[z:=x] \to \phi[z:=y] \right)

[edit] Conservative extensions

It is common to include in a Hilbert-style deduction system only axioms for implication and negation. Given these axioms, it is possible to form conservative extensions of the deduction theorem that permit the use of additional connectives. These extensions are called conservative because if a formula φ involving new connectives is rewritten as a logically equivalent formula θ involving only negation, implication, and universal quantification, then φ is derivable in the extended system if and only if θ is derivable in the original system. When fully extended, a Hilbert-style system will resemble more closely a system of natural deduction.

[edit] Existential quantification

  • Introduction
  • Elimination

[edit] Conjunction and disjunction

  • Conjunction introduction and elimination
  • Disjunction introduction and elimination

[edit] Metatheorems

Because Hilbert-style systems have very few deduction rules, it is common to prove metatheorems that show that additional deduction rules add no deductive power, in the sense that a deduction using the new deduction rules can be converted into a deduction using only the original deduction rules.

Some common metatheorems of this form are:

  • The deduction theorem: \Gamma;\phi \vdash \psi if and only if \Gamma \vdash \phi \to \psi.
  • \Gamma \vdash \phi \leftrightarrow \psi if and only if \Gamma \vdash \phi \to \psi and \Gamma \vdash \psi \to \phi.
  • Contraposition: If \Gamma;\phi \vdash \psi then \Gamma;\lnot \psi \vdash \lnot \phi.
  • Generalization: If \Gamma \vdash \phi and x does not occur free in any formula of Γ then \Gamma \vdash \forall x \phi.

[edit] Further connections

Axiom 1, 2 together with deduction rule modus ponens, corresponds to combinatory logic base combinators K, S together with the notion of application. See also Curry-Howard correspondence.

[edit] Notes

  1. ^ a b Máté & Ruzsa 1997:129

[edit] References

  • Curry, Haskell B.; Robert Feys (1958). Combinatory Logic Vol. I 1. Amsterdam: North Holland. 
  • Monk, J. Donald (1976). Mathematical Logic. Springer-Verlag. 
  • Ruzsa, Imre; Máté, András (1997). Bevezetés a modern logikába (in Hungarian). Budapest: Osiris Kiadó. 
  • Tarski, Alfred (1990). Bizonyítás és igazság (in Hungarian). Budapest: Gondolat.  It is a Hungarian translation of Alfred Tarski's selected papers on semantic theory of truth.

[edit] External links

Farmer, W. M. Propositional logic (pdf). It describes (among others) a part of the Hilbert-style deduction system (restricted to propositional calculus).