linux and windows tips, mathematics, and some recipes

Sunday, March 05, 2006

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.


Post a Comment

<< Home