順序集合

定義

定義1. 二項関係 \(\le\) の諸性質

集合 \(S\) および \(S\) 上の二項関係 \(\le\) について
論理式 \(P_i(S,\le)\ (i=1,2,3,4)\) を以下のように定義する.

\begin{align} &P_1(S,\le)\triangleq \{\forall x\in S\left(x\le x\right)\} &&[反射律]\\[2pt] &P_2(S,\le)\triangleq \{\forall x,y,z\in S\left(x\le y\wedge y\le z\rightarrow x\le z\right)\} &&[推移律]\\[2pt] &P_3(S,\le)\triangleq \{\forall x,y\in S\left(x\le y\wedge y\le x\rightarrow x=y\right)\} &&[反対称律]\\[2pt] &P_4(S,\le)\triangleq \{\forall x,y\in S\left(x\le y\vee y\le x\right)\} &&[全順序律]\\[2pt] \end{align}

定義2. 順序

集合 \(S\) および \(S\) 上の二項関係 \(\le\) について \[ \leが\ S\ 上の前順序である\overset{\mathrm{def}}{\iff} P_1(S,\le)\wedge P_2(S,\le) \] \[ \leが\ S\ 上の半順序である\overset{\mathrm{def}}{\iff} P_1(S,\le)\wedge P_2(S,\le)\wedge P_3(S,\le) \] \[ \leが\ S\ 上の全順序である\overset{\mathrm{def}}{\iff} P_1(S,\le)\wedge P_2(S,\le)\wedge P_3(S,\le)\wedge P_4(S,\le) \]

定義3. 順序集合

集合 \(S\) および \(S\) 上の二項関係 \(\le\) について

\[ (S,\le)\ が前順序集合である\overset{\mathrm{def}}{\iff} \leが\ S\ 上の前順序である \] \[ (S,\le)\ が半順序集合である\overset{\mathrm{def}}{\iff} \leが\ S\ 上の半順序である \] \[ (S,\le)\ が全順序集合である\overset{\mathrm{def}}{\iff} \leが\ S\ 上の全順序である \]

定義4. 上界と下界

半順序集合 \((S,\le)\) および \(x\in S,\ A\subseteq S\) について

\[ x\ が\ A\ の上界である\overset{\mathrm{def}}{\iff} \forall y\in S\left(y\le x\right) \] \[ x\ が\ A\ の下界である\overset{\mathrm{def}}{\iff} \forall y\in S\left(x\le y\right) \]

また

\[ U\triangleq\{x\in S\ |\ x\ が\ A\ の上界である\} \] \[ L\triangleq\{x\in S\ |\ x\ が\ A\ の下界である\} \]

とすれば

\[ x\ が\ A\ の最小上界である\overset{\mathrm{def}}{\iff} x\in U\wedge\forall z\in U\left(x\le z\right) \] \[ x\ が\ A\ の最大下界である\overset{\mathrm{def}}{\iff} x\in L\wedge\forall z\in L\left(z\le x\right) \]