部分同値関係

Mathematical concept for comparing objects

数学において、部分同値関係（しばしばPERと略され、古い文献では制限同値関係^[1]とも呼ばれる）は、対称かつ推移的な同次二項関係である。この関係が反射的である場合、その関係は同値関係となる。

意味

正式には、集合上の関係が PER となるのは、次の条件がすべて満たされている場合です。 ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle a,b,c\in X}$

1. もしならば（対称性） ${\displaystyle aRb}$ ${\displaystyle bRa}$
2. かつならば（推移性） ${\displaystyle aRb}$ ${\displaystyle bRc}$ ${\displaystyle aRc}$

より直感的な定義として、集合 がPER であるとは、のある部分集合が存在し、 が上で同値関係にある場合を言う。 を とすることで、この2つの定義は同値であることが分かる。^[2] ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle R\subseteq Y\times Y}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle Y=\{x\in X\mid x\,R\,x\}}$

特性と用途

集合上の部分同値関係には次の性質が成り立ちます。 ${\displaystyle R}$ ${\displaystyle X}$

• ${\displaystyle R}$は部分集合上の同値関係である。^{[注 1]} ${\displaystyle Y=\{x\in X\mid x\,R\,x\}\subseteq X}$
• ${\displaystyle R}$二関数的である：関係は2つの部分関数と何らかの指示子集合の集合である ${\displaystyle \{(a,b)\mid fa=gb\}}$ ${\displaystyle f,g:X\rightharpoonup Y}$ ${\displaystyle Y}$
• ${\displaystyle R}$は右ユークリッドと左ユークリッドである。 の場合、は、を意味し、 の場合も同様に左ユークリッドであり、を意味する。 ${\displaystyle a,b,c\in X}$ ${\displaystyle aRb}$ ${\displaystyle aRc}$ ${\displaystyle bRc}$ ${\displaystyle bRa}$ ${\displaystyle cRa}$ ${\displaystyle bRc}$
• ${\displaystyle R}$は準反射的である： かつならばかつ。^{[3] [注 2]} ${\displaystyle x,y\in X}$ ${\displaystyle xRy}$ ${\displaystyle xRx}$ ${\displaystyle yRy}$

これらの特性のいずれも、関係がPERであることを意味するのに十分ではない。^{[注 3]}

非集合論的設定において

型理論、構成的数学、そしてそれらのコンピュータサイエンスへの応用において、部分集合の類似物を構成することはしばしば問題となる^[4] 。そのため、これらの文脈ではPERがより一般的に用いられ、特にセットイド（部分セットイドと呼ばれることもある）を定義する際に用いられる。型とPERから部分セットイドを形成することは、古典的な集合論的数学における部分集合と商を形成することに類似している。

代数的な合同の概念は部分同値にも一般化することができ、部分合同の概念、すなわち対称的かつ推移的だが必ずしも反射的ではない準同型関係を生み出す。^[5]

例

同値関係ではないPER の簡単な例は、が空でない場合の空関係です。 ${\displaystyle R=\emptyset }$ ${\displaystyle X}$

部分関数の核

が集合上の部分 関数である場合、 ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle \approx }$

${\displaystyle x\approx y}$がで定義され、が で定義され、 ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle y}$ ${\displaystyle f(x)=f(y)}$

これは明らかに対称かつ推移的であるため、部分同値関係です。

がいくつかの要素で定義されていない場合、 は同値関係ではありません。が定義されていない場合、 は反射的ではありません。実際、そのようなに対して となるような は存在しません。したがって、 が同値関係となる の最大の部分集合は、 が定義されている部分集合と全く同じであることが直ちに分かります。 ${\displaystyle f}$ ${\displaystyle \approx }$ ${\displaystyle f(x)}$ ${\displaystyle x\not \approx x}$ ${\displaystyle x}$ ${\displaystyle y\in A}$ ${\displaystyle x\approx y}$ ${\displaystyle A}$ ${\displaystyle \approx }$ ${\displaystyle f}$

