【邏輯學】集合論（下）：比較無限的大小與集合的秩序

前言

還能說什麼，就是下集唄。沒有前言直接進入主題感覺怪怪的，姑且還是丟一個在這裡。

另外就是上集一定要看熟看懂，不然下集一定看不懂。

那麼我們就開始吧。

集合的基數與大小

集合的基數

接下來我們來關心一下集合的基數（cardinality）吧，也就是集合成員的個數。集合的基數我們表達成「｜A｜」。長得有點像絕對值是吧。比方說A={a, b, c}，它的基數我們就表達成｜{a, b, c}｜=3，這樣。

什麼時候兩個集合的基數是相同的呢？聽起來像是廢話，數一下A和B分別都有幾個元素，看兩邊相同不相同不就得了？但其實我們還有另一種方式，就是應用我們上一回提到的映射。兩個集合的基數相同還是不相同你可以直接看A和B是不是對射（bijection）的。還記得對射嗎？就是既單射又滿射，A的元素映射到B的一個元素，B的元素被射過了就不會重複被射到，並且B的元素都被射滿。

我們看下圖，很形象地表達了兩個集合基數相同的情況：

是不是一看就明白了呢？這一定個數相同嘛。這也是為什麼前回講到映射的時候說我們預設它是全函數，因為如果不這樣設定的話，你就想：

A={1, 2, 3}

B={a, b}

1->a, 2->b

這也是一個bijection唉？技術上來說，這個叫做partial bijection。我沒有看到這個的中文翻譯，姑且直翻成部分對射吧？顧名思義，雖然這是一個對射，但這是一個部分函數的對射關係。A的3沒有射出去嘛。

這個狀況就很尷尬了，剛才說了我們可以通過bijection的方式來確認集合的基數相同，但如果我們不預設全函數，接受部分函數的話，我們就要接受A和B的bijection，接受｜A｜=｜B｜，接受3=2了。

不過我要先說，這個部分課本沒有寫，教授沒有說，台大公開課沒有明說但畫出來的模型都是全函數的對射。有一些英文資源有提到它不能是部分對射，得是全函數。ChatGPT姑且是認同了我。總之，我是綜合了各式各樣的資訊之後得到的這樣的結論。如果有錯的話歡迎指正。倒不如說，快來教我==

總之呢，如果我們能在全函數的前提下建立起A和B的對射，我們就說這兩個集合的個數相同，｜A｜=｜B｜。

可數集

另外一個概念叫做可數集。顧名思義，這個集合是denumerable的，是可數的。要判斷一個集合是不是可數集，無非就是問這個集合可不可以被自然數編碼。比方說A={a, b, c}好了，我就編碼a是1；b是2；c是3。就這麼簡單。

基本上...只要它可以數就可以被自然數編碼啦。

可以被自然數編碼的集合有兩個條件，滿足其一則可數。條件為：

1. 任何非空集合的有限集（成員非無限的集合）都是可數集。它們都可以被自然數編碼。
2. ｜A｜=｜N｜。N在這裡表達的是自然數的集合。上一篇集合論有說N就是自然數的集合，如果忘記了可以複習一下。特別的是，這邊的A我要表達的是一個無限集合。顧名思義，這個集合的成員有無限多。

不知道你們會不會覺得很奇怪，無限要怎麼數啊？

可數的無限

無限可以數嗎？當然可以啊，我們一起來數數看吧？

說到數數無非就是兩種方法：要馬你一個一個數，要馬你採用一一對應的關係。

什麼叫做一一對應的關係？

假設我有一個教室，裡面有......呃，就說20張椅子好了。我現在有一組同學坐進去，我不需要去數到底有幾個同學，只要他們把椅子坐滿了，沒有人坐到別人的大腿上的話，即便我不去數有幾個學生，我也可以很明確地知道他們有20個人，對嗎？這就叫一一對應的關係。

有沒有覺得很像什麼啊？這不就是對射嗎？我把每一個學生指定給了一張椅子（全函數映射），每張椅子都被坐滿沒有遺漏（滿射），也沒有人坐到別人的大腿上（單射）。

今天我們問無限集合可不可數，我們當然不想一個一個數看看它能不能被自然數編碼。哪怕我給你無限的時間，你多半也不想在經歷永恆的光陰中永遠都在數數。那要怎麼辦？也很簡單，我們採一一對應就好。就只要問無限集合能不能和N對射就行了。換句話說，這個無限集合的每一個元素都可以一一對應自然數的集合裡的每一個元素。也等於是這無限個元素都被自然數編碼了啦。

