[Math] Proving a relation is partial ordering

elementary-set-theoryrelations

I have a problem proving that a very simple relation is partial ordering. It is defined explicitly (i.e. with pairs of numbers) and I have no idea how to do a formal proof for its antisymmetric property.

We have a set $M=\{{1,2,3,4\}}$ and relation $R=\{{(1,1),(2,2),(3,3),(4,4),(3,2),(2,4),(3,4)\}}$ at $M^2$.

Should I simply list all pairs to show that the definition (for all $x,y$ in $M$ : $xRy$ and $yRx$ implies $x=y$) is satisfied or there exist a more formal way to prove it (like formally showing there is no such pair $x,y$ that the definition would not hold).

(The same question actually applies for the remaining two properties as well – reflexivity and transitivity).

Thanks

Best Answer

You name one property you need to check: antisymmetric.

You must also ensure that the relation is reflexive, and transitive.

A relation R is a partial order on a set $S$

  1. if it is reflexive: for all $x\in S, x R x$

  2. if it is antisymmetric, which is the property you list

  3. And if it is transitive: for all $x, y, z \in S,\; (x R y \text{ and}\; y R z) \rightarrow x R z$

Reflexivity is easy to check here: $(1,1),(2,2),(3,3),(4, 4) \in R$, so for all $x\in S, xRx$.

In small sets like this, it's usually easy enough to check whether or not these three properties all hold.

There are really only three pair in your set for which you need to consider antisymmetry and transitivity.

Can you find counterexamples to these properties?

All you need is one counterexample to a property, and all you need is one property to fail to hold, to conclude that a relation is NOT a partial order on a set.

If no property fails, the relation is a partial order on your set.

Edit:

To address your question as to what constitutes a formal proof: Yes, you could list all pairs to show satisfaction of all the properties. It depends on your instructor, how detailed you have to be in a proof.

For example, you could state $\lnot \exists x \in S$ such that $\lnot (x R x)$, which translates to the equivalent, $\forall x \in S, (xRx)$. And do similarly for each property, without listing all pairs.

Again, it depends on the context context in which you need to prove that the relation defines a partial order on S.

Related Question