Examples and Counterexamples of Relations which Satisfy Certain Properties

1. Reflexivity and Irreflexivity

A relation on a nonempty set cannot be both reflexive and irreflexive. This follows almost immediately from the definitions: a reflexive relation on a nonempty set $X$ must contain every pair of the form $(x,x) \in X\times X$, while an irreflexive relation cannot contain any such pair. Reflexivity and irreflexivity are mutually exclusive properties.

2. Transitivity and Intransitivity

A relation may be vacuously transitive and intransitive: if there is no $y$ such that $(x,y),(y,z) \in R$ for some $x$ and $z$, then the hypotheses of both transitivity and intransitivity fail. Any conclusion is implied by a false hypothesis, so such a relation is both transitive and intransitive. For example, let $R$ be the relation on the three element set $X = \{1,2,3\}$ given by $$ R = \{ (1,2), (1,3) \}. $$ This relation is (trivially) both transitive and intransitive, as there is no $y$ which appears in the first slot of one pair, and in the second slot of another.

Aside from such vacuous examples (vacuous in the sense that the hypotheses are false, not in the sense that they are "easy"), a relation cannot be both transitive and intransitive: if $(x,y), (y,z) \in R$, then either $(x,z) \in R$ (and $R$ is not intransitive), or $(x,z) \not\in R$ (and $R$ is not transitive). Aside from vacuous examples, these two properties are mutually exclusive.

3. Intransitivity and Irreflexivity

A nontrivial relation which is intransitive must also be irreflexive. The essential idea here is that reflexive relations "build in" transitive relations. More formally, consider a proof by contraposition: suppose that $R$ is a nontrivial relation which is not irreflexive. Then there is some $x$ such that $(x,x) \in R$. Taking $x=y=z$, this implies that $$ (x,y), (y,z), (x,z) \in R, $$ which contradicts the definition of intransitivity. Thus $R$ is not intransitive. Therefore a relation which is not irreflexive is not intransitive.

By contraposition, an intransitive relation must be irreflexive.

4. Symmetry and Antisymmetry

Perhaps counterintuitively, a nontrivial relation can be both symmetric and antisymmetric. Suppose that $R$ is a nontrivial relation which is both symmetric and antisymmetric. As $R$ is nontrivial, it contains some pair $(x,y)$. The symmetry of $R$ implies that $(y,x)$ is also in $R$. The antisymmetry of $R$ then implies that $x=y$. Hence a relation on a set $X$ which is both symmetric and antisymmetric must be a subset of the diagonal $\{(x,x) : x \in X\}$. Any such relation is vacuously transitive, and can be reflexive if it is the entire diagonal (this is the equality relation). There is no nontrivial irreflexive relation which is both symmetric and antisymmetric.

5. Examples on a Set with Three Elements

The remainder of this answer is structured as follows: the set $X$ is the three element set $X = \{1,2,3\}$. Each of the items below gives an example of a relation $R$ on $X$ which satisfies various combinations of the properties listed in the question. The examples are labeled with a string such as "[RT-]".

• The first character may be R for a reflexive relation, I for an irreflexive relation, or - for a relation which is neither reflexive nor irreflexive.

• The second character may be T for a transitive relation, I for an intransitive relation, or - for a relation which is neither transitive nor intransitive.

• The third character may be S for a symmetric relation, A for an antisymmetric relation, or - for a relation which is neither symmetric nor antisymmetric.

Commentary is given in cases where it might be illuminating.

• [RTS] $R = \{(1,1), (1,2), (2,2), (2,1), (3,3)\}$

• [RTA] $R = \{(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)\}$

• [RT-] $R = \{ (1,1), (1,2), (2,1), (2,2), (3,1), (3,2), (3,3) \}$

• [RIS] No example exists, see 3.

• [RIA] No example exists, see 3.

• [RI-] No example exists, see 3.

• [R-S] $R = \{(1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)\}$

• [R-A] $R = \{(1,1), (1,2), (2,2), (2,3), (3,3)\}$

• [R--] $R = \{(1,1), (2,2), (3,3), (1,2), (2,3) \}$

• [ITS] No nontrivial example exists.

  Suppose that $R$ is some nontrivial, irreflexive, transitive relation. If $R$ is not antisymmetric, then there exist pairs $(x,y)$ and $(y,x)$ which are both elements of $R$. But $R$ is transitive, so $(x,x)$ and $(y,y)$ must also be elements of $R$. In other words, a nontrivial, irreflexive, transitive relation must be antisymmetric.

• [ITA] $R = \{(1,2), (1,3), (2,3)\}$

  The usual order relations ($\le$, $<$, $\ge$, $>$) on $\mathbb{R}$ are more interesting examples of relations which are transitive and antisymmetric. Weak inequalities are reflexive, while strict inequalities are irreflexive.

