序理论
背景和动机
次序无所不在——至少在数学和相关领域比如计算机科学是这样。你典型遇到的第一个次序是小学数学教育中的自然数的次序。这个直觉概念很容易扩展到其他数的集合的排序,比如整数和实数。实际上大于或小于另一个数的概念一般是数系统的基本直觉(尽管你通常还感兴趣于两个数实际的差,它不能由这个次序给出)。排序的另一个非常熟悉的例子是词典中词典次序。
上述类型的次序有特殊性质:每个元素都是可以“比较”于另一个元素,就是说,它或者大于、或者小于、或者等于另一个元素。但是,这不总是想要的要求。一个周知的例子是集合的子集排序。如果一个集合包含集合的所有元素,则被称为小于等于。然而有些集合不能在这种方式来比较,因为其中每个都包含着其他集合中不存在的某些元素。所以,子集包含是偏次序,对立了前面给出的全次序。
序理论在一般性架构下捕获了上述例子引发的直觉次序。这是通过指定关系必须是数学上次序的一些性质来完成的。这种更加抽象的方式更有意义,因为你可以从一般性架构推导出各种定理,而不用关心任何特定次序的细节。这种洞察可以容易的转换到很多具体应用中。
由次序的各种实践使用所驱动,已经定义了多个特殊种类的有序集合,其中某些已经发展出自己的数学领域。此外,序理论不限制于各种种类的排序关系,还考虑在它们之间的适当的函数。函数的序理论的性质的一个简单例子来自在数学分析中常见的单调函数。
基礎定義
偏序集合
序是特別的二元關係。假定是一集合,且是在的關係,則是個偏序當他是自反的,反對稱的,且遞移的,則,對於所有和於,皆能滿足:
- (反身性)
- 如果并且則(反對稱性)
- 如果并且則(遞移性)
一個偏序性質的集合稱為偏序集合、poset或是有序集合(當其所強調的意指明確)。藉由查看這些性質,我們能知道在自然數、整數、有理數、以致於實數皆有明確的序關係。當然,它們還有額外的性質成為全序,即在中對於每一個a和b皆能滿足:
- 或(全序性)
這些序又稱為線性序或鏈。當許多典型序為線性,集合內的有序子集合會發生不滿足此性質的例子。另一個例子為給定一個整除性關係""。對於兩個數和,當除以未留餘數時,我們書寫為,我們可輕易的明白這是一個偏序關係。非常多進階的性質主要在於非線性序中。
参考文献
- B. A. Davey and H. A. Priestley, 2002. Introduction to Lattices and Order, 2nd ed. Cambridge University Press. ISBN 0-521-78451-4
- A good contemporary introduction to the subject. Suitable for undergraduates.
- G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott, 2003, "Continuous Lattices and Domains," in Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press. ISBN 0-521-80338-1
- The comprehensive new version of the famous "Compendium" of continuous lattices. Assumes some advanced mathematical background.
- S. N. Burris and H. P. Sankappanavar, 1981. A Course in Universal Algebra. 页面存档备份,存于 Springer Verlag.
- A free online introduction to universal algebra, with much material on lattices.
外部链接
- Orders at ProvenMath 页面存档备份,存于 partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory.