Equivalence and partial order relations with examples
Equivalence relations:
A relation ‘R’ on set ‘A’ is said to be equivalent if R is
- Reflexive. It needs to be diagonal pair such as (a,a),(1,1),(8,8)
- Symmetric: it should have element such as (a,b) and (b,a) for example (1,4) and (4,1) in the relation set for symmetric
- Transitive: It needs to be in the form of (a,b), (b,c) so that we have (a,c)
Let us understand with an example
A={1,2,3} elements =2^3
|
A(1,1) |
A(1,2) |
A(1,3) |
|
A(2,1) |
A(2,2) |
A(2,3) |
|
A(3,1) |
A(3,2) |
A(3,3) |
R1={NULL} it is not reflexive and therefore equivalence does not holds.
R2={(1,1),(2,2) (3,3)} it is reflexive as it has diagonal pairs such as (a,a)
It is symmetric as all diagonal pair makes the set symmetric
Also if also transitive if it has only diagonal elements.
Therefore the relation is equivalence
R3={(1,1),(2,2) (3,3)(2,1)} It is reflexive as it has all diagonal elements
It is not symmetric as there exist only (2,1) and not (1,2) in R3. There the relation is not in
equivalence
R4={(1,1),(1,3),(2,1)(3,1)} It does not has all diagonal elements ref to table above, hence it does not have equivalence relation
R5={(1,1),(2,2),(3,3),(1,2)(1,3)(2,1)(3,1)} It is reflexive as it has all diagonal elements ref table
It is symmetric as we have (1,2) and (2,1). Also we have (1,3) and (3,1)
It is transitive as if we take (1,1) (3,3) then we have (3,1) as in (a,b) and (b,c) we have (a,c) for it to become transitive. Hence equivalence hold here.
R6={(1,1),(1,2),(2,1),(2,3),(3,1)(3,2),(3,3)} It is not reflexive as we do not have all diagonal elements ref table above and you will find (2,2) is missing.
Partial order relations
- Reflexive. It needs to be diagonal pair such as (a,a),(1,1),(8,8)
- Anti Symmetric: it should not have element such as (a,b) and (b,a) for example (1,4) and (4,1) in the relation set for symmetricity. If it has (a,b) and not (b,a) then it is said to be in anti symmetric form
- Transitive: It needs to be in the form of (a,b), (b,c) so that we have (a,c)
A=(1,2,3}
R1={NULL} it is not reflexive and therefore partial order relation does not holds.
R2={(1,1),(2,2) (3,3)} it is reflexive as it has diagonal pairs such as (a,a)
It is antii-symmetric. Also it is transitive if it has only diagonal elements.
Therefore the relation is in partial order
R3={(1,1),(2,2) (3,3)(2,1)} It is reflexive as it has all diagonal elements
It is anti symmetric as there exist only (2,1) and not (1,2) in R3. There the relation is in
Partial order
R4={(1,1),(1,3),(2,1)(3,1)} It does not has all diagonal elements ref to table above, hence it does not have reflexive property and therefore partial order does not holds for this relation
R5={(1,1),(2,2),(3,3),(1,2)(1,3)(2,1)(3,1)} It is reflexive as it has all diagonal elements ref table
It is symmetric as we have (1,2) and (2,1). Also we have (1,3) and (3,1). Therefore it is not anti symmetric
It is transitive as if we take (1,1) (3,3) then we have (3,1) as in (a,b) and (b,c) we have (a,c) for it to become transitive. Hence the relation is not in partial order
R6={(1,1),(1,2),(2,1),(2,3),(3,1)(3,2),(3,3)} It is not reflexive as we do not have all diagonal elements ref table above and you will find (2,2) is missing.Therefore relation is not set to be in partial order.
No comments:
Post a Comment