1
$\begingroup$

On Polish Wikipedia article on binary relations one can find the following statement: "a relation is antisymmetric iif it is irreflexive and transitive".

Is it correct? Does a given relation have to be irreflexive to be antisymmetric?

As far as I understand a relation ($R \subseteq A \times A$) is irreflexive iif: $$\forall_{x \in A}: \lnot (x R x) $$ and antisymmetric iff: $$\forall_{x, y \in A}: (xRy) \land (yRx) \rightarrow x = y$$ As so, if we define relations over the set $A = \{1, 2, 3, 4\}$ then both following relations should be antisymmetric: $$ R_1 = \{ (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) \}\\ R_2 = \{ (1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4) \} $$ although only $R_1$ is also irreflexive ($R_2$ is actually reflexive).

Do I miss something?

$\endgroup$
  • $\begingroup$ The “iif” in the text is “if” or “iff”? It makes a big difference. With “if” the statement is correct, with “iff” it's wrong: equality is certainly antisymmetric and transitive, but obviously not irreflexive (on a nonempty set). $\endgroup$ – egreg Jan 21 '17 at 21:49
  • $\begingroup$ It actually says "if" - my mistake. (Now you know why I'm horrible in math & double check everything. ;P) $\endgroup$ – Szpilona Jan 21 '17 at 22:08
2
$\begingroup$

No, an antisymmetric relation doesn't have to be irreflexive. However, if a relation $R$ is both transitive and irreflexive, then it is automatically antisymmetric. Here is the reason:

Say we have $(a,b)\in R$. Then, because of transitivity, if we also have $(b,a)\in R$, we must have $(a,a)\in R$, which breaks irreflexivity. Therefore we can never have both $(a,b)$ and $(b,a)$ in $R$, which means that the statement "If $(a,b)\in R$ and $(b,a)\in R$, then $a=b$" is vacuously satisfied, and $R$ is thus antisymmetric.

$\endgroup$
0
$\begingroup$

It's a common misunderstanding of “if”. Consider the following true statement about Alice, who's outside at the beach:

Alice gets wet if it rains

Does it need to rain in order that Alice gets wet? Of course not! She could be swimming in the sea in a very hot sunny day!

Now change “Alice gets wet” with “the relation $R$ is antisymmetric” and “it rains” with “the relation $R$ is irreflexive and transitive”: you get the statement on Wikipedia.

The statement says, expressed in a different way: a sufficient condition for a relation to be antisymmetric is to be irreflexive and transitive.

The statement doesn't say that this condition is also necessary. Indeed, a trivial example is the relation $\{(1,1),(2,2)\}$ on the set $\{1,2\}$ (the equality).

More generally, a partial (non strict) order is a reflexive, antisymmetric and transitive relation. We surely don't want it to be irreflexive, do we? ;-)

There is a relation that's reflexive and irreflexive, but it's a very boring one: the empty relation on the empty set.

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