• [IT-] No nontrivial example exists, see [ITS].

• [IIS] $\{(1,2), (2,1)\}$.

• [IIA] $R = \{(1,2)\}$

• [II-] $\{(1,2), (1,3), (2,1)\}$.

• [I-S] $R = \{(1,2), (2,1), (2,3), (3,2) \}$.

  Transitivity and intransitivity can be a little hard to see by inspection. This relation is not intransitive, as every intransitive relation must be antisymmetric; and it is not transitive, as $(1,2),(2,3) \in R$ but $(1,3)\not\in R$.

• There is no example of an irreflexive and antisymmetric relation on $X$ which is neither transitive nor intransitive. However, if $R$ is a relation on as set $Y = \{a,b,c,d\}$, then an example exists:

  [I-A] $R = \{ (a,b), (a,c), (b,c), (c,d) \}$

  This relation is not transitive, because $(a,c), (c,d) \in R$, but $(a,d)\not\in R$; and is not intransitive, because $(a,b), (b,c), (a,c) \in R$.

• [I--] $R = \{(1,2), (1,3), (2,1), (2,3)\}$

• [-TS] $R = \{(1,1), (1,2), (2,1), (2,2)\}$

  Note that the above relation is not reflexive on the three element set $X = \{1,2,3\}$ because it does not contain the pair $(3,3)$. However, thought of as a relation on the two element set $\{1,2\}$, this relation is reflexive.

• [-TA] $R = \{(1,1), (1,2), (2,3), (3,1)\}$

• [-T-] $R = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3) \}$

• [-IS] No nontrivial example exists, see 3.

• [-IA] No nontrivial example exists, see 3.

• [-I-] No nontrivial example exists, see 3.

• [--S] $R = \{(1,2), (2,1), (2,2) \}$

• [--A] $R = \{(1,1), (1,2), (2,3) \}$

• [---] $R = \{ (1,1), (1,2), (2,1), (2,3) \}$

Some Additional Examples

Abstractly, it is good to have simple examples and counterexamples to different permutations of relational properties. However, it is also useful to have in mind more interesting models—every one of these properties comes from something in the world. The arbitrary permutations of properties may not have any useful meaning, but the properties themselves are interesting.

• An equivalence relation is any relation which is reflexive, transitive, and symmetric. The most basic such relation is equality ($=$): $x=y$ if and only if $x$ and $y$ are, in fact, the same object. Abusing notation a bit, this means that $=$, though of as an equivalence relation on some arbitrary set $X$, is the diagonal of $X\times X$. That is, $$ = \quad\text{is the set}\quad \{ (x,x) : x \in X\}. $$ There are other important equivalence relations, and many important properties in mathematics hold only "up to equivalence" with respect to some equivalence relation.

  For example, $1/2$ and $2/4$ are not really the same object—ask any second grader. If I have a package of two cookies, then I can have one cookie, and give another to a friend. We each get one of the two cookies, or $1/2$ of the package. If I have a package of four cookies, then I can have two and give two to a friend. We each get two cookies, or $2/4$ of the package. Two is not one! These things are different. However, from the point of view of addition and multiplication, $1/2$ and $2/4$ behave in essentially the same way—they are equivalent with respect to a relation which ultimately gives us the rational numbers. Hence we can treat them as though they are the same object (and typically do!).

• Order relations are examples of transitive, antisymmetric relations. For example, $\le$, $\ge$, $<$, and $>$ are examples of order relations on $\mathbb{R}$—the first two are reflexive, while the latter two are irreflexive. Set containment relations ($\subseteq$, $\supseteq$, $\subset$, $\supset$) have simililar properties.

  In general, I think that it is reasonable to think of transitive, antisymmetric relations as those relations which "rank" or "order" things in some rough way. Inequalities order numbers, set containment relations order sets, taxonomies classify and order living organisms, etc.

• Intransitive relations are kind of an odd duck, and it is not immediately obvious how they might come up in the real world. However, they do! My favorite example is the two-player game "Rock-Paper-Scissors". Rock beats scissors, scissors beats paper, paper beats rock. The relation "beats" is intransitive. Parenthood is also (generally speaking—one can always find exceptions once human behaviour is involved) an intransitive relation: I am the parent of my daughter, and my mother is my parent, but my mother is not my daughter's parent.

To start, it's worth pointing out that, as defined in the question above, none of pairs of "opposite" properties (reflexive / irreflexive, transitive / intransitive or symmetric / antisymmetric) are actually antonyms. Not only is it possible for a relation to satisfy none of these properties (and indeed most random relations on sufficiently large sets won't satisfy any of them), but it's also possible for a relation to satisfy two seemingly opposite properties at once, with some restrictions:

