Tennenbaum's theorem (original) (raw)
Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of first-order Peano arithmetic (PA) can be recursive (Kaye 1991:153ff).
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Tennenbaum (nach Stanley Tennenbaum) ist ein Ergebnis der mathematischen Logik. Er besagt, dass kein abzählbares Nichtstandardmodell der Peano-Arithmetik berechenbar sein kann. Dabei heißt eine Struktur in der Sprache der Peano-Arithmetik berechenbar, wenn es berechenbare Funktionen und von nach , eine berechenbare binäre Relation auf und Konstanten gibt, sodass mit diesen Objekten isomorph zu ist: Während Addition und Multiplikation in keinem Nichtstandardmodell berechenbar sind, gibt es Nichtstandardmodelle, in denen die Ordnung und die Nachfolgerfunktion berechenbar sind. Für Nichtstandardmodelle der „wahren“ Arithmetik, das heißt der Theorie von in Logik erster Stufe, gilt analog, dass diese nicht arithmetisch sind. (de) Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of first-order Peano arithmetic (PA) can be recursive (Kaye 1991:153ff). (en) En logique mathématique, le théorème de Tennenbaum dit qu'aucun modèle dénombrable non-standard de l'arithmétique de Peano n'est calculable, c'est-à-dire essentiellement que l'addition et la multiplication ne sont pas toutes les deux calculables dans un tel modèle (en fait aucune des deux ne peut l'être). Ce théorème est dû à (en). (fr) |
| dbo:wikiPageExternalLink | http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum.pdf |
| dbo:wikiPageID | 13392068 (xsd:integer) |
| dbo:wikiPageLength | 6601 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112945750 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Model_theory dbr:Peano_arithmetic dbr:Μ-recursive_function dbr:Countable_set dbr:Mathematical_logic dbr:Notices_of_the_American_Mathematical_Society dbr:Juliette_Kennedy dbr:Non-standard_model_of_arithmetic dbr:Euclidean_algorithm dbr:First-order_logic dbc:Theorems_in_the_foundations_of_mathematics dbr:Oxford_University_Press dbr:Isomorphism dbc:Model_theory dbr:Bijection dbr:Natural_numbers dbr:Recursively_inseparable_sets dbr:Stanley_Tennenbaum dbr:Incompleteness_theorem dbr:Overspill_(arithmetic) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Hatnote dbt:Refbegin dbt:Refend |
| dct:subject | dbc:Theorems_in_the_foundations_of_mathematics dbc:Model_theory |
| gold:hypernym | dbr:Result |
| rdf:type | yago:WikicatMathematicalTheorems yago:WikicatTheoremsInTheFoundationsOfMathematics yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of first-order Peano arithmetic (PA) can be recursive (Kaye 1991:153ff). (en) En logique mathématique, le théorème de Tennenbaum dit qu'aucun modèle dénombrable non-standard de l'arithmétique de Peano n'est calculable, c'est-à-dire essentiellement que l'addition et la multiplication ne sont pas toutes les deux calculables dans un tel modèle (en fait aucune des deux ne peut l'être). Ce théorème est dû à (en). (fr) Der Satz von Tennenbaum (nach Stanley Tennenbaum) ist ein Ergebnis der mathematischen Logik. Er besagt, dass kein abzählbares Nichtstandardmodell der Peano-Arithmetik berechenbar sein kann. Dabei heißt eine Struktur in der Sprache der Peano-Arithmetik berechenbar, wenn es berechenbare Funktionen und von nach , eine berechenbare binäre Relation auf und Konstanten gibt, sodass mit diesen Objekten isomorph zu ist: (de) |
| rdfs:label | Satz von Tennenbaum (de) Théorème de Tennenbaum (fr) Tennenbaum's theorem (en) |
| owl:sameAs | freebase:Tennenbaum's theorem yago-res:Tennenbaum's theorem wikidata:Tennenbaum's theorem dbpedia-de:Tennenbaum's theorem dbpedia-fr:Tennenbaum's theorem https://global.dbpedia.org/id/27JHu |
| prov:wasDerivedFrom | wikipedia-en:Tennenbaum's_theorem?oldid=1112945750&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Tennenbaum's_theorem |
| is dbo:wikiPageWikiLink of | dbr:Peano_axioms dbr:Timeline_of_mathematical_logic dbr:Gödel's_completeness_theorem dbr:Robinson_arithmetic dbr:Non-standard_model_of_arithmetic dbr:List_of_theorems dbr:Stanley_Tennenbaum |
| is foaf:primaryTopic of | wikipedia-en:Tennenbaum's_theorem |