Example 4: A relation on {1, 2, 3} that is reflexive only

Basics you need

Solution

1. Lay out the relation on a grid

   Draw $A\times A$ as a 3 × 3 grid: row $a$⁠, column $b$ is the pair $(a,b)$⁠. Shade the five pairs of $R$⁠.

   With a finite relation, a picture of the whole of $A\times A$ shows every property at a glance. Reflexive means the whole diagonal is shaded. Symmetric means the shading is a mirror image across the diagonal. Transitive is harder to see, so we will check it with a full list of chains.
   $A\times A$ has 9 pairs (Basic 4); $R$ uses 5 of them.

2. Reflexive: all three diagonal pairs are present

   Reflexive needs $(a,a)\in R$ for each $a\in\{1,2,3\}$⁠. There are only three values to check:

   $$(1,1)\in R, \qquad (2,2)\in R, \qquad (3,3)\in R.$$

   All three appear in the list, so $R$ is reflexive.

   "For every $a\in A$" here means "for $a = 1, 2, 3$", because A has only three elements. Checking all three is a complete proof (Basic 3). Note the other two pairs, $(1,2)$ and $(2,3)$⁠, play no role in reflexivity: extra pairs never stop a relation from being reflexive.
   Definition 3(i): $R$ is reflexive if $(a,a)\in R$ for every $a\in A$⁠.

3. Not symmetric: $(1,2)$ is in $R$ but $(2,1)$ is not

   Symmetric would need: for every pair in $R$⁠, its reverse is also in $R$⁠. Look at $(1,2)$⁠:

   $$(1,2)\in R \qquad\text{but}\qquad (2,1)\notin R.$$

   One failure is enough, so $R$ is not symmetric.

   For completeness, here is every pair with its reverse:

   Pair in $R$	Reverse	Reverse in $R$⁠?
   $(1,1)$	$(1,1)$	yes
   $(2,2)$	$(2,2)$	yes
   $(3,3)$	$(3,3)$	yes
   $(1,2)$	$(2,1)$	no
   $(2,3)$	$(3,2)$	no

   Symmetry is a "for every pair" statement, so one pair whose reverse is missing is a full disproof. The table shows a second failure, $(2,3)$⁠, but it is not needed. The diagonal pairs are always their own reverses, so they can never break symmetry.
   Definition 3(ii): $(a_1,a_2)\in R \Rightarrow (a_2,a_1)\in R$⁠. Order matters in a pair: $(1,2) \ne (2,1)$ (Basic 1).

4. Not transitive: $(1,2)$ and $(2,3)$ are in $R$ but $(1,3)$ is not

   Transitive would need: whenever $(a,b)\in R$ and $(b,c)\in R$⁠, also $(a,c)\in R$⁠. Take $a = 1$⁠, $b = 2$⁠, $c = 3$⁠:

   $$(1,2)\in R \ \text{ and } \ (2,3)\in R, \qquad\text{but}\qquad (1,3)\notin R.$$

   So $R$ is not transitive.

   For completeness, here are all 8 chains $(a,b),(b,c)$ that can be formed from pairs of $R$ (the second pair must start where the first ends):

   $(a,b)$	$(b,c)$	Need $(a,c)$	In $R$⁠?
   $(1,1)$	$(1,1)$	$(1,1)$	yes
   $(1,1)$	$(1,2)$	$(1,2)$	yes
   $(1,2)$	$(2,2)$	$(1,2)$	yes
   $(1,2)$	$(2,3)$	$(1,3)$	no
   $(2,2)$	$(2,2)$	$(2,2)$	yes
   $(2,2)$	$(2,3)$	$(2,3)$	yes
   $(2,3)$	$(3,3)$	$(2,3)$	yes
   $(3,3)$	$(3,3)$	$(3,3)$	yes

   Exactly one chain fails, and it is the one the textbook names.

   The chain $1\to2\to3$ is the only one that uses two different non-diagonal pairs. Chains involving a diagonal pair such as $(1,1),(1,2)$ always close up automatically, because $(a,a),(a,c)$ demands only $(a,c)$⁠, which we already have. That is why, in a reflexive relation, transitivity can only fail on chains of two non-diagonal pairs.
   Definition 3(iii): $(a_1,a_2)\in R$ and $(a_2,a_3)\in R \Rightarrow (a_1,a_3)\in R$⁠. One failing chain disproves it (Basic 3).

5. Conclude

   $R$ is reflexive (Step 2), not symmetric (Step 3) and not transitive (Step 4). So $R$ is reflexive but neither symmetric nor transitive.

   This example shows the three properties are independent: having one of them tells you nothing about the others. The textbook pairs it with Example 3, which is symmetric only.

Every fact used, and where it comes from