順序関係 – 定義

導入

セット内の順序関係は、このセット内の二項関係であり、これにより、その要素を一貫した方法で相互に比較できます。順序関係を持つセットは、順序付きセット、または単純に順序です。

定義と例

順序関係

順序関係は、再帰的、推移的、および反対称の二項関係です。 E を集合とし、この集合上の二項関係を「≤」で示します。この関係は、 Eのすべてのx 、 y 、 z要素について次の場合に順序関係になります。

• x ≤ x (反射率)
• ( x ≤ yおよびy ≤ x ) ⇒ x = y (反対称)
• ( x ≤ yおよびy ≤ z ) ⇒ x ≤ z (推移性)

これらの公理は、まさにその形式によって、次のように定義される逆関係または逆関係 ≥ によって検証されます。

x ≥ yは、 y ≤ xの場合に限ります。

したがって、任意の順序関係は、同じセット上の相互順序関係 (小さいか等しい、大きいか等しい、小さいか等しい、大きいか等しいなど) に関連付けられます。また、任意の順序関係 ≤、then < で示されるいわゆる厳密な順序関係 (再帰性が満たされていないため、厳密に言えば順序関係ではありません) とも関連付けられます。これは、順序関係が別個の要素のペアに制限されるものです。

x < y は、 x ≤ yおよびx ≠ yの場合に限ります。

上記の定義の意味での順序関係は、大まかな順序と呼ばれることもあります。

特定の順序関係では、 Eの 2 つの要素は常に比較可能です。つまり、 Eのすべてのx 、 yについてです。

x ≤ yまたはy ≤ x 。

次に、順序関係はtotalであり、集合E はこの関係によって完全に順序付けされていると言います。 E上の順序関係は、完全でない場合に部分的であると言われ、 Eは部分的に順序付けされます。英語では、部分順序は任意の順序を表すため、合計順序になる可能性があることに注意してください。この用語はフランス語でも使用されることがあります。

オーダーセット

順序集合とは、順序関係を持つ集合です。順序集合が有限の場合、通常の紙上のグラフ表現と同様に、ハッセ図の形でグラフィカルに表現できるため、作業が容易になります。無限大の場合、ハッセ図の一部を描画できます。

例と反例

• 「以下である」という関係は、整数のセット (自然または相対)、有理数のセット、または実数のセットにおける全順序の関係です。

• たとえば自然数の集合における「厳密に小さい」という関係は、再帰的ではないため、順序関係ではありません (厳密な順序関係は決して広範な順序ではありません)。

• 「のサブセットである」または「〜に含まれる」という包含関係は、集合の一部の集合に対する半順序関係です。与えられたセットが有限であれば、その部分のセットも有限です（より正確には、
  $$ {\#A=n} $$
  、 我々は持っています
  $$ {\#P(A)=2^n} $$
  ）。以下の図は、3 つの要素からなる集合のハッセ図を表しています。

• 割り算関係は、自然整数では半順序関係ですが、相対整数では順序関係ではありません。1 は -1 を割り、-1 は 1 を割ります。以下の図は、割り算関係のハッセ図を表しています。 0 から 9 までの整数の間。

• のすべての機能
  $$ {\mathbb R} $$
  で
  $$ {\mathbb R} $$
  、順序関係f < gが指定された場合
  $$ {\forall x, f(x) < g(x)} $$
  、無限順序集合です。直観的には、その関数の曲線が常に他の曲線よりも下にある場合、その関数は別の関数よりも小さくなります。この例を順序集合P内の集合Xの関数に一般化できます。

• 特定のセットのパーティションのセットは、パーティションの細分化によって与えられる順序関係によって部分的に順序付けされます。定義上、パーティションが他の部分をより小さな部分に分割する場合、そのパーティションは他のパーティションよりも細かくなります。

• 2 つの順序集合EおよびFが与えられた場合、次数を定義する自然な方法が少なくとも 2 つあります。 $$ {E\times F} $$