Loading article…
数学において、ユークリッド関係は、ユークリッドの『原論』の「公理 1」である「同じ大きさのものは互いに等しい」 を形式化した二項関係の一種です。
意味
集合X上の二項関係 Rがユークリッド関係（右ユークリッド関係と呼ばれることもある）であるとは、次の条件を満たす場合である。X内のすべてのa、b、cについて、 aがbおよびcと関連している場合、b はcと関連している。[1]これを述語論理で書くと次のようになる。
双対的に、 X上の関係Rが左ユークリッドであるとは、 X内の任意のa、b、cに対して、 b がaに関連し、c がaに関連している場合、 bがcに関連している場合である。
プロパティ
- 定義の前提にある ∧ の可換性により、Rが右ユークリッドの場合、aRb ∧ aRc はbRc ∧ cRb を意味します。同様に、Rが左ユークリッドの場合、bRa ∧ cRa はbRc ∧ cRb を意味します。
- ユークリッドであるという性質は推移性とは異なります。たとえば、≤ は推移的ですが、右ユークリッドではありません。[2]一方、0 ≤ x ≤ y + 1 ≤ 2 で定義されるxRy は推移的ではありませんが、[3]自然数上では右ユークリッドです。
- 対称関係の場合、推移性、右ユークリッド性、左ユークリッド性はすべて一致します。ただし、非対称関係は推移性と右ユークリッド性の両方を兼ね備えている場合もあります。たとえば、xRyはy =0で定義されます。
- 右ユークリッド関係かつ反射関係でもある関係は対称関係でもあるため同値関係である。[1] [4]同様に、左ユークリッド関係および反射関係も同値関係である。
- 右ユークリッド関係の値域は常にその定義域の部分集合 [5] である。右ユークリッド関係の値域への制限は常に反射的であり[6]、したがって同値である。同様に、左ユークリッド関係の定義域はその値域の部分集合であり、左ユークリッド関係の定義域への制限は同値である。したがって、X上の右ユークリッド関係で右全（または左全）は、その値域（または定義域）がXであるため同値である。[7]
- 関係Rが左ユークリッド関係と右ユークリッド関係の両方を持つためには、 Rの定義域と値域集合が一致し、Rがその集合上で同値関係である必要があります。[8]
- 右ユークリッド関係は常に準推移的であり[9]、左ユークリッド関係も同様である[10] 。
- 連結された右ユークリッド関係は常に推移的である。[11]連結された左ユークリッド関係も同様である。[12]
- X が少なくとも 3 つの要素を持つ場合、 X上の連結された右ユークリッド関係R は反対称にはなれません[13]。また、X上の連結された左ユークリッド関係も反対称にはなれません[14] 。たとえば、 2 要素セットX = { 0, 1 } 上で、y =1によって定義される関係xRyは連結され、右ユークリッドで、反対称であり、x =1によって定義される関係xRy は連結され、左ユークリッドで、反対称です。
- 集合X上の関係R が右ユークリッド的であるためには、制約R ′ := R | ran( R )が同値であり、X \ran( R )内の各xに対して、 Rのもとでxに関連付けられているすべての要素がR ′のもとで同値である必要があります。[15]同様に、X上のR が左ユークリッド的であるためには、R ′ := R | dom( R )が同値であり、X \dom( R )内の各xに対して、 Rのもとでxに関連付けられているすべての要素がR ′のもとで同値である必要があります。
- 左ユークリッド関係は、反対称である場合に限り、左一意です。同様に、右ユークリッド関係は、反対称である場合に限り、右一意です。
- 左ユークリッド関係と左一意関係は空虚に推移的であり、右ユークリッド関係と右一意関係も同様です。
- 左ユークリッド関係は左準反射的である。左一意関係については逆も成り立つ。双対的に、各右ユークリッド関係は右準反射的であり、各右一意かつ右準反射的関係は右ユークリッド的である。[16]
参考文献
- ^ ab フェイギン、ロナルド（2003）、知識についての推論、MITプレス、p.60、ISBN 978-0-262-56200-3。
- ^ 例えば、0 ≤ 2 かつ 0 ≤ 1 だが、2 ≤ 1 ではない
- ^ 例えば 2 R 1 と 1 R 0 だが 2 R 0ではない
- ^ xRyとxRx はyRx を意味します。
- ^定義域と値域が等しい必要はありません 。y =min{ x ,2}で定義される関係xRy は自然数上で右ユークリッド的であり、その値域 {0,1,2} は自然数の定義域の適切な部分集合です。
- ^ y がRの範囲内にある場合、適切なxに対してxRy ∧ xRy はyRyを意味します。これはy がRの定義域にあることも証明します。
- ^ バック、チャールズ（1967）、「同値関係の代替定義」、数学教師、60：124-125。
- ^ 唯一の if方向は前の段落から続きます。 — if方向では、aRbとaRc を仮定すると、a、b、c はRの定義域と値域のメンバーであり、したがって対称性と推移性によりbRc になります。 Rの左ユークリッド性も同様に従います。
- ^ xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRyが成り立つ場合、yとz は両方ともRの範囲内にあります。R はそのセット上の同値であるため、yRz はzRy を意味します。したがって、準推移性の定義式の前提は満たされません。
- ^ x、y がRの定義域内にあることを観察すると、同様の議論が当てはまります。
- ^ xRy ∧ yRzが成り立つ場合、yとz はRの範囲内にあります。R は連結なので、xRzまたはzRxまたはx = zが成り立ちます。 ケース 1 では、示すべきことは何も残っていません。 ケース 2 と 3 では、x も範囲内にあります。 したがって、xRz は、それぞれRの値域における対称性と反射性から導かれます。
- ^ 同様に、x、y はRの定義域内にあるとします。
- ^ R は連結なので、その値域には少なくとも 2 つの異なる要素x、y があり、xRy ∨ yRxが成り立ちます。 R はその値域で対称なので、 xRy ∧ yRxも成り立ちます。 これは反対称性の性質と矛盾します。
- ^同様の議論により、 Rのドメインを使用します。
- ^次 の場合のみ: R ′ は上記のように同値です。x ∈ X \ran( R ) かつxR ′ y 1かつxR ′ y 2の場合、右ユークリッド性によりy 1 Ry 2となり、したがってy 1 R ′ y 2となります。 —次の場合: xRy ∧ xRzが成り立つ場合、y、z ∈ran( R ) です。x ∈ran( R ) の場合、xR ′ y ∧ xR ′ zも成り立つため、R ′の対称性と推移性によりyR ′ zとなり、したがってyRzとなります。 x ∈ X \ran( R )の場合、仮定により要素yとz はR ′ の下で同値でなければならないため、 yRzでもあります。
- ^ Jochen Burghardt (2018年11月). 二項関係の非顕著な特性に関する単純な法則 (技術レポート). arXiv : 1806.05036v2 .補題44-46。