現在我有一個超級大的教室，裡面有無限張椅子，每一張椅子都代表一個自然數。我現在有無限個同學，要問這些同學是不是無限可數的集合，就是問他們能不能把這無限張分別代表不同自然數的椅子坐滿。當然，不可以坐在別人大腿上。

一個無限集合是可數的意味著｜A｜=｜N｜。我們前面說了兩個集合基數相等就是它們bijection嘛。這要特別記一下，這是正式的定義。不是說我之前給的東西都不正式啦，但就是希望大家特別記一下。我們說一個集合是無限可數的就是說這個集合和自然數的集合有對射關係。｜A｜=｜N｜。

那自然數的集合自己是不是無限可數的啊？當然是嘛，自己對射自己沒問題啊。｜N｜=｜N｜。

正整數不說，整數Z的集合可不可數？應該都還記得整數的集合固定叫Z吧？自然數固定叫N；整數固定叫Z；有理數固定叫Q；實數固定叫R。

直覺上好像會覺得Z比N大一點是不是？畢竟多了負數嘛。這個我們稍後談談。但基本上無限和無限一樣大嘛，當然Z也可以和N對射，沒毛病。Z也是無限可數集。

那有理數的集合Q可不可以數啊？當然可以啊，把那些重複的跳過就是了。比方說那些2/1、4/2、8/4...這種的，跳過就對了。Q當然也是無限可數的集合。

那實數可數嗎？

康托爾對角線證明

令人意外地，實數R的集合不可數耶。這個證明是當初發明集合的人，康托爾想出來的。我們來看看他怎麼做。

基本上這個證明是採反證法的策略，也就是我先假設它是對的，再從中抓出矛盾，藉此證明它是錯的。

首先我們先假設R是可數的，也就是說R和N對射。既然R和N對射，我們取R的一個線段當然也和N對射，不是嗎？這個線段就取[0, 1]好了。如果你不知道的話，[0, 1]就是0到1之間的數字。反正就一堆小數啦。

你可能會覺得R的線段比R小耶。A={1, 2, 3, 4}和B={a, b, c, d}對射，｜A｜=｜B｜。但是我取S⊂A，S={1, 2}沒有辦法和B對射啊！唉，你說得沒錯。但無限就不一樣了。無限的特性就是你不管取哪一段都和原本那個無限集合一樣大。

回到康托爾的證明，現在我們就開始把這些小數列出來，但我們有一個小小的要求，那就是我們要用無限小數來列。也就是當我們遇到有限小數例如0.5的時候，我們偏偏就要表達成0.49999999999......這樣。

然後我們就來開始列吧：

r表達[0, 1]之間的小數，並且我們直接用a來表達小數點後面的數字。a後面的號碼表達幾行幾列，比方說a32表達第三行第二列。這些a都可以是任何數字，比方說r1就可以等於0.34785......等等等等等等。

反正r這樣列下來會窮盡所有[0, 1]之間的小數就對了。很重要所以我再說一次，我們現在窮盡了[0, 1]之間所有的小數。

但是！我們居然可以挑出一個新的數耶？

這個數就是：0.b1b2b3b4b5.........bn無限延伸下去。b當然就表達了小數點後的數，b1就是小數點後第一位，以此類推。

我使b1不等於a11；使b2不等於a22；使b3不等於a33......以此類推。你發現了嗎？這個數不等於前面提到的任何一個r耶，最少都會有那麼一個數不等於前面提到的任何一個r。這是一個全新的數。

但這不是很矛盾嗎？設定上那串r就是窮盡了[0, 1]之間的小數了才對啊，然而這個新的數確實存在於[0, 1]之間，卻不等於任何一個r，這就是一個矛盾。

你可能會想，0.b1b2b3b4b5.........bn是不是早就已經存在r之中了。當然也沒有。因為設定上它就是會有至少一個數不等同於任何一個r，但又不可否認它確實又是[0, 1]之間的數。確確實實的矛盾。

當然你也可以把我們設定的這個新數再丟進這串r裡面，但我同樣可以設定另一個0.b1b2b3b4b5.........bn，一樣不等同任何一個r，永遠沒完沒了。

所以這個矛盾就使得康托爾的反證法證明成立了，實數的集合R是不可數的。這是我們第一個遇到的無限不可數集合。

至於為什麼叫對角線證明？因為它長這樣：

紅圈的地方就是我們設定bi的時候不等同於amn的地方，剛好就是一條對角線，所以我們叫它對角線證明。amn就是第幾行第幾列的a啦，我直接當成一個矩陣看了。

比無限還要更大的無限

