同値関係と順序関係(前順序・弱順序・半順序・全順序・整列順序・狭義半順序・狭義全順序)の定義
同値関係と順序関係(前順序・弱順序・半順序・全順序・整列順序・狭義半順序・狭義全順序)の定義
このとき、非対称律を満たす。
(1)同値関係
反射律・対称律・推移律を満たす2項関係を同値関係という。(2)前順序関係
反射律・推移律を満たす2項関係を前順序関係という。(3)弱順序関係
前順序関係(反射律・推移律)で完全律を満たす2項関係を弱順序関係という。(4)半順序関係
前順序関係(反射律・推移律)で反対称律を満たす2項関係を半順序関係という。(5)全順序関係
半順序関係(反射律・推移律・反対称律)で完全律を満たす2項関係を全順序関係という。(6)整列順序関係
全順序関係(反射律・推移律・反対称律・完全律)で整礎律を満たす2項関係を整列順序関係という。(7)狭義半順序関係
非反射律・推移律を満たす2項関係を狭義半順序関係という。このとき、非対称律を満たす。
(8)狭義全順序関係
狭義半順序関係(非反射律・推移律)で3分律を満たす2項関係を狭義全順序関係という。-
同値関係の例としては等号\(=\)の他に剰余演算や合同や相似などがある。-
グー・チョキ・パーの関係は推移律を満たさない。グーを\(a\)、チョキを\(b\)、パーを\(c\)で表し、順序を\(\preceq\)で表す。
推移律を満たすと仮定する。
すると\(c\preceq b\land b\preceq a\Rightarrow c\preceq a\)となるが\(a\preceq c\)なので矛盾。
したがって背理法より、推移律を満たさない。
反射律・対称律・推移律を満たさない例。
反例:\(0\sim0\)は成り立たないので反射律は成り立たない。
反例:\(1\leq2\)であるが\(2\leq1\)とはならないので対称律は満たさない。
反例:\(3\sim2,2\sim1\)は成り立つが\(3\sim1\)は成り立たないので推移律は満たさない。
反例:\(1\sim3\)は成り立つが\(3\sim1\)は成り立たないので対称律は満たさない。
\(2\sim1,1\sim0\)は成り立つが\(2\sim0\)は成り立たないので推移律は成り立たない。
反例:\(1\ne2,2\ne1\)であるが\(1\ne1\)とはならないので推移律は成り立たない。
反例:\(a\in\left\{ a\right\} ,\left\{ a\right\} \in\left\{ \left\{ a\right\} \right\} \)であるが\(a\in\left\{ \left\{ a\right\} \right\} \)とはならないので推移律は満たさない。
また、反射律も対称律も満たさない。
(1)反射律・対称律・推移律を満たす例
-
全体集合を\(X=\emptyset\)として2項関係を\(R=\emptyset\)とする。-
全体集合を\(X\)として2項関係を\(R=\left\{ \left(a,b\right)\in X^{2}\right\} \)とする。(2)対称律と推移律を満たすが反射律は満たさない例
-
全体集合を\(X=\left\{ a,b,c\right\} \)として2項関係を\(R=\left\{ \left(b,c\right),\left(c,b\right),\left(b,b\right),\left(c,c\right)\right\} \)とする。-
\(a\sim b\Leftrightarrow ab>0\)とする。反例:\(0\sim0\)は成り立たないので反射律は成り立たない。
(3)反射律と推移律を満たすが対称律は満たさない例
-
全体集合を\(X=\left\{ a,b\right\} \)として2項関係を\(R=\left\{ \left(a,a\right),\left(a,b\right),\left(b,b\right)\right\} \)とする。-
2項関係を\(\leq\)とする。反例:\(1\leq2\)であるが\(2\leq1\)とはならないので対称律は満たさない。
(4)反射律と対称律を満たすが推移律は満たさない例
-
全体集合を\(X=\left\{ a,b,c\right\} \)として2項関係を\(R=\left\{ \left(a,a\right),\left(a,b\right),\left(b,a\right),\left(b,b\right),\left(b,c\right),\left(c,b\right),\left(c,c\right)\right\} \)とする。-
2項関係を\(a\sim b\Leftrightarrow\left|a-b\right|\leq1\)とする。反例:\(3\sim2,2\sim1\)は成り立つが\(3\sim1\)は成り立たないので推移律は満たさない。
(5)反射律を満たすが対称律と推移律は満たさない例
-
全体集合を\(X=\left\{ a,b,c\right\} \)として2項関係を\(R=\left\{ \left(a,a\right),\left(a,b\right),\left(b,b\right),\left(b,c\right),\left(c,c\right)\right\} \)とする。-
2項関係を\(a\sim b\Leftrightarrow a-b\leq1\)とする。反例:\(1\sim3\)は成り立つが\(3\sim1\)は成り立たないので対称律は満たさない。
\(2\sim1,1\sim0\)は成り立つが\(2\sim0\)は成り立たないので推移律は成り立たない。
(6)対称律を満たすが反射律と推移律は満たさない例
-
全体集合を\(X=\left\{ a,b\right\} \)として2項関係を\(R=\left\{ \left(a,b\right),\left(b,a\right)\right\} \)とする。-
2項関係を\(\ne\)とする。反例:\(1\ne2,2\ne1\)であるが\(1\ne1\)とはならないので推移律は成り立たない。
(7)推移律を満たすが反射律と対称律は満たさない例
-
全体集合を\(X=\left\{ a,b,c\right\} \)として2項関係を\(R=\left\{ \left(a,b\right),\left(b,c\right),\left(a,c\right)\right\} \)とする。-
2項関係を\(<\)とする。(8)反射律も対称律も推移律も満たさない例
-
全体集合を\(X=\left\{ a,b,c\right\} \)として2項関係を\(R=\left\{ \left(a,b\right),\left(b,c\right)\right\} \)とすると、反射律も対称律も推移律も満たさない。-
2項関係を\(\in\)とする。反例:\(a\in\left\{ a\right\} ,\left\{ a\right\} \in\left\{ \left\{ a\right\} \right\} \)であるが\(a\in\left\{ \left\{ a\right\} \right\} \)とはならないので推移律は満たさない。
また、反射律も対称律も満たさない。
(1)前順序関係
順序対\(\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\in\mathbb{R}^{2}\)に対し、\(\left(a_{1},a_{2}\right)R\left(b_{1},b_{2}\right)\Leftrightarrow\left|a_{1}\right|\leq\left|b_{1}\right|\land\left|a_{2}\right|\leq\left|b_{2}\right|\)は前順序関係になる。しかし、\(\left(a_{1},a_{2}\right)=\left(1,1\right),\left(b_{1},b_{2}\right)=\left(-1,-1\right)\)とすると\(aRb,bRa\)は共に成り立つが、\(\left(a_{1},a_{2}\right)\ne\left(b_{1},b_{2}\right)\)であるので反対称律を満たさないので半順序関係ではない。
また\(\left(a_{1},a_{2}\right)=\left(0,1\right),\left(b_{1},b_{2}\right)=\left(1,0\right)\)のとき比較不能なので完全律を満たさなく弱順序関係でもない。
(2)弱順序関係
\(a,b\in\mathbb{R}\)として\(aRb\Leftrightarrow\left|a\right|\leq\left|b\right|\)とすると、弱順序関係になる。しかし、\(a=1,b=-1\)とすると\(aRb,bRa\)であるが、\(a\ne b\)であるので反対称律を満たさなく半順序関係ではない。
(3)半順序関係
\(R=\left\{ \left(A,B\right)\in\left\{ \left\{ x\right\} ,\left\{ x,y\right\} ,\left\{ x,z\right\} \right\} ;A\subseteq B\right\} \)すなわち、\(A,B\in\left\{ \left\{ x\right\} ,\left\{ x,y\right\} ,\left\{ x,z\right\} \right\} \)として\(ARB\Leftrightarrow A\subseteq B\)とすると半順序関係にあるが全順序関係ではない。例えば\(\left\{ x\right\} R\left\{ x,y\right\} \)であるが、\(\left\{ x,y\right\} \)と\(\left\{ x,z\right\} \)は比較不能であるので完全律を満たさなく全順序関係ではない。
(4)半順序関係
順序対\(\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\in\mathbb{R}^{2}\)に対し、\(\left(a_{1},a_{2}\right)R\left(b_{1},b_{2}\right)\Leftrightarrow a_{1}\leq b_{1}\land a_{2}\leq b_{2}\)は半順序関係であるが全順序関係ではない。例えば\(\left(1,2\right)R\left(2,3\right)\)であるが、\(\left(1,4\right)\)と\(\left(2,3\right)\)は比較不能であるので完全律を満たさなく全順序関係ではない。
(5)全順序関係
\(R=\left\{ \left(a,b\right)\in\mathbb{R}^{2};a\leq b\right\} \)すなわち、\(a,b\in\mathbb{R}\)として\(aRb\Leftrightarrow a\leq b\)とすると全順序関係となる。(6)整列順序関係
\(R=\left\{ \left(a,b\right)\in\mathbb{N}^{2};a\leq b\right\} \)すなわち、\(a,b\in\mathbb{N}\)として\(aRb\Leftrightarrow a\leq b\)とすると整列順序関係となる。(7)狭義半順序関係
\(A,B\)を集合として\(ARB\Leftrightarrow A\subsetneq B\)とすると、狭義半順序関係であるが狭義全順序関係ではない。例えば\(A=\left\{ a\right\} ,B=\left\{ b\right\} \)とすると、\(A\subsetneq B\)も\(B\subsetneq A\)も\(A=B\)も満たさないので3分律を満たさなく狭義全順序関係ではない。
(8)狭義半順序関係
順序対\(\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\in\mathbb{R}^{2}\)に対し、\(\left(a_{1},a_{2}\right)R\left(b_{1},b_{2}\right)\Leftrightarrow a_{1}<b_{1}\land a_{2}<b_{2}\)は狭義半順序関係であるが狭義全順序関係ではない。例えば\(\left(1,4\right)R\left(2,3\right)\)も\(\left(2,3\right)R\left(1,4\right)\)も\(\left(1,4\right)=\left(2,3\right)\)も満たさないので3分律を満たさなく狭義全順序関係ではない。
(9)狭義全順序関係
\(R=\left\{ \left(a,b\right)\in\mathbb{R}^{2};a<b\right\} \)すなわち、\(a,b\in\mathbb{R}\)として\(aRb\Leftrightarrow a<b\)とすると狭義全順序関係となる。ページ情報
タイトル | 同値関係と順序関係(前順序・弱順序・半順序・全順序・整列順序・狭義半順序・狭義全順序)の定義 |
URL | https://www.nomuramath.com/ltlky102/ |
SNSボタン |
2項関係の性質
\[
a=b\Rightarrow aRb\land bRa
\]
隣接関係の定義
\[
\forall x,y\in X,x\nsim x\land\left(x\sim y\rightarrow y\sim x\right)
\]
2項関係の定義
\[
\left(a,b\right)\in R\Leftrightarrow aRb
\]
集合の色々な2項関係(反射律・非反射律・余反射律・対称律・反対称律・非対称律・推移律・完全律・3分律・ユークリッド律・連続律・集合律・整礎律・外延律の定義)の定義
\[
\forall a\in X,a
\]