良序集

全序集A的任一非空序子集必有最前元素

良序集

良序集（well-ordered set），也称正序集，若全序集A的任一非空序子集必有最前元素，则称A为良序集。[0][15]一个集合A，如果满足 是有序集，则这个集合被定义为良序集，并记为。[1]良序集最早在1895年由德国数学家康托尔在论证了相同的势与不同的势的集合都存在之后，继续研究集合这个概念并且引进了基数与序数的理论，为了引进新的序数而提出的概念。[4][3]

良序集（well-ordered set），也称正序集，若全序集A的任一非空序子集必有最前元素，则称A为良序集。[1][16]一个集合A，如果满足 是有序集，则这个集合被定义为良序集，并记为。[2]

良序集最早在1895年由德国数学家康托尔在论证了相同的势与不同的势的集合都存在之后，继续研究集合这个概念并且引进了基数与序数的理论，为了引进新的序数而提出的概念。[5][4]

[7]良序集还有很多普通序集不具备的重要性质。如良序集的子集是良序集；不空的良序集必有首元素；两集相似，如果其中一个是良序的，另一个也必然是良序集等。[17]良序集在数学中良序集作为自然数的数学归纳法之一，是数学推理常用的工具。同时良序集法在计算机、农业等方面都有广泛的应用。[9][8]

定义

如果一个集合满足 ，则被定义为良序集，并记为。良序集又称正序集。[2][16]

简史

在19世纪初期,数学界对数学分析基础的批判运动促进了集合论的诞生。1851年，波尔查诺(Bolzano,B.)发表著作《无穷悖论》，并肯定了实无穷的存在,建立了集合等价的概念，还注意到了无穷集合的某些真部分有可能等价于整体的情况。[3]1874年，德国数学家康托尔(G.Cantor，1845-1918)创立的集合论，是现代数学的基础。[18]集合是指具有某种特定性质的具体的或抽象的对象汇总而成的集体，其中构成集合的这些对象则称为该集合的元素。[19]

康托尔
康托尔

康托尔在论证了相同的势与不同的势的集合都存在之后，继续研究集合这个概念并且引进了基数与序数的理论。后来康托尔为了引进新的序数，他把全序集限制在良序集的范围之内。康托尔在1895年发表的文章中提出了良序集的概念即一个全序集叫做良序集，假如它有为首的元素，并且它的每一子集都有为首的元素。[5]后来关于良序集的相关问题还被德国数学家希尔伯特在1900年的国际数学会议上，列入了著名问题的名单中。[4]

性质

良序集有许多普通序集不具有的重要性质。[17]

性质1：良序集的子集是良序集。[17]

证明：设为任一良序集。当时必为良序集，否则至少存在一子集没有首元素，那么也是的子集，无首元素，这与是良序集矛盾。[20]

性质2：不空的良序集必有首元素。[17]

证明：不空的良序集本身是的一个子集，应有首元素。[20]

性质3：两集相似，如果其中一个是良序的，另一个也必然是良序集。[17]

证明：设，而不是良序集，则至少存在一个子集无首元素，如果，那么将有无限递降序列

这里对每个有，并且永远不会终止，设到的相似对应为则 ，并且对于每个有，把这里列出的所有作成一个A的子集，它无首元素，这与为良序集是矛盾的。这证明了也是良序集。[20]

性质4：良序焦除了末元素外(假如有末元素的话)，每元素必有元素紧跟其后。[17]

证明：如不是的末元，那么必然存在，满足，把所有满足此式的收集为一个集合，是的一个子集，设其首元为，那么就是紧随后的元素。事实上，并且若，由的定义，必有，故在与之间不会有其它的元素。[20]

性质5：在良序集中不能选取一个如下的无限单调减少元素列，由性质3可证。[17][20]

相关定理

定理1：良序集的子集仍是良序集。[21]

定理2：若为良序集，且，则也是良序集。[21]

证明：设是相似变换，的任意非空子集，在下的象是的非空子集，因为是良序集，故有最前元素，就是的最前元素。的任意非空子集都有最前元素，故是良序集。[22]

例如，是良序集。[1]

设为的非空子集，在中取任何元素，如果不是的最前元素，取在中确定的截段，则，为非空有限集。得这个最前元素就是的最前元素。故是良序集。[1]

定理3：良序集除了最后元素外，每个元素都有后纪元。[21]

证明：设为良序集，任取，不是的最后元素，取在的截段，作，则是的非空子集。它的最前元素就是的后继元。[22]

