一道离散数学题设＜A,＜＝＞为一有限全序集,｜A｜＞＝2,R是A*A上的关系,根据R下列各定义,确定是否为半序集、全序集或良序集.设x,y,u,v为A中的任意元素1、＜x,y＞R＜u,v＞＜＝＞u∧y＜＝v2、＜

Question

一道离散数学题
设＜A,＜＝＞为一有限全序集,｜A｜＞＝2,R是A*A上的关系,根据R下列各定义,确定是否为半序集、全序集或良序集.设x,y,u,v为A中的任意元素
1、＜x,y＞R＜u,v＞＜＝＞u∧y＜＝v
2、＜x,y＞R＜u,v＞＜＝＞x＜＝u∧x≠u∨（x＝u∧y＜＝v）
3、＜x,y＞R＜u,v＞＜＝＞x＜＝u
4、＜x,y＞R＜u,v＞＜＝＞x＜＝u∧x≠u

Answer 1

1.题目没打全.猜测应该是x ≤ u∧y ≤ v.
这是一个半序关系,但不是全序关系.
验证基本是平凡的,由≤的自反性,反对称性与传递性可对应得到R的相应性质.
不是全序也很简单,若a ≠ b,则 R 与 R 都不能成立.
否则有a ≤ b∧b ≤ a,由≤的反对称性得a = b,矛盾.
2.结合关系是(x ≤ u∧x ≠ u)∨(x = u∧y ≤ v)吧?
这就是字典序,是一个全序关系,从而也是半序关系,由A×A是有限集,也是良序关系.
反对称性:若 R 且 R .
由 R 即(x ≤ u∧x ≠ u)∨(x = u∧y ≤ v),
得(x ≤ u∧x ≠ u)∨x = u,即x ≤ u.
同理由 R 即(u ≤ x∧u ≠ x)∨(u = x∧v ≤ y)可得u ≤ x.
于是由≤的反对称性得x = u.
代入 R 得y ≤ v,代入 R 得v ≤ y.
再由≤的反对称性得y = v,于是 = .
传递性:若 R 且 R .
由 R 得x ≤ u,由 R 得u ≤ s.于是由≤的传递性得x ≤ s.
若x ≠ s,则 R 成立.
若x = s,有u ≤ s = x,可得u = x (≤反对称性),于是x = u = s.
代入 R 得y ≤ v,代入 R 得v ≤ t.于是由≤的传递性得y ≤ t.
可知 R 也成立.
完全性:任给,.
由≤的完全性,成立x ≤ u或u ≤ x.不妨设x ≤ u.
若x ≠ u,则有 R .
若x = u,当y ≤ v时有 R ,v ≤ y时有 R .
而由≤的完全性,成立y ≤ v或v ≤ y至少有一个成立.
因此 R 与 R 至少有一个成立.
3.不是半序关系,因为没有反对称性.
对a ≠ b,由≤的完全性,不妨设a ≤ b.可知 R ,R ,但 ≠ .
4.不是半序关系,因为没有自反性.即 R 不成立.
个人对离散数学的语言不是很熟悉,