• There is only one relation which is both reflexive and irreflexive, as defined above: the empty relation $R = \emptyset$ on the empty set $S = \emptyset$. For relations on non-empty sets, reflexivity and irreflexivity are mutually exclusive.
• If no element $x \in X$ appears on both the left side and the right side of a relation, it is vacuously both transitive and intransitive. In other words, $R$ is both transitive and intransitive if and only if $R \subset A \times B$ for some disjoint subsets $A$ and $B$ of $X$. Such relations are always irreflexive and antisymmetric, never symmetric unless $R = \emptyset$, and never reflexive unless $R = X = \emptyset$.
• A relation is both symmetric and antisymmetric if all its elements are of the form $(x, x)$ for some $x \in X$. In other words, $R$ is both symmetric and antisymmetric if and only if $(x,y) \in R \implies x = y$. Such relations are always transitive, and never intransitive unless $R = \emptyset$; they can be either reflexive (if $R = \{(x,x): x \in X\}$) or irreflexive (if $R = \emptyset$) or neither.

Except for the "paradoxical" combinations described above, the three properties of (ir)reflexivity, (in)transitivity and (anti)symmetry are mostly independent of each other. The only further restrictions are that:

• An intransitive relation must also be irreflexive (and thus cannot be reflexive unless the underlying set is empty): setting $x = y = z$ in the definition of intransitivity leads to a contradiction unless $(x,x) \notin R$ for all $x \in X$.
• An irreflexive transitive relation must be antisymmetric (and cannot be symmetric unless empty): if $R$ contains both $(x,y)$ and $(y,x)$, then transitivity implies that $R$ must also contain $(x,x)$ and $(y,y)$.

For all other combinations of the six properties, examples of relations with (only) those properties exist on the four-element set $X = \{a,b,c,d\}$. Here is a complete list of them, generated using a simple Python script:

• reflexive, symmetric, antisymmetric, transitive: $R_d = \{(a,a), (b,b), (c,c), (d,d)\}$
• reflexive, symmetric, transitive: $\{(a,b), (b,a)\} \cup R_d$
• reflexive, symmetric: $\{(a,b), (a,c), (b,a), (c,a)\} \cup R_d$
• reflexive, antisymmetric, transitive: $\{(a,b)\} \cup R_d$
• reflexive, antisymmetric: $\{(a,b), (b,c)\} \cup R_d$
• reflexive, transitive: $\{(a,b), (b,a), (c,d)\} \cup R_d$
• reflexive: $\{(a,b), (a,c), (b,a)\} \cup R_d$
• irreflexive, symmetric, antisymmetric, transitive, intransitive: $\emptyset$
• irreflexive, symmetric, intransitive: $\{(a,b), (b,a)\}$
• irreflexive, symmetric: $\{(a,b), (a,c), (b,a), (b,c), (c,a), (c,b)\}$
• irreflexive, antisymmetric, transitive, intransitive: $\{(a,b)\}$
• irreflexive, antisymmetric, transitive: $\{(a,b), (a,c), (b,c)\}$
• irreflexive, antisymmetric, intransitive: $\{(a,b), (b,c)\}$
• irreflexive, antisymmetric: $\{(a,b), (a,c), (b,c), (b,d)\}$
• irreflexive, intransitive: $\{(a,b), (a,c), (b,a)\}$
• irreflexive: $\{(a,b), (a,c), (b,a), (b,c)\}$
• symmetric, antisymmetric, transitive: $\{(a,a)\}$
• symmetric, transitive: $\{(a,a), (a,b), (b,a), (b,b)\}$
• symmetric: $\{(a,a), (a,b), (b,a)\}$
• antisymmetric, transitive: $\{(a,a), (a,b)\}$
• antisymmetric: $\{(a,a), (a,b), (b,c)\}$
• transitive: $\{(a,a), (a,b), (b,a), (b,b), (c,d)\}$
• none: $\{(a,a), (a,b), (a,c), (b,a)\}$

Each relation in the list above satisfies all the properties named in that entry and no others out of the six properties listed in the question. Each example relation on the list has the smallest possible number of pairs among all relations on $X$ with that combination of properties, and is the first in lexicographical order among those with the same number of pairs.

The only combination of properties that requires a four-element set is "irreflexive and antisymmetric (and neither transitive nor intransitive)," for which the minimal example is $R = \{(a,b), (a,c), (b,c), (b,d)\}$. All other combinations on the list above can also be exhibited with relations on a three-element set, although in some cases an example with only three elements may require more pairs than if a fourth element is allowed.

The only technically possible combination of properties missing from the list above is "reflexive, irreflexive, symmetric, antisymmetric, transitive, intransitive", which, as noted above, is only possible in the vacuous case when $R = X = \emptyset$.