這篇文章會分成兩部分，第一部分介紹一下數學中，兩個集合中的元素個數相等的概念。
第一部分是寫給對數學有興趣的中學生閱讀的，如果能理解第一部分，就也可能可以稍微理解第二部分也很有意思的部分。
雖然我原本是只想寫第二部分的，但只寫第二部分可能讓這篇文章的受眾僅限於學習大學數學的人，補上第一部分這篇文章的受眾就是國中學生就有可能理解的程度了。（所以我的標題沒有寫哪個層級的數學，事實上我認為集合論入門的部分幾乎沒有數學程度的限制（？））
第二部分會介紹schroeder-bernstein定理的概念，即兩個集合之間存在１－１函數送至彼此，則兩集合中元素個數＂一樣多＂。
前一段時間看到有人提起了這個定理的證明，就在自己腦海中構思／回憶了一下，其實也是滿有意思的，雖然我一直以為這個證明是「構造性」的（後面會再提及何謂構造），在腦中一直想了想，總感覺好像構造不出來，最後回去翻書，才確認了只是我記錯ＸＤ，這個證明只是看起來像是構造性的，但實際上不一定能構造。
基於這篇文章的目的，文中不會嚴謹地使用各種數學描述的方式，也不會嚴格地證明定理，重點在於介紹、幫助理解，如果讀者覺得有趣那就更棒了。
有興趣參閱嚴謹證明的可自行上網搜尋「schroeder-bernstein定理」就可以看到很多資料了。
－－－－－第一部分：偶數跟整數一樣多？－－－－－
這裡會概念性地介紹「一樣多」的概念是如何應用在說明「無限多的東西」跟「無限多的東西」一樣多，其實關於這個主題已經有很有趣／也滿好理解的影片可以看。
參考：無限旅館悖論 - 傑夫‧德克夫斯基https://youtu.be/Uj3_KqkI9Zo
（可開啟字幕選擇中文台灣）
什麼是「一樣多」呢？你有３顆蘋果，我有３顆橘子，那你有的蘋果數量跟我有的橘子數量「一樣多」，這是一個很日常的概念。
套用在數學中的情境，數字１、２、３有共３個數，５、６、７也有３個數，所以集合｛１，２，３｝跟｛５，６，７｝中元素的個數就一樣多（都有３個元素）。
到這部分都符合直覺，那如果我問你－－正整數跟負整數一樣多嗎？
正整數有１，２，３，４，……，一直下去無窮無盡，有＂無限多＂個。
而負整數也有－１，－２，－３，……也是無限多個。
你覺得這兩個無限多的數量是一樣多的嗎？
當然這裡你可能會有一個懷疑，無限多的數量怎麼能比較誰多誰少呢？但如果忽略這個懷疑，如果真的要問這個問題的話，你覺得誰多誰少，還是一樣多？
你知道你所學過的正數，只要在前面寫上負號，就是它對應的負數；或者說，每個正數都有對應的相反數，在數線上與原點距離相等，位置在另一側的數。
所以你或許會同意，正整數應該跟負整數一樣多，畢竟每一個正整數就對應到一個負整數。
那麼第二個問題，你覺得正整數中，奇數跟偶數誰比較多？
（註：後面提奇數、偶數均指「正」的，覺得都寫出「正」妨礙閱讀）
我們列出來看一下，
奇數有１，３，５，７，……
偶數有２，４，６，８，……
你可能會想，如果我們看１０以內的話，偶數跟奇數一樣多，看２０以內也是一樣多，雖然如果看９以內的話，奇數會比偶數多１個，但長遠來看，它們要不然是一樣多，要不然就只差１個，這樣或許，全部的奇數跟偶數也是一樣多的吧？
接下來就是重頭戲的問題了，正整數中，偶數跟整數一樣多嗎？
你的直覺肯定會回答否定（除非你已經學過了（Ｘ）），想想看，正整數中，只有一半的數是偶數（另一半是奇數），正整數＂顯然＂比偶數還要多吧？
在古希臘時期，這樣的想法稱為「整體必然大於部分」，你從一個量裡面取出一部份的量，取出的部分一定比全部的量還要少。
但是！現代的數學中不是這樣說的，面對＂無限＂的量，很多事情會超出我們的直覺。
回到正整數跟負整數一樣多的例子，我們是基於什麼樣的想法認為它們一樣多的呢？直覺是怎麼說的呢？
一個正整數對應到一個負整數，兩兩配對，不多不少（原點兩側對稱）。
而奇數跟偶數呢？
我們是用「範圍內所含的量」去估算的，其實剛才的正負整數也可以用這樣的概念去想（以原點往兩側框相同距離的範圍）。
不過換個角度，我們也同樣可以用「對應」來看。
每一個奇數１，３，５，７，……
只要多加１，就變成了每一個偶數２，４，６，８，……
我只是把每個數字都加１，這些數的個數當然也不會改變（想像你把每個同學的頭髮都剃掉，你同學的數量也不會因此減少（？））。
每個奇數都對應到了一個偶數。
那我們到底要用「範圍內的量」還是「對應關係」來說明一樣多呢？
數學上應該是兩種觀點都有人研究，但單以集合的角度來看，數學上採取的論點是後者。
畢竟並不是所有的量都能被適當的範圍劃分，地球上所有的水果跟地球上所有的動物，要比較這兩者的數量多寡，沒有明顯可以訂的範圍可言。
但對應關係就能比較出這兩者的數量，如果一一對應的話，就知道兩者一樣多。
（但當然這兩者的數量是有限的，所以其實也沒有這麼複雜的問題）
那現在我們以「對應關係」來看，偶數跟正整數一樣多嗎？
整數是：１，２，３，４，５，……
偶數是：２，４，６，８，１０，……
如果剛才奇數跟偶數之間，可以用奇數加１得到所有偶數來判斷相等，那現在我們將每個正整數都乘以２的話？
就會是所有的偶數！
所有的正整數乘以２是：２，４，６，８，……
所有的偶數是：２，４，６，８，……
這不就是一樣的嗎？
或許你仍覺得難以接受，但又很難反駁這樣的論點。（除非你要說一堆數字每個都乘以２以後，這些數字的個數就變少了XDD）
總之數學中就是用這個「對應」來表示「一樣多」的概念。
延續著這樣的論點，我們不僅可以說明偶數跟正整數一樣多，其他各種超出一般人直覺的範例也是多如牛毛。
如正整數跟整數一樣多，對應的方法是這樣，我們把正整數中的奇數跟偶數拆成兩部分，那因為偶數跟正整數一樣多，把所有奇數對應到所有非正的整數即可。
具體的對應如下：
正整數：１，２，３，４，５，６，７，８，９，……
對應到整數：０，１，－１，２，－２，３，－３，４，－４，…‥
繼續嘗試其他範例的話，也能得到「分數（有理數）」跟「正整數」一樣多，掌握這種對應的原則，或許你也能大概猜到如何把所有的正整數對應到分數。
那從上面這種列出來對應的過程，你可能有個錯覺－－「是不是所有無限多都是一樣多的？」
畢竟其實我們只要把兩個都這樣一個一個列出來，就能找到兩個集合之間的對應關係。
那這件事情也是不對的，即使都是無限多，也有比較多的無限多跟比較少的無限多。
最常見的例子是實數比正整數多，如果不知道什麼是實數，可以想成是小數，包含小數點後有無窮位的小數。
我們能夠證明，不存在正整數跟實數之間的一一對應。
底下的證明改成證明「不存在正整數跟０～１的實數的一一對應」，因為這樣比較好講解，但你可以想像０～１之間的數只是實數中的一小部分，如果連一小部分都對應不了，全部也沒辦法。
證明方法是反證法，假設存在這種對應方式，再製造出不合理的矛盾。
如果真的存在這種對應，我們將這種對應寫成一個表：
１→０．０３３４５２……
２→０．６２９３０……
３→０．３０９２３４５……
４→０．８８２０２……
．
．
．
以此類推，每個正整數都對應到一個０～１的實數。
接著要說明，我們能找到至少一個０～１的實數，它不在這個表裡面。
方法是我們建構一個數，它的整數部分是０；
接著小數點後第一位是多少呢，看剛才表中１對應到數的小數點後第一位是多少，選個跟它不同的數字；
小數點後第二位就看表中２對應的數的小數點後第二位，選個不同的；
後面都以此類推。
以上面的表為例，我們選：
０．１３０１……
這個數肯定不會在剛才的表中，原因是它的小數點後第一位，跟１所對應到的小數不一樣，所以這個數不會是１對應到的數；它的第二位跟２對應到的小數不一樣，所以也不會是２對應到的數。
以此類推，這個數跟表中的每個數比，都至少有小數點後某一位數字不同，所以我們就找到了一個０～１之間的實數，它不在剛才的表內。
那就表示原本說存在這個對應的表就是錯的了，原本說這個表可以全部一一對應，結果我們卻能找出一個小數沒有被對應到。
如果你以前就學過上述這些，對這些概念駕輕就熟，有一個有意思的問題你可以想想看。
我們知道所有的有理數都能寫成有限小數或無窮循環小數，如果我們同樣假設存在這樣的一個正整數對應到０～１之間有理數的表，然後同樣構造一個小數點後每一位都不相同的數出來，是不是同樣也能製造出矛盾？
答案當然是不行，因為我們早就知道正整數跟有理數一樣多。
但問題是在於這樣的論證過程區別在哪？你可以想想看。
總結一下，我們知道可以用一一對應的方法，來說明兩個有無限多元素的集合有「一樣多」的元素數量。
只要找得到一一對應的關係，就能說明一樣多。
－－－－－第二部分：schroeder-bernstein定理的證明概念－－－－－
接下來的部分就會更偏數學一些了。
這個定理是說，如果兩個集合，用左右邊的集合來稱呼好了，你能夠從「左邊的」一一對應到「右邊的一部份」，也能從「右邊的」一一對應到「左邊的一部份」，那麼這兩個集合中元素的數量就一樣多（就存在全部都能一一對應到全部的方法）。
（數學的講法是如果兩集合Ａ、Ｂ，存在兩函數ｆ：Ａ→Ｂ跟ｇ：Ｂ→Ａ都是１－１，那就必然存在函數ｈ：Ａ→Ｂ是１－１且ｏｎｔｏ）（１－１是一對一對應，ｏｎｔｏ則表示右邊的所有元素都有被對應到）
這裡講的一對一跟之前的差別在於，你不知道有沒有送到另一邊的＂所有＂元素。
例如我們可以將所有的偶數對應到部分的正整數，直接對應過去就好了。
２→２，４→４，……
這個對應是一對一的，但並不是所有的正整數都有被對應到，所以光是這樣是不足以說明兩個集合一樣多的，必須要一對一，且另一邊的所有元素都有被對應到才算。
而這個定理的核心功能就在於，我們並不用真的去找出那個兩個集合之間一一對應的關係，只要兩邊都能找到可以一對一到另一邊的方式，就表示這兩個集合中的量一樣多。
也就是說找對應關係的方式會比較簡單啦。
舉例來說，我們可以用這個定理說明正整數中，２的倍數跟３的倍數一樣多。
（註：底下講到倍數也一律都是指正的，方便閱讀）
我們找一個２的倍數一對一到３的倍數的方法，最簡單的就乘以３就好。
２→６，４→１２，６→１８，……
而反過來３的倍數也能直接乘以２來對應到２的倍數。
３→６，６→１２，９→１８，……
雖然這兩個一對一對應都沒有完整地對應到另個集合，例如２的倍數送到３的倍數的對應中，９就沒有被對應到；反過來４也沒有被３的倍數對應到。
但是只要我們有了這兩個對應方式，根據＂定理＂的結果，我們就能確定這兩個集合之間存在全部一一對應的方法，即使我們還沒有實際構造出對應的方式。
上述都只是在說明這個定理的意義與用途，接著我們來看這個定理證明的概念。
想法上很直接，我們希望透過這個兩邊各別一對一的關係，建構出一個兩邊全部一一對應的關係，只要辦到這件事情，就能說明兩個集合中的元素一樣多。
接著如果開始寫數學證明、假設函數的長相、構造集合，那就沒什麼意思了，畢竟書上也就是這樣寫的。
這裡我用一個例子來說明這個證明的概念，其實只要你理解了這個例子，實際的證明幾乎只是把這個例子的概念寫成嚴格的形式而已。
例子是這樣的，我們來看（０，１）（即０～１之間的實數不含０跟１），與（０，１］（即０～１之間不含０但含１的實數）之間的一一對應如何建立。
兩個集合之間其實只差了一個元素，就是１。
所以現在的問題是，我們要如何從０～１之間抽出一個數，讓它對應到１，但又不會少對應到一個數。
（岔題一下，如果你有看第一部分中無限旅館的故事，我們是可以把無限多個正整數多安插一個數進去的，數量還是一樣多，這裡的邏輯也類似，只是更不直覺一點）
那麼方法是這樣的，例如我們原本（０，１）中所有的數都對應到自己（就數字沒變），這樣會少對應到（０，１］中的１，為了對應這個１，我們找個數去對應它。
例如將０．１→１
那問題來了，原本左邊的０．１是對應到右邊的０．１的，現在它改成對應到１了，那誰去對應右邊的０．１呢？
簡單，我們將左邊的０．０１對應到右邊的０．１
那０．０１原本對應到０．０１的，現在誰來對應０．０１呢？
相信你也知道了，就是０．００１→０．０１
一直這樣下去，右邊每個１、０．１、０．０１、０．００１、……都被它們的１／１０對應到。
即：
０．１→１
０．０１→０．１
０．００１→０．０１
０．０００１→０．００１
一直下去
而除了這些０．０…１以外，其他的數對應的都不變（也就是對應到它自己）。
這樣就是（０，１）跟（０，１］之間全部一一對應的關係了。
在剛才的過程中，我們實際上做的事情是，按照一個規律找一個無限長度的鏈，然後把這個鏈裡的每個數往前推一位，就成功＂多＂對應到一個數了。
這個鏈是１→０．１→０．０１→０．００１→０．０００１→……
（當然有個要注意的點是，這個鏈上的每個數必須要仍在（０，１）的範圍內。）
那這跟定理的證明有什麼關係呢？我們可以這樣想，這條鏈實際上是種「一對一的對應方式」所產生的結果。
這個對應方式叫做「把數字送到它的１／１０」：
（０，１）←（０，１］
Ｘ／１０ ← Ｘ
而從（０，１）→（０，１］的對應方式是不變，即：
（０，１）→（０，１］
Ｘ → Ｘ
剛才我們就是利用這兩個雙邊的一對一對應關係，來構造出了雙邊一一對應的關係。
一路複習方才的操作，我們做的事情是，首先將左邊用一對一送到右邊，檢查右邊剩下什麼還沒有對應到，結果只剩下１。
我們需要從左邊找東西去送到右邊的這個１，從右到左的關係（送到它的１／１０），我們找０．１去對應到右邊的１。
結果這導致右邊的０．１沒被對應到，那就再次利用右到左的關係去找是誰要對應它，也就是０．０１。
這個操作可以無窮地進行下去。
結果就構造出了一個從左到右全部一一對應的關係。
現在把上面的實際數字都換成抽象的集合概念，就得到定理的證明了。
我們有一個左到右的一對一對應，以及一個右到左的一對一對應。
首先把左邊的全部用「左到右」送到右邊，看右邊剩餘那些沒有被送到。
把右邊沒有被送到的每個元素，都利用「右到左」送回左邊，看看要用左邊的哪些元素去填補方才剩餘的。
這些左邊的元素被用來填補剛才右邊剩餘的了，那麼這些左邊的元素「原本對應到的右邊元素」就又沒被對應到了。
繼續對右邊剩餘的元素重複做上述的操作，無窮地進行下去，就得到了左到右全部一一對應的關係。
上述這個論證的瑕疵是，我們怎麼知道這個操作不會有循環的情況出現，也就是會不會有一個左邊的數，再某次被用來填補後，之後又再次被用來填補，如果這件事情發生了，那就有可能會產生循環，導致這個過程無法無限回推，始終有個東西沒有被對應到。
看不懂我在解釋什麼的話我舉例說明，想把１借來用，可以把１←２←３←４←５←６←……一路往回推無窮無盡下去，每個數都還是被對應到了。
但如果把「剪刀」←「石頭」←「布」←「剪刀」←……裡面抽一個出來，剩下兩個不停用後面的來遞補，總還是會缺一個，因為這個過程是循環的。
而實際上，方才的論證過程是不會循環的，這個留給你自己想會比較明白（不好用文字解釋），因為兩邊都是一對一的對應，每次對應到的元素都會是不一樣的。
（又或是你也可以姑且接受，等到你真的有需要論證再想這個問題）
最後再提兩件事情，第一個是我們再用一個複雜一點的例子來示範如何構造出兩邊全部一一對應的關係。
第二個是解釋「為何這個證明不算是構造性的」，看看我們先前做的事情，不是都能實際構造出對應關係嗎？
底下就用剛才２的倍數和３的倍數的例子來構造兩邊一一對應的關係。
（提醒一下，這兩者其實有更簡單的對應方式，就是把２的ｎ倍對應到３的ｎ倍，這裡的重點只是示範。）
２的倍數→３的倍數，方法是乘以３
２→６，４→１２，６→１８，……
３的倍數→２的倍數，方法是乘以２
３→６，６→１２，９→１８，……
底下我們稱２的倍數為「左邊」，３的倍數為「右邊」。
先將左邊全部用「左到右」送到右邊，對應到：
６，１２，１８，２４，……，實際上就是所有６的倍數。
那來看右邊剩餘哪些沒有被對應到。
是３，９，１５，２１，……，即３的奇數倍。
把這些用「右到左」送回來，看要挪出哪些左邊的數去對應它們。
送回來是乘以２，得到：
６，１８，３０，４２，……，即６的奇數倍。
我們現在調整一下左到右的方式，將：
６→３，１８→９，３０→１５，４２→２１，……
那右邊哪些東西因此沒有人對應到呢？
就是這些左邊數字的３倍，即１８、５４、９０、……
我想你可能也跟我一樣已經有點昏頭了，這個操作當然可以無窮地進行下去，當然也確實有規律可以觀察（就像之前１→０．１→０．０１→……那樣），但看著這麼多數字也是有點亂。
實際上最後建構出來的一一對應關係，左邊要不然是透過原本的「左到右」送到右邊（即送到其３倍）；要不然就是透過「右到左」（即送到其２倍）的反向操作（即送到其１／２倍）到右邊。
例如方才的左邊的２就可以確定會送到右邊的６（利用左到右），而６是送到右邊的３（利用右到左反過來）。
所以只要我們能判斷，從左邊選一個數出來，它會不會在那些無止盡的鏈上？
如果不會的話，就用「左到右」的對應；如果會的話，就用「右到左」的反過來。
所以真正決定我們能不能實際構造出來的關鍵在於－－「我們能不能判斷一個元素在不在鏈上？」
在最初（０，１）→（０，１］的例子中，我們最後發現只有１，０．１，０．０１，０．００１，……這些數在鏈上，其他的都不在，所以我們實際構造出了這個一一對應關係。
在剛才的２的倍數和３的倍數，雖然如果有耐心一點，應該也可以推出鏈的規則，但剛才已經做得有點複雜了，結果沒做出來。
如果利用這個定理的證明，我們總是能實際找出一一對應的關係，那這個證明就是構造性的；如果不一定可以，那就只是存在性的證明，我們知道這個對應關係必然存在，但不知道它長什麼模樣。
前面的兩個例子，我們實際上都能真的構造出一一對應的關係，但是一般而言，如果互相對應的方式稍微複雜一點的話，我們就可能很難／幾乎不可能判定左邊的一個元素是否會在鏈上。
我隨意舉一個複雜的例子。
偶數→正整數
「左到右」的關係是乘以小於該數的最大質數。
「右到左」的關係是乘以２再乘以大於該數的最小質數。
那現在我們隨便選一個左邊的數３０９８７８２，我們能判斷它在不在某條鏈上嗎？
我們只能沿著鏈一直做下去，或許做到某個時刻會發現它在鏈上，就算一直都沒找到，也不一定能判斷它確實不在鏈上。（當然這個例子中應該到頭來還是能判斷單一數字的，我只是不想舉用到無理數的例子）
對於更複雜的對應關係，這種判斷在不在鏈上的過程就更困難了，我們未必能構造出適切的判定方法。
但透過這個定理，我們仍是知道，這個「全部一一對應的關係」是確實存在的。
留言列表
電腦遊戲 (3)