相關(guān)系的一些基本性質(zhì)

相關(guān)系可以看作是許多代際系統(tǒng)的系統(tǒng)，例如從域中線性空間和周期中的共同抽象。它在代數(shù)學(xué)、組合研究和理論計算機科學(xué)等方面得到了廣泛的應(yīng)用。在這項工作中，我們主要討論了相關(guān)系（尤其是傳遞相關(guān)系）的幾個基本性質(zhì)。這些性質(zhì)被郭玉琦教授和岑嘉贊教授在文獻中描述的有限維線性空間的病理方法推廣到相關(guān)系中。有關(guān)相關(guān)系的系統(tǒng)討論，可以添加。1線性相關(guān)系定義1.1設(shè)S是一個集合,D?2S.稱D為S上的一個相關(guān)系,或稱(S,D)構(gòu)成一個相關(guān)系,若對于任意X?S,X∈D當(dāng)且僅當(dāng)X含有一個有限非空子集X′使得X′∈D.D中的元素稱為D-相關(guān)子集,簡稱相關(guān)子集,S中的其他子集稱為D-無關(guān)子集,簡稱無關(guān)子集.注意,S中可以沒有相關(guān)子集(即D可以為空),但由定義S一定存在無關(guān)子集,空集?總是任何相關(guān)系中的無關(guān)子集.例1.2設(shè)V是一個線性空間,L為V中所有線性相關(guān)的子集組成的集合.則顯然L為V上的一個相關(guān)系,稱為V上的線性相關(guān)系.例1.3設(shè)A*為字母表A上的自由幺半群,DC為A*中所有非自由子幺半群的生成元集組成的集合.則DC為A*上的一個相關(guān)系,稱為自然相關(guān)系或碼相關(guān)系.A*中的DC無關(guān)子集稱為A上的碼.定義1.4設(shè)D是S上的一個相關(guān)系,X?S,x∈S.若x∈X或者存在無關(guān)子集X′?X使得X′∪{x}為相關(guān)子集,則稱x相關(guān)于X.記所有與X相關(guān)的元素組成的集合為〈X〉,稱為X的閉包.滿足〈X〉=X的子集X稱為S中的閉集.由后面的例子(例2.3或2.5)可知,上述的閉包概念并不滿足通常意義下閉包公理中的傳遞性,即〈〈X〉〉=〈X〉不一定成立.因此有如下定義:定義1.5稱S上的一個相關(guān)系D為一個傳遞相關(guān)系,如果對于任意X?S,〈〈X〉〉=〈X〉.以下定理說明傳遞相關(guān)系與某種特殊的代數(shù)閉包算子有一一對應(yīng)關(guān)系.定理1.6設(shè)D是S上的一個傳遞相關(guān)系.則由D誘導(dǎo)出的算子clD∶X〈X〉是一個滿足以下替換性質(zhì)(?X?S,y,z∈S)y?〈X〉ue84aSymbolYCpy∈〈X∪{z}〉?z∈〈X∪{y}〉(1)的代數(shù)閉包算子.反之,設(shè)cl∶2S→2S是S上的一個滿足替換性質(zhì)(?X?S,y,z∈S)y?cl(X)ue84aSymbolYCpy∈cl(X∪{z})?z∈cl(X∪{y})(2)的代數(shù)閉包算子,則存在S上的相關(guān)系D使得對于任意X?S,cl(X)=〈X〉.在線性相關(guān)系(V,L)中,〈X〉即為X生成的子空間.定義1.7設(shè)(S,D)是一個相關(guān)系,S′?S.則顯然(S′,D∩2S)也是一個相關(guān)系,稱為(S,D)的一個子系.2x是zr-pcs的一個無關(guān)集定義2.1設(shè)(S,D)是一個相關(guān)系,X?S.若〈X〉=S,則稱X為S的一個生成元集.S的無關(guān)生成元集稱為基.命題2.2設(shè)(S,D)為一個相關(guān)系,X?S.則在以下兩個條件等價:(1)X是S的基;(2)X是S的極大無關(guān)集;且它們都蘊涵以下條件:(3)X是S的極小生成元集.另外,若此相關(guān)系是傳遞的,則以上三個條件等價.證明(1)?(2).若X是S的一個基,則X是無關(guān)集.下面證明其極大性.對于任意x∈S\X,由X是S的生成元集可知,x∈〈X〉.從而X∪{x}是相關(guān)集.這說明X是S的一個極大無關(guān)集.(2)?(1).若X是S的一個極大無關(guān)集,則對于任意x∈S\X,X∪{x}是相關(guān)集.從而有x∈〈X〉.因此〈X〉=S,從而X是S的一個無關(guān)生成元集(即基).(1)?(3).若X是S的一個基,則X是S的生成元集.下面證明其極小性.對于任意x∈X,由X是無關(guān)集可知,x?〈X\{x}〉.從而X\{x}不是S的生成元集.這說明X是S的極小生成元集.關(guān)于傳遞相關(guān)系的情形,我們只需再證明(3)?(1)即可.若X是S的一個極小生成元集,下面證明X是無關(guān)集.假設(shè)X是相關(guān)集,則存在x∈X使得x∈〈X\{x}〉.從而有:S=〈X〉=〈x∪X\{x}〉?〈〈X\{x}〉〉=〈X\{x}〉.因此X\{x}是S的一個生成元集.這與X是S的極小生成元集矛盾.所以,X是S的一個無關(guān)生成元集(即基).一般說來,在非傳遞相關(guān)系中,上述命題中的條件(3)推不出條件(1),(2).設(shè)X?2S.記:U(X)={X?S|(?X′?X)X′∈X}.例2.3設(shè)S={1,2,3},D=U({1}).則〈?〉={1},〈1〉=S.從而D不是傳遞的.在S中,{1}和{2,3}都是S的極小生成元集,其中{1}是相關(guān)的,{2,3}是無關(guān)的.由Zorn引理不難得到如下定理,它反映了基的存在性.定理2.4任何無關(guān)子集都包含于一個極大無關(guān)集中.在一般的相關(guān)系中,雖然基總是存在的,但是各個基的大小卻可能并不相同.例2.5設(shè)S={1,2,3,4},D=U({1},{2,3},{2,4}).則〈?〉={1},〈1〉=S.從而D不是傳遞的.在S中,{2}和{3,4}是S中大小不同的兩個基.定義2.6若相關(guān)系(S,D)中任何基都是等勢集,則稱此相關(guān)系為可定義維數(shù)的,而稱其任一基的勢為此相關(guān)系的維數(shù).定理2.7傳遞相關(guān)系都是可定義維數(shù)的.注意,由例2.3可知,上述定理的逆是不成立的.3tm的線性變換定義3.1設(shè)(S,D)是一個相關(guān)系,S′?S.若存在X?S使得S′=〈X〉,則稱子系(S′,D∩2S′)為[由X生成的]子空間.在不引起混淆的時候,我們也常稱S′為S的子空間.注3.2顯然,閉集一定是子空間,但子空間未必是閉的.例如,在例2.3中,{1}是一個由空集生成的子空間,但不是閉集.若上述定義中的相關(guān)系是傳遞的,則S′是S的子空間當(dāng)且僅當(dāng)它是閉的.定義3.3設(shè)(S,D)是一個相關(guān)系,X?S,n∈?.若X的任意n元子集都是無關(guān)子集,則稱X為S的n-無關(guān)子集.郭聿琦和岑嘉評在文獻中給出了有限維線性空間中與子空間、向量的線性相關(guān)性、線性變換等有關(guān)的若干命題的等價性:定理3.4設(shè)V是某個域上的n維線性空間.則以下條件等價.(1)對于任意s∈?,若Vi是V的真子空間,i=1,2,…,s,則s∪i=1Vi/?V(即V的有限個真子空間不能覆蓋整個空間V).(2)對于任意s∈?,若{αi1,αi2,…,αir}是V的線性無關(guān)子集,1≤r≤n-1,i=1,2,…,s,則存在α∈V\s∪i=1{αi1,αi2,?,αir}使得{α,αi1,αi2,…,αir}仍線性無關(guān).(3)V中存在無限n-無關(guān)子集.(4)對于任意s∈?,若Ti是V上兩兩不同的線性變換,i=1,2,…,s,則存在α∈V,使得對于任意i,j=1,2,…,s,i≠j,有Ti(α)≠Tj(α).(5)將(4)中的“線性變換”改為“秩為n的線性變換”.(6)將(4)中的“線性變換”改為“秩為1的線性變換”.定理3.5設(shè)(S,D)是一個n維傳遞相關(guān)系.則以下條件等價.(1)對于任意s∈?,若Si是S的真子空間,i=1,2,…,s,則s∪i=1Si/?S(即S的有限個真子空間不能覆蓋整個空間S).(2)對于任意s∈?,若{αi1,αi2,…,αir}是S的無關(guān)子集,1≤r≤n-1,i=1,2,…,s,則存在α∈S\s∪i=1{αi1,αi2,?,αir}使得{α,αi1,αi2,…,αir}仍無關(guān).(3)S中存在無限n-無關(guān)子集.證明(1)?(2).設(shè)Si=〈αi1,αi2,…,αir〉,i=1,2,…,s.若某個Si=S,則{αi1,αi2,…,αir}是S的無關(guān)生成元集,即S的基.而r≤n-1,這與S的維數(shù)為n矛盾.因此Si≠S,即Si是S的真子空間,i=1,2,…,s.由(1),s∪i=1Si/?S,即存在α∈S\s∪i=1Si.因α?Si,由定義1.4,{α,αi1,αi2,…,αir}是無關(guān)子集.(2)?(3).以下用歸納法定義集合Tm,m≥n,使得Tm是S的一個含有m個元素的n-無關(guān)子集.首先,因為S是n維的,設(shè)Tn={α1,α2,…,αn}是S的一個基,則顯然Tn是S的一個含有n個元素的n-無關(guān)子集.假設(shè)Tm已經(jīng)定義好,以下定義Tm+1.因為Tm是n-無關(guān)的,從而也是n-1-無關(guān)的,即Tm的所有n-1元子集都是無關(guān)的.Tm共有s=Cn-1m個n-1元子集,設(shè)為Tm,1,Tm,2,…,Tm,s.則由(2),存在α∈S\s∪i=1Τm,i使得{α}∪Τm?i為無關(guān)子集,i=1,2,…,s.注意到這樣選取的α?Tm,且易見Tm∪{α}仍是S的一個n-無關(guān)子集.從而Tm+1=Tm∪{α}是S的一個含有m+1個元素的n-無關(guān)子集.令Τ=∞∪m=nΤm.則顯然T為S的一個無限子集.以下證明T為S的n-無關(guān)子集.設(shè){β1,β2,…,βn}為T的任意一個n-元子集.由T的定義,存在Ti使得βi∈Tmi,i=1,2,…,n.注意到,由各個Ti的構(gòu)造有Tn?Tn+1?….令m=max{m1,m2,…,mn},則有β1,β2,…,βn∈Tm.因Tm是S的n無關(guān)子集,故{β1,β2,…,βn}是S的無關(guān)子集.這樣即證明了T為S的n-無關(guān)子集.(3)?(1).設(shè)Si是S的真子空間,i=1,2,…,s.由(3),存在S的無限n-無關(guān)子集T.以下證明對于任意i,|Si∩T|<n.如若不然,則存在i以及兩兩不同的α1,α2,…,αn∈Si∩T.因為T是n-無關(guān)子集,所以{α1,α2,…,αn}為S的無關(guān)子集.又因S的維數(shù)是n,由定理2.4,定義2.6和命題2.2可知,{α1,α2,…,αn}為S的一個基.由定義2.1,{α1,α2,…,αn}生成S.從而有S=〈α1,α2,…,αn〉?〈Si〉=Si?S,即Si=S,這