超限帰納法

by nomura · 2023年10月29日

超限帰納法
整列集合$\left(X,\preceq\right)$があり、$X$の各元$x$に命題$P\left(x\right)$が与えられてるとする。
このとき、

(a)

$P\left(\min X\right)$が真である。

(b)

$x$が$\min X$以外の元$x\ne\min X$のときに、任意の$a\in X\left\langle x\right\rangle $に対し$P\left(a\right)$が真であるなら$P\left(x\right)$も真である。

-

の両方が成り立つならば、$X$の任意の元$x$について$P\left(x\right)$は真となる。
また1つの式で表すと、
\[ P\left(\min X\right)\land\forall x\in X,\left(\forall a\prec x,P\left(a\right)\right)\Rightarrow P\left(x\right) \] が成り立てば任意の$x\in X$に対し$P\left(x\right)$は真となる。
すなわち、
\[ P\left(\min X\right)\land\forall x\in X,\left(\forall a\prec x,P\left(a\right)\right)\rightarrow P\left(x\right)\Rightarrow\forall x\in X,P\left(x\right) \] である。

背理法で示す。
$P\left(X\right)$が偽となる元が存在し、偽となる最小の元を$b=\min\left(\left\{ x\in X;\lnot P\left(X\right)\right\} \right)$と仮定する。
$P\left(\min X\right)$は真であるので$b\ne\min X$であり、任意の$a\in X\left\langle b\right\rangle $に対し、命題$P\left(a\right)$は真である。
このとき$P\left(b\right)$も真になるが$P\left(b\right)$は偽としていたので矛盾。
故に題意は成り立つ。

ページ情報

タイトル	超限帰納法
URL	https://www.nomuramath.com/u6fe5uo2/
SNSボタン

整列集合の定義

ツォルンの補題

帰納的順序集合$\left(X,\preceq\right)$は極大元をもつ。

順序を反映する写像(順序単射)ならば単射

上方集合と下方集合の定義

\[ \forall x\in A,\forall y\in X,x\preceq y\rightarrow y\in A \]