Is there a faster way to determine partial orderings of basic finite sets?

Question

For example, consider the set $S = \{ 0, 1, 2, 3 \}$, and the following relation on $S$:

$$ R = \{(0,0), (1,1), (1,2), (1,3), (2,0), (2,2), (2,3), (3,0), (3,3) \}. $$

Obviously, I can go through each element and check for reflexivity, antisymmetry, and transitivity to confirm that this is, in fact, a partial ordering; but such methods of "brute force" become rather time consuming quite quickly as the size of $S$ and $R$ grow. In particular, I'm wondering if, perhaps, there is a way to use a logical matrix to determine these properties, because that would be quick and easy, I'd say. That is to say, I'm looking for something along the lines of "a logical matrix $M$ corresponding to a relation $R$ on a set $S$ is invertible iff $R$ is a partial ordering on $S$." Of course, I just made that up, but hopefully you get the idea.

Answer 1

As your question suggests, you can indeed use a matrix to visualize the relation. In your example, the matrix is $$ A = \left[\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 \end{array}\right]. $$ Note that there is a $1$ in the $(i,j)$-th cell if and only if $(i,j)\in R$.

Reflexivity: $R$ is reflexive if and only if $\operatorname{diag}A=\vec{1}$.

Now, let $B=A-I$ where $I$ denotes the identity.

Antisymmetry: $R$ is antisymmetric if and only if $b_{ij}=1$ implies $b_{ji}=0$.

Now, consider the graph of $B$:

Transitivity: $R$ is transitive if and only if the graph satisfies the following property: for each path $i_1 \rightarrow i_2 \rightarrow i_3$, there is an edge $i_1 \rightarrow i_3$.

Clearly, this is not true for your example due to the path $1\rightarrow 2\rightarrow 0$ and the missing edge $1\rightarrow 0$.

Answer 2

In practice you just check it by brute force. You can make it a bit faster to conduct by drawing a diagram with nodes indicating the elements 0, 1, 2, 3 and arrows between elements that are related (and such a diagram is good to do anyway in order to train your intuition). Then, instead of checking every combination of pairs for transitivity, you can just go to each node and check each combination of incoming edge and outgoing edge to see if their composition is also there.

Here one fairly quickly sees that we have $1\to 2\to 0$ without having $1\to 0$, so the relation fails to be transitive.

---

But, apart from that, don't bother with finding a smarter procedure. Determining whether a random set of pairs constitute a partial order is a problem of vanishingly small importance. In fact the only situation I can think of when anyone does this is if you're a student in an introductory set/order theory course, and the exercises contain a few problems of this kind -- for the sole purpose of verifying that you have understood the definition correctly.

Partial orders are of great importance in many areas of mathematics, but you essentially never come across them by checking an explicit set of pairs one by one. Instead you define the partial order abstractly from something you already have present, and then you prove in general that the kind of definition you're looking at will always produce a partial order under such-and-suck assumptions. And that kind of proof are not really helped by having a clever way to check explicit lists of pairs for partial-orderness.