谈谈良序原理
所谓良序原理事实上就是这么个东西:任何集合上都可以构建一个良序关系。
一、所谓那些良基性质。 良基的性质是很有用的。我们都知道数学归纳法,但是数学归纳法只能归纳下标为自然数的东西;
而用良基的性质,就可以弄出来更强大的transfinite induction(超限归纳法),可以归纳下标为任意序数的东西。
一个良基的全序关系就叫良序关系。常见的实数上的≤就是良序关系。
超限归纳法:令“<”为集盒W上的一个严格良序关系,phi(w)是关于某w∈W的一个性质。
如果对于所有w,都满足:“假如对所有x<w,phi(x)都为真,那么phi(w)必为真”,那么对于所有w∈W,phi(w)都必为真。
这个跟我们所熟悉的数学归纳法有点不同,但是也有相似的地方。证明如下:
已知对于所有w,都满足:“假如对所有x小于w,phi(x)都为真,那么phi(w)必为真”。
假设存在一个w_0其phi(w_0)为假,那么必有w_1<w_0其phi(w_1)为假…如此下去,
{w: phi(w)为假}这个集盒就没有最小的元素,违反了良基性质。证完。
用超限归纳法,我们就可以对一个函数进行recursive definition(递归定义),
即f(x)的值由x和{有序对<x',f(x')>: x'<x} 共同来定义。
即,我们递归地定义一个G(x, {<x',f(x')>: x'<x}),再令f(x)=G(x, {<x',f(x')>: x'<x})。
这是可以通过良序性和超限归纳法做到的。
可以证明以下三种情况必有且只有一种为真:
{x: x<w}在f的定义域里且f(w)=G(w, {<x',f(x')>: x'<w});
{x: x<w}在f的定义域里但w不在f的定义域里,且G(w, {<x',f(x')>: x'<w})未定义;
w不在f的定义域里且存在一个x<w也不在f的定义域里。
证明如下:
如果一个定义域为W的子集的函数 h 符合
“w ∈ Dom(h) => 所有<w 的 w'∈Dom(h), 且 h(w)=G(w, {<x',f(x')>: x'<w})”
我们就把 h 叫做一个 “好”的函数。
用超限归纳法易得:如果 h 和 h' 都是好的,且w 在它们定义域的交集里,那么必有h(w)=h'(w)。
所以,令 f 为所有的好的函数的并集(即,只有有一个好的函数h的定义域包含了w,就有f(w)=h(w)),则 f 自己也是一个好的函数。