字典序

字典序是给偏序集乘积赋予偏序的一种方式. 字典序依次对各个乘积分量进行比较来确定顺序, 正如在字典中一样.

1定义

定义 1.1. 设 $I$ 是良序集, $(A_i{)}_{i\in I}$ 是一族偏序集. Descartes 积 ${\prod }_{i\in I}{A}_i$ 上的字典序指如下偏序:

•	对 $(x_i{)}_{i\in I},(y_i{)}_{i\in I}\in {\prod }_{i\in I}{A}_i$, $(x_i{)}_{i\in I}<(y_i{)}_{i\in I}$ 指的是存在 $j\in I$, 使得 $x_j<y_j$, 且对任意 $i<j$ 都有 $x_i=y_i$.

如 $n$ 是自然数, $A_1,\dots ,A_n$ 是 $n$ 个偏序集, 则 $A_1\times \cdots \times A_n$ 上的字典序指上述定义中把 $I$ 取成 $\{1,\dots ,n\}$ 所得偏序, 即:

•	对 $(x_i{)}_{i=1}^n,(y_i{)}_{i=1}^n\in A_1\times \cdots \times A_n$, $(x_i{)}_{i=1}^n<(y_i{)}_{i=1}^n$ 指的是存在 $j\in \{1,\dots ,n\}$, 使得 $x_j<y_j$, 且对 $i\in \{1,\dots ,j-1\}$ 都有 $x_i=y_i$.

注 1.2. 显然, 字典序依赖于指标集 $I$ 的偏序. 如把 $I$ 取成离散偏序 (即元素之间都没有大小关系), 对应的字典序就是偏序集范畴中的乘积偏序; 不过我们通常不称此为字典序.

2性质

命题 2.1. 如 $I$ 是良序集, $(A_i{)}_{i\in I}$ 是一族全序集, 则带字典序的 ${\prod }_{i\in I}{A}_i$ 是全序集.

命题 2.2. 如 $A_1,\dots ,A_n$ 是良序集, 则带字典序的 $A_1\times \cdots \times A_n$ 是良序集.

注 2.3. 即便 $I$ 是良序集, $(A_i{)}_{i\in I}$ 是一族良序集, 带字典序的 ${\prod }_{i\in I}{A}_i$ 也未必是良序集. 事实上, 当这些 $A_i$ 都非空, 且有无穷多个有多于一个元素时, 带字典序的 ${\prod }_{i\in I}{A}_i$ 总不是良序集.

3相关概念

术语翻译

字典序 • 英文 lexicographical order • 德文 lexikographische Ordnung (f) • 法文 ordre lexicographique (m)