0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.