0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't believe so, I htink it is just the regular ≤ relation. @TomCruise $\endgroup$ – JCMcRae Nov 9 '14 at 20:16
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.