0

I know that to prove something is a partial order, the relation ≤ has to be reflexive, transitive, and anti-symmetric. So, given this relation {(1, 1),(2, 2),(3, 3),(4, 4),(3, 2),(2, 1),(3, 1),(4, 1)} on the set S = {1, 2, 3, 4}:

For reflexivity, can I say that since for all a in the set S, a is greater than or equal to itself as denoted by the pairs in the relation, and therefore, reflexive?

For transitivity, and reflexivity, I am stuck.

Any help would be greatly appreciated.

JCMcRae
  • 843

1 Answers1

0

Reflexivity is just a matter of noting every element in $S$ is related to itself, which you have.

For transitivity I would just note 1 is only related to itself, so there are no nontrivial instances of transitivity to explore. Similarly, no elements are related to $3$ or $4$ except themselves. (When I say related to, I mean on the left hand side of the pair)

$2$ is related to $1$ and $2$, that is $(2,1)$ and $(2,2)$ are in the relation, so then check that anything related to $2$ is also related to $1$. This is satisfied because $(3,2)$ and $(3,1)$ are in the relation.

Then check $3$, we have $(3,2)$ and $(3,1)$. So if for some element $a$, $(a,3)$ is in the relation, we need $(a,2)$ and $(a,1)$. But then we see there is no such element $a$. The same goes for $4$.

This is a bit of brute force, in arguing away each possible failure, but that seems like it might be the point of the exercise.

Pburg
  • 1,226