Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Trakhtenbrots_theorem> ?p ?o }
Showing triples 1 to 33 of
33
with 100 triples per page.
- Trakhtenbrots_theorem abstract "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 (FO) on the class of all finite models is undecidable. In fact, the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable).It is considered a very important result, since it implies that the completeness theorem (that is fundamental to FO) does not hold in the finite case. Also it seems counter intuitive that being valid over all structures is 'easier' than over just the finite ones.The Theorem was first published in 1950: \"The Impossibility of an Algorithm for the Decidability Problem on Finite Classes\".".
- Trakhtenbrots_theorem wikiPageExternalLink Churchtrakhtenbrot.pdf.
- Trakhtenbrots_theorem wikiPageID "4232656".
- Trakhtenbrots_theorem wikiPageLength "9705".
- Trakhtenbrots_theorem wikiPageOutDegree "19".
- Trakhtenbrots_theorem wikiPageRevisionID "700238564".
- Trakhtenbrots_theorem wikiPageWikiLink Boris_Trakhtenbrot.
- Trakhtenbrots_theorem wikiPageWikiLink Category:Computability_theory.
- Trakhtenbrots_theorem wikiPageWikiLink Category:Finite_model_theory.
- Trakhtenbrots_theorem wikiPageWikiLink Computability_theory.
- Trakhtenbrots_theorem wikiPageWikiLink Finite_model_theory.
- Trakhtenbrots_theorem wikiPageWikiLink First-order_logic.
- Trakhtenbrots_theorem wikiPageWikiLink Gxc3xb6dels_completeness_theorem.
- Trakhtenbrots_theorem wikiPageWikiLink Logic.
- Trakhtenbrots_theorem wikiPageWikiLink Löwenheim–Skolem_theorem.
- Trakhtenbrots_theorem wikiPageWikiLink Recursive_set.
- Trakhtenbrots_theorem wikiPageWikiLink Recursively_enumerable_set.
- Trakhtenbrots_theorem wikiPageWikiLink Satisfiability.
- Trakhtenbrots_theorem wikiPageWikiLink Validity.
- Trakhtenbrots_theorem wikiPageWikiLink Σ-sentence.
- Trakhtenbrots_theorem wikiPageWikiLinkText "Trakhtenbrot 1950".
- Trakhtenbrots_theorem wikiPageWikiLinkText "Trakhtenbrot's theorem".
- Trakhtenbrots_theorem subject Category:Computability_theory.
- Trakhtenbrots_theorem subject Category:Finite_model_theory.
- Trakhtenbrots_theorem comment "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 (FO) on the class of all finite models is undecidable. In fact, the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable).It is considered a very important result, since it implies that the completeness theorem (that is fundamental to FO) does not hold in the finite case.".
- Trakhtenbrots_theorem label "Trakhtenbrot's theorem".
- Trakhtenbrots_theorem sameAs Q10965882.
- Trakhtenbrots_theorem sameAs Satz_von_Trachtenbrot.
- Trakhtenbrots_theorem sameAs Teoremo_de_Trahtenbrot.
- Trakhtenbrots_theorem sameAs m.0br9_c.
- Trakhtenbrots_theorem sameAs Q10965882.
- Trakhtenbrots_theorem wasDerivedFrom Trakhtenbrots_theorem?oldid=700238564.
- Trakhtenbrots_theorem isPrimaryTopicOf Trakhtenbrots_theorem.