离散数学课件-第4章-7.pptVIP

一、偏序 定义1：集合S上的关系R，如果它是自反的、反对称的 和传递的，就称为偏序。 集合S与偏序R一起叫做偏序集，记作（S,R）. 例如数值的≤、≥关系和集合的?都是偏序关系。 【example 1】证明“大于或等于”关系（ ≥ ）是整数集合上 的偏序。 solution： 因为对所有整数a，有a ≥a， ≥是自反的。 如果a ≥b且b ≥a，那么a=b，因此≥是反对称的。 最后，因为a ≥b和b ≥c，所以≥是传递的。 从而≥是整数集合上的偏序且（Z, ≥ ）是偏序集。 【example 2】整除关系“ | ”是正整数集合上的偏序，因为由前 几节所述，它是自反的、反对称的和传递的。我们看到 （Z+, | ）是偏序集（Z+表示正整数集合）。 【example 3】证明包含关系?是集合S的幂集上的偏序。 Solution： 因为只要A是S的子集，就有A ?A, ?是自反的。 因为A ?B和B ?A推出A=B，因此它是反对称的。 最后，因为A ?B和B ?C推出A ? B, ?是传递的。 因此， ? 是P(S)上的偏序，且（ P(S) ， ? ）是偏序集。 在任意一个偏序集中记号a ? b表示(a，b)?R.使用这个记号 是由于“小于或等于”关系是偏序关系的范例。 注意：符号 ? 表示任意偏序关系，并不仅仅是“小于或等于”关系。 记号ab表示a ? b但a≠b.如果ab,我们说“a小于b”或 “b大于a”。 当a与b是偏序集（S, ? ）的元素时，不一定有a ? b 或b ? c。 例如，在（P(Z), ?）中,{1,2}与{1,3}没有关系，反之亦然，因为 没有一个集合被另一个集合包含。类似地在(Z,|)中，2与3没关系，3 与2也没关系。由此得到定义2. 定义2：偏序集(S, ? ) 的元素a和b叫做可比的，如果a ? b 或 b ? a。当a和b是S的元素并且既没有a ? b，也没 有b ? a，则称a与b是不可比的。 【example 4】在偏序集(Z+, ? ) 中，整数3和9是可比的吗？5 和7是可比的吗？ 整数3和9是可比的，因为3|9.整数5和7是不可比的，因为5 不能整除7，并且7也不能整除5. 用形容词“部分的（偏的）”描述偏序是由于一些对元素可能是不可比的。当集合中的每对元素都可比时，这个关系叫做全序。 定义3：如果(S, ? ) 是偏序集，且S的每对元素都是可比的，则S叫做全序集或线序集，且? 叫做全序或线序。一个全序集也叫做链。 【example 5】偏序集(Z, ≤)是全序集，因为只要a和b是整数 ，就有a ≤b或b ≤a。 【example 6】偏序集(Z+, | )不是全序集，因为它包含着不可比的元素，例如5和7. 定义4：对于偏序集(S, ? ) ，如果?是全序，并且S的每 个非空子集都有一个最小元素，就称它为良序集。 For example， N是自然数集合，I是整数集合，≤是小于等于关系，N, ≤就是良序集。而I,≤不是良序集。 定理 所有良序集，一定是全序集。 Proof： 设A,≤为良序集,任取x, y ∈ A, 则{x, y} ?A, 它有最小 元素。该最小元素或是x,或是y。 于是有x ≤ y或 y ≤ x，所以A,≤是全序集。 定理 有限的全序集，一定是良序集。 Proof： 设A={a1, a2, …，an}, A,≤是全序集。 假设它不是良序，必存在非空子集B?A，B中无最小元素， 因B是有限集，必存在x, y ∈ B,使得x与y之间不满足≤关系,与 ≤是全序矛盾。 ∴A,≤是良序集。 【example 7】正整数的有序对的集合Z+×Z+与?构成 良序集，对于(a1, a2)和(b1, b2),如果a1b1,或如果a1=b1 且a2 ≤b2（字典顺序），则(a1, a2) ? (b1, b2). 在前几章的学习中我们现实了怎样使用良序归纳原则证明关于一个良序集的结果。现在我们叙述并证明这个证明技术是有效的。 定理1 良序归纳原理 设S是一个良序集，如果下述条件成立： 基础步：P(x0)对S的最小元素为真，且 归纳步: 对一切y ∈ S, 如果P(x)对所有的xy为真，则P(y)为 真。那么P(x)对所有的x∈ S为真。 proof： 假若P(x)不对所有的x∈ S为真。那么存在一个元素y ∈ S使 得P(y)为假。于是集合A={x ∈