设R是有限集X上的二元关系定义 R＋=R∪R2∪…∪Rn∪… 证明：

大学 2020-04-02 16:46:27 定义,关系已帮助人

设R是有限集X上的二元关系，定义

R⁺=R∪R²∪…∪Rⁿ∪…，

证明：

难度★★☆ 搜索

对任意x，y，z∈X，若〈x，y〉∈R+，〈y，z〉∈R+，则存在正整数s和t，使得〈x，y〉∈Rs，〈y，z〉∈Rt，所以〈x，z〉∈=Rs+t，而Rs+tR+，因此〈x，z〉∈R+，故R+是可传递的．$对任意〈x，y〉∈R+，必存在正整数s，使得〈x，y〉∈Rs，因此存在z1，z2，…，zs-1∈X，使得〈x，z1〉∈R，〈z1，z2〉∈R，…，〈zs-1，y〉∈R．因为RP，所以〈x，z1〉∈P，〈z1，z2〉∈P，…，〈zs-1，y〉∈P．由P的传递性，可得〈x，y〉∈P，故R+P．$由R+的定义可知R+R，又由题(1)和(2)可知R+是包含R的最小可传递关系，故R+就是R的传递闭包．

设R是有限集X上的二元关系 定义 R＋=R∪R2∪…∪Rn∪… 证明：