Partial Preorders
How many transitive and reflexive relations (partial preorders) are there on a set of three elements? This question was recently posed in a first-year maths problem sheet at the University of Oxford.
It can easily be shown that there are 64 reflexive relations on such a set, and one can determine which of them are transitive. This is a bit of a pain, so I wrote a Maple worksheet to simplify the process.
The worksheet computes all relations on a set of 3 elements and represents them as matrices. Without loss of generality, the set of 3 elements is S = {1, 2, 3}. A relation is then represented by a matrix A with entries from {0, 1}, where A[i, j]=1 iff i ~ j.
With this representation, a matrix is reflexive iff the diagonal entries are all 1. The transitivity condition is a little more complicated, but can be coded without much difficulty.
It turns out that the answer is 29.
It can easily be shown that there are 64 reflexive relations on such a set, and one can determine which of them are transitive. This is a bit of a pain, so I wrote a Maple worksheet to simplify the process.
The worksheet computes all relations on a set of 3 elements and represents them as matrices. Without loss of generality, the set of 3 elements is S = {1, 2, 3}. A relation is then represented by a matrix A with entries from {0, 1}, where A[i, j]=1 iff i ~ j.
With this representation, a matrix is reflexive iff the diagonal entries are all 1. The transitivity condition is a little more complicated, but can be coded without much difficulty.
It turns out that the answer is 29.
posted by j.shoehorn @ 9:27 pm
0 Comments:
Post a Comment
<< Home