等價關係和等價劃分

      

     在一個集合上的等價關係和等價劃分是一一對應的。「一一對應「這四個字，表示知道一個等價關係，可以求出一個等價劃分；反之，知道一個等價劃分，也能求出一個等價關係。

       下面講述這兩種題型的解法。        

        1、已知A上的一個等價關係R，求R在A上所誘導的劃分。

        解法：畫出等價關係R的關係圖，圖中有幾個不連通的部分，就有幾個劃分塊。

        例題：設A={1,2,3,4,5,6,7,8}，A上的等價關係R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<8,8><1,4><1,7>,<2,5>,<2,8>,<3,6><4,1>,<4,7>,<5,2>,<5,8>,<6,3>,<7,1>,<7,4>,<8,2>,<8,5>}，求R在A上所誘導的等價劃分。

         解：直接根據R中的序偶畫出關係R的關係圖。

      圖中的結點分為不連通的三個部分，所以A上由關係R所誘導的劃分是{{1,4,7},{2,5,8},{3,6}}.

     

    2、已知A上的一個劃分S={S1,S2,...,Sn}，求S在A上所誘導的等價關係R。

     解法：R=(S1ⅩS1)∪(S2ⅩS2)∪…∪ (SnⅩSn)

     例題：設A={1,2,3,4,5,6,7}，確定A上的等價關係R，使R能產生劃分{{1，2，5}，{4,6}，{3,7}}。

      解：R=({1,2,5}Ⅹ{1,2,5})∪({4,6}Ⅹ{4,6})∪ ({3,7}Ⅹ{3,7})

             ={<1,1>,<1,2>,<1,5>,<2,1>,<2,2>,<2,5>,<5,1>,<5,2>,<5,5>}∪{<4,4>,<4,6>,<6,4>,<6,6>}∪{<3,3>,<3,7>,<7,3>,<7,7>}

       ={<1,1>,<1,2>,<1,5>,<2,1>,<2,2>,<2,5>,<5,1>,<5,2>,<5,5>,<4,4>,<4,6>,<6,4>,<6,6>,<3,3>,<3,7>,<7,3>,<7,7>}