Open Topic 1-9(1) : 概念辨析 2017 年 12 月 11 日 何润雨 & 孙思钰 中文翻译仅供参考

Presentation on theme: "Open Topic 1-9(1) : 概念辨析 2017 年 12 月 11 日 何润雨 & 孙思钰 中文翻译仅供参考"— Presentation transcript:

1 Open Topic 1-9(1) : 概念辨析 2017 年 12 月 11 日 何润雨 & 孙思钰 中文翻译仅供参考
主要给大家补充一些比较基础的知识 如部分内容有误还请大佬们及时指出 2017 年 12 月 11 日 何润雨 & 孙思钰

2 Partial Order Strict Partial Order Total Order Partial Equivalence Relation

3 Partial Order 偏序 Reflective 自反的 Antisymmetric 反对称的 Transitive 可传递的
定义：设R为非空集合A上的关系，如果R是自反的、反对称的和可传递的，则称R为A上的偏序关系。 其中（自反性）x~x； （反对称性）如果x~y,且y~x,则x=y； （传递性）如果x~y,且y~z ,则x~z。

4 Partial Order 偏序 Wikipedia :
A (non-strict) partial order is a binary relation ≤ over a set P satisfying particular axioms which are discussed below. When a ≤ b, we say that a is related to b. The most familiar partial orders are the relations “less than or equal to” and “more than or equal to” on Z and R. So when speaking in general of a partial order R on a set A, we shall always use symbols or for R.

5 Partial Order 偏序 Poset 偏序集
The set A together with the partial order R (on A) is called a partially ordered set, or simply a poset, and we will denote this poset by (A, R). 一个集合A与A上的偏序关系R一起叫作偏序集，记作<A,R>或<A, ≦>。

6 Partial Order 偏序 Example 01 A : a collection of subsets of a set S.
The relation is a partial order on A. (A, ) is a poset. A 是集合S所有子集所构成的集合。包含关系是A上的一个偏序关系。

7 Partial Order 偏序 Example 02 Z+ (the set of all positive integers)
“less than or equal to” is a partial order on Z+. “more than or equal to” is a partial order on Z+. 小于等于和大于等于是正整数集上的偏序。

8 Partial Order 偏序 Example 03
Divisibility ( a R b if and only if a | b ) is a partial order on Z+. 整除关系是整数集上的偏序。

9 Partial Order 偏序 Example 04 Dual 对偶
Let R be a partial order on a set A. Let R-1 be the inverse relation of R. R-1 is also a partial order. Dual 对偶 The poset (A, R-1) is the dual poset of (A, R). R-1 is the dual of the partial order R. 若一个关系R是集合A上的偏序， 则R的逆也是A上的一个偏序。 对偶

10 Partial Order 偏序 Theorem :
The diagraph of the partial order has no cycle of length greater than 1. 偏序的diagraph上没有长度超过1的cycle。

11 Strict Partial Order 严格偏序
Irreflective 反自反的 Asymmetric 强反对称的 Transitive 可传递的 与偏序最大的不同在于反自反 且 强反对称 x<x不成立 x < y  y < x 不成立

12 Strict Partial Order 严格偏序
Example The relation “less than” is a strict partial order on Z+. The relation “more than” is a strict partial order on Z+. “x is less than x”不成立 x is less than y, y is less than z  x is less than z x is less than y  y is not less than x

13 Every partial order  induces a strict order :
a < b : (a  b)  (a  b). Every strict order < induces a partial order : a  b : (a < b)  (a = b). 严格偏序与偏序的互推

14 Comparability If (A,  ) is a poset, the elements a and b are said to be comparable if a  b or b  a 可比性 （a, b）或（b, a）满足A上的这个偏序关系

15 Total Order 全序 Reflective 自反的 Antisymmetric 反对称的 Transitive 可传递的
Comparable 可比的 要求其中任意2个元素都是可比的

16 全序是一种特殊的偏序

17 Total Order 全序 Example 01 Z+ : the set of all positive integers
“less than or equal to” is a total order on Z+ “more than or equal to” is a total order on Z+ 大于等于，小于等于 也都是正整数上的全序

18 Total Order 全序 Example 02 Lexicographic (Dictionary order)
(a, b) < (a’, b’) if a < a’ or if a = a’ and b  b’. 字典序

19 Extrema Greatest element and least element:
An element g in P is a greatest element if for every element a in P, a ≤ g. An element m in P is a least element if for every element a in P, a ≥ m. A poset can only have one greatest or least element. 解释几个概念 不一定有（不可比）

20 Extrema Maximal elements and minimal elements:
An element g in P is a maximal element if there is no element a in P such that a > g. An element m in P is a minimal element if there is no element a in P such that a < m. Maximal和minimal不一定唯一

21 Extrema Upper and lower bounds : For a subset A of P,
An element x in P is an upper bound of A if a ≤ x for each element a in A. An element x in P is a lower bound of A if a ≥ x, for each element a in A. X不一定是A中的元素 但是必须是P中的元素

22 Extrema Example： Consider the positive integers, ordered by divisibility. 1 is a least element. No greatest element. No maximal element. 举例分析 1 可以整除其他任何元素 没有greatest，没有maximal(any g divides for instance 2g)

23 Extrema Example： Consider the positive integers and 0, ordered by divisibility. 1 is a least element. 0 is a greatest element. 举例分析 0是任何数的倍数（如果认为0|0的话）

24 Extrema Example： Consider the positive integers but 1 excluded, ordered by divisibility. No least element. Any prime number is a minimal element. 举例分析 没有least（不可比） 任何素数都是minimal

25 Extrema Example： Consider the positive integers but 1 excluded, ordered by divisibility. 60 is an upper bound of the subset {2, 3, 5, 10}, which does not have a lower bound. 举例分析 1不在偏序集中

26 Partial Equivalence Relation
Symmetric 对称的 Transitive 可传递的 If R is also reflexive, then R is an equivalence relation. 部分等价 区别于等价：不一定自反

27 Partial Equivalence Relation
Example f is defined on some elements of A but not all. x ≈ y if and only if f is defined at x, f is defined at y, and f ( x ) = f ( y ). ≈ is a partial equivalence but not a equivalence. X上可能没有定义，所以不是reflective。

28 参考文献 1-9关系及其基本性质.pptx Discrete Mathematical Structures ( Sixth Edition)