對角線論證不僅僅只是證明了實數是無限不可數的而已。雖然說實數和自然數的集合都有無限個成員，但他們之間的對射不成立耶？我們再複習一下，我們之前說｜A｜=｜B｜兩個集合的個數相同的定義就是兩個集合之間的對射成立，對嗎？

那這個情況......難道不意味著實數的集合比自然數的集合個數還要來得大嗎？

康托爾接受了｜R｜>｜N｜這件事，並且進一步地提出了無限層級的概念。

1. ℵ0：表示一個無限可數的集合。
2. ℵ1：表示一個無限不可數的集合。

並且我們說ℵ1>ℵ0。無限之間也有大小之分。

順帶一提，符號是用希伯來字母的ℵ，念作aleph。跟人家溝通的時候就說aleph zero, aleph one......so on 就好了。

希爾伯特旅館悖論

無限有一些很奇特的性質，使得它難以被理解。大家有聽過無限旅館悖論嗎？也有人叫它希爾伯特旅館悖論，這是因為提出這個悖論的人叫做大衛．希爾伯特。

希爾伯特用無限旅館悖論像我們展示一些無限的奇異性質，我就來看看他怎麼說吧：

首先我們要想像一間超大的旅館，裡面有無限間房間。有一天旅館生意超好，房間被無限個住客給住滿了（對射），但此時還是來了一位新的旅客進來要登記入住。這時候前台要怎麼辦呢？這錢不賺白不賺啊！

於是前台就想了一個聰明的點子，就是讓所有住客往後挪一間房。一號房挪到二號房，二號房挪到三號房......n號房挪到n+1號房，這樣房間不就空出來了嗎！真聰明！

你可能會想：剛剛不是說房間都住滿了嗎？是啊，是住滿了沒錯，但這可是無限旅館啊！雖然說被住滿了，但如果它有極限就不是無限了啊。

這個方法可以用來應對任何數量的新訪客，比方我一台遊覽車又載了40個旅客要來住房好了，那前台就讓所有住客從n號房移動到n+40號房，不就又空出40個房間來了嗎！這些住客脾氣還真好，換作是我可就生氣了呢。

哪怕來了無限台遊覽車，載了無限可數個旅客要來住無限間房，當然也沒問題！我們只要讓一號房的住客移動到二號房，二號房移動到四號房，四號房移動到八號房......以此類推。讓所有住客移動到2n號房就行了，這樣一來就只有偶數號房住滿，空出了無限間基數號房了呢！旅館今晚又多賺了無限多錢。

無限旅館之所以成立是因為我們考慮最低層級的無限，也就是ℵ0，可數的無限。如果是不可數的無限的話我們就沒辦法做這種事了。我們沒辦法系統地處理所有的數字，什麼√2號房啊，或是π號房啊，沒辦法，考慮全部這些的話我們處理不了。這是屬於無限可數集的特性。

ℵ2

老實說關於無限的大小這件事哲學系就只談到這裡了，但不死心的我還是試著去找了ℵ2這種東西。不用我說，這意味著ℵ2>ℵ1>ℵ0，比R還要更大的無限。

我也老實說了，我看不懂。我們沒教這麼深。但我大概試著梳理一下。

首先很重要的一個前提，如果我們要做出ℵ2的話就一定得是一個無限不可數的集合，並且假設了某種廣義連續體假設（Generalized Continuum Hypothesis）。我不知道那是什麼東西。

接下來我們有兩種可能是ℵ2的例子：

1. 所有R->R可能的映射模型所組成的集合。
2. 所有R->{0, 1}可能的映射模型所組成的集合。

如果你想知道的話，我看的東西連結在這：

反正我是看不懂。加油。

這可能要找一個數學系的來問了。

有序的集合

n元組

上集我們在談集合的等同時談到，集合是沒有秩序的，集合在表達上成員你可以隨便亂排完全沒關係，甚至你可以同一個元素放兩次，像是A={1, 1, 2}之類的，但實際上A裡面還是只有一個1，你只是寫兩次而已，不意味著A有兩個1。這叫做extensionality（外延性）。

但如果我想要表達一個有秩序的集合怎麼辦？

我想要一個集合它的擺放排列表達了這些元素之間的順序關係，並且也嚴格要求同樣的元素如果重複出現的話它們就不是同一個東西，那麼我需要的就是n元組（n-tuple）。n元組的n就是看你的集合有幾個成員就自己代入，兩個成員就2元組，十個成員就10元組，以此類推。

n元組表達成「<a1...an>」，也可以寫成「（a1...an）」啦，但我比較習慣前者。比方說如果{1, 1, 2}是一個3元組的話就是表達成<1, 1, 2>。{1, 1, 2}={1, 2, 1}，但<1, 1, 2>不等於<1, 2, 1>。

