若不認可選擇公理,該怎麼證明整數比實數少？

01-06

通常，證明的方法是假設能枚舉所有實數，然後證明能夠構造一個實數不在枚舉的實數之內，從而證明實數的個數是不可數的。但構造的過程默認了選擇公理，認為這個構造過程能夠結束。但如果我不承認選擇公理，該怎麼證明實數比整數多呢？

@阿成的答案引用的定理是正確的，但之後犯了若干錯誤，最致命的一個是：不承認選擇公理的情況下，無法證明可數個可數集的並是可數的！其他的錯誤有以下幾個：

1. 不可數集合不能用 Hartogs 數構造. Hartogs 數的構造可以由不可數集合的存在性推出不可數序數的存在性，但不可數集合的存在性並不能由此證明.

2. 即使不承認選擇公理，也不可能存在既非可數也非不可數的集合. 因為不可數的定義是非可數集，這是一個簡單的排中律.

正確的結論是：可以證明.

在完成實數的定義後，實數不可數的證明只需用到概括公理. 其證明大致可以分為兩部分：

1. 證明 $|mathbb N| < |mathcal P(mathbb N)|$ . 這是一個標準結果，證明與 @余翔所說的類似，用反證法：假定存在這樣的雙射 $f colon mathbb N o mathcal P(mathbb N)$ , 則可以（用概括公理）取 $X = {n in mathbb N mid n otin f(n)} in mathcal P(mathbb N)$ , 由於 f 是雙射，有 $x = f^{-1}(X) in mathbb N$ . 現在問題來了：是否有 $x in X$ ? 不論如何假定，都會引出矛盾.

2. 證明可以將 $mathcal P(mathbb N)$ 嵌入 $mathbb R$ . 仍然與 @余翔的證明相同，只要令 $g colon mathcal P(mathbb N) o mathbb R, X mapsto sum_{x in X} 3^{-x}$ (此處感謝 @余翔指出，不能用 2 作為底數), 很容易由實數的完備性推出這是良定義的單射. 注意這裡對實數的完備性的使用是必要的. 實際上，我們可以用此法證明任何一個包含有理數的完備度量空間都是不可數的. 而實數的完備性是否可以不用選擇公理證明呢？當然可以，參見 Dedekind cut.

這樣就完成了證明.

實數比整數多是怎麼定義的？不知道題主是如何定義一個集合包含的元素比另一個集合多。

證明實數不可數不用選擇公理也是可以的，可以這樣證明

設 $X$ 是集合， $X$ 的冪集記作 $2^X:={A:Asubset X}$ ，它是 $X$ 的一切子集構成的集合。

定理.（Cantor定理）設 $X$ 是一個任意的集合，那麼 $X$ 和 $2^X$ 不能有同樣的基數。

因為集合 $A={xin X:x otin f(x)}$ 不能是 $f$ 的像，從而沒有從 $X$ 到 $2^{X}$ 的滿射，這個定理的證明不需要公理。

推論. $2^{mathbf{N}}$ 不可數。

根據Cantor定理， $2^{mathbf{N}}$ 不能與 $mathbf{N}$ 有相同的基數，那麼它或者是不可數的，或者是有限的，但 $2^{mathbf{N}}$ 包含單元素集的集合 ${{n}:ninmathbf{N}}$ ，它明顯與 $mathbf{N}$ 存在雙射，從而是可數無限的，於是 $2^{mathbf{N}}$ 不能是有限的(因為有限集合的子集都是有限的)，所以是不可數的。

推論. $mathbf{R}$ 不可數

證明定義映射 $f:2^{mathbf{N}} omathbf{R}$ ， $extstyle f(A):=sum_{nin A}10^{-n}=sum_{n=0}^infty 1_A(n)10^{-n}$

這裡 $1_A$ 表示集合 $A$ 的指示函數，注意 $extstylesum_{n=0}^infty 10^{-n}$ 是絕對收斂的級數，因此 $extstyle sum_{nin A}10^{-n}$ 也是絕對收斂的. 於是，映射 $f$ 是定義良好的，

