This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs attention from an expert in mathematics. See the talk page for details. WikiProject Mathematics may be able to help recruit an expert. (March 2011) This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2019) (Learn how and when to remove this template message) (Learn how and when to remove this template message)
In mathematical physics, Hilbert system is an infrequently used term for a physical system described by a C*-algebra.

In logic, especially mathematical logic, a Hilbert system, sometimes called Hilbert calculus, Hilbert-style deductive system or Hilbert–Ackermann 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 systems take a characteristic tack in the way they balance a trade-off between logical axioms and rules of inference.[1] Hilbert systems can be characterised by the choice of a large number of schemes of logical axioms and a small set of rules of inference. Systems of natural deduction take the opposite tack, including many deduction rules but very few or no axiom schemes. The most commonly studied Hilbert systems have either just one rule of inference – modus ponens, for propositional logics – or two – with generalisation, to handle predicate logics, as well – and several infinite axiom schemes. Hilbert systems for propositional modal logics, sometimes called Hilbert-Lewis systems, are generally axiomatised with two additional rules, the necessitation rule and the uniform substitution rule.

A characteristic feature of the many variants of Hilbert 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 one is interested only in the derivability of tautologies, no hypothetical judgments, then one can formalize the Hilbert 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:[citation needed] 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.

Formal deductions

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 inference. 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 means that there is a deduction that ends with using as axioms only logical axioms and elements of . Thus, informally, 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. The set of logical axioms includes not only those axioms generated from this pattern, but also any generalization of one of those axioms. A generalization of a formula is obtained by prefixing zero or more universal quantifiers on the formula; for example is a generalization of .

Logical axioms

There are several variant axiomatisations of predicate logic, since for any logic there is freedom in choosing axioms and rules that characterise that logic. We describe here a Hilbert system with nine axioms and just the rule modus ponens, which we call the one-rule axiomatisation and which describes classical equational logic. We deal with a minimal language for this logic, where formulas use only the connectives and and only the quantifier . Later we show how the system can be extended to include additional logical connectives, such as and , without enlarging the class of deducible formulas.

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


The axiom P1 is redundant, as it follows from P3, P2 and modus ponens (see proof). These axioms describe classical propositional logic; without axiom P4 we get positive implicational logic. Minimal logic is achieved either by adding instead the axiom P4m, or by defining as .


Intuitionistic logic is achieved by adding axioms P4i and P5i to positive implicational logic, or by adding axiom P5i to minimal logic. Both P4i and P5i are theorems of classical propositional logic.


Note that these are axiom schemes, which represent infinitely many specific instances of axioms. For example, P1 might represent the particular axiom instance , or it might represent : the is a place where any formula can be placed. A variable such as this that ranges over formulae is called a 'schematic variable'.

With a second rule of uniform substitution (US), we can change each of these axiom schemes into a single axiom, replacing each schematic variable by some propositional variable that isn't mentioned in any axiom to get what we call the substitutional axiomatisation. Both formalisations have variables, but where the one-rule axiomatisation has schematic variables that are outside the logic's language, the substitutional axiomatisation uses propositional variables that do the same work by expressing the idea of a variable ranging over formulae with a rule that uses substitution.

US. Let be a formula with one or more instances of the propositional variable , and let be another formula. Then from , infer .[dubious ]

The next three logical axiom schemes provide ways to add, manipulate, and remove universal quantifiers.

Q5. where t may be substituted for x in
Q7. where x is not free in .

These three additional rules extend the propositional system to axiomatise classical predicate logic. Likewise, these three rules extend system for intuitionstic propositional logic (with P1-3 and P4i and P5i) to intuitionistic predicate logic.

Universal quantification is often given an alternative axiomatisation using an extra rule of generalisation (see the section on Metatheorems), in which case the rules Q6 and Q7 are redundant.[dubious ]

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

I8. for every variable x.

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.

Existential quantification

where is not a free variable of .

Conjunction and disjunction

elimination left:
elimination right:
introduction left:
introduction right:


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:

Some useful theorems and their proofs

Following are several theorems in propositional logic, along with their proofs (or links to these proofs in other articles). Note that since (P1) itself can be proved using the other axioms, in fact (P2), (P3) and (P4) suffice for proving all these theorems.

(HS1) - Hypothetical syllogism, see proof.
(L1) - proof:
(1)       (instance of (P3))
(2)       (instance of (P1))
(3)       (from (2) and (1) by modus ponens)
(4)       (instance of (HS1))
(5)       (from (3) and (4) by modus ponens)
(6)       (instance of (P2))
(7)       (from (6) and (5) by modus ponens)

The following two theorems are known together as Double negation:

See proofs.
(L2) - for this proof we use the method of the hypothetical syllogism metatheorem as a shorthand for several proof steps:
(1)       (instance of (P3))
(2)       (instance of (HS1))
(3)       (from (1) and (2) using the hypothetical syllogism metatheorem)
(4)       (instance of (P3))
(5)       (from (3) and (4) using modus ponens)
(6)       (instance of (P2))
(7)       (instance of (P2))
(8)       (from (6) and (7) using modus ponens)
(9)       (from (8) and (5) using modus ponens)
(HS2) - an alternative form of the hypothetical syllogism. proof:
(1)       (instance of (HS1))
(2)       (instance of (L2))
(3) (from (1) and (2) by modus ponens)
(TR1) - Transposition, see proof (the other direction of transposition is (P4)).
(TR2) - another form of transposition; proof:
(1)       (instance of (TR1))
(2)       (instance of (DN1))
(3)       (instance of (HS1))
(4)       (from (2) and (3) by modus ponens)
(5)       (from (1) and (4) using the hypothetical syllogism metatheorem)
(L3) - proof:
(1)       (instance of (P2))
(2)       (instance of (P4))
(3)       (from (1) and (2) using the hypothetical syllogism metatheorem)
(4)       (instance of (P3))
(5)       (from (3) and (4) using modes ponens)
(6)       (instance of (P4))
(7)       (from (5) and (6) using the hypothetical syllogism metatheorem)
(8)       (instance of (P1))
(9)       (instance of (L1))
(10)       (from (8) and (9) using modes ponens)
(11)       (from (7) and (10) using the hypothetical syllogism metatheorem)

Alternative axiomatizations

Further information: List of logic systems

The axiom 3 above is credited to Łukasiewicz.[2] The original system by Frege had axioms P2 and P3 but four other axioms instead of axiom P4 (see Frege's propositional calculus). Russell and Whitehead also suggested a system with five propositional axioms.

Further connections

Axioms P1, P2 and P3, with the deduction rule modus ponens (formalising intuitionistic propositional logic), correspond to combinatory logic base combinators I, K and S with the application operator. Proofs in the Hilbert system then correspond to combinator terms in combinatory logic. See also Curry–Howard correspondence.

See also


  1. ^ a b Máté & Ruzsa 1997:129
  2. ^ A. Tarski, Logic, semantics, metamathematics, Oxford, 1956