正文 第十四章 評介王浩的《數理邏輯通俗講話》(1 / 3)

連續統問題

連續統問題(或者說實數有多少的問題)可能是集合論未解決的問題中最引人注意的一個。著名的數學家仏扭出時在1900年召開的國際數學會議上曾提出了二十三個未解決的重要問題。連續統問題就是其中的一個,是所謂第一問題,這個問題的另一種陳述方式是自然數集合的子集有多少。

在19世紀70年代創立了一種新的數學理論,即集合論。這是一種研究一般集合的性質的理論(這裏所說的集合包括有窮集合也包括無窮集合)。發現無窮大的數有兩種,一種是可數的無窮大的數,如自然數集合的分子的個數;另一種是不可數的無窮大的數,如實數的個數或自然數集合的子集的個數。後者比前者要大得多。前者是數不完的,但還可以數。後者則不但是數不完的而且是沒法數的,也就是多得無從數起。

還發現,不可數的無窮基數不是隻有一個而是有無窮多個(在集合論中一個集合的分子的個數稱作這個集合的基數集合論中將這無窮多個無窮基數記作。是自然數集合的基數,是一個可數的無窮基數。從叫起則都是不可數的無窮基數,一個比一個大。叫是一切可數序數構成的集合的基數,是最小的大於叫的無窮基數,叫是最小的大於的無窮基數,如此等等。

由一切實數構成的集合的基數(或者說由自然數集合的一切子集構成的集合的基數)究竟有多大呢?猜測,這個基數是不可數的無窮基數之中最小的那一個,也就是等於叫。用公式寫出來就是:一個序數可以定義為一個集合,即由一切比小的序數構成的集合。例如自然數 (自然數是有窮序數)可以定義為這一集合。

2心二叫這就是有名的連續統假設在19世紀70年代這一猜測。作這一百年中不少著名的數學家包括曾經研究過這個問題,想要解決它,但至今沒有解決。本世紀30年代後期和60年代初期,曾在這個問題取得了重要進展。他們的研究結果表明,現有的集合論的工具是不可能解決這個問題的。這種結果之所以重要,是因為它使得我們不必再試圖用現有的集合論的工具去解決這個問題,因為這樣做是徒勞無益的,從而可以把時間和精力用來尋找可能解決這個問題的新工具和新方法。這種結果的意義是和在19世紀初期證明用圓規直尺三等分角的不可能性的意義類似的。

在通常的集合論中,我們不能證明連續統假設是假的。他的具體做法是定義了八種集合運算(他稱之為“基本運算”)。然後他在這八種運算的基礎上定義了一個集合的類(這個類通常記作)是一切可以空集出發經過應用這八種基本運算而構成的集合所組成的類。稱這種集合為“可構成集”。他證明下列的重要結果:

通常的集合論公理(如2打和連續統假設在中均成立。因而在通常的集合論是無矛盾的前提下不可能推出連續統假設的否定(即不可能推出)如的結果結合起來,就得到下列的定理。

在通常的集合論(如2巧是無矛盾的前提下,對通常的集合論的公理而言是獨立的。

這也就是說,通常的集合論的公理不能判定是否成立;或者說僅僅靠通常的集合論公理是不可能解決連續統問題的。

目前大多數人則認為,通常的集合論公理不能判定連續統假設這一類的基本命題的這一事實說明了現有的公理集合論的不完備性。於是問題歸結為到哪裏去尋找能判定連續統問題等基本命題的新公理,以及一旦找到以後如何去論證這條公理是可接受的。

另一條尋找新公理的途徑是在通常的集合論公理上加上強無窮公理。這方麵可以考慮的是大基數存在公理(如“至少存在一個大於的可測基數”等)龍。但現在已經知道,即使在通常的集合論公理上加可測基數存在公理,仍然是無濟於事的。對這樣一組公理而言,連續統假設仍是獨立的。

還有一條途徑是設法推廣,使得某種推廣仍保持有的優良件質(可以推出連續統假設等)。近幾年有些人在從事這方麵的研究。這是一個俏得注意的方向。

這個問題是當前計算理論中的一個中問題,我們在後麵要解釋為什麼它在計算理論中居於關鍵地位。這個問題通常是就圖林機器來討論的~可以表示成下列的形式:是確定性的機器在多項式有界的時間內能夠識別的語言的類,是非確定性的機器在多項式有界的時間內能夠識別的語言,一個計算機程序,而就計算機程序來討論可能直觀上會更清楚一些,我們下麵將專就程序來討論。

我們早已知道,如果不考慮計算時間的界(即計算長度可以任意長),那麼這兩種程序所能識別的語言的類是相同的。這是因為在這種條件下,對任一非確定性程序都能夠有一個確定性程序來摸擬它,隻是後者所需要的計算時間一般要比前者長得多,但實際計算是必須考慮到計算時間的長短的。事實上隻有計算時間有界的計算才可以算作是實際可行的計算。而且這個上界必須相當低。例如,決不能以指數函數為界。現在計算機科學中一般是以多項式為界。通常所說的“可行計算”(即實際可行的計算就是多項式時間有界的計算。