(1)

\(\Rightarrow\)

集合\(X\)に2項関係\(R\)与えられているとする。
前件より、\(R\)は反対称律を満たす。

反射律

任意の\(a\in X\)を選ぶ。
そうすると、\(X\)は整列性を満たしているので、部分集合\(\left\{ a\right\} \subseteq X\)について、最小元が存在する。
このとき、部分集合\(\left\{ a\right\} \)の元は\(a\)のみなので、\(a\)は最小元となり、\(\forall x\in\left\{ a\right\} ,aRx\)となるので、\(aRa\)を満たす。
従って、任意の\(a\in X\)について、\(aRa\)となるので反射律を満たす。

推移律

任意の\(a,b,c\in X\)を選ぶ。
このとき、\(aRb\)かつ\(bRc\)を満たしているとする。
前件より整列性を満たすので、空集合でない部分集合\(\left\{ a,b,c\right\} \subseteq X\)には最小元が存在する。
最小元が\(a\)とすると、\(aRc\)を満たす。
最小元が\(b\)とすると、\(bRa\)を満たし、\(aRb\)を満たすとしていて、前件より、反対称律が成り立つので\(\top\Leftrightarrow bRa\land aRb\Rightarrow a=b\)となり、\(\top\Leftrightarrow bRc\Leftrightarrow aRc\)となる。
最小元が\(c\)とすると、\(cRb\)を満たし、\(bRc\)を満たすとしていて、前件より、反対称律が成り立つので\(\top\Leftrightarrow cRb\land bRc\Rightarrow b=c\)となり、\(\top\Leftrightarrow aRb\Leftrightarrow aRc\)となる。
従って、最小元が\(a\)でも\(b\)でも\(c\)でも\(aRc\)となる。
これより、\(aRb\)かつ\(bRc\)ならば、\(aRc\)となるので推移律を満たす。

完全律

任意の\(a,b\in X\)を選ぶ。
そうすると、部分集合\(\left\{ a,b\right\} \subseteq X\)は空集合ではないので整列性より、\(\left\{ a,b\right\} \)は最小元をもつ。
\(\left\{ a,b\right\} \)の最小元が\(a\)とすると\(aRa\land aRb\)より、\(aRb\)を満たし、最小元が\(b\)とすると、\(bRa\land bRb\)より、\(bRa\)を満たす。
これより、\(\left\{ a,b\right\} \)の最小元が存在するので、最小元は\(a\)または\(b\)であり、\(aRb\)または\(bRa\)を満たすので、完全律を満たす

-

従って、前件より、反対称律を満たし、反射律・推移律・完全律も満たすので、広義全順序関係(反射律・反対称律・推移律・完全律)を満たす。
故に整列性と広義全順序関係(反射律・反対称律・推移律・完全律)を満たす。

\(\Leftarrow\)

明らかに成り立つ。

\(\Leftrightarrow\)

これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。

(2)

\(\Rightarrow\)

整列集合ならば、整礎集合となる。
有効グラフ\(\left(X,R\right)\)を整列集合とすると\(\left(X,R\right)\)は反対称律と整列性を満たす。
このとき、空でない任意の部分集合\(A\subseteq X\)を選ぶ。
そうすると整列性より、\(A\)は最小元をもち、最小元ならば極小元であるので、\(A\)は極小元をもつ。
従って、空でない任意の部分集合\(A\subseteq X\)について、極小元をもつので、整礎性を満たす。
従って、\(X\)は整礎集合となる。

逆は一般的に成り立たない

反例で示す。
\(X=\left\{ a_{1},a_{2},b\right\} \)として2項関係\(\prec\)を\(a_{1}\prec b,a_{2}\prec b\)のみとすると、2項関係\(\prec\)は整礎関係となるので\(\left(X,\prec\right)\)は整礎集合となる。
しかし、この\(X\)には部分集合として\(X=\left\{ a_{1},a_{2},b\right\} \)を選ぶと最小元が存在しないので、整列集合ではない。
従って、整礎集合であっても整列集合とは限らない。

別証明

\(\Rightarrow\)を示す。
\(\left(X,\preceq\right)\)を整列集合とする。
このとき、\(\left(X,\preceq\right)\)は全順序集合でもある。
\(X\)の空でない任意の部分集合\(A\subseteq X\)を選ぶ。
そうすると、\(X\)は整列集合なので、ある最小元\(m\in A\)が存在して、任意の\(x\in A\)について、\(m\preceq x\)となる。
このとき、\(m\)が\(A\)の極小元でないと仮定する。
そうすると、ある\(y\in A\)が存在し、\(y\prec m\)となる。
これより、任意の\(x\in A\)について、\(m\preceq x\)となり、ある\(y\in A\)が存在し、\(y\prec m\)となるので矛盾。
従って、背理法より、\(m\)が\(A\)の極小元となる。
これは任意の空でない部分集合について成り立つので\(X\)は整礎律を満たす。
これらより、\(X\)は整礎律を満たすので、整礎集合となる。
故に\(\Rightarrow\)が成り立つ。

(3)

整列集合ならば整礎集合であり、整礎集合は\(R\)の非対称部分\(\prec_{R}\)についての無限狭義降下列をもたないので、整列集合も\(R\)の非対称部分\(\prec_{R}\)についての無限狭義降下列をもたない。
従って題意は成り立つ。

(3)-2

直接示す。
整列集合\(\left(X,R\right)\)があるとき、\(R\)の非対称部分を\(\prec_{R}\)とする。
このとき、\(X\)にある列\(\left(x_{k}\right)_{k\in\mathbb{N}}\subseteq X\)が存在し、無限降下列\(x_{1}\prec_{R}^{-1}x_{2}\prec_{R}^{-1}\cdots\)になっていると仮定する。
そうして、\(A=\left\{ x_{1},x_{2},\cdots\right\} \)とおくと、\(A\ne\emptyset\)となり、\(\left(X,R\right)\)は整列集合であり、部分集合\(A\subseteq X\)は空集合ではないので\(R\)最小元\(m=\min\left(A\right)\in A\)が存在する。
これより、\(m\)は\(R\)最小元なので、\(\forall a\in A,mRa\)となる。
このとき、\(m\in A=\left\{ x_{1},x_{2},\cdots\right\} \)なのである自然数\(n\in\mathbb{N}\)が存在し、\(m=x_{n}\)となる。
しかし、\(x_{n+1}\in A\)であり、\(x_{n+1}\prec_{R}x_{n}=m=\min\left(A\right)\)であり、
\begin{align*} \top & \Leftrightarrow x_{n+1}\prec_{R}m\\ & \Leftrightarrow x_{n+1}Rm\land\lnot\left(mRx_{n+1}\right)\cmt{\because a\prec_{R}b\Leftrightarrow aRb\land\lnot\left(bRa\right)}\\ & \Leftrightarrow x_{n+1}Rm\land\lnot\top\cmt{\because\forall a\in A,mRa}\\ & \Leftrightarrow x_{n+1}Rm\land\bot\\ & \Leftrightarrow\bot \end{align*} となるので矛盾する。
従って背理法より、任意の列\(\left(x_{k}\right)_{k\in\mathbb{N}}\subseteq X\)について、無限降下列\(x_{1}\prec_{R}^{-1}x_{2}\prec_{R}^{-1}\cdots\)とはならない。
これより、整列集合\(\left(X,R\right)\)は\(R\)の非対称部分\(\prec_{R}\)についての無限狭義降下列をもたない。
従って題意は成り立つ。