2項関係の性質
2項関係の性質
\[ a=b\Rightarrow aRb\land bRa \] が成り立つ。
\[ aRb\land bRa\Leftrightarrow a=b \] が成り立つ。
逆は一般的に成り立たない。
(1)
対称律・推移律・連続律を満たすなら反射律を満たす。(2)
反射律が成り立つとき、反対称律の逆\[ a=b\Rightarrow aRb\land bRa \] が成り立つ。
(3)
反射律・反対称律が成り立つとき、\[ aRb\land bRa\Leftrightarrow a=b \] が成り立つ。
(4)
非対称律を満たすならば非反射律を満たす。逆は一般的に成り立たない。
(5)
非対称律を満たすことと、反対称律かつ非反射律を満たすことは同値である。(1)
対称律・推移律・連続律を満たすとき、\begin{align*} \top & \Leftrightarrow\forall a\exists b,aRb\land aRb\\ & \Leftrightarrow\forall a\exists b,aRb\land bRa\\ & \Rightarrow\forall a,aRa \end{align*} となり、\(\forall a,aRa\)は真となるので反射律を満たす。
(2)
反射律\(aRa\)が成り立っているので、\begin{align*} a=b & \Leftrightarrow\left(aRa\land bRb\right)\land a=b\\ & \Leftrightarrow\left(aRa\land a=b\right)\land\left(bRb\land b=a\right)\\ & \Leftrightarrow\left(aRb\land a=b\right)\land\left(bRa\land b=a\right)\\ & \Leftrightarrow\left(aRb\land bRa\right)\land a=b\\ & \Rightarrow aRb\land bRa \end{align*} となり題意は成り立つ。
(3)
反射律が成り立っているとき、(2)より\(a=b\Rightarrow aRb\land bRa\)が成り立ち、反対称律が成り立っているとき、\(aRb\land bRa\Rightarrow a=b\)が成り立つ。従って反射律・反対称律が成り立つとき、\(aRb\land bRa\Leftrightarrow a=b\)が成り立つ。
(4)
\(\Rightarrow\)
集合\(X\)上に2項関係\(R\)があり、非対称律を満たすとする。このとき、\(\forall a,b\in X,aRb\rightarrow\lnot\left(bRa\right)\)であるので、\(a=b\)とすると、\(\top\Leftrightarrow aRa\rightarrow\lnot\left(aRa\right)\Leftrightarrow\lnot aRa\lor\lnot\left(aRa\right)\Leftrightarrow\lnot\left(aRa\right)\)となるので、\(\forall a\in X,\lnot\left(aRa\right)\)となり、非反射律を満たす。
逆は一般的に成り立たない。
反例で示す。集合を\(X=\left\{ a,b\right\} \)として、2項関係を\(R=\left\{ \left(a,b\right),\left(a,b\right)\right\} \)とすると、非反射律を満たす。
しかし、\(aRb\rightarrow\lnot\left(bRa\right)\Leftrightarrow\top\rightarrow\lnot\top\Leftrightarrow\top\rightarrow\bot\Leftrightarrow\bot\)となるので、非対称律を満たさない。
従って、逆は一般的に成り立たない。
(5)
次を使う。\(R\)が非対称律を満たすことと、\(R\cap R^{-1}=\emptyset\)となることは同値である。
\(R\)が反対称律を満たすことと、\(R\cap R^{-1}\subseteq\Delta_{X}\)となることは同値である。
\(R\)が非反射律を満たすことと、\(R\subseteq\Delta_{X}^{c}\)を満たすことは同値である。
\(\Rightarrow\)
前件より、\(R\)が非対称律であるので、\(R\cap R^{-1}=\emptyset\)となる。このとき、\(R\cap R^{-1}=\emptyset\subseteq\Delta_{X}\)となるので、反対称律を満たす。
次に、\(R\cap R^{-1}=\emptyset\)かつ\(R\nsubseteq\Delta_{X}^{c}\)となると仮定する。
そうすると、\(\top\Leftrightarrow R\nsubseteq\Delta_{X}^{c}\Leftrightarrow R\cap\Delta_{X}\ne\emptyset\)となるので、ある\(a\in X\)が存在して、\(\left(a,a\right)\in R\cap\Delta_{X}\)となる。
このとき、\(\left(a,a\right)\in R\)かつ\(\left(a,a\right)\in\Delta_{X}\)となり、\(\left(a,a\right)\in R\)より、\(R\cap R^{-1}\ne\emptyset\)となるが、\(R\cap R^{-1}=\emptyset\)なので矛盾。
従って背理法より、\(R\cap R^{-1}=\emptyset\)ならば\(R\subseteq\Delta_{X}^{c}\)となる。
これより、非反射律を満たす。
これらより、反対称律・非反射律を満たす。
従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
\(R\)が反対称律・非反射律を満たすとき、\(R\cap R^{-1}\subseteq\Delta_{X}\)かつ\(R\subseteq\Delta_{X}^{c}\)を満たすので、\begin{align*} R\cap R^{-1}\subseteq\Delta_{X}\land R\subseteq\Delta_{X}^{c} & \Leftrightarrow R\cap R^{-1}\subseteq\Delta_{X}\land\Delta_{X}\subseteq R^{c}\\ & \Rightarrow R\cap R^{-1}\subseteq R^{c}\land\Delta_{X}\subseteq R^{c}\\ & \Rightarrow R\cap R^{-1}\subseteq R^{c}\\ & \Rightarrow R\cap R^{-1}\subseteq R^{c}\cup R^{-1,c}\\ & \Leftrightarrow R\cap R^{-1}\subseteq\left(R\cap R^{-1}\right)^{c}\\ & \Leftrightarrow R\cap R^{-1}=\emptyset \end{align*} となり、\(R\cap R^{-1}=\emptyset\)となるので\(R\)は非対称律を満たす。
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので、\(\Leftrightarrow\)が成り立つ。ページ情報
| タイトル | 2項関係の性質 |
| URL | https://www.nomuramath.com/uguho9u7/ |
| SNSボタン |
2つの集合上の二項関係(一意性・全域性)の定義
\[
aRc\land bRc\Rightarrow a=b
\]
2項関係の性質
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
\]

