Trakhtenbrot's Theorem states that the set of first-order sentences valid on every finite structure is not decidable, meaning no algorithm can determine in general whether a given first-order sentence holds in all finite models. Named for Boris Trakhtenbrot, it shows that finite model theory does not inherit the completeness and decidability properties available for first-order logic over arbitrary structures, since validity on finite models and validity in general diverge in this fundamental way.
Facts
StatementThe problem of validity in first-order logic on the class of all finite models is undecidable. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Trakhtenbrot's theorem (Wikipedia)
Source Trakhtenbrot's theorem (Wikipedia)
Principal Result Of
Source Boris Trakhtenbrot (Wikipedia)
Proved By
Source Trakhtenbrot's theorem (Wikipedia)
In the Other Atlases
Credited To
Also in Computing Atlas: credited with this subject.
Sources
1. Trakhtenbrot's theorem (Wikipedia)
Mathematical formulation section
The problem of validity in first-order logic on the class of all finite models is undecidable.
Opening section, publication sentence
The theorem was first published in 1950
Proved By: Boris Trakhtenbrot, Lead sentence
In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable.
In Branch: Model Theory, Lead paragraph
In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable.
In Branch: Computability Theory, Lead paragraph
In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable.
In Group: Mathematical Logic and Model Theory, Lead section
In logic, finite model theory, and computability theory, Trakhtenbrot's theorem
View the SourceBoris Trakhtenbrot (Wikipedia)
Principal Result Of: Boris Trakhtenbrot, Biography, Trakhtenbrot theorem (principal result)Quote, Principal Result Of: Boris Trakhtenbrot, Biography, Trakhtenbrot theorem (principal result)
He also discovered and proved the theorem in logic, model theory, and computability theory now known as Trakhtenbrot's theorem.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.