整列集合と超限帰納法

23.整列集合

整列順序

\(A\)上の全順序\(\leq_R\)が整列順序:
\(\forall B(\)\(\scriptsize \neq \phi)\)\(\subset A \exists b_0\in B(b_0\)は最小元\()\)

整列集合

整列順序\(\leq_R\)が定義された集合\(A,\leq_R\)を整列集合という

整列集合

整列集合は空でない任意の部分集合が最小元を持つ全順序集合である

<\(_R\)

順序集合\((A,\leq_R) ,a,b\in A\)において
\(a\)<\(_R b \ \Leftrightarrow (a \leq_R b) \land (a\neq b)\)

辞書式順序

\(A=\mathbb{N}\times \mathbb{N}\)上の二項関係\(\leq\):
\(\small (a,b)\leq (a',b')\Leftrightarrow a< a' \lor (a=a' \land b\leq b')\)

\((1)(\mathbb{N},\leq) \)は整列集合
\((2)(\mathbb{Z},\leq) \)は整列集合でない
\((3)\)辞書式順序は整列順序である

24.超限帰納法

超限帰納法

整列集合\((A,\leq_R)\),と\(A\)上の命題関数\(P(a)\)において
\(\small \forall a\in A(\forall b\in A(b<a \rightarrow P(b)) \rightarrow P(a))) \)
\(\small \Rightarrow \forall a\in A(p(a))\)

超限帰納法の言明を証明せよ

\(A= \phi\)の時、成立するので\(A\neq \phi\)とする
(*1)「\(\small \forall a\in A(\forall b\in A(b<a \rightarrow P(b)) \rightarrow P(a))) \)
を真とする。」

(*2)「\(\forall a \in A(P(a))\)を偽とする」(背理法)
\(\small X=\{a\in A|P(a)\)が偽\(\}\)とすると*2より\(\small X\neq \phi\)。
\(X\subset A\)より\(X\)の最小元\(a_0\)が取れる。このとき\(P(a_0)\)は偽である。しかし\(a_0\)の最小性から\(\forall b\in A(b<a_0 \rightarrow P(b))\)が成り立つので*1より\(P(a_0)\)は真となり矛盾。

よって*1のとき\(\forall a \in A(P(a))\)なので示された。