被覆関係

順序付け内の数学的関係

包含によって部分的に順序付けられた3 つの要素の冪集合のハッセ図。

数学、特に順序理論において、半順序集合の被覆関係とは、隣接する比較可能な要素間に成立する二項関係である。被覆関係は、ハッセ図を用いて半順序をグラフで表現するためによく用いられる。

意味

を半順序 を持つ集合とします。通常通り、がおよび のときのみ成り立つ関係であるとします。 ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle <}$ ${\displaystyle X}$ ${\displaystyle x<y}$ ${\displaystyle x\leq y}$ ${\displaystyle x\neq y}$

およびを の要素とします。 ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$

すると、 （ と表記）であり、 となる元が存在しない場合に、は をカバーします。同様に、区間が2元集合 である場合、は をカバーします。より直感的に言えば、がそれぞれの poset の順序関係において に直接的に取って代わる、または に続く場合です。 ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x\lessdot y}$ ${\displaystyle x<y}$ ${\displaystyle z}$ ${\displaystyle x<z<y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle [x,y]}$ ${\displaystyle \{x,y\}}$ ${\displaystyle x\lessdot y}$ ${\displaystyle y}$ ${\displaystyle x}$

のとき、は の被覆であるといわれる。また、被覆関係にあるそのようなペアを表すために「被覆」という用語を使用する著者もいる。 ${\displaystyle x\lessdot y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle (x,y)}$

例

• 有限の線型順序集合において、は との間のすべての を覆い、他の被覆関係は存在しません。 ${\displaystyle \{1,2,...,n\}}$ ${\displaystyle i+1}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle n-1}$
• 集合Sのべき集合のブール代数において、 Sの部分集合BがSの部分集合Aを覆うのは、 Aにない 1 つの要素を追加することによってBが得られる場合のみである。
• すべての非負整数の分割によって形成されるヤングの格子では、分割λ が分割μをカバーするのは、 λのヤング図がμのヤング図から追加のセルを追加することによって得られる場合のみです。
• タマリ格子の被覆関係を表すハッセ図は、連想面体の骨格です。
• 任意の有限分配格子の被覆関係は中央値グラフを形成します。
• 通常の全体順序 ≤ を持つ実数では、ある数が他の数を覆うことはありません。

プロパティ

• 半順序集合が有限である場合、その被覆関係は半順序関係の推移的縮約となる。したがって、そのような半順序集合はハッセ図によって完全に記述される。一方、標準順序を持つ有理数のような稠密順序においては、どの元も他の元を被覆しない。

参考文献

• Knuth, Donald E. (2006)、『The Art of Computer Programming』、第4巻、Fascicle 4、Addison-Wesley、ISBN 0-321-33570-8。
• スタンリー、リチャード・P.（1997）、列挙的組合せ論、第1巻（第2版）、ケンブリッジ大学出版局、ISBN 0-521-55309-1。
• ブライアン・A・デイヴィー、ヒラリー・アン・プリーストリー（2002年）、格子と秩序入門（第2版）、ケンブリッジ大学出版局、ISBN 0-521-78451-4、LCCN  2001043910。

「https://en.wikipedia.org/w/index.php?title=Covering_relation&oldid=1298010519」より取得