超限帰納法
超限帰納法
整列集合\(\left(X,\preceq\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) \] である。
整列集合\(\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)\)は偽としていたので矛盾。
故に題意は成り立つ。
\(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ボタン |
部分順序集合
\[
b_{1}\preceq_{A}b_{2}\Leftrightarrow b_{1}\preceq_{B}b_{2}
\]
整列集合の順序同型は一意的
半順序関係と狭義半順序関係
\[
x\prec y\Leftrightarrow x\preceq y\land x\ne y
\]
順序写像・順序単射・順序埋め込み写像の合成写像
順序写像同士の合成写像は順序写像になる。