良序原理(well-ordering)

原创
2018/03/21 23:39
阅读数 5.6K
良序原理(well-ordering)
  • 自然数集的每个非空子集都有个最小元素,即自然数在其标准的大小关系下构成一良序集
  • 在公理集合论中,自然数集定义为最小的归纳集合(包含0且包含本身中每个元素的后继的集合),可以证明,所有满足{0,...,n}为良序集的n组成的集合是一个归纳集合,从而是自然数集本身。由此可以推出自然数集本身也是个良序集。
  • 良序定理是选择公理的等价形式之一
    • 其内容为:对任何集合S,存在S上的二元关系R,使得<S,R>是良序集
  • 意义
    • 良序原理的意义主要在于,在证明时可以使用所谓的“最小反例法”,它相当于反证法和数学归纳法的结合。
  • 一般描述:设"<"是集合S上的一个关系,它满足以下性质:
    1. 给定S中的x,y,和z,如果 x<y 和 y<z,则 x<z;
    2. 给定S中的x和y,以下三种可能中恰有一种为真:
      1. x<y
      2. x=y
      3. y<x
    3. 如果A是S的任何非空子集,则A中有一个元素x,使得对于A中所有的y,有x<=y(即x<y或x=y)
    • 这个关系被称为S的一个良序关系
  • 在计算机算法中的应用
    • 如果我们能把一个计算的诸状态x映射到属于良序集S的一个元素f(x),且使得计算的每一步把一个状态x转换成状态y,并有f(y)<f(x),则算法必然终止。

在计算机算法中,最经典(个人觉得^_^)

设S对于<是良序,且设P(x)是关于S的元素x的一个命题。
求证:如果在对于所有的y < x,P(y)为真的假定下能证得P(x)为真,则P(x)对S中得所有x为真。
证明:
令A是使得P(x)为假的所有的x的集合。
如果A非空,则它含有最小的元素x0。
因此,P(y)对于所有y < x0为真。
但这意味着P(x0)为真,所以x0不在A中(与假设矛盾)
因此:A必须为空 => 即P(x)总是为真。

以上,也可用于P(1)的证明

对于所有正整数 y < 1,如果P(y)为真,则P(1)为真。
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
0 收藏
0
分享
返回顶部
顶部