超限帰納法
超限帰納法
整列集合\(\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ボタン |
順序写像・単調写像・順序反映・順序埋め込み・順序同型写像の定義
\[
a\preceq_{X}b\Rightarrow f\left(a\right)\preceq_{Y}f\left(b\right)
\]
有向集合と有向点列の定義
\[
\forall a,b\in\Lambda,\exists c\in\Lambda,a\preceq c\land b\preceq c
\]
順序同型は同値関係
順序同型は同値関係(反射律・対称律・推移律)を満たす。
整列集合の基本的な性質
\[
X\left\langle \min X\right\rangle =\emptyset
\]