按年被提到
20052016 · 1 次2026
数学、逻辑与理论›范畴论与逻辑·arXiv:cs/0505034 · cs.LO

Essential Incompleteness of Arithmetic Verified by Coq

Russell O'Connor · 2005
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2016-10-13 · 最近 2017-10-11
2不同的人
2活跃月份
2讨论串
31被引(OpenAlex)
arXiv 摘要(候选层不写导读)

A constructive proof of the Goedel-Rosser incompleteness theorem has been completed using the Coq proof assistant. Some theory of classical first-order logic over an arbitrary language is formalized. A development of primitive recursive functions is given, and all primitive recursive functions are proved to be representable in a weak axiom system. Formulas and proofs are encoded as natural numbers, and functions operating on these codes are proved to be primitive recursive. The weak axiom system is proved to be essentially incomplete. In particular, Peano arithmetic is proved to be consistent in Coq's type theory and therefore is incomplete.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论jplasmeier · 2016-10

“I find this argument to be an unsatisfactory against "algorithmic consciousness". There have been automated proofs of Godel's theorem for a long while [0]. I don't mean this to be evidence on the contrary, but Penrose seems to ignore the fact that a computer can realize multiple axiomatic systems, and use them to make statements like Godel's Theorem(s). G…”

What were Einstein and Gödel talking about? (2005)原评论 ↗
评论auggierose · 2017-10

“I don't think working with Coq has ever or will ever be particularly pleasant:-) O'Connor gave a nice talk at TPHol's which I attended: https://arxiv.org/abs/cs/0505034 Keeping up with Coq shouldn't have been too difficult for him.”

Functor-Oriented Programming原评论 ↗