全序关系

维基百科,自由的百科全书
跳转至: 导航搜索

全序关系集合X上的反对称的、传递的和完全二元关系(一般称其为≤)。

X满足全序关系,则下列陈述对于X中的所有a, bc成立:

  • 反对称性:若abbaa = b
  • 传递性:若abbcac
  • 完全性:abba

满足全序关系的集合叫做全序集合线性序集合简单序集合还常用来描述偏序集合的全序子集。

全序关系的完全性可以如下这样描述:集合中的任何一对元素都是可相互比较的。

注意完全性条件蕴涵了自反性aa,因此全序关系也是(满足“完全性”条件的)偏序关系。

严格全序[编辑]

对于每一(非严格)全序关系≤都有一关联的非对称的严格全序关系<,它可以以一下两种等价的方式定义:

  • a < b当且仅当abab
  • a > b当且仅当¬(ba)(即>为≤的补关系)

性质:

  • 传递性a < bb < c蕴涵a < c
  • 三分性a < b, b < aa = b中有且仅有一个成立。
  • 弱序性:其中关联的等价是相等的。

我们可以通过指定<为三分二元关系,用这两种等阶的方式来定义全序≤:

  • ab当且仅当a < ba = b
  • ab当且仅当¬(b < a)

另两个关联的关系是补关系≥和>,它们构成了四元组{<, >, ≤, ≥}。

我们可以用这四个关系中的任何一个来定义全序集,符号指明了全序集的严格性。

例子[编辑]

  • 字典序的字母表,比如A < B < C等等。
  • 全序集的任何保持原次序不变的子集。
  • 满足完全性的偏序集。
  • 基数序数集(严格地说,它们都是良序集)。
  • X为任何集合,fX到一全序集的单射,则f诱导X为x1 < x2当且仅当f(x1) < f(x2)的全序集。
  • 有序数的全序集的直积的字典序是全序的,例如按字典序排序的任何单词表——长为n的单词可视为字母表集合的直积自乘n次所得结果集合中的元素。
  • 拥有小于(<)和大于关系(>)的实数集是全序的,因此其子集(自然数集、整数集、有理数集等)均为全序集。
    • 自然数集是最小的无上界全序集。
    • 整数集是最小的无界全序集。
    • 有理数集是最小的无界稠密全序集。
    • 实数集是最小的无界连通全序集。

参见[编辑]

引用[编辑]

  • George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
  • John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4