除了順序以外，我們也提到了成員數量對n元組來說是有差的。<1, 1, 2>不等於<1, 2>。

1. {1, 2}={2, 1}={1, 1, 2}={1, 2, 1}={1, 2, 2, 1} ...... so on
2. <1, 2>不等於<2, 1>不等於<1, 1, 2>不等於<1, 2, 1>不等於<1, 2, 2, 1> ...... so on

注意，n元組只能用來表達一個有限的有序集合，無限集合我們不用n元組表達。

序對

序對（order pairs）很單純地就是表達2元組而已，傳統上2元組我們就是這樣叫的。就像前面說的，元組是一個有序的集合，所以一個關於序對的基本定義就是如果<a, b>=<c, d>，若且唯若（if and only if）a=c且b=d。很直白，就不多說了。

其實n元組我們也可以把它理解成特殊的序對。以3元組來說好了，<a, b, c>你可以簡單地把它理解成<<a, b>, c>。4元組也一樣，<a, b, c, d>你就簡單理解成<<<a, b>, c>, d>，以此類推。

為什麼要把序對獨立出來講？除了它姑且有一個專屬的名稱以外，之後的模態邏輯系列也會很常用序對來表達關係。什麼是關係我們暫且不管，總之先記住序對吧。

威納-庫拉托夫斯基定義

不知道你有沒有想過用集合來表達n元組呢？唉，威納和庫拉托夫斯基有。威納-庫拉托夫斯基定義（Wiener-Kuratowski definition）就是用集合來表達元組的秩序，這樣一來就不需要另外引入新的概念了。即使不需要元組我們也一樣能表達有秩序的集合，只是會搞剛很多而已，所以其實基本上其實都還是會用元組啦。我姑且還是教一下怎麼做。

所以他們建議我們怎麼做？

<a>你就把它表達成{{a}}

<a1, a2>就把它表達成{{a1}, {a1, a2}}

<a1, a2, a3>就把它表達成{{a1}, {a1, a2}, {a1, a2, a3}}

以此類推。

笛卡兒積

笛卡兒積（Cartesian product）很單純就是集合與集合相乘，我們會因此得到由A的元素去配對B的元素所形成的由序對組成的集合。

我們直接舉個例子：

A={a, b}

B={1, 2, 3}

A×B={<a, 1>, <a, 2>, <a, 3>, <b, 1>, <b, 2>, <b, 3>}

有看懂發生什麼事嗎？我們再用一張圖說明：

我在每一條紅線上標了數字告訴你我是按照什麼順序分配的，第一步把a配給1做成<a, 1>，第二步把a配給2做成<a, 2>，......第五步把b配給2做成<b, 2>，第六步把b配給3做成<b, 3>。就這麼簡單，A×B={<a, 1>, <a, 2>, <a, 3>, <b, 1>, <b, 2>, <b, 3>}就是這樣做成的。

任何集合相乘，其笛卡兒積都是按照這種方式，把集合A的元素分配給集合B的每一個元素，然後再換下一個集合A的元素做一樣的事情，直到集合A的元素分完，一個笛卡兒積就做成了。

任何一個笛卡兒積的數量都是n×m，也就是說如果A有n個元素，而B有m個元素，那麼A×B就會有n×m個元素。

當然，笛卡兒積不限定一對一，你要多個集合相乘當然也可以。我們示範一下三個集合相乘吧。

A={1, 2}

B={a, b}

C={red, blue}

A×B×C={<1, a, red>, <1, a, blue>, <1, b, red>, <1, b, blue>, <2, a, red>, <2, a, blue>, <2, b, red>, <2, b, blue>}

總之差不多一樣，我先考慮1a配然後配給red，然後再配給blue。接著我們考慮1b配，先配red再配blue。2也是一樣的道理。

我畫了張圖：

基本上複雜的笛卡兒積你都可以這樣處理。這個真的要多麻煩就有多麻煩，我就不繼續舉例了。大家應該都學會舉一反三了吧？

三個以上的集合形成的笛卡兒積，其元素個數就是（（A×B）×C），以此類推。

還有最後一種笛卡兒積就是A^n，顧名思義，這是由A重複乘自己形成的笛卡兒積。操作還是老樣子，大家都學會了吧？

結語

其實......我複習這麼多集合論的東西很單純就是想讀一篇Putnam的Models and reality而已。我想我現在終於可以去讀了。

如果我要接續模態邏輯系列，接下來我會寫一篇數學歸納法的一階邏輯應用，以及一篇關係（relation）的入門。等這兩篇也寫完了，我們就可以準備進入模態邏輯了。

那就先這樣，我們下回見。