generated at
順序に関する諸概念
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
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
前順序集合だと最大値/最小値の一意性が成り立たないのは驚き
むむ？nishio
あー、なるほど、前順序集合だと反対称律がないからサイクルになってるとかのときに「存在して、かつ一意じゃない」ってなるのか
x⇄yのような2要素間のサイクルのときですねtakker
3要素以上のときも、推移律を使えば2要素間サイクルに帰着できる
m_1,m_2が最大元で、m_1\neq m_2の例
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
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
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