狭義の順序
from 論理と集合から始める数学の基礎 読書会
非反射律\forall x\in U.\lnot(x<x)
無反射律とも
非反射的反対称律\forall x,y\in U.x<y\implies\lnot(y<x)
非対称律とも
推移律\forall x,y,z\in U.x<y\land y<z\implies x<z
三分律\forall x,y\in U.x<y\veebar y<x\veebar x=y
\veebarは排他的論理和
テキストは\lorを採用している
\begin{dcases}\forall x\in U.\lnot(x<x)\\\forall x,y,z\in U.x<y\land y<z\implies x<z\end{dcases}
\implies\begin{dcases}\forall x\in U.\lnot(x<x)\\\forall x,y\in U.x<y\land y<x\implies x<x\end{dcases}
\implies\forall x,y\in U.x<y\land y<x\implies\bot
\iff\forall x,y\in U.\lnot(x<y\land y<x)
\iff\forall x,y\in U.\lnot(x<y)\lor\lnot(y<x)
\underline{\iff\forall x,y\in U.x<y\implies\lnot(y<x)\quad}_\blacksquare
2. x<y:\iff(x\le y\land x\neq y)とする。以下を証明せよ
非反射律は\leが任意の2項関係でも成り立つ
\forall x\in U.
x<x
\iff x\le x\land x\neq x
\implies x\neq x
\iff\bot
\therefore\forall x\in U.\lnot(x<x)
推移律
\forall x,y,z\in U.
x<y\land y<z
\iff x\le y\land x\neq y\land y\le z\land y\neq z
\iff x\le y\land x\neq y\land y\le z\land y\neq z
\land(x=z\implies x\le y\land y\le x
\implies x=y
\because半順序集合の反対称律
\implies\bot)
\because x\neq y
\implies x\le y\le z\land x\neq z
\implies x\le z\land x\neq z
\because半順序集合の推移律
\iff x<z
(U,\le)は半順序集合でもあるので、非反射律と推移律が成り立つことは2.1.より自明
三分律が成り立つことを示す
\forall x,y\in U.x<y\lor y<x\lor x=y
\iff\forall x,y\in U.x<y\lor x=y\lor y<x\lor x=y
\underline{\iff\forall x,y\in U.x\le y\lor y\le x\quad}_\blacksquare
3. x\le y:\iff x<y\lor x=yとする。以下を証明せよ
3. 1. 2.1.の逆が成り立つことを示せ
反射律
推移律
反対称律
3. 2. 2.2.の逆が成り立つことを示せ
完全律