これは、関連する半順序を完全に説明する便利なツールです。したがって、順序図とも呼ばれます。集合 A 上の関係の有向グラフを同等のハッセ図に変換するのは非常に簡単です。したがって、ハッセ図を描くときは次の点に注意する必要があります。
- ハッセ図の頂点は、円ではなく点で表されます。
- 半順序は再帰的であるため、A の各頂点はそれ自体に関連している必要があるため、頂点からそれ自体までの辺はハッセ図では削除されます。
- 半順序は推移的であるため、aRb、bRc の場合は常に aRc が存在します。ハッセ図の推移的特性によって暗示されるすべてのエッジを削除します。つまり、a から c までのエッジを削除しますが、他の 2 つのエッジは保持します。
- 頂点「a」がエッジ、つまり aRb によって頂点「b」に接続されている場合、頂点「b」は頂点「a」の上に表示されます。したがって、ハッセ図の辺から矢印が省略される場合があります。
ハッセ図は半順序の有向グラフよりもはるかに単純です。
例： 集合 A = {4, 5, 6, 7} について考えてみましょう。 R を A 上の関係 ≦ とします。R の有向グラフとハッセ図を描きます。
解決： 集合 A 上の関係 ≦ は次のように与えられます。
R = {{4, 5}、{4, 6}、{4, 7}、{5, 6}、{5, 7}、{6, 7}、{4, 4}、{5, 5} 、{6、6}、{7、7}}
関係 R の有向グラフは図に示すとおりです。
半順序のハッセ図を描画するには、次の点を適用します。
- 再帰的プロパティによって暗示されるすべてのエッジを削除します。
(4, 4)、(5, 5)、(6, 6)、(7, 7) - 推移的なプロパティによって暗示されるすべてのエッジを削除します。
(4, 7)、(5, 7)、(4, 6) - 頂点を表す円をドットに置き換えます。
- 矢印は省略します。
ハッセ図は図に示すとおりです。
上界： B が部分的に順序付けられた集合 A の部分集合であるとします。すべての y ∈ B について y ≦ x である場合、要素 x ∈ A は B の上限と呼ばれます。
下限: B が部分的に順序付けられた集合 A の部分集合であるとします。すべての x ∈ B について z ≦ x である場合、要素 z ∈ A は B の下限と呼ばれます。
例： 図に示すように、ポセット A = {a, b, c, d, e, f, g} が順序付けされると考えてください。また、B = {c, d, e} とします。 B の上限と下限を決定します。
解決： B のすべての要素が '≦' e、f、および g であるため、B の上限は e、f、および g です。
a と b は B のすべての要素 '≦' であるため、B の下限は a と b になります。
最小上限 (SUPREMUM):
A を部分順序集合 S の部分集合とします。S の要素 M は、M が A のすべての要素に続く場合、つまり A のすべての x に対して x がある場合、A の上限と呼ばれます。<=m< p>
A の上限が A の他のすべての上限に先行する場合、それは A の上限と呼ばれ、Sup (A) で表されます。
最大下限 (INFIMUM):
ポセット S の要素 m は、m が A のすべての要素に先行する場合、つまり A のすべての y に対して m がある場合、S のサブセット A の下限と呼ばれます。<=y < p>
A の下限が A の他のすべての下限に続く場合、それは A の下限と呼ばれ、Inf (A) で表されます。
例： 図にハッセ図が示されているポセットの B = {a, b, c} の最小上限と最大下限を決定します (存在する場合)。
解決： 最小上限は c です。
最大の下限は k です。