集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・整礎律・全域性・集合性の定義)の定義と性質
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・全域性・集合性・整礎性の定義)の定義と性質
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・全域性・集合性・整礎性の定義)の定義
集合\(X\)の元に対し2項関係\(R\)が定義されているとする。
すなわち\(\forall a\in X,aRa\)である。
例：\(\leq\)は反射律を満たすが\(<\)は反射律を満たさない。
すなわち\(\forall a\in X,\lnot\left(aRa\right)\)である。
例：\(<\)は非反射律を満たす。
すなわち\(\forall a,b\in X,aRb\rightarrow a=b\)である。
例：\(=\)は余反射律を満たす。
すなわち\(\forall a,b\in X,aRb\rightarrow bRa\)である。
例：\(=\)と\(\ne\)は対称律を満たす。
すなわち\(\forall a,b\in X,aRb\land bRa\rightarrow a=b\)である。
例：\(\leq\)は反対称律を満たす。
すなわち\(\forall a,b\in X,aRb\rightarrow\lnot\left(bRa\right)\)である。
例：\(<\)は非対称律を満たす。
すなわち\(\forall a,b,c\in X,aRb\land bRc\rightarrow aRc\)である。
例：\(<\)と\(\leq\)は推移律である。
すなわち\(\forall a,b\in X,aRb\lor bRa\)である。
\(aRb\)または\(bRc\)どちらか又は両方が成り立つとき\(a\)と\(b\)は比較可能であるという。
\(aRb\)または\(bRc\)のどちらも成り立たないとき\(a\)と\(b\)は比較不能であるという。
例：\(\leq\)は完全律を満たすが、\(<\)は完全律を満たさない。
例:\(<\)は三分律を満たす。
すなわち\(\forall a,b,c\in X,aRb\land aRc\rightarrow bRc\land cRb\)である。
これは対称性から\(\forall a,b,c\in X,aRb\land aRc\rightarrow bRc\)としても同値である。
任意の\(a,b,c\in X\)に対し\(aRc\)かつ\(bRc\)ならば\(aRb\)かつ\(bRa\)となるとき、\(R\)は左ユークリッド律を満たすという。
すなわち\(\forall a,b,c\in X,aRc\land bRc\rightarrow aRb\land bRa\)である。
これは対称性から\(\forall a,b,c\in X,aRc\land bRc\rightarrow aRb\)としても同値である。
例：\(=\)は右ユークリッド律を満たし、左ユークリッド律も満たす。
すなわち\(\forall a,b\in Y,\left(\forall c\in X,cRa\leftrightarrow cRb\right)\rightarrow a=b\)である。
また、任意の\(a,b\in X\)について、\(\forall c\in Y,aRc\leftrightarrow bRc\)ならば\(a=b\)となるとき、\(R\)は左外延律を満たすという。
すなわち\(\forall a,b\in X,\left(\forall c\in Y,aRc\leftrightarrow bRc\right)\rightarrow a=b\)である。
例：\(=\)は外延律を満たす。
すなわち\(\forall a\in X,\exists b\in Y,aRb\)である。
任意の\(b\in Y\)に対し、ある\(a\in X\)が存在し、\(aRb\)が成り立つとき、\(R\)は右全域性を満たすという。
すなわち\(\forall b\in Y,\exists a\in X,aRb\)である。
例：集合として整数\(\mathbb{Z}\)を考えると、\(<\)も\(>\)も左全域性と右全域性を満たす。
例：集合として自然数\(\mathbb{N}\)を考えると、\(<\)は左全域性を満たすが、\(>\)は左全域性を満たさない。
2項関係を\(\left(X,Y,R\right)\)として、任意の\(a\in X\)について、\(\left\{ b\in Y;aRb\right\} \)が集合となるとき、\(R\)を右集合性を満たすという。
例:2つの集合同士の関係や\(\in\)の関係は集合律となる。
これは\(\forall A\subseteq X,A\ne\emptyset\rightarrow\left(\exists m\in A,\forall x\in A,xRm\rightarrow mRx\right)\)である。
例：部分集合として自然数\(\mathbb{N}\)を考えると、\(\leq\)も\(<\)も整礎性を満たす。
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・全域性・集合性・整礎性の定義)の性質
同様に、2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が左ユークリッド律を満たすことと、\(R^{-1}\circ R\subseteq R\)を満たすことは同値である。
同様に、2項関係を\(\left(X,Y,R\right)\)とすると、\(R\)が左外延律を満たすことと、\(\left(R^{-1}\circ R^{c}\right)^{c}\cap\left(R^{-1}\circ R^{c}\right)^{-1,c}\subseteq\Delta_{X}\)を満たすことは同値である。
同様に、2項関係\(\left(X,Y,R\right)\)があるとき、\(R\)が右全域性を満たすことと、\(\Delta_{Y}\subseteq R\circ R^{-1}\)を満たすことは同値である。
また、左全域性は\(\dom\left(R\right)=X\)、右全域性は\(\cod\left(R\right)=Y\)と同値です。
同様に\(X\ne\emptyset\)として2項関係を\(\left(X,Y,R\right)\)とすると、\(R\)が右全域性を満たすことと、\(R\circ\left(X\times X\right)=X\times Y\)を満たすことは同値である。
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・全域性・集合性・整礎性の定義)の定義
集合\(X\)の元に対し2項関係\(R\)が定義されているとする。
(1)反射律(reflexive)
任意の\(a\in X\)に対し\(aRa\)が成り立つとき、\(R\)は反射律を満たすという。すなわち\(\forall a\in X,aRa\)である。
例：\(\leq\)は反射律を満たすが\(<\)は反射律を満たさない。
(2)非反射律(irreflexive)
任意の\(a\in X\)に対し\(aRa\)が成り立たないとき、\(R\)は非反射律を満たすという。すなわち\(\forall a\in X,\lnot\left(aRa\right)\)である。
例：\(<\)は非反射律を満たす。
(3)余反射律(coreflexive)
任意の\(a,b\in X\)に対し\(aRb\)ならば\(a=b\)となるとき、\(R\)は余反射律を満たすという。すなわち\(\forall a,b\in X,aRb\rightarrow a=b\)である。
例：\(=\)は余反射律を満たす。
(4)対称律(symmetric)
任意の\(a,b\in X\)に対し\(aRb\)ならば\(bRa\)となるとき、\(R\)は対称律を満たすという。すなわち\(\forall a,b\in X,aRb\rightarrow bRa\)である。
例：\(=\)と\(\ne\)は対称律を満たす。
(5)反対称律(antisymmetric)
任意の\(a,b\in X\)に対し\(aRb\)かつ\(bRa\)ならば\(a=b\)となるとき、\(R\)は反対称律を満たすという。すなわち\(\forall a,b\in X,aRb\land bRa\rightarrow a=b\)である。
例：\(\leq\)は反対称律を満たす。
(6)非対称律(asymmetric)
任意の\(a,b\in X\)に対し\(aRb\)ならば\(bRa\)とならないとき、\(R\)は非対称律を満たすという。すなわち\(\forall a,b\in X,aRb\rightarrow\lnot\left(bRa\right)\)である。
例：\(<\)は非対称律を満たす。
(7)推移律(transitive)
任意の\(a,b,c\in X\)に対し\(aRb\)かつ\(bRc\)ならば\(aRc\)となるとき、\(R\)は推移律を満たすという。すなわち\(\forall a,b,c\in X,aRb\land bRc\rightarrow aRc\)である。
例：\(<\)と\(\leq\)は推移律である。
(8)完全律(total)・全順序律
任意の\(a,b\in X\)に対し\(aRb\)または\(bRa\)のどちらか又は両方が成り立つとき、\(R\)は完全律という。すなわち\(\forall a,b\in X,aRb\lor bRa\)である。
\(aRb\)または\(bRc\)どちらか又は両方が成り立つとき\(a\)と\(b\)は比較可能であるという。
\(aRb\)または\(bRc\)のどちらも成り立たないとき\(a\)と\(b\)は比較不能であるという。
例：\(\leq\)は完全律を満たすが、\(<\)は完全律を満たさない。
(9)3分律(trichotomous)
任意の\(a,b\in X\)に対し\(aRb\)または\(bRa\)または\(a=b\)のいづれか1つのみ成り立つとき、\(R\)は3分律を満たすという。例:\(<\)は三分律を満たす。
(10)ユークリッド律(Euclidean)
任意の\(a,b,c\in X\)に対し\(aRb\)かつ\(aRc\)ならば\(bRc\)かつ\(cRb\)となるとき、\(R\)は右ユークリッド律を満たすという。すなわち\(\forall a,b,c\in X,aRb\land aRc\rightarrow bRc\land cRb\)である。
これは対称性から\(\forall a,b,c\in X,aRb\land aRc\rightarrow bRc\)としても同値である。
任意の\(a,b,c\in X\)に対し\(aRc\)かつ\(bRc\)ならば\(aRb\)かつ\(bRa\)となるとき、\(R\)は左ユークリッド律を満たすという。
すなわち\(\forall a,b,c\in X,aRc\land bRc\rightarrow aRb\land bRa\)である。
これは対称性から\(\forall a,b,c\in X,aRc\land bRc\rightarrow aRb\)としても同値である。
例：\(=\)は右ユークリッド律を満たし、左ユークリッド律も満たす。
(11)外延律(extensive)
2項関係を\(\left(X,Y,R\right)\)として、任意の\(a,b\in Y\)について、\(\forall c\in X,cRa\leftrightarrow cRb\)ならば\(a=b\)となるとき、\(R\)は右外延律を満たすという。すなわち\(\forall a,b\in Y,\left(\forall c\in X,cRa\leftrightarrow cRb\right)\rightarrow a=b\)である。
また、任意の\(a,b\in X\)について、\(\forall c\in Y,aRc\leftrightarrow bRc\)ならば\(a=b\)となるとき、\(R\)は左外延律を満たすという。
すなわち\(\forall a,b\in X,\left(\forall c\in Y,aRc\leftrightarrow bRc\right)\rightarrow a=b\)である。
例：\(=\)は外延律を満たす。
(12)全域性(serial)
2項関係を\(\left(X,Y,R\right)\)として、任意の\(a\in X\)に対し、ある\(b\in Y\)が存在し、\(aRb\)が成り立つとき、\(R\)は左全域性を満たすという。すなわち\(\forall a\in X,\exists b\in Y,aRb\)である。
任意の\(b\in Y\)に対し、ある\(a\in X\)が存在し、\(aRb\)が成り立つとき、\(R\)は右全域性を満たすという。
すなわち\(\forall b\in Y,\exists a\in X,aRb\)である。
例：集合として整数\(\mathbb{Z}\)を考えると、\(<\)も\(>\)も左全域性と右全域性を満たす。
例：集合として自然数\(\mathbb{N}\)を考えると、\(<\)は左全域性を満たすが、\(>\)は左全域性を満たさない。
(13)集合性(set-like)
2項関係を\(\left(X,Y,R\right)\)として、任意の\(b\in Y\)について、\(\left\{ a\in X;aRb\right\} \)が集合となるとき、\(R\)を左集合性を満たすという。2項関係を\(\left(X,Y,R\right)\)として、任意の\(a\in X\)について、\(\left\{ b\in Y;aRb\right\} \)が集合となるとき、\(R\)を右集合性を満たすという。
例:2つの集合同士の関係や\(\in\)の関係は集合律となる。
(14)整礎性(well-founded)
2項関係\(\left(X,X,R\right)\)があるとき、集合\(X\)の任意の空でない部分集合\(A\)が極小元\(a\)を持つとき、\(R\)は整礎性を満たすという。これは\(\forall A\subseteq X,A\ne\emptyset\rightarrow\left(\exists m\in A,\forall x\in A,xRm\rightarrow mRx\right)\)である。
例：部分集合として自然数\(\mathbb{N}\)を考えると、\(\leq\)も\(<\)も整礎性を満たす。
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・全域性・集合性・整礎性の定義)の性質
(1)反射律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が反射律を満たすことと、\(\Delta_{X}\subseteq R\)を満たすことは同値である。(2)非反射律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が非反射律を満たすことと、\(R\subseteq\Delta_{X}^{c}\)を満たすことは同値である。(3)余反射律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が余反射律を満たすことと、\(R\subseteq\Delta_{X}\)を満たすことは同値である。(4)対称律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が対称律を満たすことと、\(R=R^{-1}\)を満たすことは同値である。(5)反対称律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が反対称律を満たすことと、\(R\cap R^{-1}\subseteq\Delta_{X}\)を満たすことは同値である。(6)非対称律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が非対称律を満たすことと、\(R\cap R^{-1}=\emptyset\)を満たすことは同値である。(7)推移律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が推移律を満たすことと、\(R^{2}\subseteq R\)を満たすことは同値である。(8)完全律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が完全律を満たすことと、\(R\cup R^{-1}=X^{2}\)を満たすことは同値である。(9)3分律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が3分律を満たすことと、\(R\sqcup R^{-1}\sqcup\Delta_{X}=X^{2}\)を満たすことは同値である。(10)ユークリッド律
2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が右ユークリッド律を満たすことと、\(R\circ R^{-1}\subseteq R\)を満たすことは同値である。同様に、2項関係\(\left(X,X,R\right)\)があるとき、\(R\)が左ユークリッド律を満たすことと、\(R^{-1}\circ R\subseteq R\)を満たすことは同値である。
(11)外延律
2項関係を\(\left(X,Y,R\right)\)とすると、\(R\)が右外延律を満たすことと、\(\left(R^{c}\circ R^{-1}\right)^{c}\cap\left(R^{c}\circ R^{-1}\right)^{-1,c}\subseteq\Delta_{Y}\)を満たすことは同値である。同様に、2項関係を\(\left(X,Y,R\right)\)とすると、\(R\)が左外延律を満たすことと、\(\left(R^{-1}\circ R^{c}\right)^{c}\cap\left(R^{-1}\circ R^{c}\right)^{-1,c}\subseteq\Delta_{X}\)を満たすことは同値である。
(12)全域性
2項関係\(\left(X,Y,R\right)\)があるとき、\(R\)が左全域性を満たすことと、\(\Delta_{X}\subseteq R^{-1}\circ R\)を満たすことは同値である。同様に、2項関係\(\left(X,Y,R\right)\)があるとき、\(R\)が右全域性を満たすことと、\(\Delta_{Y}\subseteq R\circ R^{-1}\)を満たすことは同値である。
また、左全域性は\(\dom\left(R\right)=X\)、右全域性は\(\cod\left(R\right)=Y\)と同値です。
(13)全域性
2項関係を\(\left(X,Y,R\right)\)として\(Y\ne\emptyset\)とすると、\(R\)が左全域性を満たすことと、\(\left(Y\times Y\right)\circ R=X\times Y\)を満たすことは同値である。同様に\(X\ne\emptyset\)として2項関係を\(\left(X,Y,R\right)\)とすると、\(R\)が右全域性を満たすことと、\(R\circ\left(X\times X\right)=X\times Y\)を満たすことは同値である。
(1)
反対称律の条件は以下と同値である。\(\forall a,b\in X,aRb\land a\ne b\rightarrow\lnot bRa\)
なぜなら
\begin{align*} aRb\land bRa\rightarrow a=b & \Leftrightarrow\lnot aRb\lor\lnot bRa\lor a=b\\ & \Leftrightarrow\lnot\left(aRb\land a\ne b\right)\lor\lnot bRa\\ & \Leftrightarrow aRb\land a\ne b\rightarrow\lnot bRa \end{align*} となるからである。
(2)論理式と集合論的表現
\[ \begin{array}{|c|c|c|c|} \hline & \text{2項関係} & \text{論理式} & \text{集合論的表現}\\ \hline \text{反射律} & \left(X,X,R\right) & aRa & \Delta_{X}\subseteq R\\ \hline \text{非反射律} & \left(X,X,R\right) & \lnot\left(aRa\right) & R\subseteq\Delta_{X}^{c}\\ \hline \text{余反射律} & \left(X,X,R\right) & aRb\rightarrow a=b & R\subseteq\Delta_{X}\\ \hline \text{対称律} & \left(X,X,R\right) & aRb\rightarrow bRa & R=R^{-1}\\ \hline \text{反対称律} & \left(X,X,R\right) & aRb\land bRa\rightarrow a=b & R\cap R^{-1}\subseteq\Delta_{X}\\ \hline \text{非対称律} & \left(X,X,R\right) & aRb\rightarrow\lnot\left(bRa\right) & R\cap R^{-1}=\emptyset\\ \hline \text{推移律} & \left(X,X,R\right) & aRb\land bRc\rightarrow aRc & R^{2}\subseteq R\\ \hline \text{完全律} & \left(X,X,R\right) & aRb\lor bRa & R\cup R^{-1}=X^{2}\\ \hline \text{3分律} & \left(X,X,R\right) & aRb,bRa,a=b\text{のいづれか1つのみ成り立つ} & R\sqcup R^{-1}\sqcup\Delta_{X}=X^{2}\\ \hline \text{右ユークリッド律} & \left(X,X,R\right) & aRb\land aRc\rightarrow bRc & R\circ R^{-1}\subseteq R\\ \hline \text{左ユークリッド律} & \left(X,X,R\right) & aRc\land bRc\rightarrow aRb & R^{-1}\circ R\subseteq R\\ \hline \text{右外延律} & \left(X,Y,R\right) & \left(\forall c\in X,cRa\leftrightarrow cRb\right)\rightarrow a=b & \left(R^{c}\circ R^{-1}\right)^{c}\cap\left(R^{c}\circ R^{-1}\right)^{-1,c}\subseteq\Delta_{Y}\\ \hline \text{左外延律} & \left(X,Y,R\right) & \left(\forall c\in Y,aRc\leftrightarrow bRc\right)\rightarrow a=b & \left(R^{-1}\circ R^{c}\right)^{c}\cap\left(R^{-1}\circ R^{c}\right)^{-1,c}\subseteq\Delta_{X}\\ \hline \text{左全域性} & \left(X,Y,R\right) & \forall a\in X,\exists b\in Y,aRb & \Delta_{X}\subseteq R^{-1}\circ R\\ & & & \dom\left(R\right)=X\\ \hline \text{右全域性} & \left(X,Y,R\right) & \forall b\in Y,\exists a\in X,bRa & \Delta_{Y}\subseteq R\circ R^{-1}\\ & & & \cod\left(R\right)=Y \\\hline \end{array} \](3)
\(X\ne Y\)として2項関係\(\left(X,Y,R\right)\)では、反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律は定義できません。(4)
\(A\)ならば\(B\)のようなものは○○律といい、存在して\(A\)が真になるようなものは○○性ということが多いです。ただし、必ずこうなっているとは限らず、群論の逆元の存在は逆元性とは言わずに逆元律と言います。
(1)
\(\Rightarrow\)
任意の\(\left(a,b\right)\in\Delta_{X}\)を選ぶ。このとき、\(\left(a,b\right)\in\Delta_{X}=\left\{ \left(x,x\right);x\in X\right\} \)より、\(a=b\)となり、前件より\(\left(a,a\right)\in R\)なので\(\left(a,b\right)=\left(a,a\right)\in R\)となる。
従って、\(\Delta_{X}\subseteq R\)となる。
故に\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(a\in X\)を選ぶ。このとき、\(\left(a,a\right)\in\Delta_{X}\)であるので、\(\left(a,a\right)\in\Delta_{X}\subseteq R\)となる。
従って、\(R\)は反射律を満たす。
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。補足
これより、\(R=R\cup\Delta_{X}\)とも同値となる。(2)
\(\Rightarrow\)
任意の\(\left(a,b\right)\in R\)を選ぶ。このとき、前件より、\(R\)は非反射律を満たしているので、\(a\ne b\)となり、\(\left(a,b\right)\notin\left\{ \left(x,x\right);x\in X\right\} =\Delta_{X}\)となるので、\(\left(a,b\right)\in\Delta_{X}^{c}\)となる。
これより、\(R\subseteq\Delta_{X}^{c}\)となる。
従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
\(R\subseteq\Delta_{X}^{c}\)、かつある\(a\in X\)が存在して、\(\left(a,a\right)\in R\)となると仮定する。そうすると、\(\left(a,a\right)\in R\subseteq\Delta_{X}^{c}=\left\{ \left(x,x\right);x\in X\right\} ^{c}\)となるので\(\left(a,a\right)\notin\left\{ \left(x,x\right);x\in X\right\} \)となり矛盾。
従って背理法より、\(R\subseteq\Delta_{X}^{c}\)ならば任意の\(a\in X\)について\(\left(a,a\right)\notin R\)となる。
これより、\(R\subseteq\Delta_{X}^{c}\)ならば\(R\)は非反射律を満たす。
従って、\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。補足
これより、\(R=R\setminus\Delta_{X}\)とも同値となる。(3)
\(\Rightarrow\)
任意の\(\left(a,b\right)\in R\)を選ぶ。そうすると、前件より、\(a=b\)となるので、\(\left(a,b\right)=\left(a,a\right)\)となり、\(\left(a,b\right)=\left(a,a\right)\in\Delta_{X}\)となる。
従って、\(R\subseteq\Delta_{X}\)となる。
これより、\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(\left(a,b\right)\in R\)を選ぶ。そうすると、前件より、\(R\subseteq\Delta_{X}\)であるので、\(\left(a,b\right)\in R\subseteq\Delta_{X}=\left\{ \left(x,x\right);x\in X\right\} \)となり、\(a=b\)となる。
これより、任意の\(\left(a,b\right)\in R\)について、\(a=b\)となるので、\(R\)は余反射律を満たす。
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。補足
これより、\(R=R\cap\Delta_{X}\)とも同値となる。(4)
\(\Rightarrow\)
任意の\(\left(a,b\right)\in R\)を選ぶ。そうすると、前件より、\(\left(b,a\right)\in R\)となるので、\(\left(a,b\right)\in R^{-1}\)となる。
これより、\(R\subseteq R^{-1}\)となる。
同様に任意の\(\left(a,b\right)\in R^{-1}\)について、前件より、\(\left(b,a\right)\in R^{-1}\)となるので、\(\left(a,b\right)\in R\)となり、\(R^{-1}\subseteq R\)となる。
これらより、\(R\subseteq R^{-1}\)と\(R^{-1}\subseteq R\)が成り立つので\(R=R^{-1}\)となる。
従って、\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(\left(a,b\right)\in R\)を選ぶ。そうすると、前件より、\(R=R^{-1}\)であるので、\(\left(a,b\right)\in R=R^{-1}\)となり、\(\left(b,a\right)\in R\)となる。
これより、任意の\(\left(a,b\right)\in R\)について、\(\left(b,a\right)\in R\)となるので、\(R\)は対称律を満たす。
従って\(\Leftarrow\)が成り立つ
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。補足
これより、\(R=R\cup R^{-1}\)や\(R=R\cap R^{-1}\)とも同値となる。(5)
\(\Rightarrow\)
任意に\(\left(a,b\right)\in R\cap R^{-1}\)を選ぶ。そうすると、\(\left(a,b\right)\in R\)かつ\(\left(a,b\right)\in R^{-1}\)となり\(\left(a,b\right)\in R\)かつ\(\left(b,a\right)\in R\)であり、前件より\(R\)は反対称律を満たすので、\(a=b\)となる。
これより、\(\left(a,b\right)=\left(a,a\right)\in\Delta_{X}\)となる。
従って、\(R\cap R^{-1}\subseteq\Delta_{X}\)となる。
故に\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意に\(a,b\in X\)を選ぶ。このとき、\(\left(a,b\right)\in R\)かつ\(\left(b,a\right)\in R\)を満たすとする。
そうすると、\(\left(a,b\right)\in R\text{かつ}\left(a,b\right)\in R^{-1}\)となるので、\(\left(a,b\right)\in R\cap R^{-1}\)となり、前件より、\(R\cap R^{-1}\subseteq\Delta_{X}\)であるので、\(\left(a,b\right)\in R\cap R^{-1}\subseteq\Delta_{X}\)となり、\(a=b\)となる。
これより、任意の\(a,b\in X\)について、\(\left(a,b\right)\in R\text{かつ}\left(b,a\right)\in R\)ならば\(a=b\)となるので\(R\)は反対称律を満たす。
従って、\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。(6)
\(\Rightarrow\)
\(R\)が非対称律を満たし、かつ\(R\cap R^{-1}\ne\emptyset\)と仮定する。そうすると、ある\(\left(a,b\right)\in R\cap R^{-1}\)が存在する。
このとき、\(\left(a,b\right)\in R\)かつ\(\left(a,b\right)\in R^{-1}\)となるので、\(\left(a,b\right)\in R\)かつ\(\left(b,a\right)\in R\)となる。
しかし、\(R\)は非対称律を満たしているので、\(\left(a,b\right)\in R\)ならば\(\left(b,a\right)\notin R\)でなければいけないが\(\left(b,a\right)\in R\)なので矛盾。
従って、背理法より、\(R\)が非対称律を満たすならば\(R\cap R^{-1}=\emptyset\)となる。
故に\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(\left(a,b\right)\in R\)を選ぶ。ここで、\(\left(b,a\right)\in R\)と仮定する。
そうすると、\(\left(a,b\right)\in R^{-1}\)となるので、\(\left(a,b\right)\in R\)かつ\(\left(a,b\right)\in R^{-1}\)より、\(\left(a,b\right)\in R\cap R^{-1}\)となるが、前件より、\(R\cap R^{-1}=\emptyset\)であるので、\(\left(a,b\right)\in R\cap R^{-1}=\emptyset\)となり矛盾。
従って背理法より、\(\left(b,a\right)\notin R\)となる。
これより、任意の\(\left(a,b\right)\in R\)について、\(\left(b,a\right)\notin R\)となるので\(R\)は非対称律を満たす。
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。(7)
\(\Rightarrow\)
任意の\(\left(a,b\right)\in R^{2}=R\circ R\)を選ぶ。このとき、ある\(c\in X\)が存在し、\(\left(a,c\right)\in R\)かつ\(\left(c,b\right)\in R\)を満たす。
ここで、\(R\)は推移律を満たすので、\(\left(a,c\right)\in R\)かつ\(\left(c,b\right)\in R\)ならば\(\left(a,b\right)\in R\)となる。
これより、任意の\(\left(a,b\right)\in R^{2}\)について、\(\left(a,b\right)\in R\)となるので、\(R^{2}\subseteq R\)を満たす。
従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(a,b,c\in X\)を選ぶ。このとき、\(\left(a,c\right)\in R\)かつ\(\left(c,b\right)\in R\)とする。
そうすると、\(\left(a,b\right)\in R\circ R=R^{2}\)となり、前件より\(R^{2}\subseteq R\)であるので、\(\left(a,b\right)\in R^{2}\subseteq R\)となる。
従って、任意の\(a,b,c\in X\)について、\(\left(a,c\right)\in R\)かつ\(\left(c,b\right)\in R\)ならば\(\left(a,b\right)\in R\)となるので、\(R\)は推移律を満たす。
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。補足
これより、任意の自然数\(n\in\mathbb{N}\)について、\(R^{n}\subseteq R\)を満たすことと同値となります。これを示す。
\(\Rightarrow\)
\(n=1\)のときは\(R^{n}=R^{1}=R\subseteq R\)は明らかに成り立つ。\(n=k\)のとき成り立つと仮定すると、\(R^{k+1}=R^{k}\circ R\subseteq R\circ R=R^{2}\subseteq R\)となるので、\(n=k+1\)のときも成り立つ。
従って数学的帰納法より任意の自然数\(n\in\mathbb{N}\)について、\(R^{n}\subseteq R\)を満たす。
故に、\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の自然数\(n\in\mathbb{N}\)について、\(R^{n}\subseteq R\)を満たすとき、\(n=2\)とすると、\(R^{2}\subseteq R\)を満たす。従って、\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。(8)
\(\Rightarrow\)
\(R\cup R^{-1}\subseteq X^{2}\)は明らかなので、\(X^{2}\subseteq R\cup R^{-1}\)を示せばよい。任意の\(\left(a,b\right)\in X^{2}\)を選ぶ。
このとき、前件より、\(R\)は完全律を満たすので、\(\left(a,b\right)\in R\)または\(\left(b,a\right)\in R\)の少なくとも一方は満たす。
もし、\(\left(a,b\right)\in R\)が成り立っているとすると、\(\left(a,b\right)\in R\cup R^{-1}\)となり、\(\left(b,a\right)\in R\)が成り立っているとすると、\(\left(a,b\right)\in R^{-1}\)であり、\(\left(a,b\right)\in R\cup R^{-1}\)となる。
従って、\(\left(a,b\right)\in R\)でも\(\left(b,a\right)\in R\)でも\(\left(a,b\right)\in R\cup R^{-1}\)となる。
これより、\(X^{2}\subseteq R\cup R^{-1}\)となる。
これらより、\(\subseteq\)と\(\supseteq\)が成り立つので、\(R\cup R^{-1}=X^{2}\)が成り立つ。
従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(a,b\in X\)を選ぶ。このとき、\(\left(a,b\right)\in X^{2}\)であり、前件より、\(R\cup R^{-1}=X^{2}\)であるので、\(\left(a,b\right)\in X^{2}=R\cup R^{-1}\)となる。
これより、\(\left(a,b\right)\in R\)または\(\left(a,b\right)\in R^{-1}\)の少なくとも一方は満たすので、\(\left(a,b\right)\in R\)または\(\left(b,a\right)\in R\)の少なくとも一方を満たす。
従って、任意の\(a,b\in X\)について、\(\left(a,b\right)\in R\)または\(\left(b,a\right)\in R\)の少なくとも一方は満たすので、\(R\)は完全律を満たす。
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。(9)
\(\Rightarrow\)
\(R\sqcup R^{-1}\sqcup\Delta_{X}\subseteq X^{2}\)は明らかなので、\(X^{2}\subseteq R\sqcup R^{-1}\sqcup\Delta_{X}\)を示せばよい。任意の\(\left(a,b\right)\in X^{2}\)を選ぶ。
このとき、前件より\(R\)は3分律を満たすので、\(\left(a,b\right)\in R\lor\left(b,a\right)\in R\lor\left(a,b\right)\in\Delta_{X}\)は真となり、\(\top\Leftrightarrow\left(a,b\right)\in R\lor\left(b,a\right)\in R\lor\left(a,b\right)\in\Delta_{X}\Leftrightarrow\left(a,b\right)\in R\lor\left(a,b\right)\in R^{-1}\lor\left(a,b\right)\in\Delta_{X}\Leftrightarrow\left(a,b\right)\in R\cup R^{-1}\cup\Delta_{X}\)となる。
これより、\(X^{2}\subseteq R\cup R^{-1}\cup\Delta_{X}\)が成り立つ。
従って、\(\subseteq\)と\(\supseteq\)が成り立つので、\(R\cup R^{-1}\cup\Delta_{X}=X^{2}\)が成り立つ。
次に排他性を示す。
\(R\)は3分律を満たすので、任意の\(a,b\in X\)について、\(\left(a,b\right)\in R\land\left(b,a\right)\in R\Leftrightarrow\bot\)より、\(\bot\Leftrightarrow\left(a,b\right)\in R\land\left(a,b\right)\in R^{-1}\Leftrightarrow\left(a,b\right)\in R\cap R^{-1}\)となるので、\(R\cap R^{-1}=\emptyset\)となる。
また、任意の\(a,b\in X\)について、\(\left(a,b\right)\in R\land\left(a,b\right)\in\Delta_{X}\Leftrightarrow\bot\)より、\(\bot\Leftrightarrow\left(a,b\right)\in R\land\left(a,b\right)\in\Delta_{X}\Leftrightarrow\left(a,b\right)\in R\cap\Delta_{X}\)となるので、\(R\cap\Delta_{X}=\emptyset\)となる。
同様に、任意の\(a,b\in X\)について、\(\left(a,b\right)\in R^{-1}\land\left(a,b\right)\in\Delta_{X}\Leftrightarrow\bot\)より、\(\bot\Leftrightarrow\left(a,b\right)\in R^{-1}\land\left(a,b\right)\in\Delta_{X}\Leftrightarrow\left(a,b\right)\in R^{-1}\cap\Delta_{X}\)となるので、\(R^{-1}\cap\Delta_{X}=\emptyset\)となる。
これらより、\(R\cup R^{-1}\cup\Delta_{X}=X^{2}\)かつ\(R\cap R^{-1}=\emptyset\)かつ\(R\cap\Delta_{X}=\emptyset\)かつ\(R^{-1}\cap\Delta_{X}=\emptyset\)となるので、\(R\sqcup R^{-1}\sqcup\Delta_{X}=X^{2}\)となる。
従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(\left(a,b\right)\in X^{2}\)を選ぶ。このとき、\(\left(a,b\right)\in X^{2}=R\sqcup R^{-1}\sqcup\Delta_{X}\)となるので、\(\left(a,b\right)\in R\)または\(\left(a,b\right)\in R^{-1}\)または\(\left(a,b\right)\in\Delta_{X}\)のいずれか1つのみが成り立つ。
従って、\(R\)は3分律を満たす。
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。(10)
\(\Rightarrow\)
任意の\(\left(b,c\right)\in R\circ R^{-1}\)を選ぶ。このとき、ある\(a\in X\)が存在し、\(\left(b,a\right)\in R^{-1}\)かつ\(\left(a,c\right)\in R\)を満たす。
これより、\(\left(a,b\right)\in R\)かつ\(\left(a,c\right)\in R\)を満たし、前件より、\(R\)は右ユークリッド律を満たすので、\(\left(b,c\right)\in R\)となる。
従って、\(R\circ R^{-1}\subseteq R\)となる。
故に\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(a,b,c\in X\)を選ぶ。このとき、\(\left(a,b\right)\in R\)かつ\(\left(a,c\right)\in R\)が成り立つとする。
そうすると、\(\left(b,a\right)\in R^{-1}\)かつ\(\left(a,c\right)\in R\)が成り立つので、\(\left(b,c\right)\in R\circ R^{-1}\)となる。
このとき、前件より、\(R\circ R^{-1}\subseteq R\)が成り立つので、\(\left(b,c\right)\in R\circ R^{-1}\subseteq R\)となる。
従って、任意の\(a,b,c\in X\)について、\(\left(a,b\right)\in R\)かつ\(\left(a,c\right)\in R\)ならば\(\left(b,c\right)\in R\)となるので\(R\)は右ユークリッド律を満たす。
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。左ユークリッド律についても同様である。
(11)
任意の\(a,b\in Y\)について、\begin{align*} & \left(\forall c\in X,cRa\leftrightarrow cRb\right)\rightarrow a=b\\ \Leftrightarrow & \lnot\left(\exists c\in X,cRa\nleftrightarrow cRb\right)\rightarrow a=b\\ \Leftrightarrow & \lnot\left(\exists c\in X,\left(cRa\nrightarrow cRb\right)\lor\left(cRa\nleftarrow cRb\right)\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \lnot\left(\exists c\in X,\left(cRa\land\lnot\left(cRb\right)\right)\lor\left(\lnot\left(cRa\right)\land cRb\right)\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \lnot\left(\exists c\in X,\left(\left(c,a\right)\in R\land\left(c,b\right)\in R^{c}\right)\lor\left(\left(c,a\right)\in R^{c}\land\left(c,b\right)\in R\right)\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \lnot\left(\exists c\in X,\left(\left(a,c\right)\in R^{-1}\land\left(c,b\right)\in R^{c}\right)\lor\left(\left(c,a\right)\in R^{c}\land\left(b,c\right)\in R^{-1}\right)\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \lnot\left(\left(\exists c\in X,\left(a,c\right)\in R^{-1}\land\left(c,b\right)\in R^{c}\right)\lor\left(\exists c\in X,\left(c,a\right)\in R^{c}\land\left(b,c\right)\in R^{-1}\right)\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\cmt{\because\exists x\left(P\left(x\right)\lor Q\left(x\right)\right)\Leftrightarrow\exists xP\left(x\right)\lor\exists xQ\left(x\right)}\\ \Leftrightarrow & \lnot\left(\left(a,b\right)\in R^{c}\circ R^{-1}\lor\left(b,a\right)\in R^{c}\circ R^{-1}\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \lnot\left(\left(a,b\right)\in R^{c}\circ R^{-1}\lor\left(a,b\right)\in\left(R^{c}\circ R^{-1}\right)^{-1}\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \lnot\left(\left(a,b\right)\in\left(R^{c}\circ R^{-1}\right)\cup\left(R^{c}\circ R^{-1}\right)^{-1}\right)\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \left(a,b\right)\in\left(\left(R^{c}\circ R^{-1}\right)\cup\left(R^{c}\circ R^{-1}\right)^{-1}\right)^{c}\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \left(a,b\right)\in\left(R^{c}\circ R^{-1}\right)^{c}\cap\left(R^{c}\circ R^{-1}\right)^{-1,c}\rightarrow\left(a,b\right)\in\Delta_{Y}\\ \Leftrightarrow & \left(R^{c}\circ R^{-1}\right)^{c}\cap\left(R^{c}\circ R^{-1}\right)^{-1,c}\subseteq\Delta_{Y} \end{align*} となるので題意は成り立つ。
(12)
\(\Rightarrow\)
任意の\(\left(a,b\right)\in\Delta_{X}\)を選ぶ。このとき、\(\left(a,b\right)\in\Delta_{X}=\left\{ \left(x,x\right);x\in X\right\} \)より、\(a=b\)となる。
また、前件より、\(R\)は左全域性を満たすので、\(a\)について、ある\(c\in Y\)が存在し\(\left(a,c\right)\in R\)となる。
これより、\(\left(c,a\right)\in R^{-1}\)となるので、\(\left(a,b\right)=\left(a,a\right)\in R^{-1}\circ R\)となる。
従って、\(\Delta_{X}\subseteq R^{-1}\circ R\)となる。
故に\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(a\in X\)を選ぶ。そうすると、\(\left(a,a\right)\in\Delta_{X}\)であり、前件より\(\Delta_{X}\subseteq R^{-1}\circ R\)であるので、\(\left(a,a\right)\in\Delta_{X}\subseteq R^{-1}\circ R\)となる。
これより、ある\(b\in Y\)が存在し、\(\left(a,a\right)\in R^{-1}\circ R\)より、\(\left(b,a\right)\in R^{-1}\)かつ\(\left(a,b\right)\in R\)となる。
従って、任意の\(a\in X\)についてある\(b\in Y\)が存在し、\(\left(a,b\right)\in R\)となるので左全域性を満たす
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。右全域性についても同様である。
また、\(\dom\left(R\right)=\left\{ a\in X;\exists b\in Y,\left(a,b\right)\in R\right\} \)であるので、\(R\)が左全域性を満たすことと、\(\dom\left(R\right)=\left\{ a\in X;\exists b\in Y,\left(a,b\right)\in R\right\} =X\)となること同値となる。
同様に\(\cod\left(R\right)=\left\{ b\in Y;\exists a\in X,\left(a,b\right)\in R\right\} \)であるので、\(R\)が右全域性を満たすことと、\(\cod\left(R\right)=\left\{ b\in Y;\exists a\in X,\left(a,b\right)\in R\right\} =Y\)となること同値となる。
(13)
\(\Rightarrow\)
\(\left(Y\times Y\right)\circ R\subseteq X\times Y\)は明らかに成り立つので、\(X\times Y\subseteq\left(Y\times Y\right)\circ R\)を示す。任意の\(\left(a,b\right)\in X\times Y\)を選ぶ。
このとき、前件より\(R\)は左全域性を満たすので、ある\(c\in Y\)が存在し、\(\left(a,c\right)\in R\)となる。
そうすると、\(c,b\in Y\)なので、\(\left(c,b\right)\in Y\times Y\)となり、\(\left(a,b\right)\in Y\times Y\circ R\)となる。
従って、\(X\times Y\subseteq\left(Y\times Y\right)\circ R\)となる。
これらより、\(\subseteq\)と\(\supseteq\)が成り立つので、\(\left(Y\times Y\right)\circ R=X\times Y\)が成り立つ。
従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
任意の\(a\in X\)を選ぶ。このとき、\(Y\ne\emptyset\)なので適当に\(b\in Y\)を選ぶことができ、\(\left(a,b\right)\in X\times Y\)となるので、\(\left(a,b\right)\in X\times Y=\left(Y\times Y\right)\circ R\)となる。
これより、ある\(c\in Y\)が存在し、\(\left(c,b\right)\in Y\times Y\)かつ\(\left(a,c\right)\in R\)となる。
従って、任意の\(a\in X\)について、ある\(c\in Y\)が存在し、\(\left(a,c\right)\in R\)となるので、\(R\)が左全域性を満たす。
故に\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。
ページ情報
| タイトル | 集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・整礎律・全域性・集合性の定義)の定義と性質 |
| URL | https://www.nomuramath.com/mi6xjdt2/ |
| SNSボタン |
2つの集合上の二項関係(一意性・全域性)の定義
\[
aRc\land bRc\Rightarrow a=b
\]
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・外延律・整礎律・全域性・集合性の定義)の定義と性質
2...
隣接関係の定義
\[
\forall x,y\in X,x\nsim x\land\left(x\sim y\rightarrow y\sim x\right)
\]
自明な同値関係と相等関係
\[
\forall x,y\in X,x\sim y
\]