• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >What's So Special about Kruskal's Theorem and the Ordinal Gammo sub 0. A Surveyof Some Results In Proof Theory
【24h】

What's So Special about Kruskal's Theorem and the Ordinal Gammo sub 0. A Surveyof Some Results In Proof Theory

机译：关于Kruskal定理和序数Gammo子0的特别之处。对证明理论的一些结果的调查

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper consists primarily of a survey of results of Harvey Friedman aboutsome proof theoretic aspects of various forms of Krusal's tree theorem, and in particular the connection with the ordinal Gamma 0. We also include a fairly extensive treatment of normal functions on the countable ordinals, and we give a glimpse of Veblen Hierarchies, some subsystems of second-order logic, slow-growing and fast-growing hierarchies including Girard's result, and Goodstein sequences. The central theme of this paper is a powerful theorem due Kruskal, the 'tree theorem', as well as a 'finite miniaturization' of Kruskal's theorem due to Harvey Friedman. These versions of Kruskal's theorem are remarkable from a proof-theoretic point of view because they are not provable in relatively strong logical systems. They are examples of so called 'natural independence phenomena', which are considered by more logicians as more natural than the mathematical incompleteness results first discovered by Godel. Kruskal's tree theorem also plays a fundamental role in computer science because it is one of the main tools for showing that certain orderings on trees are well founded. These orderings play a crucial role in proving the termination of systems of rewrite rules and the correctness of Knuth-Bandix completion procedures. There is also a close connection between a certain infinite countable ordinal called Gamma sub 0 and Kruskal's theorem. Previous definitions of the function involved in this connection are known to be incorrect, in that, the function is not monotonic. We offer a repaired definition of this function. and explore briefly the consequences of its existence. (MM).

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号