问题标题：
一道离散数学题设＜A,＜＝＞为一有限全序集,｜A｜＞＝2,R是A*A上的关系,根据R下列各定义,确定是否为半序集、全序集或良序集.设x,y,u,v为A中的任意元素1、＜x,y＞R＜u,v＞＜＝＞u∧y＜＝v2、＜
问题描述：
一道离散数学题
设＜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
沈群书回答：
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不成立.
个人对离散数学的语言不是很熟悉,
点击显示
数学推荐
热门数学推荐