同値関係を尊重する関数

XとYを同値関係（PER）を備えた集合とします。に対して、 は以下を意味します。 ${\displaystyle \approx _{X},\approx _{Y}}$ ${\displaystyle f,g:X\to Y}$ ${\displaystyle f\approx g}$

${\displaystyle \forall x_{0}\;x_{1},\quad x_{0}\approx _{X}x_{1}\Rightarrow f(x_{0})\approx _{Y}g(x_{1})}$

は、 f が商の明確に定義された関数を誘導することを意味します。したがって、PER は商の定義性と、2つの関数が商に同じ関数を誘導するという両方の概念を捉えています。 ${\displaystyle f\approx f}$ ${\displaystyle X/{\approx _{X}}\;\to \;Y/{\approx _{Y}}}$ ${\displaystyle \approx }$

IEEE浮動小数点値の等価性

浮動小数点数に関するIEEE 754:2008規格は、浮動小数点値に対して「EQ」関係を定義しています。この述語は対称的かつ推移的ですが、それ自身とEQではないNaN値が存在するため、反射的ではありません。^[6]

注記

1. 構成上、は 上で反射的であり、したがって 上で同値関係にある。 ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle Y}$
2. ならば対称性により、推移性によりとなるので、これは従う。これはユークリッドの性質からも導かれる。 ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle xRx}$ ${\displaystyle yRy}$
3. 同値関係について、集合と関係を考えてみましょう。は 上の同値関係ですが、 上の PER ではありません。なぜなら、対称 (だが ではない) でも推移的 (かつだが ではない) でもないからです。ユークリッド性 (および準反射性) については、0 ≤ x ≤ y +1 ≤ 2 で定義される自然数上のxRy は、右ユークリッド的 (したがって準反射的) ですが、対称 (例えば 2 R 1 だが 1 R 2 ではないため) でも推移的 (例えば 2 R 1 かつ 1 R 0 だが 2 R 0 ではないため) でもありません。 ${\displaystyle E=\{a,b,c,d\}}$ ${\displaystyle R=\{a,b,c\}^{2}\cup \{(d,a)\}}$ ${\displaystyle R}$ ${\displaystyle \{a,b,c\}}$ ${\displaystyle E}$ ${\displaystyle dRa}$ ${\displaystyle aRd}$ ${\displaystyle dRa}$ ${\displaystyle aRb}$ ${\displaystyle dRb}$

参考文献

1. スコット、ダナ（1976年9月）「格子としてのデータ型」SIAM Journal on Computing 5 ( 3): 560. doi :10.1137/0205037.
2. ミッチェル, ジョン・C. (1996). 『プログラミング言語の基礎』マサチューセッツ州ケンブリッジ: MIT 出版. pp.  364– 365. ISBN 0585037892。
3. ブリタニカ百科事典 (EB); EB の準反射性の概念は Wikipedia の左準反射性の概念であるが、対称関係については一致する。
4. Salveson, A.; Smith, JM (1988). 「Martin-Lofの型理論におけるサブセット型の強さ」. [1988] Proceedings. Third Annual Information Symposium on Logic in Computer Science . pp.  384– 391. doi :10.1109/LICS.1988.5135. ISBN 0-8186-0853-6. S2CID  15822016。
5. J. Lambek (1996). 「蝶と蛇」. Aldo Ursini, Paulo Agliano (編). Logic and Algebra . CRC Press. pp.  161– 180. ISBN 978-0-8247-9606-8。
6. ゴールドバーグ、デイヴィッド (1991). 「すべてのコンピュータ科学者が浮動小数点演算について知っておくべきこと」. ACMコンピューティングサーベイ. 23 (1): 5– 48. doi :10.1145/103162.103163.33ページをご覧ください。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Partial_equivalence_relation&oldid=1299631405"