基交換公理

擬陣的基公理是刻畫擬陣的一種法則，有限集E的某些子集構成的集族B滿足如下條件：1.B非空；2.B中的元素之間均不具有集合的包容關係；3.B₁，B₂為B中的元素，且e₁∈B₁，則在B₂中有元素e₂，使得(B₁-{e₁})∪{e₂}為B中的元素。這幾個條件即為基公理，由它決定的集族B，其元素即為擬陣的基。因此，基公理是刻畫擬陣的又一等價形式。條件2表明B是一條反鏈，而條件3稱為基交換公理(basis exchange axiom)，它和線性空間理論中的基交換定理是一致的，基交換公理可以等價敘述為如下的中間基公理：對於E的任意子集X，Y，且X⊆Y，若在B中有元素B₁，B₂，使得X⊆B₁，B₂⊆Y，則在B中有元素B₃存在，使得X⊆B₃⊆Y。

基本介紹

• 中文名：基交換公理
• 外文名：basis exchange axiom
• 所屬學科：數學
• 所屬問題：離散數學（組合序）
• 簡介：刻畫擬陣的一種法則

基本介紹

沿用線性代數中的術語，我們稱擬陣M中的極大獨立子集為M的基(base)。記(M)為M中全體基的集合。則 (M)=Max()。若E是某個有限維線性空間V(n，F)的子集，則E中任意兩個極大線性無關子集含有相同個數的元素；若B是E中一個極大線性無關子集，且x∈E-B，則B∪x含有唯一的一個極小線性相關子集。擬陣的基也有同樣的性質。

定理1設B是擬陣M的一個基，且x∈E-B，則B∪x含有一個唯一的極小圈C。 (我們稱B∪x中這個唯一的極小圈C為元素x對應於基B的基本極小圈(fundamental circuit of x with respect to B)，記作C_M(x，B)或C(x，B)。)

定理2 設M(E，)是個擬陣，令=(M)，則有如下性質：

(B1)至少含有一個元素(即M有至少一個基)。

(B2) 若B₁，B₂∈且x∈B₁-B₂，則必有y∈B₂-B₁使得(B₁-x)∪y∈B。

(B1)和(B2)叫做擬陣的基公理，(B2) 為基交換公理。

相關定理

定理3 設E是個非空集，又設⊆2^E滿足條件(B2)，則

(B3) 若B₁，B₂∈ ，則|B₁|=|B₂|。

證明 用反證法。設有B₁，B₂∈(M)並設|B₁|<|B₂|。在這些使(B3)不成立的子集對中，取反例B₁，B₂，滿足|B₂|>|B₁|，並且|B₁∩B₂|儘可能大。

由於|B₂|>|B₁|，可取x∈B₂-B₁。據(B2)，恆有y∈B₁-B₂使B₃=(B₂∪y)-x∈B。於是從及可知， ，且。

因而 ，據B₁，B₂的選取，B₁，B₃不能是反例子集對，故有

這與B₁，B₂是個反例子集對的假設矛盾，因而(B3)得證。

定理2中的條件(B2)也可以有下列的形式。

定理4 設M是個擬陣，則(M)滿足下面的條件。

(B2)' 若B₁，B₂∈(M)且x∈B₁-B₂，則必有y∈B₂-B₁，使得(B₂-y)∪x∈。

擬陣的基完全由條件(B1)和(B2)所決定，像擬陣的獨立集和極小圈一樣，擬陣的基也唯一地確定了所在的擬陣，故(B1)和(B2)叫做擬陣的基公理。

定理5 設E是個非空集，又設 ⊆2^E滿足條件(B1)和(B2)，則存在擬陣M(E， )，滿足=(M)。

證明 若有這樣的擬陣M存在，使(M)=，則(M)中的元素一定是中某個成員的子集。