Proving a relation is partial ordering

Question

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

Answer 1

First we need to understand the definitions, and then we need to see that they hold for this case.

$R$ is a relation on $M$ means that $R\subseteq M^2$.

• We say that $R$ is reflexive if for every $m\in M$ the pair $(m,m)\in R$.
• We say that $R$ is antisymmetric if whenever $(m,n)\in R$ and $(n,m)\in R$ then $m=n$.
• We say that $R$ is transitive if whenever $(m,n)\in R$ and $(n,k)\in R$ then $(m,k)\in R$.

Now let us see what happens in this case.

1. To check that $R$ is reflexive we need to see that $(1,1),(2,2),(3,3),(4,4)\in R$. That is quite easy to check.
2. To check that $R$ is antisymmetric we need to look for two pairs $(m,n)$ and $(n,m)$. If we found such pairs and $m\neq n$ then $R$ is not antisymmetric, if there is no such counterexample then we are done. That too is easy to check.
3. To check that $R$ is transitive we need to check that whenever we have pairs of the form $(m,n)$ and $(n,k)$ then $(m,k)\in R$ as well. For example we have $(3,2)$ and $(2,4)$ so we need $(3,4)$ to be in $R$ as well, and indeed it happens. (Note that this is not the only case needs verifying!)

Answer 2

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.