離散數(shù)學(xué)電子教材

可編輯可編輯精品精品可編輯精品第4章映射（函數(shù)）映射（函數(shù)）是一個(gè)基本的數(shù)學(xué)概念，它是一個(gè)特殊的二元關(guān)系，我們可以把映射看作輸入輸出關(guān)系，它把一個(gè)集合（輸入集合）的元素變成另一個(gè)集合（輸出集合）的元素。例如，計(jì)算機(jī)中的程序可以把一定范圍內(nèi)的任一組數(shù)據(jù)變化成另一組數(shù)據(jù)，它就是一個(gè)映射。映射的概念經(jīng)常出現(xiàn)在開關(guān)理論、自動(dòng)機(jī)理論和可計(jì)算理論等領(lǐng)域中，在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用。4.1映射（函數(shù)）的概念考慮下面幾個(gè)由圖4-1所示的集合到集合的關(guān)系。圖4-1可編輯可編輯精品精品可編輯精品在這６個(gè)關(guān)系中，后４個(gè)關(guān)系，，，與，不同，它們都有下面兩個(gè)特點(diǎn)：（1）其定義域?yàn)?；?）中任一元素對(duì)應(yīng)唯一一個(gè)中的元素。我們稱具有這樣兩個(gè)特征的關(guān)系為映射（函數(shù)）。定義4.1.1設(shè)是兩個(gè)任意的集合，而是到的一個(gè)關(guān)系，若對(duì)每一個(gè)，都存在一個(gè)唯一的，使得，則稱關(guān)系為到的映射(Mapping)，記作或若，則稱為自變量(IndependentVariable)，稱為映射在處的值（或像（Image）），亦可記作，的值域ran，有時(shí)也記為，即或記為集合稱為的共域，亦稱為映射的像集合。對(duì)于，稱為的像（Imageof），定義為顯然,，。映射是到的特殊的二元關(guān)系，其特殊性在于：（1）dom，即關(guān)系的前域是本身，而不是的真子集。（2）若，則映射在處的值是唯一的，即例4.1.1設(shè)，且有，求dom、和。解dom可編輯可編輯精品精品可編輯精品ran例4.1.2判別下列關(guān)系中哪個(gè)構(gòu)成映射（1）（2）（3）（4）（5）為小于的素?cái)?shù)個(gè)數(shù)（6）（7）（8）解（1）構(gòu)成映射。（2），即值不唯一，故不構(gòu)成映射。（3）因?yàn)椴荒苋《x域中所有的值，且對(duì)應(yīng)很多，故不構(gòu)成映射。（4）因?yàn)椴荒苋《x域中所有的值，故不構(gòu)成映射。（5）構(gòu)成映射。（6）構(gòu)成映射。（7）因?yàn)閷?duì)，值不唯一，故不構(gòu)成映射。（8）因?yàn)閷?duì)，值不唯一，故不構(gòu)成映射。例4.1.3下列集合中，哪些是映射？并求（1）（2）（3）（4）解（1）是映射。dom，（2）是映射。dom，可編輯可編輯精品精品可編輯精品（3）不是映射。（4）是映射。dom，請(qǐng)注意區(qū)別的像和的像兩個(gè)不同的概念。的像，而像。關(guān)于像有下列性質(zhì)：定理4.1.1設(shè)為到映射，對(duì)任意，有（1）；（2）；（3）。證明（1）對(duì)任一，因此，。（2）、（3）的證明請(qǐng)讀者完成。注意：（2）、（3）中的“”不能用“=”代替。下面我們舉例說明。例4.1.4設(shè)，，如圖4-2所示。那么，可編輯可編輯精品精品可編輯精品圖4-2例4.1.4由于映射歸結(jié)為關(guān)系，因而映射的表示及運(yùn)算可歸結(jié)為集合的表示及運(yùn)算，映射的相等的概念、包含概念，也便歸結(jié)為關(guān)系相等的概念及包含概念。定義4.1.2設(shè)，，如果，，且對(duì)于所有，有，則稱映射和相等，記作。如果，，且對(duì)于所有，有，則稱映射包含于，記作。事實(shí)上，當(dāng)不強(qiáng)調(diào)映射是定義在哪個(gè)集合上的時(shí)候，由于映射是序偶的集合（特殊的關(guān)系），所以f=g的充分必要條件是且。從映射的定義可以知道的子集并不能都成為到的映射。例如，設(shè)，，，有個(gè)可能的子集，但其中只有個(gè)子集為從到的映射：，，，，同理可知，從到可定義個(gè)不同的映射：可編輯可編輯精品精品可編輯精品，，，，，，，一般地，設(shè)和都為有限集，分別有和個(gè)不同元素，由于從到任意一個(gè)映射的定義域是，在這些映射中每一個(gè)恰有個(gè)序偶。另外任何元素，可以有的個(gè)元素中的任何一個(gè)作為它的像，故共有個(gè)不同的映射。在上例中，故從到有個(gè)不同的映射，從到有個(gè)不同的映射。今后我們用符號(hào)表示從到的所有映射的集合，甚至當(dāng)和是無限集時(shí)，也用這個(gè)符號(hào)，即則有。特別地表示集合上映射的全體。習(xí)題4.11．指出下列各關(guān)系是否為到的函數(shù)：（1），（2）(實(shí)數(shù)集)，（3），（4）設(shè)，，，，。2．設(shè)，，求證：（1）為到的函數(shù)當(dāng)且僅當(dāng)。（2）為到的函數(shù)當(dāng)且僅當(dāng)。3．設(shè)為一函數(shù)，計(jì)算，，。4．設(shè)，為：，求可編輯可編輯精品精品可編輯精品，，，。4.2特殊映射定義4.2.1（1）如果ran，即的每一個(gè)元素都是中一個(gè)或多個(gè)元素的像，則稱這個(gè)映射為滿射(Surjection)（或到上映射）。（2）如果對(duì)于任意，若，則有，則稱這個(gè)映射為入射(Injection)（或單射）。（3）若既是滿射又是入射，則稱是雙射(Bijection)。雙射也稱為1—1對(duì)應(yīng)(OneToOneMapping)。由定義不難看出，如果是滿射，則對(duì)于任意，必存在，使得成立；如果是入射，則中沒有兩個(gè)不同元素有相同的像，即對(duì)于任意，。圖4-3說明了這三類映射之間的關(guān)系。注意，既非單射又非滿射的函數(shù)是大量存在的。圖4-3例4.2.1（1）設(shè)，如果定義為則是滿射的。（2）定義為，則這個(gè)函數(shù)是入射，但不是滿射?？删庉嬁删庉嬀肪房删庉嬀罚?）令表示實(shí)數(shù)的閉區(qū)間，即，定義為：則這個(gè)映射是雙射。例4.2.2在圖4-4中，、是滿射，、是入射，是雙射。圖4-4例4.2.3設(shè)是自然數(shù)集，下列映射哪些是滿射、入射、雙射。（1），。（2），。（3），（4），（5），（6），。（7），解：（1）入射。（2）一般映射（既非滿射，也非入射）。（3）一般映射（既非滿射，也非入射）。（4）滿射。（5）不是映射，無定義。（6）一般映射（既非滿射，也非入射）。（7）不是映射，無定義?？删庉嬁删庉嬀肪房删庉嬀范ɡ?.2.1令和為有限集，若和的元素個(gè)數(shù)相同，即，則是入射的，當(dāng)且僅當(dāng)它是一個(gè)滿射。證明（1）若是入射，則。從的定義我們有，而，因?yàn)槭怯邢薜?，故，因此，是一個(gè)滿射。（2）若是一個(gè)滿射，則，于是。因?yàn)楹褪怯邢薜?，所以，是一個(gè)入射。這個(gè)定理必須在有限集情況下才能成立，在無限集上不一定有效，如，這里，在這種情況下整數(shù)映射到偶數(shù)，顯然這是一個(gè)入射，但不是滿射。另外，還有兩個(gè)特殊而又重要的映射—常映射和恒等映射。定義4.2.2（1）設(shè)，如果存在，使得對(duì)所有的都有，即，則稱是常映射。（2）任意集合上的恒等關(guān)系為一映射，常稱為恒等映射，因?yàn)閷?duì)任意都有，即。對(duì)任意，有，故是入射；且，是滿射。所以，是雙射。習(xí)題4.21．設(shè)分別表示正整數(shù)集、整數(shù)集、實(shí)數(shù)集、復(fù)數(shù)集，試指出下列映射中哪些是單射、滿射、雙射，并寫出定義域和值域。為。為。為。為?？删庉嬁删庉嬀肪房删庉嬀窞?。為（其中為一常數(shù)）。2．下列關(guān)系中哪些能構(gòu)成映射？。（1），其中為自然數(shù)集。（2），其中為實(shí)數(shù)集。(3)，其中為實(shí)數(shù)集。3．下列集合能定義成映射嗎？如能，試求出它們的定義域及值域。（1）。（2）。（3）。（4）4．設(shè)映射，這里，（1）定義了何種關(guān)系？(2)的值域是什么？（3）有多少與具有同樣定義域和陪域的不同映射？。（4）設(shè)的映射且，問可能是單射嗎？可能是雙射嗎？（5）證明存在一個(gè)從到的單射，其中為任意集合。（6）設(shè)與均是有限集且有個(gè)元素，有個(gè)元素，說明下列斷言為真時(shí)，和必須成立的關(guān)系：存在從到的單射。存在從到的滿射。存在從到的雙射。4.3復(fù)合映射和逆映射可編輯可編輯精品精品可編輯精品4.3.1復(fù)合因?yàn)橛成涫且环N特殊的關(guān)系，所以和關(guān)系一樣也有復(fù)合運(yùn)算。定義4.3.1設(shè)映射，，若，則稱在映射的左邊可復(fù)合。對(duì)于映射的復(fù)合我們有下面的定理：定理4.3.1設(shè)，，在映射的左邊可復(fù)合，即，則是一個(gè)映射。證明(1)對(duì)于任意，因?yàn)闉橛成?，故必有唯一的序偶，使成立，而即，又因?yàn)槭怯成?，故必有唯一序偶，使成立，根?jù)復(fù)合定義，，即中每個(gè)對(duì)應(yīng)中某個(gè)。(2)假定中包含序偶和，這樣在中必存在和，使得在中有和，在中有和。因?yàn)槭且粋€(gè)映射，故；又因?yàn)槭且粋€(gè)映射，故，即每個(gè)只能有唯一的。由(1)、(2)可知是一個(gè)映射。在定義4.3.1稱為映射與映射的復(fù)合映射，或稱為對(duì)的左復(fù)合。注意：在定義4.3.1中，假定random，如果不滿足這個(gè)條件，則定義為空。根據(jù)復(fù)合映射的定義，顯然有。例4.3.1設(shè)，，求?？删庉嬁删庉嬀肪房删庉嬀方饫?.3.2設(shè)，均為實(shí)函數(shù)，，。求，，，。解所以定理4.3.2設(shè)是一個(gè)復(fù)合（1）若和是滿射，則是滿射。（2）若和是入射，則是入射。（3）若和是雙射，則是雙射。證明給定集合，，，（1），因?yàn)槭菨M射，故，使得；又因?yàn)槭菨M射，故，使得，所以，即，，使得。因此，，是滿射。（2）對(duì)，，因?yàn)槭侨肷洌?；又因?yàn)槭侨肷?，故，于是可編輯可編輯精品精品可編輯精品所以，是入射。?）因?yàn)楹褪请p射，根據(jù)（1）和（2），為滿射和入射，即是雙射。定理4.3.3設(shè)是一個(gè)復(fù)合映射。（1）若是滿射，則是滿射。（2）若是入射，則是入射。（3）若是雙射，則是滿射，是入射。證明設(shè)，，。（1）因?yàn)槭菨M射，則，，，使，故使得，，可見，，所以是滿射。（2）設(shè)且。因?yàn)槭侨肷洌?，即，因?yàn)槭且粋€(gè)映射，則，即所以，是入射。（3）是雙射，則是滿射且是入射。是滿射，由（1）可知是滿射；是入射，由（2）可知是入射。由于映射的復(fù)合仍然是一個(gè)映射，故可求三個(gè)以上映射的復(fù)合。例4.3.3設(shè)為實(shí)數(shù)集合，對(duì)，有，，求，，與。解：，可編輯可編輯精品精品可編輯精品所以有一般地，有如下定理。定理4.3.4設(shè)有函數(shù)，和，則有證明這可由關(guān)系的復(fù)合的可結(jié)合性得出，這里我們直接由映射相等的定義證明。首先和都是到的函數(shù)。另外對(duì)任一，有由元素的任意性，有由此可見，映射的復(fù)合運(yùn)算滿足結(jié)合律，因此多個(gè)映射復(fù)合時(shí)可去掉括號(hào)，對(duì)3個(gè)映射的復(fù)合即有。若有，則仍為到的映射，簡記為，一般地簡記為。顯然注意：映射的復(fù)合運(yùn)算不滿足交換律。例4.3.4（1，，，，則，。所以?？删庉嬁删庉嬀肪房删庉嬀酚成涞膹?fù)合運(yùn)算還有如下明顯的性質(zhì)：定理4.3.5設(shè)映射，則。證明對(duì)，有，，則所以，當(dāng)時(shí)，有4.3.2在關(guān)系的定義中曾提到，從到的關(guān)系，其逆關(guān)系是到的關(guān)系，但是，對(duì)于映射就不能用簡單的交換序偶的元素而得到逆映射，這是因?yàn)槿粲杏成?，但的值域可能只是的一個(gè)真子集，即，此時(shí)，dom，這不符合映射對(duì)定義域的要求。此外，若的映射是多對(duì)一的，即有，其逆關(guān)系將有，這就違反了映射值唯一性的要求。為此，有如下定理：定理4.3.6設(shè)是一個(gè)雙射，那么是的雙射。證明設(shè)，，因?yàn)槭菨M射，故對(duì)每一，必存在，所以，，即的前域?yàn)?。又因?yàn)槭侨肷?，?duì)每一個(gè)恰有一個(gè)，使，即僅有一個(gè)，使，對(duì)應(yīng)唯一的，故是映射。因?yàn)閞andom，所以，是滿射。又設(shè)時(shí)，有，令，則，故可編輯可編輯精品精品可編輯精品，即，與假設(shè)矛盾。所以，即是單射。因此，是一個(gè)雙射。定義4.3.2設(shè)是一雙射，稱的雙射為的逆映射，記作。例如，設(shè)。若為：，則有，。若，則的逆關(guān)系就不是一個(gè)函數(shù)。再如，，，則。函數(shù)的逆具有下面一些重要性質(zhì)。定理4.3.7如果映射有逆映射，則，。證明因?yàn)槭请p射，所以也是雙射。由定理4.3.2知，和都是雙射。任取，若，，則所以，；。定理4.3.8若是雙射，則證明因是雙射，也是雙射，因此，是雙射可編輯可編輯精品精品可編輯精品。由于dom=dom且所以，。定理4.3.9若，均為雙射，則。證明（1）因，均為雙射，故和均存在，且，均為雙射，所以，為雙射。根據(jù)定理4.3.2，是雙射，故是雙射dom=dom（2）對(duì)任意存在唯一，使得存在唯一，使得故又故因此，對(duì)任一有：由（1）、（2）可知。例4.3.5設(shè)，若有，，其中，，求和。解，，可編輯可編輯精品精品可編輯精品可見，習(xí)題4.3證明或反駁下列命題：設(shè)，為任一映射，則，其中，，。是雙射，當(dāng)且僅當(dāng)對(duì)中任兩個(gè)子集與，若，則。設(shè)，均為有限集且，則下列命題等價(jià)：①是單射；②是滿射；③是可逆的。2．設(shè)為，其中為實(shí)數(shù)集，試求。3．證明從到存在單射，并說明此映射是否為滿射。4．設(shè)。試定義映射使且是單射。求。能否找到另一的單射，有？試定義一個(gè)映射使且。試定義一個(gè)映射使且。5．求下列各映射的逆映射：；；；可編輯可編輯精品精品可編輯精品.6．如果為且為；為；為試求，，，，，。7．設(shè)，為任意兩個(gè)映射，證明如果不是滿射，則也不是滿射。如果不是單射，則也不是單射。如果為滿射，，則。 4.4置換定義4.4.1設(shè)，雙射稱為集合的置換(Permutation)，記作這里，中元素的個(gè)數(shù)稱作置換的階。定理4.4.1在個(gè)元素的集合中，不同的階置換的總數(shù)為！個(gè)。證明形如：中的可以取的任意一個(gè)全排列，故總數(shù)為！個(gè)。定義4.4.2給定，恒等映射稱為集合上的恒等置換(IdenticalPermutation)，記作可編輯可編輯精品精品可編輯精品定義4.4.3設(shè)是集合的置換，如果可以取到的元素，使，且的其余元素（如果還有的話）不變，則稱為一個(gè)輪換，記為。若，則的個(gè)置換都是輪換，它們分別記為和。當(dāng)時(shí)，置換不是輪換。一般地，時(shí)，的置換都是輪換；時(shí)，的置換未必是輪換。定義4.4.4把置換看作定義在集合上的雙射，置換的復(fù)合定義為相應(yīng)映射復(fù)合構(gòu)成的置換。例如，，則，可見，。兩個(gè)輪換與的復(fù)合記為：。定義4.4.5給定，對(duì)任意的階置換記容易驗(yàn)證可編輯可編輯精品精品可編輯精品我們稱為的逆置換。集合上的所有階置換的全體記作。置換的復(fù)合有以下性質(zhì)：（1）對(duì)于復(fù)合運(yùn)算是封閉的；（2）結(jié)合律成立，即，有；（3）中有一個(gè)元素稱為恒等置換，使對(duì)任意有；（4）任意，都存在有逆置換，使。習(xí)題4.41．若，試寫出上的全部置換，并指出各置換的逆。2．設(shè)，是上的置換，，，，求，，，，，及。3．已知，，，請(qǐng)驗(yàn)證：。4．設(shè)，計(jì)算。5．設(shè)，上的置換，。求（1）；（2）。*4.5特征函數(shù)有些映射與集合之間可以建立一些特殊的關(guān)系，借助于這些映射，可對(duì)集合進(jìn)行運(yùn)算。定義4.5.1令是全集，，由可編輯可編輯精品精品可編輯精品定義的映射，稱為集合的特征函數(shù)(Eigen-function)。定理4.5.1給定全集，且，，對(duì)于所有，特征函數(shù)有如下一些性質(zhì)。（1）（2）（3）（4）（5）（6）（7）（8）證明：（1）、（2）、（7）顯然。（3）若，則對(duì)，當(dāng)時(shí)，必有，即，，可見，；當(dāng)時(shí)，則，故也有。若，即時(shí)，，亦即時(shí)必有，所以，。（4）若，即且。由（3）得且，所以，。若，則時(shí)，，即時(shí)必有，故；時(shí)，，即時(shí)必有，則時(shí)必有，即。所以，。（5）且所以可編輯可編輯精品精品可編輯精品（6），有以下三種可能：1)且，則，，，，所以，；2)且，則，，，，所以，；3)且，則，，，，所以，。，則，，，所以，。綜上所述，。（8）由于，則應(yīng)用特征函數(shù)的一些性質(zhì)，也可以證明一些集合恒等式。例4.5.1試證明：（1）（2）證明（1）因?yàn)?，所以，。?）可編輯可編輯精品精品可編輯精品所以，。例4.5.2設(shè)，的子集是：和，試給出的所有子集的特征函數(shù)且建立特征函數(shù)與二進(jìn)制之間的對(duì)應(yīng)關(guān)系。解：的任何子集的特征函數(shù)的值由表4-1列出。表4-1的任何子集的特征函數(shù)的值000100010001110101011111如果規(guī)定元素的次序?yàn)?，則每個(gè)子集的特征函數(shù)與一個(gè)三位二進(jìn)制數(shù)相對(duì)應(yīng)。如。令，那么表4-1亦可看作從的冪集到的一個(gè)雙射。習(xí)題4.51．設(shè)，其中是全集的子集，試用特征函數(shù)來表示。2．利用特征函數(shù)的性質(zhì)證明下列等式。(1)(2)(3)(4)*4.6基數(shù)4.6.1無限集合定義4.6.1如果有一個(gè)從集合到的雙射函數(shù)，那么稱集合是有限的，并稱為的計(jì)數(shù)(Counting)（中元素的個(gè)數(shù)），規(guī)定空集的計(jì)數(shù)為；如果集合可編輯可編輯精品精品可編輯精品不是有限的，則它是無限的。使用定義4.6.1證明集合是無限集，就要證明對(duì)任意，在與之間都不會(huì)建立雙射。這種排除無數(shù)可能再確立結(jié)論的推論方法，其困難是固有的。一個(gè)切實(shí)有效的克服困難的選擇是：定義4.6.2稱集合是無限集，當(dāng)且僅當(dāng)存在到自身的單射，使得。如果不是無限集，則稱它是有限集。定理4.6.1自然數(shù)集合證明存在單射，，并且，。所以，是無限集。定理4.6.2證明若集合的子集是無限集合，則存在上的單射，使得。擴(kuò)充到上記為，滿足：若，則；若，則。顯然，是上的單射，且。所以，是無限集。子集是無限集合的集合是無限集，其逆否命題是：有限集合的子集都是有限集合。定理4.6.3設(shè)是任意兩個(gè)集合且是無限集，則：若從到存在單射，則也是無限集；的冪集是無限集；是無限集；若，則是無限集；證明僅證（1），其余都是（1）的推論。是無限集，存在單射，使得。是從到的單射，，是從到的雙射，存在逆映射。定義映射，滿足：若，則；，則。由于都是單射，所以是上的單射，且所以，是無限集。4.6.2基數(shù)的概念兩個(gè)集合，如果它們都是有限集，其中元素哪個(gè)多哪個(gè)少是很容易知道的，只要比較可編輯可編輯精品精品可編輯精品有限集的計(jì)數(shù)即可。但是，如果兩個(gè)集合都是無限集，怎樣比較它們的元素哪個(gè)多哪個(gè)少呢？例如，自然數(shù)集，正偶數(shù)集，整數(shù)集，實(shí)數(shù)集。設(shè)與是兩個(gè)集合，若中元素和中元素可以一一對(duì)應(yīng)，即存在到的一個(gè)雙射，這意味著的元素個(gè)數(shù)和B的元素個(gè)數(shù)一樣多。但這句話很不確切，因?yàn)樵跓o限集的情形下，談不上其中元素個(gè)數(shù)是多少。在集合論中，若集合中元素和中元素可以一一對(duì)應(yīng)，我們不說它們的元素個(gè)數(shù)相等，而說它們有相同的勢(shì)。定義4.6.3對(duì)于集合與，如果存在著從到的雙射，則稱與為等勢(shì)的(Equivalent)，或稱與對(duì)等(Equipollent)，記作。例4.6.1驗(yàn)證自然數(shù)集與非負(fù)偶數(shù)集合是等勢(shì)的。證明與的元素之間可做雙射，即，所以，與等勢(shì)。例4.6.2設(shè)為實(shí)數(shù)集合，是的子集，即，且證明：證明令，顯然的值域是，是雙射函數(shù)，所以。定理4.6.4集合族上等勢(shì)關(guān)系是一個(gè)等價(jià)關(guān)系。證明設(shè)集合族為（1）對(duì)任意，恒等映射是到的雙射，所以；（2）對(duì)任意，如果，則存在到的雙射，從而為到的雙射，故；（3）對(duì)任意，如果且，則存在到的雙射和到的雙射，由定理4.3.2知是到的雙射，故。綜合（1）、（2）和（3）知集合族上的等勢(shì)關(guān)系是一個(gè)等價(jià)關(guān)系。顯然，兩個(gè)有限集對(duì)等，當(dāng)且僅當(dāng)它們的計(jì)數(shù)相等。即根據(jù)計(jì)數(shù)是否相等就能判斷兩個(gè)有限集是否對(duì)等。很自然，我們希望將有限集的計(jì)數(shù)這個(gè)概念推廣到無限集。定義4.6.4我們將相互對(duì)等的集合歸為同一類，不對(duì)等的集合不屬于同一類，對(duì)每類集合予以一個(gè)記號(hào)，稱這個(gè)記號(hào)是這一類集合中每個(gè)集合的基數(shù)(CardinalNumber)（勢(shì)，濃度，權(quán)）。集合的基數(shù)記為?？删庉嬁删庉嬀肪房删庉嬀范x4.6.5設(shè)、是兩個(gè)集合。如果，就稱與的基數(shù)相同，記作；如果存在從到的入射，就稱的基數(shù)小于等于的基數(shù)，記作；如果且，就稱的基數(shù)小于的基數(shù)，記作。例4.6.3證明區(qū)間與基數(shù)相同。證明設(shè)集合，。定義使得則是雙射，故區(qū)間與基數(shù)相同。4.6.定義4.6.6我們稱自然數(shù)集的基數(shù)為，稱為可列基數(shù)(CountableCardinalNumber)。凡與自然數(shù)集對(duì)等的任意集合稱為可列集（或可數(shù)集）(CountableSet)。例如，，均為可數(shù)集。定義4.6.7如果集合是有限的或無限可數(shù)的，則統(tǒng)稱為至多可數(shù)的。如果集合是無限的且是不可數(shù)的，則稱是不可數(shù)的(Non-countable)。定理4.6.5的形式。證明若可排成上述形式，那么將的元素與腳標(biāo)對(duì)應(yīng)，就得到與之間的雙射，故是可數(shù)集。反之，若為可數(shù)集，那么在與之間存在一個(gè)雙射，由得