Is a transitive asymmetric relation a partial order?

1.4k Views Asked by At

Is a transitive asymmetric relation a partial order? I'm asking this because of the following situation:

If a relation $R$ is transitive and assymmetric, it cannot be reflexive. (Otherwise, $R(x,x)\rightarrow R(x,x)$ trivially, denying asymmetry). Hence, $R$ is also irreflexive.

If a relation $R$ is transitive and irreflexive, then it cannot be symmetric (since symmetry + transitivity $\rightarrow$ reflexivity). Hence, $R$ is asymmetric.

Many textbooks describes a partial order as transitive irreflexive relations. By the reasoning above, does this follows also to transitive asymmetric ones? I'm having trouble grasping this notion. thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

First, to terminology, partial order is usually interpreted as a transitive, anti-symmetric, reflexive relation, with strict partial order being used for a transitive, asymmetric, irreflexive relation. (So, ironically but in a common twist, a strict partial order is not a partial order. This is like how a manifold with boundary is not a manifold.)

A relation being transitive and asymmetric is equivalent to it being transitive and irreflexive, and so either can be used as a definition.

If $R$ is asymmetric, meaning $R(a,b)\implies \neg R(b,a)$ for all $a$ and $b$, then $R(a,a)\implies \neg R(a,a)$ for all $a$ and thus $R(a,a)$ must not hold for any $a$, hence $R$ is irreflexive. We can establish this without even transitivity.

Conversely, if $R$ is transitive and irreflexive, then we have $R(a,b)\land R(b,c) \implies R(a,c)$ and $\neg R(a,a)$ for all $a$, $b$, and $c$. Choosing $a = c$, we get $R(a,b)\land R(b,a) \implies R(a,a)$ for all $a$ and $b$, and thus it can't be the case that both $R(a,b)$ and $R(b,a)$ are true, and so $R(a,b)\implies \neg R(b,a)$, hence $R$ is asymmetric.

Your conclusion is correct and your reasoning is almost correct. The only issue is a relation being asymmetric is not equivalent to it not being symmetric. Asymmetry is a stronger condition which means that it's never the case that both $R(a,b)$ and $R(b,a)$ hold. Symmetry means it's always the case that $R(a,b)$ holds if $R(b,a)$ does. The negation of this is that sometimes it's the case that $R(a,b)$ doesn't hold when $R(b,a)$ does, but this allows that $R(a,b)$ and $R(b,a)$ do sometimes hold too. For example, $R = \{(1,2),(2,1),(1,3)\}$ is a relation that is not symmetric but also not asymmetric.