集合の色々な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\)である。
任意の\(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\in X,\exists b\in X,aRb\)である。
例:集合として整数\(\mathbb{Z}\)を考えると、\(<\)も\(>\)も連続律を満たす。
例:集合として自然数\(\mathbb{N}\)を考えると、\(<\)は連続律を満たすが、\(>\)は連続律を満たさない。
例:2つの集合同士の関係や\(\in\)の関係は集合律となる。
例:部分集合として自然数\(\mathbb{N}\)を考えると、\(\leq\)も\(<\)も整礎律を満たす。
すなわち\(\forall a,b,c\in X,cRa\leftrightarrow cRb\Rightarrow a=b\)である。
例:\(=\)は外延律を満たす。
集合\(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\)である。
任意の\(a,b,c\in X\)に対し\(aRc\)かつ\(bRc\)ならば\(aRb\)かつ\(bRa\)となるとき、\(R\)は左ユークリッド律を満たすという。
すなわち\(\forall a,b,c\in X,aRc\land bRc\rightarrow aRb\land bRa\)である。
例:\(=\)は右ユークリッド律を満たし、左ユークリッド律も満たす。
(11)連続律(serial)
任意の\(a\in X\)に対し、ある\(b\in X\)が存在し、\(aRb\)が成り立つとき、\(R\)は連続律を満たすという。すなわち\(\forall a\in X,\exists b\in X,aRb\)である。
例:集合として整数\(\mathbb{Z}\)を考えると、\(<\)も\(>\)も連続律を満たす。
例:集合として自然数\(\mathbb{N}\)を考えると、\(<\)は連続律を満たすが、\(>\)は連続律を満たさない。
(12)集合律(set-like)
任意の\(a\in X\)に対し\(\left\{ b\in Y;bRa\right\} \)が集合となるとき、\(R\)を集合律を満たすという。例:2つの集合同士の関係や\(\in\)の関係は集合律となる。
(13)整礎律(well-founded)
集合\(X\)の任意の空でない部分集合\(A\)が極小元\(a\)を持つとき、\(R\)は整礎律を満たすという。例:部分集合として自然数\(\mathbb{N}\)を考えると、\(\leq\)も\(<\)も整礎律を満たす。
(14)外延律(extensive)
任意の\(a,b,c\in X\)に対し、\(cRa\Leftrightarrow cRb\)ならば\(a=b\)となるとき、\(R\)は外延律を満たすという。すなわち\(\forall a,b,c\in X,cRa\leftrightarrow cRb\Rightarrow a=b\)である。
例:\(=\)は外延律を満たす。
反対称律の条件は以下と同値である。
\(\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*} となるからである。
\(\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項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・連続律・集合律・整礎律・外延律の定義)の定義 |
URL | https://www.nomuramath.com/mi6xjdt2/ |
SNSボタン |
自明な同値関係と相等関係
\[
\forall x,y\in X,x\sim y
\]
2項関係の定義
\[
\left(a,b\right)\in R\Leftrightarrow aRb
\]
隣接関係の定義
\[
\forall x,y\in X,x\nsim x\land\left(x\sim y\rightarrow y\sim x\right)
\]
同値関係と順序関係(前順序・弱順序・半順序・全順序・整列順序・狭義半順序・狭義全順序)の定義