Goodstein's theorem (original) (raw)
Goodsteinova věta, vyslovená v roce 1944 , tvrdí:Pro každou Goodsteinovu posloupnost existuje takové přirozené číslo , pro které je .
| Property | Value |
|---|---|
| dbo:abstract | Goodsteinova věta, vyslovená v roce 1944 , tvrdí:Pro každou Goodsteinovu posloupnost existuje takové přirozené číslo , pro které je . (cs) In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0. Kirby and Paris showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic). This was the third example of a true statement that is unprovable in Peano arithmetic, after the examples provided by Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic. The Paris–Harrington theorem gave another example. Laurence Kirby and Jeff Paris introduced a graph-theoretic hydra game with behavior similar to that of Goodstein sequences: the "Hydra" (named for the mythological multi-headed Hydra of Lerna) is a rooted tree, and a move consists of cutting off one of its "heads" (a branch of the tree), to which the hydra responds by growing a finite number of new heads according to certain rules. Kirby and Paris proved that the Hydra will eventually be killed, regardless of the strategy that Hercules uses to chop off its heads, though this may take a very long time. Just like for Goodstein sequences, Kirby and Paris showed that it cannot be proven in Peano arithmetic alone. (en) En mathématiques, et plus précisément en logique mathématique, le théorème de Goodstein est un énoncé arithmétique portant sur des suites, dites suites de Goodstein. Les suites de Goodstein sont des suites d'entiers à la croissance initiale extrêmement rapide, et le théorème établit que (en dépit des apparences) toute suite de Goodstein se termine par 0. Il doit son nom à son auteur, le mathématicien et logicien Reuben Goodstein. Le théorème de Goodstein n'est pas démontrable dans l'arithmétique de Peano du premier ordre, mais peut être démontré dans des théories plus fortes, comme la théorie des ensembles ZF (une démonstration simple utilise les ordinaux jusqu'à ), ou l'arithmétique du second ordre. Le théorème donne ainsi, dans le cas particulier de l'arithmétique du premier ordre, un exemple d'énoncé indécidable plus naturel que ceux obtenus par les théorèmes d'incomplétude de Gödel. (fr) グッドスタインの定理（グッドスタインのていり、Goodstein's theorem）は、数理論理学における自然数に関する命題であり、「全てのグッドスタイン数列は必ず0で終わる」という主張。ペアノ算術の範囲では証明も否定の証明もできないが、集合論の公理系、特に無限集合の公理を用いると真であることが言える。たとえばゲーデルの不完全性定理から導かれる決定不能な命題などは、いかにも不自然だったり人工的に見えたりする場合があるのに対し、この定理は「自然な」決定不能命題の例として知られる。 (ja) 굿스타인의 정리(Goodstein's theorem, -定理)는 집합론의 정리이다. 이 정리는 처음에는 증가하는 것 같지만 결국에는 0으로 감소하는 수열(약한 굿스타인 수열)의 예를 들고 있다. 영국 수학자 루벤 루이스 굿스타인의 이름이 붙어 있으며, 굿스타인에 의해 1944년 처음 증명되었다.:71 이 정리의 보다 강한 판본은 패리스의 정리로 주어진다. 는 영국 수학자 (Jeff Paris)의 이름에서 따왔으며, 1981년 처음 증명되었다.:71 (ko) Twierdzenie Goodsteina – twierdzenie teorii liczb sformułowane przez Goodsteina w 1944 roku dotyczące pewnej własności ciągów liczb naturalnych. Mimo że sformułowanie twierdzenia jest czysto arytmetyczne i względnie nieskomplikowane, twierdzenie to jest niezależne od aksjomatyki Peana, co udowodnili w 1982 roku Jeff Paris i Laurie Kirby. (pl) In matematica, il teorema di Goodstein è un teorema sui numeri naturali, relativamente semplice da enunciare, la cui particolarità consiste nel fatto di essere indecidibile dall'aritmetica di Peano ma dimostrabile nella teoria assiomatica degli insiemi. Esso può essere considerato un esempio di enunciato indecidibile dagli usuali assiomi dell'aritmetica più "naturale" rispetto alle complicate costruzioni dei teoremi di incompletezza di Gödel. Per enunciare il teorema di Goodstein occorre dare alcune definizioni preliminari. (it) Na matemática lógica, o Teorema de Goodstein é um enunciado sobre os números naturais, provado por Reuben Goodstein em 1994, o qual define que toda sequência de Goodstein termina em zero. Kirby & Paris, em 1982, mostraram que isto não é demonstrável na aritmética de Peano (mas isto pode ser provado em sistemas em ordem maior, de acordo com a ordem aritmética). Este foi o terceiro exemplo “natural” de um enunciado verdadeiro que não é demonstrável na aritmética de Peano(depois da prova direta, de Gerhard Gentzen, em 1943,da indemonstrabilidade da indução-ε0 na aritmética de Peano e o Teorema de Paris-Harrington).Anteriormente, enunciados deste tipo tinham sido, exceto para Gentzen, extremamente complicados, construções aleatórias (como os enunciados gerados pela construção dada no Teorema da Incompletude de Gödel) ou interessou metamatemáticos ou resultados combinatoriais (Kirby & Paris 1982). Laurie Kirby e Jeff Paris deram uma interpretação do Teorema de Goodstein como um jogo de hidras: a “Hidra” é uma árvore enraizada, e um movimento, ou jogada, consiste em cortar uma das suas CABEÇAS (um galho da árvore), a qual a hidra reage com o crescimento de um número finito de novos galhos, de acordo com determinadas regras. A interpretação de Kirby-Paris do teorema diz que a Hidra vai, eventualmente, ser morta, independentemente da estratégia que Hércules usa para cortar fora as cabeças, embora isto possa levar muito, muito tempo. (pt) Goodsteins teorem är inom matematisk logik ett uttalande om de naturliga talen, som bevisade 1944, vilket säger att varje Goodstein-sekvens till slut terminerar vid 0. Kirby och Paris visade att det är oavgörbart i Peano-aritmetik (men det kan bevisas i starkare system, såsom ). Detta var det tredje exemplet på ett sant uttalande som är oavgörbart inom Peano-aritmetik, efter Gödels ofullständighetsteorem och direkta bevis 1943 av att ε0-induktion är oavgörbar i Peano-aritmetik. Paris-Harringtons sats var ett senare exempel. Laurence Kirby och Jeff Paris introducerade ett grafteoretiskt hydra-spel med ett beteende som liknar Goodstein-sekvenser: "Hydra" är ett rotat träd och ett drag består av att klippa av ett av dess "huvuden" (en gren av trädet), på vilket Hydra svarar genom att odla ett begränsat antal nya huvuden enligt vissa regler. Kirby och Paris visade att Hydra så småningom kommer att dödas, oavsett vilken strategi Herakles använder för att hugga av huvudena, men det kan ta mycket lång tid. Precis som för Goodstein-sekvenser visade Kirby och Paris att detta inte kan bevisas i Peano-aritmetiken ensam. (sv) Теорема Гудштейна — твердження математичної логіки про натуральні числа, зроблене , стверджує, що всі послідовності Гудштейна закінчуються нулем. Це теорема є невиводимою із аксіом Пеано, але може бути доведена в . (uk) Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном. Утверждает, что все последовательности Гудстейна заканчиваются нулём. Как показали и Джефф Парис, теорема Гудстейна недоказуема в аксиоматике Пеано (но может быть доказана, например, в ). (ru) 古德斯坦定理是數理邏輯中的一個關於自然數的敘述，是在 1944 年由所證明。其主要是在說明「古德斯坦序列」最終會結束於 0 。柯比和柏麗斯 證明它在皮亞諾算術中是（但它可以在一個更強的系統如二階算術中被證明）。這是繼哥德爾不完備定理構造的命題（）和 1943 年格哈德·根岑直接證明皮亞諾算術中 ε0-induction 不可被證明之後，第三個（對自然數為真的）命題被證明在皮亞諾算術中不可證明。之後的例子是。 勞倫斯·柯比和傑夫·柏麗斯介紹了一個圖論中的九頭蛇遊戲，其行為類似古德斯坦序列：「九頭蛇」是一棵有根的樹，而序列每一步是砍掉它的一顆頭（即樹的分支），然後九頭蛇則對應地會依據某些規則來增加有限數量的頭。柯比和柏麗斯則證明，不管赫拉克勒斯使用何種策略來砍頭，九頭蛇最終會被斬殺（儘管這個過程可能會非常漫長）。如古德斯坦序列，柯比和柏麗斯證明其在皮亞諾算術中是不可證明的。 (zh) |
| dbo:wikiPageExternalLink | http://andrescaicedo.files.wordpress.com/2008/04/goodstein.pdf http://blog.kleinproject.org/%3Fp=674 http://mc.edmi.nl:1340/exp/Goodstein/ https://web.archive.org/web/20160411094806/https:/dspace.fandm.edu/bitstream/handle/11016/23900/Kaplan_S12_MATH_Thesis_Final_5-8-12.pdf%3Fsequence=1 http://citeseerx.ist.psu.edu/viewdoc/summary%3Fdoi=10.1.1.22.3296 http://math.andrej.com/2008/02/02/the-hydra-game/ http://www.madore.org/~david/math/hydra.xhtml https://github.com/tromp/AIT/blob/master/Goodstein.hs |
| dbo:wikiPageID | 150062 (xsd:integer) |
| dbo:wikiPageLength | 21591 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1114510669 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Paris–Harrington_theorem dbr:Peano_axioms dbr:Reuben_Goodstein dbr:Independence_(mathematical_logic) dbr:Infinite_regress dbc:Articles_containing_proofs dbc:Large_numbers dbr:Computable_function dbr:Mathematical_logic dbr:Epsilon_numbers_(mathematics) dbr:Gerhard_Gentzen dbc:Independence_results dbr:Hardy_hierarchy dbr:Kruskal's_tree_theorem dbc:Set_theory dbr:Total_function dbr:Well-founded dbr:Non-standard_model_of_arithmetic dbc:Integer_sequences dbc:Theorems_in_the_foundations_of_mathematics dbr:Fast-growing_hierarchy dbr:Graham's_number dbr:Journal_of_Symbolic_Logic dbr:Kanamori–McAloon_theorem dbc:Numeral_systems dbr:Gödel's_incompleteness_theorem dbr:Jeff_Paris_(mathematician) dbr:Hydra_game dbr:Ackermann_function dbr:Natural_number dbr:Ordinal_number dbr:Turing_machine dbr:Second-order_arithmetic dbr:Cantor_normal_form dbr:Hydra_of_Lerna |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Mathworld dbt:Reflist dbt:Short_description dbt:Val dbt:OEIS2C |
| dct:subject | dbc:Articles_containing_proofs dbc:Large_numbers dbc:Independence_results dbc:Set_theory dbc:Integer_sequences dbc:Theorems_in_the_foundations_of_mathematics dbc:Numeral_systems |
| gold:hypernym | dbr:Statement |
| rdf:type | yago:WikicatLargeNumbers yago:WikicatMathematicalAxioms yago:WikicatMathematicalTheorems yago:WikicatTheorems yago:WikicatTheoremsInTheFoundationsOfMathematics yago:Abstraction100002137 yago:Arrangement107938773 yago:AuditoryCommunication107109019 yago:Battalion113775093 yago:Communication100033020 yago:Group100031264 yago:IndefiniteQuantity113576355 yago:LargeIndefiniteQuantity113757724 yago:Maxim107152948 yago:Measure100033615 yago:Message106598915 yago:Ordering108456993 yago:Proposition106750804 yago:WikicatIntegerSequences yago:Saying107151380 yago:Sequence108459252 yago:Series108457976 yago:Speech107109196 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Goodsteinova věta, vyslovená v roce 1944 , tvrdí:Pro každou Goodsteinovu posloupnost existuje takové přirozené číslo , pro které je . (cs) グッドスタインの定理（グッドスタインのていり、Goodstein's theorem）は、数理論理学における自然数に関する命題であり、「全てのグッドスタイン数列は必ず0で終わる」という主張。ペアノ算術の範囲では証明も否定の証明もできないが、集合論の公理系、特に無限集合の公理を用いると真であることが言える。たとえばゲーデルの不完全性定理から導かれる決定不能な命題などは、いかにも不自然だったり人工的に見えたりする場合があるのに対し、この定理は「自然な」決定不能命題の例として知られる。 (ja) 굿스타인의 정리(Goodstein's theorem, -定理)는 집합론의 정리이다. 이 정리는 처음에는 증가하는 것 같지만 결국에는 0으로 감소하는 수열(약한 굿스타인 수열)의 예를 들고 있다. 영국 수학자 루벤 루이스 굿스타인의 이름이 붙어 있으며, 굿스타인에 의해 1944년 처음 증명되었다.:71 이 정리의 보다 강한 판본은 패리스의 정리로 주어진다. 는 영국 수학자 (Jeff Paris)의 이름에서 따왔으며, 1981년 처음 증명되었다.:71 (ko) Twierdzenie Goodsteina – twierdzenie teorii liczb sformułowane przez Goodsteina w 1944 roku dotyczące pewnej własności ciągów liczb naturalnych. Mimo że sformułowanie twierdzenia jest czysto arytmetyczne i względnie nieskomplikowane, twierdzenie to jest niezależne od aksjomatyki Peana, co udowodnili w 1982 roku Jeff Paris i Laurie Kirby. (pl) In matematica, il teorema di Goodstein è un teorema sui numeri naturali, relativamente semplice da enunciare, la cui particolarità consiste nel fatto di essere indecidibile dall'aritmetica di Peano ma dimostrabile nella teoria assiomatica degli insiemi. Esso può essere considerato un esempio di enunciato indecidibile dagli usuali assiomi dell'aritmetica più "naturale" rispetto alle complicate costruzioni dei teoremi di incompletezza di Gödel. Per enunciare il teorema di Goodstein occorre dare alcune definizioni preliminari. (it) Теорема Гудштейна — твердження математичної логіки про натуральні числа, зроблене , стверджує, що всі послідовності Гудштейна закінчуються нулем. Це теорема є невиводимою із аксіом Пеано, але може бути доведена в . (uk) Теорема Гудстейна — теорема математической логики о натуральных числах, доказанная Рубеном Гудстейном. Утверждает, что все последовательности Гудстейна заканчиваются нулём. Как показали и Джефф Парис, теорема Гудстейна недоказуема в аксиоматике Пеано (но может быть доказана, например, в ). (ru) 古德斯坦定理是數理邏輯中的一個關於自然數的敘述，是在 1944 年由所證明。其主要是在說明「古德斯坦序列」最終會結束於 0 。柯比和柏麗斯 證明它在皮亞諾算術中是（但它可以在一個更強的系統如二階算術中被證明）。這是繼哥德爾不完備定理構造的命題（）和 1943 年格哈德·根岑直接證明皮亞諾算術中 ε0-induction 不可被證明之後，第三個（對自然數為真的）命題被證明在皮亞諾算術中不可證明。之後的例子是。 勞倫斯·柯比和傑夫·柏麗斯介紹了一個圖論中的九頭蛇遊戲，其行為類似古德斯坦序列：「九頭蛇」是一棵有根的樹，而序列每一步是砍掉它的一顆頭（即樹的分支），然後九頭蛇則對應地會依據某些規則來增加有限數量的頭。柯比和柏麗斯則證明，不管赫拉克勒斯使用何種策略來砍頭，九頭蛇最終會被斬殺（儘管這個過程可能會非常漫長）。如古德斯坦序列，柯比和柏麗斯證明其在皮亞諾算術中是不可證明的。 (zh) In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0. Kirby and Paris showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic). This was the third example of a true statement that is unprovable in Peano arithmetic, after the examples provided by Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic. The Paris–Harrington theorem gave another example. (en) En mathématiques, et plus précisément en logique mathématique, le théorème de Goodstein est un énoncé arithmétique portant sur des suites, dites suites de Goodstein. Les suites de Goodstein sont des suites d'entiers à la croissance initiale extrêmement rapide, et le théorème établit que (en dépit des apparences) toute suite de Goodstein se termine par 0. Il doit son nom à son auteur, le mathématicien et logicien Reuben Goodstein. (fr) Na matemática lógica, o Teorema de Goodstein é um enunciado sobre os números naturais, provado por Reuben Goodstein em 1994, o qual define que toda sequência de Goodstein termina em zero. Kirby & Paris, em 1982, mostraram que isto não é demonstrável na aritmética de Peano (mas isto pode ser provado em sistemas em ordem maior, de acordo com a ordem aritmética). Este foi o terceiro exemplo “natural” de um enunciado verdadeiro que não é demonstrável na aritmética de Peano(depois da prova direta, de Gerhard Gentzen, em 1943,da indemonstrabilidade da indução-ε0 na aritmética de Peano e o Teorema de Paris-Harrington).Anteriormente, enunciados deste tipo tinham sido, exceto para Gentzen, extremamente complicados, construções aleatórias (como os enunciados gerados pela construção dada no Teorema d (pt) Goodsteins teorem är inom matematisk logik ett uttalande om de naturliga talen, som bevisade 1944, vilket säger att varje Goodstein-sekvens till slut terminerar vid 0. Kirby och Paris visade att det är oavgörbart i Peano-aritmetik (men det kan bevisas i starkare system, såsom ). Detta var det tredje exemplet på ett sant uttalande som är oavgörbart inom Peano-aritmetik, efter Gödels ofullständighetsteorem och direkta bevis 1943 av att ε0-induktion är oavgörbar i Peano-aritmetik. Paris-Harringtons sats var ett senare exempel. (sv) |
| rdfs:label | Goodsteinova věta (cs) Satz von Goodstein (de) Théorème de Goodstein (fr) Goodstein's theorem (en) Teorema di Goodstein (it) 굿스타인의 정리 (ko) グッドスタインの定理 (ja) Twierdzenie Goodsteina (pl) Теорема Гудстейна (ru) Teorema de Goodstein (pt) Goodsteins sats (sv) Теорема Гудштейна (uk) 古德斯坦定理 (zh) |
| owl:sameAs | freebase:Goodstein's theorem yago-res:Goodstein's theorem wikidata:Goodstein's theorem dbpedia-cs:Goodstein's theorem dbpedia-de:Goodstein's theorem dbpedia-fr:Goodstein's theorem dbpedia-it:Goodstein's theorem dbpedia-ja:Goodstein's theorem dbpedia-ko:Goodstein's theorem dbpedia-pl:Goodstein's theorem dbpedia-pt:Goodstein's theorem dbpedia-ru:Goodstein's theorem dbpedia-sv:Goodstein's theorem dbpedia-uk:Goodstein's theorem dbpedia-zh:Goodstein's theorem https://global.dbpedia.org/id/CZvw |
| prov:wasDerivedFrom | wikipedia-en:Goodstein's_theorem?oldid=1114510669&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Goodstein's_theorem |
| is dbo:knownFor of | dbr:Reuben_Goodstein dbr:Jeff_Paris_(mathematician) |
| is dbo:wikiPageRedirects of | dbr:Goodstein's_function dbr:Goodstein_function dbr:Kirby-Paris_theorem dbr:Kirby–Paris_theorem dbr:Paris-Kirby_theorem dbr:Paris–Kirby_theorem dbr:Goldstein's_theorem dbr:Goldstein_sequence dbr:Goodstein_Sequence dbr:Goodstein_sequence dbr:Goodstein_theorem dbr:Goodstein´s_theorem |
| is dbo:wikiPageWikiLink of | dbr:List_of_University_of_Leicester_people dbr:Paris–Harrington_theorem dbr:Peano_axioms dbr:Reuben_Goodstein dbr:List_of_mathematical_proofs dbr:List_of_numeral_systems dbr:Computability_theory dbr:Ordinal_collapsing_function dbr:Gentzen's_consistency_proof dbr:Theorem dbr:Epsilon_number dbr:Ant_on_a_rubber_rope dbr:Friedman's_SSCG_function dbr:Kruskal's_tree_theorem dbr:Large_countable_ordinal dbr:Non-standard_model_of_arithmetic dbr:Fast-growing_hierarchy dbr:Kanamori–McAloon_theorem dbr:Ramsey_theory dbr:Goodstein's_function dbr:Goodstein_function dbr:Gödel's_incompleteness_theorems dbr:Jeff_Paris_(mathematician) dbr:Tetration dbr:Hydra_game dbr:Natural_number dbr:Undecidable_problem dbr:List_of_theorems dbr:Kirby-Paris_theorem dbr:Kirby–Paris_theorem dbr:Paris-Kirby_theorem dbr:Paris–Kirby_theorem dbr:Goldstein's_theorem dbr:Goldstein_sequence dbr:Goodstein_Sequence dbr:Goodstein_sequence dbr:Goodstein_theorem dbr:Goodstein´s_theorem |
| is dbp:knownFor of | dbr:Reuben_Goodstein |
| is foaf:primaryTopic of | wikipedia-en:Goodstein's_theorem |