[科普中國(guó)]-全序集

定義

設(shè)R為非空集合A上的偏序關(guān)系，如果任意的 ，都有 或 ，則稱R為A上的全序關(guān)系(或線序關(guān)系)，且 構(gòu)成一個(gè)全序集或鏈。

由定義可以知道，全序集的哈斯圖是一條直線段2。

任一偏序集，若任意且S中存在最小元，則稱為良序集。

若兩個(gè)全序集的元素相同，并且序關(guān)系也相同，則稱這兩個(gè)全序集是相同的，即當(dāng)用列舉法表示全序集時(shí)，通常規(guī)定從左到右表示元素的順序。例如,設(shè)N為自然數(shù)集,關(guān)系“≤”為平常的數(shù)的小于或等于關(guān)系，則全序集表示為；若序關(guān)系“”定義為

則全序集表示為。1

良序集與全序集定理1每一個(gè)良序集一定是全序集2。

注意：全序集不一定是良序集。

證明： 設(shè) 是良序集，則對(duì)于任意的 構(gòu)成的子集一定存在最小元，該最小元不是a就是b，因此一定滿足 或 ，所以 是全序集。

定理2任一個(gè)有限的全序集一定是良序集。

證明：設(shè) 是任一有限全序集， 為任一非空子集，則B也是全序集。設(shè)B中有n個(gè)元素，將B中的元素依次進(jìn)行比較，找出最小的那個(gè)元素，則最多進(jìn)行 次比較，即 可找出最小元，因此是良序。

例題解析例1 給定 上的包含關(guān)系 ，則 構(gòu)成全序集。2

例2 給定自然數(shù)集N上的小于等于(≤)關(guān)系，則 構(gòu)成全序集。

例3 給定自然數(shù)集N上的小于等于(≤)關(guān)系，則 是良序集合。

例4 給定整數(shù)集Z上的小于等于(≤)關(guān)系，則 構(gòu)成全序集。但因?yàn)樵谡麛?shù)集上不存在最小元，所以該偏序集不是良序集。

常見(jiàn)全序集1、 自然數(shù)集 、有理數(shù)集 、實(shí)數(shù)集 在通常的大小序下是全序的。

2、 有限長(zhǎng)度的序列按字典序是全序的。最常見(jiàn)的是單詞在字典中是全序的。

3、 任何良序集是全序的。

4、 自然數(shù)的子集按集合包含關(guān)系是一個(gè)偏序，但不是全序的，即 不是全序的。因?yàn)?img src="https://img-xml.kepuchina.cn/images/newsWire/6SyMz7oxQpW7otjW2Do7JNlqVz6dqIgMJ8bv.jpg" alt="" /> 與 是不可比較的。