定理4：良序集中不存在无限单调减少元素列[21]

证明：若存在这样的元素列，则集是良序集的子集而无最前元素，是矛盾的。[22]

定理5：设是良序集的子集，则到的相似变换对任意必有。[21]

证明：否则，有相似变换及使设为中具有此性质的元素全体，则，故必有最前元素，设则。因，，因相似变换是保序的，故在中有

则，这与的最前元素为矛盾，故必须有。[22]

定理6：二良序集若相似，则相似变换是唯一的。[23]

证明：设都是良序集到的相似变换，若，则必有，使设，，则与的两个截段，都相似，于是，与定理5推论2矛盾，故。[21]

定理7：任何二良序集，或为相似，或为其中之一相似于另一集的截段。[23]

定理8：设是两两不相似的良序集，则中存在一个最短的集。[24]

定理9：良序集的全序和是良序集。[25]

相关推论

推论1：良序集不能与其任一截段相似，也不能与其任一截段的子集相似。[23]

推论 2：良序集的任何两个不同的截段不能相似。[23]

推论 3：良序集不能与其子集的一个截段相似。[23]

序关系

用表示集合上的一个二元关系，这个关系被称为序关系。[10]

序数

良序集的序型称为序数。如果序数有无限势，则称之为超限数。[11]

偏序集

一个集合与上的一个偏序关系一起称为偏序集，记作，或，其中是对应于有序集合的一个普通符号，即用代替有序对。[12]

全序集

链：设是一个偏序集，若集合的一个子集中任何两个元素都相关，则称这个子集为一条链。[12]

全序集：若集合是一条链，则偏序集.称为全序集。[12]

超限归纳法

把数学归纳法由自然数集合推广到任意良序集合，称这样的归纳法为超限归纳法。[13]

超限归纳法：令是一个关于序的良序集，令是定义在上的一个性质，即对任何，或者成立或者不成立。对任何的元素，假定存在蕴含关系：一切，成立必然能够得到成立，那么，对于集合性质成立，即对任何，成立。[13]

第二数类

把全体有限序数所组成的集叫做第一数类。所以第一数类就是自然数集。[15]

把全体可数良序集的序数所构成的集称为第二数类，并记为，所以。[15]

良序关系

是一个偏序集，若的任何非空子集都有最小元，则称该偏序集为良序集，“”是上的良序关系。[26]

应用

在数学中良序集的超限归纳法，被用作数学推理和处理问题的常用的工具。[13][27]在软件技术中良序集法可以用来证明程序中可以截断和终止证明过程的运行。[8]在农业上良序集算法可以优化改善农机在使用中的弊端。[9]

数学

关于自然数的数学归纳法，是数学推理常用的工具。在集合论研究中提出良序集(即任何非空子集必有最先元素的有序集)的概念后，发现数学归纳法还可以推广到一般的良序集，即超限归纳法。[7]同时良序集的数学归纳法还被用作处理有限问题的推理基础。[27]“算术相容性”一开始在希尔伯特的“元数学”体系中属于一个不可判定命题，后来德国的数学家根岑在1936年利用超限归纳法完成了对这个命题的证明。[28]

软件技术

良序集法是R.W.Floyd在1967年提出来的一种证明程序终止性的方法。它在证明程序中可以截断和终止证明过程的运行。[8]

电脑程序终止图片
电脑程序终止图片

良序集算法在农业上的应用

根据田间作物垄行间杂草离散的特点，基于图像矩阵，运用像素子集的良序性，结合垄宽先验知识得到垄行轨迹中心。同时，系统选择图像的绿色成分为目标特征空间，滤掉了非绿色的背景噪声，对光照也有一定的适应性为寻找垄行子集奠定了基础。[9]

无人机农田摄影
无人机农田摄影

参考资料 28

  1. 参考 1
  2. 参考 2
  3. 参考 3
  4. 参考 4
  5. 参考 5
  6. 参考 6
  7. 参考 7
  8. 参考 8
  9. 参考 9
  10. 参考 10
  11. 参考 11
  12. 参考 12
  13. 参考 13
  14. 参考 14
  15. 参考 15
  16. 参考 16
  17. 参考 17
  18. 参考 18
  19. 参考 19
  20. 参考 20
  21. 参考 21
  22. 参考 22
  23. 参考 23
  24. 参考 24
  25. 参考 25
  26. 参考 26
  27. 参考 27
  28. 参考 28
广告位：底部（ad-bottom）—— 请到中台「公共区块」编辑此内容