2項関係の性質

2項関係の性質

(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ボタン