現在證明 $f$ 是單射。採用反證法，假設存在兩個不同的集合 $A,Bin2^{mathbf{N}}$ ，使得 $f(A)=f(B)$ ，由於 $A eq B$ ，集合

$(Asetminus B)cup(Bsetminus A)$

是 $mathbf{N}$ 的非空子集，根據良序原理，這個集合存在最小元，即 $n_0=min(Asetminus B)cup(Bsetminus A)$ ，那麼 $n_0$ 屬於 $Asetminus B$ 或 $Bsetminus A$ ，根據對稱性，不妨認為 $n_0$ 屬於 $Asetminus B$ ，那麼 $n_0in A,~n_0 otin B$ ，並且對一切 $n<n_0$ ， $nin A,B$ 或 $n otin A,B$ 。於是

$egin{align} 0=f(A)-f(B)=sum_{nin A}10^{-n}-sum_{nin B}10^{-n}\ =left(sum_{n<n_0:nin A}10^{-n}+sum_{n>n_0:nin A}10^{-n} ight)-left(sum_{n<n_0:nin B}10^{-n}+sum_{n>n_0:nin B}10^{-n} ight)\ =10^{-n_0}+sum_{n>n_0:nin A}10^{-n}-sum_{n>n_0:nin B}10^{-n}\ geq 10^{-n_0}+0-sum_{n>n_0}10^{-n}\ geq 10^{-n_0}-frac1910^{-n_0}>0 end{align} $

得到矛盾，於是 $f$ 是單射，這意味著 $f(2^{mathbf{N}})$ 與 $mathbf{N}$ 具有相同的集合，從而不可數，由於 $f(2^mathbf{N})$ 是 $mathbf{R}$ 的子集，這使得 $mathbf{R}$ 也不可數(因為可數集的子集是之多可數的)

ps.自然數良序與數學歸納法等價，所以證明自然數良序不需要選擇公理。

數學歸納法 $Rightarrow$ 自然數良序

命題(良序原理) 設 $X$ 是自然數 $mathbf{N}$ 的非空子集, 那麼存在一個元素 $nin X$ ，使得對一切 $min X$ 成立 $nleq m$ ，換而言之，自然數的每個非空子集都有最小元。

證明反證，假設 $X$ 不存在最小元，使用歸納法，設關於 $n$ 的命題 $P(n)$ 是 $n otin X$ 。

首先 $0 otin X$ (因為 $X$ 不存在最小元)，因此 $P(0)$ 成立。
設對一切自然數 $m<n$ ， $P(m)$ 成立，那麼對一切 $m<n$ ，有 $m otin X$ ，因此 $n otin X$ (如果 $nin X$ ，那麼 $n$ 就是 $X$ 的最小元)，於是 $P(n)$ 成立。

根據數學歸納法，對一切 $nin mathbf{N}$ ， $P(n)$ 成立，於是對所有的自然數 $n$ ，有 $n otin X$ ，因此 $X=emptyset$ ，得到矛盾。

自然數良序 $Rightarrow$ 數學歸納法

命題(數學歸納原理) 設 $P(n)$ 是關於自然數 $n$ 的一個性質，設 $P(0)$ 是真的，並假設只要 $P(n)$ 是真的，則 $P(n+1)$ 也是真的，那麼對每個自然數 $n$ ， $P(n)$ 都是真的。

證明設 $X={ninmathbf{N}:P(n) ext{是假的}}$ ，我們斷定 $X$ 是空集，如果 $X$ 不是空集，那麼根據良序原理， $X$ 存在最小元 $n_0=min X$ ，而對一切 $n<n_0$ ， $P(n)$ 都真，特別地 $P(n_0-1)$ 也真，因此 $P(n_0)$ 也真，這是一個矛盾。

這是不可能的。

整數和實數，都是無限集，所以不能用有限集中的個數（多少）來區分。

拓撲學（原書第2版）（[美] 芒克里斯著；熊金城，等譯），書中，有不使用構造法證明實數不可數的證明，大約在講連通性的第三章。