Question

离散数学关于等价关系的题

设R是一个二元关系，设S={<a，b>|对于某一c，有<a,c>∈R,且<b,c>∈R}，证明：若R是一个等价关系，则S也是一个等价关系。

Answer 1

　　证明 只需验证如下3个条件，即知 S 也是一个等价关系。设 R 是 A 上的关系，
　　1）自反性：对任意 a∈A，因<a,a>∈R，<a,a>∈R，故 <a,a>∈S；
　　2）传递性：设 <a,b>, <b,c>∈S，则有 d, e∈A，使
　　　　<a,d>∈R，<d,b>∈R，<b,e>∈R，<e,c>∈R，
而 R 具传递性，得
　　　　<a,e>∈R，<e,c>∈R，
由 S 的定义，得 <a,c>∈S，传递性得证。
　　3）对称性：设 <a,b>∈S，则有 c∈A，使
　　　　<a,c>∈R，<c,b>∈R，
而 R 具传递对称性，得
　　　　<c,a>∈R，<b,c>∈R，
由 S 的定义，得 <b,a>∈S，对称性得证。