language-agnostic - 全序、弱序、偏序 - 完整定义

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

2年前关闭。




Improve this question




之间有什么区别

严格/非严格排序，

弱/非弱排序，以及

部分/总排序？

Answer 1

设 X 是一个集合。关系 < ⊆ X × X 是偏序，如果

对于所有 x ∈ X，我们永远不会有 x < x,

每当 x < y，我们永远不会有 y < x 和

每当 x < y 和 y < z 时，我们就有 x < z。

全序是具有附加属性的偏序，对于任何两个 x 和 y，我们正好有 x < y、y < x 或 x = y 之一。

集合 X 上的弱排序是(据我所知)偏序 < 具有附加属性，即商集 X/~ 上的诱导排序是全排序，其中 [x] = [y] ∈ X/~ 当且仅当 x < y 和 y < x 都不在 X 中成立。

换句话说，在偏序中，某些元素是可以比较的，如果可以比较，则排序是一致的。偏序示例:

集合 X 的真子集，其中 A < B 表示 A ⊊ B。

a < b 表示“a 除 b”的自然数。

C++ 中的模板特化。

总排序是指所有元素同时形成一个单一的、一致的顺序。

如果您愿意将几个元素放在一起并将它们视为等价的以进行排序，那么弱排序就是总排序。

术语“严格”是指使用“<”作为定义关系，而不是“≤”。您可以看到根据 ≤ 重写所有定义是多么容易，例如在偏序中，我们总是有 x ≤ x 等。

这里有两个例子，都是 C++ 模板特化。当然，两者都是部分有序的，但第一个也是完全有序的。

示例#1:

template <typename T> struct Foo {};               // A1
template <typename U> struct Foo<U*> {};           // A2
template <> struct Foo<int*> {};                   // A3

这些专业完全按照 A3 < A2 < A1 排序，其中“<”表示“比”更专业。

示例#2:

template <typename T1, typename T2> struct Bar {}; // B1
template <typename U> struct Bar<int, U> {};       // B2a
template <typename V> struct Bar<V, int> {};       // B2b
template <> struct Bar<int, int> {};               // B3

这一次，我们有 B3 < B2b < B1 和 B3 < B2a < B1，但 B2a 和 B2b 没有可比性。

在 C++ 中，这表现为以下方式:如果未定义特化 B3，则尝试实例化 Bar<int, int>将导致编译器错误，因为没有明确的“最特化”特化。

部分有序集合可以有许多“最少”元素和“最大”元素，因为这些概念只能谈论可比较的元素。在 B1、B2a 和 B2b 中，B2a 和 B2b 都是“最少元素”，因为没有更小的元素。尽管如此，没有唯一的最小元素。