关于 Godel 定理,请教 ...

新用户注册 | 用户登陆 | 刷新
论坛嘉宾: 萍踪浪迹 gauge 季候风

dfj


发表文章数: 186
内力值: 182/182
贡献度: 768
人气: 122

学术成员

关于 Godel 定理,请教 ... [文章类型: 原创]

由于没有时间去仔细学习相关的理论和证明,所以我想先知道个最基本的,那就是: 那个不完全性定理究竟与熟知的那些悖论——比如“本语句陈述的内容无法判定”这样的东西有无实质性区别?
我感觉那个定理不应该是这么简单的,那么不完全性定理与上面那个悖论的区别是什么?

另一方面,这个定理有无“实际”的用途?我的意思是,就好比假定黎曼猜想成立的话,就可以用来证明很多其它猜想或定理, Godel 不完全性定理有这种用途吗?
还有,比如黎曼几何的很多结论有助于增加我们对于我们所存在的时空的认识,那么 Godel 定理有这种作用吗?

我也看过一些关于 Godel 定理的科普,但是似乎都没有解答我的上述问题,因此来请教诸位。

发表时间: 2007-02-23, 23:40:20 个人资料

Omni


发表文章数: 280
内力值: 263/263
贡献度: 4868
人气: 688

论坛嘉宾学术成员

Re: 关于 Godel 定理 [文章类型: 原创]

>>那个不完全性定理究竟与熟知的那些悖论——比如“本语句陈述的内容无法判定”这样的东西有无实质性区别?
我感觉那个定理不应该是这么简单的,那么不完全性定理与上面那个悖论的区别是什么?

This is an easy question to answer. The second cornerstone of Godel's Incompleteness Theorem (with the first one being the Godel numbering system) is a formalized version of the statement:

"This statement is unprovable."

This is a SUBTLE VARIANT of the Liar's paradox you mentioned (e.g., "This sentence is false"). The sentence in the Liar's paradox can be neither true nor false without leading to absurdity. However, Godel's statement avoided the paradox by focusing on PROVABILITY rather than on truth.

The end result of Godel's theorem is the existence of UNPROVABILITY in any formal arithmetic system, therefore leading to the notion of "incompleteness" and "inconsistency" in any formal mathematical systems. I have to use quotation marks here for the two words, they were chosen by mathematicians for brevity, more accurate descriptions of the two concepts are:

* In any formal system, there always exists a statement that cannot be proven WITHIN the system even if its truth is apparent. ---The unprovability of completeness within the system ("incompleteness theorem" for brevity)

* If the formal arithmetic of the Natural Numbers is consistent, then that consistency cannot be proven WITHIN formal arithmetic itself as David Hilbert had sought. --- The unprovability of consistency within the system ("inconsistency theorem" for brevity)

So the take-home message to answer your question is the distinction of provability from truth. If you are interested to learn more about Godel's theorems without having to deal with the difficult mathematics, the famous "Godel, Escher, Bach" book written by Douglas Hofstadter should be your best reference.

>>另一方面,这个定理有无“实际”的用途?我的意思是,就好比假定黎曼猜想成立的话,就可以用来证明很多其它猜想或定理, Godel 不完全性定理有这种用途吗?

Of course, the impact of Godel's two incomplete theorems on the whole mathematical community was almost immediate after its publication in 1931. I'm not an expert in this area to give you a comprehensive list of the applications of Godel's theorems. I'll only give you one example.

In 1928, David Hilbert repeated three challenges to the world of mathematics out of his famous 23 questions proposed in 1900:

(1) To prove that all true mathematical statements could be proven, that is, the completeness of mathematics.

(2) To prove that only true mathematical statements could be proven, that is, the consistency of mathematics.

(3) To prove the decidability of mathematics, that is, the existence of a decision procedure to decide the truth or falsity of any mathematical proposition.

It is obvious that Godel's theorems have firmly disproven the first two challenges. This would be the foundation for Alan Turing to start attacking the third challenge in 1935. As is well known now, Turing's conclusion was the nonexistence of such a decision procedure. But more importantly, Turing came up with the important conception of "Turing Machine", which is the foundation of modern computer science. It's fair to say that without Godel's and Turing's successful tackling of Hilbert's 3 difficult challenges, the invention of computer would have been delayed significantly.

计算机是人类发现使用火以来最伟大的发明!

To further understand the historical development from Godel to Turing and modern computer science, you may want to read the accessible popular science book "The New Turing Omnibus --- 66 Excursions in Computer Science" written by A.K. Dewdney (1993). I bought the book during a visit to Princeton's bookstore as soon as I saw "Omni-" in its title, hehe.

发表时间: 2007-02-25, 10:53:53 个人资料

dfj


发表文章数: 186
内力值: 182/182
贡献度: 768
人气: 122

学术成员

Re: 关于 Godel 定理,请教 ... [文章类型: 原创]

多谢指教!

发表时间: 2007-02-27, 00:01:01 个人资料
您尚未登陆 | 用户登陆