Question

一道离散数学题

设＜A，＜＝＞为一有限全序集，｜A｜＞＝2，R是A*A上的关系，根据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, 则<a,b> R <b,a>与<b,a> R <a,b>都不能成立.
否则有a ≤ b∧b ≤ a, 由≤的反对称性得a = b, 矛盾.

2. 结合关系是(x ≤ u∧x ≠ u)∨(x = u∧y ≤ v)吧?
这就是字典序, 是一个全序关系, 从而也是半序关系, 由A×A是有限集, 也是良序关系.

反对称性: 若<x,y> R <u,v>且<u,v> R <x,y>.
由<x,y> R <u,v>即(x ≤ u∧x ≠ u)∨(x = u∧y ≤ v),
得(x ≤ u∧x ≠ u)∨x = u, 即x ≤ u.
同理由<u,v> R <x,y>即(u ≤ x∧u ≠ x)∨(u = x∧v ≤ y)可得u ≤ x.
于是由≤的反对称性得x = u.
代入<x,y> R <u,v>得y ≤ v, 代入<u,v> R <x,y>得v ≤ y.
再由≤的反对称性得y = v, 于是<x,y> = <u,v>.

传递性: 若<x,y> R <u,v>且<u,v> R <s,t>.
由<x,y> R <u,v>得x ≤ u, 由<u,v> R <s,t>得u ≤ s. 于是由≤的传递性得x ≤ s.
若x ≠ s, 则<x,y> R <s,t>成立.
若x = s, 有u ≤ s = x, 可得u = x (≤反对称性), 于是x = u = s.
代入<x,y> R <u,v>得y ≤ v, 代入<u,v> R <s,t>得v ≤ t. 于是由≤的传递性得y ≤ t.
可知<x,y> R <s,t>也成立.

完全性: 任给<x,y>, <u,v>.
由≤的完全性, 成立x ≤ u或u ≤ x. 不妨设x ≤ u.
若x ≠ u, 则有<x,y> R <u,v>.
若x = u, 当y ≤ v时有<x,y> R <u,v>, v ≤ y时有<u,v> R <x,y>.
而由≤的完全性, 成立y ≤ v或v ≤ y至少有一个成立.
因此<x,y> R <u,v>与<u,v> R <x,y>至少有一个成立.

3. 不是半序关系, 因为没有反对称性.
对a ≠ b, 由≤的完全性, 不妨设a ≤ b. 可知<a,a> R <a,b>, <a,b> R <a,a>, 但<a,a> ≠ <a,b>.

4. 不是半序关系, 因为没有自反性. 即<x,y> R <x,y>不成立.

个人对离散数学的语言不是很熟悉, 有疑问请追问.