狭義大小関係

引用WIIS 定義 10反射律、11反対称律、12推移律、13完備律を備えののが大小関係。 狭義大小関係は、上に加えて同値関係が成り立たないもの。 x<y⇔x≤y∧x≠y 定理 x<y⇒¬(y<x) の証明。 感覚的には自明なんだけど一応。...

riku-nagahama.xyz

2025.03.18

大小関係

大小関係の定義。

広義大小関係

ここで P は集合であり、「≤」を P 上で定義された二項関係とする。

反射律：P の任意の元 a に対し、a ≤ a が成り立つ。

推移律：P の任意の元 a, b, c に対し、a ≤ b かつ b ≤ c ならば a ≤ c が成り立つ。

反対称律：P の任意の元 a, b に対し、a ≤ b かつ b ≤ a ならば a = b が成り立つ。

全順序律：P の任意の元 a, b に対し、a ≤ b または b ≤ a が成り立つ。

狭義大小関係

「≤」が半順序であるとき、その反射的簡約「<」は任意の a, b, c ∈ P に対して以下を満たす：

非反射性：¬(a < a);

非対称性：a < b ならば ¬(b < a); （非反射性と推移性から従う）

推移性：a < b かつ b < c ならば a < c

ウィキペディア

広義大小関係の中の反射律、推移律を満たすものを前順序。
前順序かつ反対称律を満たすものを半順序。

半順序集合である<は非反射律、非対称律、推移律を満たす。

小学校で習った大小関係を厳密に説明しているので多少は混乱しますが、感覚的な理解とも整合的です。

定理

同値関係x=xを仮定①します。

x<x(仮定)
x≤x∧x≠x(<定義)
x=x(①)
x≠x∧x=x∧x≤x
⊥∧x≤x
⊥
x<x→⊥(→導入)①

同値関係から矛盾が導けました。

次は非対称律。先に証明した非反射律を使います。

x<y∧y<x(仮定)
x≤y∧y≤x∧x≠y(狭義大小関係定義)
x=y∧x≠y(≤反対称律)
⊥(①)

<は反対称律は成立しません。

x<y∧y<z(仮定)
x≤y∧y≤z∧x≠y∧y≠z(≤定義)
x≤z∧x≠z(推移律)
x<z(<定義)

<には推移律が成り立ちます

x<y∧y<x(仮定)
x≤y∧y≤x∧x≠y(<定義)
x=y∧x≠y(反対称律)
⊥(排中律)

非反射律を定義すれば非対称律導ける。逆も然り。また≤の推移律から<の推移律も導ける。

引用WIIS