Herbrand's theorem

E238234

mathematical theorem result in mathematical logic result in proof theory

Herbrand's theorem is a fundamental result in mathematical logic and proof theory that characterizes the validity of first-order formulas via finite sets of ground instances, forming a basis for automated theorem proving.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (6)

Label	Occurrences
Herbrand’s theorem	10
Herbrand's theorem canonical	4
Herbrand theorem	2
Herbrand's theorem for unsatisfiability	1
Herbrand's theorem for validity	1
Herbrand-style proof calculi	1

How this entity was disambiguated

This entity first appeared as the object of triple T2139569 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Herbrand's theorem
Context triple: [Jacques Herbrand, knownFor, Herbrand's theorem]

A. Hilbert’s program
Hilbert’s program was an influential early-20th-century initiative in the foundations of mathematics that sought to formalize all of mathematics and prove its consistency using finitistic methods.
B. Tarski's undefinability theorem
Tarski's undefinability theorem is a fundamental result in mathematical logic showing that, in sufficiently strong formal systems, the notion of truth for the language of the system cannot be defined within that same language.
C. completeness theorem for first-order logic
The completeness theorem for first-order logic is a fundamental result in mathematical logic, proved by Kurt Gödel, which states that every logically valid first-order formula is provable from the axioms of first-order logic.
D. Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
E. Church–Rosser property
The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Herbrand's theorem
Target entity description: Herbrand's theorem is a fundamental result in mathematical logic and proof theory that characterizes the validity of first-order formulas via finite sets of ground instances, forming a basis for automated theorem proving.

A. Hilbert’s program
Hilbert’s program was an influential early-20th-century initiative in the foundations of mathematics that sought to formalize all of mathematics and prove its consistency using finitistic methods.
B. Tarski's undefinability theorem
Tarski's undefinability theorem is a fundamental result in mathematical logic showing that, in sufficiently strong formal systems, the notion of truth for the language of the system cannot be defined within that same language.
C. completeness theorem for first-order logic
The completeness theorem for first-order logic is a fundamental result in mathematical logic, proved by Kurt Gödel, which states that every logically valid first-order formula is provable from the axioms of first-order logic.
D. Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
E. Church–Rosser property
The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
F. None of above. chosen

Statements (45)

Predicate	Object
instanceOf	mathematical theorem ⓘ result in mathematical logic ⓘ result in proof theory ⓘ
appliesTo	Skolemized formulas ⓘ prenex form formulas ⓘ
assumes	classical first-order logic ⓘ
characterizes	validity of first-order formulas ⓘ
concerns	first-order logic ⓘ first-order predicate calculus ⓘ
concernsProperty	satisfiability of first-order formulas ⓘ unsatisfiability of sets of clauses ⓘ
field	automated theorem proving ⓘ mathematical logic ⓘ proof theory ⓘ
formalizes	connection between models and ground instances ⓘ
hasConsequence	existence of Herbrand disjunctions ⓘ reduction of first-order entailment to propositional entailment over ground instances ⓘ
hasVersion	Herbrand's theorem for unsatisfiability ⓘ linked to: Herbrand's theorem Herbrand's theorem for validity ⓘ linked to: Herbrand's theorem
historicalPeriod	20th century ⓘ
implies	existence of finite set of ground instances for valid formulas ⓘ
influenced	development of Prolog ⓘ development of automated deduction ⓘ development of logic programming ⓘ
introducedBy	Jacques Herbrand ⓘ
isAbout	elimination of quantifiers via ground instances ⓘ reduction of first-order reasoning to propositional reasoning ⓘ
namedAfter	Jacques Herbrand ⓘ
provides	basis for automated theorem proving ⓘ foundation for resolution methods ⓘ foundation for sequent calculi for first-order logic ⓘ foundation for tableau methods ⓘ
relatedTo	Gödel's completeness theorem ⓘ linked to: completeness theorem for first-order logic Skolemization ⓘ compactness theorem ⓘ linked to: completeness theorem for first-order logic resolution principle ⓘ semantic tableaux ⓘ
relates	first-order validity to propositional validity ⓘ
usedIn	automated theorem provers ⓘ model checking of first-order properties ⓘ proof search procedures ⓘ
usesConcept	Herbrand base ⓘ Herbrand universe ⓘ ground instance ⓘ ground term ⓘ

How these facts were elicited

Referenced by (19)

Full triples — surface form annotated when it differs from this entity's canonical label.

Jacques Herbrand → knownFor → Herbrand's theorem ⓘ

Jacques Herbrand → theoremNamedAfter → Herbrand's theorem ⓘ

Herbrand's theorem → hasVersion → Herbrand's theorem for unsatisfiability ⓘ

linked to: Herbrand's theorem

Herbrand's theorem → hasVersion → Herbrand's theorem for validity ⓘ

linked to: Herbrand's theorem

Herbrand universe → appearsIn → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

Herbrand expansion → relatedTo → Herbrand theorem ⓘ

linked to: Herbrand's theorem

Recherches sur la théorie de la démonstration → introducesConcept → Herbrand's theorem ⓘ

Herbrand disjunction → isCentralTo → Herbrand's theorem ⓘ

Herbrand disjunction → occursIn → Herbrand-style proof calculi ⓘ

linked to: Herbrand's theorem

Davis–Putnam algorithm → relatedConcept → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

Herbrand interpretation → roleIn → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

First-Order Logic and Automated Theorem Proving → topic → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

Logic for Computer Science: Foundations of Automatic Theorem Proving → hasSubject → Herbrand’s theorem ⓘ

subject linked to: "Logic for Computer Science: Foundations of Automatic Theorem Proving"

linked to: Herbrand's theorem

Herbrand base → relatedConcept → Herbrand theorem ⓘ

linked to: Herbrand's theorem

Skolemization → relatedConcept → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

Herbrand semantics → relatedConcept → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

Herbrand conjunction (for universal formulas) → usedIn → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

Herbrand quotient → relatedTo → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

cut-elimination theorem → relatedTo → Herbrand’s theorem ⓘ

linked to: Herbrand's theorem

All labels observed (6)

How this entity was disambiguated Show

Statements (45)

How these facts were elicited Show

Referenced by (19)

How this entity was disambiguated

How these facts were elicited