largest partial order $\equiv$ total order.
base set = A has 5 elements.
Consider, this A = {1, 2, 3, 4, 5} and less than equal to relation R.
We know less than equal to relation on any subset of natural numbers is Toset.
Here –
- 1 is related to 1, 2, 3, 4, 5.
- 2 is related to 2, 3, 4, 5.
- 3 is related to 3, 4, 5.
- 4 is related to 4, 5.
- 5 is related to 5.
Summing up elements in relation = 5 + 4 + 3 + 2 + 1 = 15.
One other way to solve this is –
Relations are represented using matrix.
A Matrix representation of largest POR will look like a triangular matrix.
example – A = {a, b, c, d, e}
R |
a |
b |
c |
d |
e |
a |
1 |
|
|
|
|
b |
1 |
1 |
|
|
|
c |
1 |
1 |
1 |
|
|
d |
1 |
1 |
1 |
1 |
|
e |
1 |
1 |
1 |
1 |
1 |
all empty cells represent “is not related to” and 1 represent “is related to”.
Note : Adding any more 1 in above table will violate anti-symmetry property. Thus, will no longer be POR.
Total number of 1’s = Number of elements in largest POR = 15.