How to Prove a Relation Is Reflexive and Transitive

A relation is a rule that tells you which pairs of elements are related. To prove that a relation has a property, translate the definition into a statement about arbitrary elements, then show that statement holds. The underlying set matters: the same rule can be reflexive on one set but not another.

State the relation and its set

A binary relation $R$ on a set $A$ is a collection of ordered pairs from $A \times A$. The notation $aRb$ means that the pair $(a,b)$ belongs to $R$. You may also see a relation written as a condition, such as “$a \leq b$” or “$a-b$ is divisible by 3.”

Before proving anything, identify both the set and the relation. For example, “$\leq$ on the integers” means the set is $\mathbb{Z}$ and $aRb$ exactly when $a \leq b$. Without the set, claims about relation properties can be ambiguous.

The two definitions

A relation $R$ on $A$ is reflexive if every element is related to itself:

$$\forall a \in A,\quad aRa.$$

It is transitive if whenever one element is related to a second and the second to a third, the first is related to the third:

$$\forall a,b,c \in A,\quad (aRb \text{ and } bRc) \Longrightarrow aRc.$$

These definitions give the proof structure directly. For reflexivity, start with an arbitrary $a \in A$ and verify $aRa$. For transitivity, assume $aRb$ and $bRc$, and use the definition of $R$ to establish $aRc$.

Worked example: divisibility

Let $A$ be the positive integers, and define $aRb$ to mean “$a$ divides $b$.” By definition, $a$ divides $b$ if there is an integer $k$ such that $b=ak$.

Reflexivity: Take any positive integer $a$. Since $a=a\cdot 1$ and $1$ is an integer, $a$ divides $a$. This works for every $a \in A$, so the relation is reflexive.

Transitivity: Suppose $aRb$ and $bRc$. Then there are integers $m$ and $n$ such that

$$b=am \quad\text{and}\quad c=bn.$$

Substitute the first equation into the second:

$$c=(am)n=a(mn).$$

Because the product $mn$ is an integer, this shows that $a$ divides $c$. Thus $aRc$, and the relation is transitive.

The proof uses arbitrary positive integers, not a few sample values. Testing examples can suggest a property, but it cannot prove that it holds for every element of an infinite set.

A second example: equality of remainders

On the integers, define $aRb$ when $a-b$ is divisible by 3. This relation is reflexive because $a-a=0$, and 0 is divisible by 3.

For transitivity, suppose $aRb$ and $bRc$. Then for some integers $m$ and $n$, $a-b=3m$ and $b-c=3n$. Adding gives $a-c=3(m+n)$. Since $m+n$ is an integer, $a-c$ is divisible by 3, so $aRc$. The key move is to combine the equations supplied by the assumptions.

A useful proof template

For a relation defined by a condition, write the proof in this order:

1. Reflexivity: “Let $a$ be arbitrary in $A$. By the definition of $R$, … Therefore $aRa$.”
2. Transitivity: “Let $a,b,c$ be arbitrary in $A$, and suppose $aRb$ and $bRc$. By the definition of $R$, … Combining these facts gives … Therefore $aRc$.”

Fill in the middle using the actual rule defining your relation. If the rule is an equation, substitute or combine equations. If it is an inequality, use the relevant order property. If it involves a function, apply the function’s given assumptions.

Common mistakes

• Forgetting the underlying set. Reflexivity requires $aRa$ for every element in the specified set, not for every possible object.
• Checking only examples. A few successful cases do not establish a universal claim. Start with arbitrary elements.
• Proving symmetry instead of transitivity. Symmetry asks whether $aRb$ implies $bRa$. Transitivity requires two assumptions, $aRb$ and $bRc$, and a conclusion about $a$ and $c$.
• Assuming a property from the name of a relation. A relation can be reflexive without being transitive, or transitive without being reflexive. Verify each definition independently.
• Ignoring the assumptions in a transitivity proof. You must use both $aRb$ and $bRc$ to reach $aRc$; merely restating the desired conclusion is not a proof.

If either property fails, one counterexample is enough to show that it does not hold. To disprove reflexivity, find one $a \in A$ for which $aRa$ is false. To disprove transitivity, find $a,b,c \in A$ with $aRb$ and $bRc$ true but $aRc$ false.