不可判定數學理論

不可判定數學理論(undecidable mathematicaltheory)不具有能行判定算法的數學理論.對於語言丫上的理論T,如果不存在一個能行的算法,使得對於丫中的任何語句。,該算法可以判定“aET"是否成立,則稱理論T是不可判定的.最早被證明為不可判定的數學理論是佩亞諾算術PA(該問題是美國數學家、邏輯學家丘奇(Church , A.)於1936年證明的),實際上,PA的任何無矛盾擴張都是不可判定的(如各種公理集合論系統就是不可判定見“算術系統的不可判定性”).目前已知下列數學理論是不可判定的:
1. Th((z,+,·>)(z為整數集).
2.Th((Q,十,·>)(Q為有理數集).
3.群理論.
4.半群的理論.
5.環的理論.
6.域的理論.
7.格的理論.
8.分配格的理論.
9.偏序理論.

相關詞條

熱門詞條

聯絡我們