順序に関する諸概念
from 論理と集合から始める数学の基礎 読書会
数式を/takker/位相空間問題集#6561b1c81280f00000859d2aより拝借
任意の半順序集合$ (X,\le)と$ A\subseteq X,s,i\in Xについて、
$ sが$ Aの上界である$ :\iff A \le s:\iff\forall a\in A;a\le s
$ iが$ Aの下界である$ :\iff i\le A:\iff\forall a\in A;i\le a
$ Aが上に有界である$ :\iff\exist s\in X;A\le s
$ Aが下に有界である$ :\iff\exist i\in X;i\le A
上界と下界の記号は、半順序関係をそのまま流用した
/mrsekut-p/上限#62a74428198270000013c636を真似た
正直紛らわしいので、別の記法を考えたいtakker.icon
$ sが$ Aの最大値$ :\iff s\in A\land A\le s
存在するなら一意で、$ s=\max Aと書く
$ \because\forall x,y\in X.
$ x\in A\land A\le x\land y\in A\land A\le y
$ \iff x,y\in A\land\forall a\in A.a\le x\land\forall a\in A.a\le y
$ \implies y\le x\land x\le y
$ \implies x=y
$ \because反対称律
これ前順序じゃ成り立たないのかtakker.icon
前順序集合だと最大値/最小値の一意性が成り立たないのは驚き
むむ？nishio.icon
あー、なるほど、前順序集合だと反対称律がないからサイクルになってるとかのときに「存在して、かつ一意じゃない」ってなるのか
$ x⇄yのような2要素間のサイクルのときですねtakker.icon
3要素以上のときも、推移律を使えば2要素間サイクルに帰着できる
$ m_1,m_2が最大元で、$ m_1\neq m_2の例
https://kakeru.app/0cb060287e1ade45363afab8634d3526 https://i.kakeru.app/0cb060287e1ade45363afab8634d3526.svg
cf. 9.7 演習問題9.1
存在するなら上限と等しい
証明
$ \forall x\in X.
$ x=\max A
$ \iff x\in A\land A\le x
$ \iff x\in\{s\in X|A\le s\}\land x\in A
$ \iff x\in\{s\in X|A\le s\}\land x\in A\land\forall s\in X.((\forall a\in A.a\le s)\implies x\le s)
$ \because x\in Aなので、$ \forall a\in A.a\le sに$ a=xを代入すれば$ x\le sが導かれる
$ \iff x\in\{s\in X|A\le s\}\land x\in A\land\forall s\in X.(A\le s\implies x\le s)
$ \iff x\in\{s\in X|A\le s\}\land x\in A\land\forall s\in\{s\in X|A\le s\}.x\le s
$ \iff x\in\{s\in X|A\le s\}\land x\in A\land x\le\{s\in X|A\le s\}
$ \iff x=\sup A\land x\in A
$ \underline{\implies x=\sup A\quad}_\blacksquare
どうやら$ x=\max A\iff x=\sup A\land x\in Aらしいなtakker.icon
$ iが$ Aの最小値$ :\iff i\in A\land i\le A
存在するなら一意で、$ i=\min Aと書く
$ \because\forall x,y.
$ x\in A\land A\ge x\land y\in A\land A\ge y
$ \iff x,y\in A\land\forall a\in A.a\ge x\land\forall a\in A.a\ge y
$ \implies y\ge x\land x\ge y
$ \implies x=y
$ \because反対称律
存在するなら下限と等しい
証明
$ \forall x\in X.
$ x=\min A
$ \iff x\in A\land x\le A
$ \iff x\in\{s\in X|s\le A\}\land x\in A
$ \iff x\in\{s\in X|s\le A\}\land x\in A\land\forall s\in X.((\forall a\in A.s\le a)\implies s\le x)
$ \because x\in Aなので、$ \forall a\in A.s\le aに$ a=xを代入すれば$ s\le xが導かれる
$ \iff x\in\{s\in X|s\le A\}\land x\in A\land\forall s\in X.(s\le A\implies s\le x)
$ \iff x\in\{s\in X|s\le A\}\land x\in A\land\forall s\in\{s\in X|s\le A\}.s\le x
$ \iff x\in\{s\in X|s\le A\}\land x\in A\land\{s\in X|s\le A\}\le x
$ \iff x=\inf A\land x\in A
$ \underline{\implies x=\inf A\quad}_\blacksquare
先ほどと同様、$ x=\min A\iff x=\inf A\land x\in Aらしいtakker.icon
$ sが$ Aの上限$ :\iff s\in\{s\in X|A\le s\}\land s\le\{s\in X|A\le s\}
存在するなら一意で、$ s=\sup A(=\min\{s\in X|A\le s\})と書く
$ \because\supは$ \minで書き換えられるが、$ \minは存在すれば一意に定まるので、$ \supも一意に定まる
2元集合のとき、二項演算結び$ x\vee y:=\sup\{x,y\}を定義する
$ iが$ Aの下限$ :\iff i\in\{i\in X|i\le A\}\land \{i\in X|i\le A\}\le i
存在するなら一意で、$ i=\inf A(=\max\{i\in X|i\le A\})と書く
$ \because\infは$ \maxで書き換えられるが、$ \maxは存在すれば一意に定まるので、$ \infも一意に定まる
2元集合のとき、二項演算交わり$ x\wedge y:=\inf\{x,y\}を定義する
$ Mが$ Aの極大元$ :\iff M\in A\land\lnot\exist a\in A;M\le a\land M\neq a
$ M\in A\land\forall a\in A.(M\le a\implies M=a)のほうがわかりやすい
全順序なら最大元と一致する
証明
$ \forall M\in X.
$ M=\max A
$ \iff M\in A\land\forall a\in A.a\le M
$ \forall x,y\in X.x\le y\lor y\le x
$ \iff M\in A\land\forall a\in A.a\le M
$ \land\forall a\in A.(M\le a\implies M\le a\land a\le M\implies M=a)
$ \because反対称律
$ \implies M\in A\land\forall a\in A.(M\le a\implies M=a)
$ \forall M\in X.
$ \begin{dcases}M\in A\land\forall a\in A.(M\le a\implies M=a)\\\forall x,y\in A. x\le y\lor y\le x\end{dcases}
$ \implies \begin{dcases}M\in A\land\forall a\in A.(M\le a\implies M=a)\\\forall a\in A.M\le a\lor a\le M\end{dcases}
$ \implies \begin{dcases}M\in A\\\forall a\in A.M=a\lor a\le M\end{dcases}
$ \iff M\in A\land\forall a\in A.a\le M
$ \iff M=\max A
以上より、半順序集合なら最大元があるならそれが極大元に、全順序集合だと極大元が存在するならそれが最大元になる
$ mが$ Aの極小元$ :\iff m\in A\land\lnot\exist a\in A;a\le m\land m\neq a
全順序なら最小元と一致する
(証明略)
空でない有限全順序集合には必ず(最大元|最小元)が存在する
例9.7
例9.8
例9.9