Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Herbrand’s theorem
View through CrossRef
According to Herbrand’s theorem, each formula F of quantification theory can be associated with a sequence F1, F2, F3,… of quantifier-free formulas such that F is provable just in case Fn is truth-functionally valid for some n. This theorem was the centrepiece of Herbrand’s dissertation, written in 1929 as a contribution to Hilbert’s programme. It provides a finitistically meaningful interpretation of quantification over an infinite domain. Furthermore, it can be applied to yield various consistency and decidability results for formal systems. Herbrand was the first to exploit it in this way, and his work has influenced subsequent research in these areas. While Herbrand’s approach to proof theory has perhaps been overshadowed by the tradition which derives from Gentzen, recent work on automated reasoning continues to draw on his ideas.
Title: Herbrand’s theorem
Description:
According to Herbrand’s theorem, each formula F of quantification theory can be associated with a sequence F1, F2, F3,… of quantifier-free formulas such that F is provable just in case Fn is truth-functionally valid for some n.
This theorem was the centrepiece of Herbrand’s dissertation, written in 1929 as a contribution to Hilbert’s programme.
It provides a finitistically meaningful interpretation of quantification over an infinite domain.
Furthermore, it can be applied to yield various consistency and decidability results for formal systems.
Herbrand was the first to exploit it in this way, and his work has influenced subsequent research in these areas.
While Herbrand’s approach to proof theory has perhaps been overshadowed by the tradition which derives from Gentzen, recent work on automated reasoning continues to draw on his ideas.
Related Results
Herbrand's Theorem in Inductive Proofs
Herbrand's Theorem in Inductive Proofs
An inductive proof can be represented as a proof schema, i.e. as a parameterized sequence of proofs defined in a primitive recursive way. A corresponding cut-elimination method, ca...
Extracting Herbrand systems from refutation schemata
Extracting Herbrand systems from refutation schemata
Abstract
An inductive proof can be represented as a proof schema, i.e. as a parameterized sequence of proofs defined in a primitive recursive way. A corresponding cu...
An abstract form of the first epsilon theorem
An abstract form of the first epsilon theorem
Abstract
We present a new method of computing Herbrand disjunctions. The up-to-date most direct approach to calculate Herbrand disjunctions is based on Hilbert’s eps...
VIRTUAL CONTACT POINT METHOD.
SIDE MILL GENERATING A CYLINDRICAL HELICAL SURFACE
VIRTUAL CONTACT POINT METHOD.
SIDE MILL GENERATING A CYLINDRICAL HELICAL SURFACE
Cylindrical helical surfaces with constant pitch can be generated using tools bounded by primary peripheral surfaces of revolution, such as side mills, end mills, cylindrical plani...
ON SKOLEMIZATION AND PROOF COMPLEXITY
ON SKOLEMIZATION AND PROOF COMPLEXITY
The impact of Skolemization on the complexity of proofs in the sequent calculus is investigated. It is shown that prefix Skolemization may result in a nonelementary increase of Her...
An embedding theorem for multidimensional subshifts
An embedding theorem for multidimensional subshifts
AbstractKrieger’s embedding theorem provides necessary and sufficient conditions for an arbitrary subshift to embed in a given topologically mixing
$\mathbb {Z}$
-subshift of fini...
Disproving the Coase Theorem?
Disproving the Coase Theorem?
This essay explores the detailed argument of the Coase Theorem, as found in Ronald Coase's The Problem of Social Cost and subsequently defended by Coase in The Firm, the Market, an...
The complexity of the four colour theorem
The complexity of the four colour theorem
AbstractThe four colour theorem states that the vertices of every planar graph can be coloured with at most four colours so that no two adjacent vertices receive the same colour. T...