Chapter 1 · Relations and Functions

Exercise 1.1 · Q3: $b = a+1$ on {1, …, 6}

Exercise 1.1Types of relations · Exercise 1.1

The question

Check whether the relation $R$ defined in the set $\{1, 2, 3, 4, 5, 6\}$ as $R = \{(a, b) : b = a + 1\}$ is reflexive, symmetric or transitive.

Exam answer

$R = \{(1, 2), (2, 3), (3, 4),$ $(4, 5), (5, 6)\}$ ⁠.

$(1, 1) \notin R$ ⁠, as $1 \ne 1 + 1$ ⁠. So $R$ is not reflexive.

$(1, 2) \in R$ but $(2, 1) \notin R$ ⁠, as $1 \ne 2 + 1$ ⁠. So $R$ is not symmetric.

$(1, 2), (2, 3) \in R$ but $(1, 3) \notin R$ ⁠, as $3 \ne 1 + 1$ ⁠. So $R$ is not transitive.

Hence $R$ is neither reflexive nor symmetric nor transitive.

Want the reason behind every step, the basics and the checks?

The one idea this problem is built on

The rule $b = a+1$ says " $b$ is the next number after $a$ ". Moving one step forward can never leave you where you started (so no number is related to itself), can never be undone by another step forward (so the reverse pair is never in $R$ ⁠), and two steps forward land you two places on, not one (so chains do not close up). Each property fails, and each failure is shown by one explicit pair.

Given, to find, and the plan

Given: The set $A = \{1,2,3,4,5,6\}$ and the rule: $(a,b)\in R$ exactly when $b = a+1$ ⁠, with both $a$ and $b$ in $A$ ⁠.
To find: Whether $R$ is reflexive, whether it is symmetric, and whether it is transitive.
Plan: (1) The set is small, so list every pair of $R$ ⁠. (2) Test each of the three properties against the list. Each property is a "for all" statement, so a single pair that breaks it is a complete disproof; we give that pair and the arithmetic. (3) For good measure, show the failure is not a fluke: it happens for every element.

Basics you need

1A relation is a set of ordered pairs

A relation $R$ in a set $A$ is a subset of $A\times A$ ⁠. A pair $(a,b)$ belongs to $R$ only if both $a$ and $b$ are in $A$ and the rule holds. Order matters: $(1,2)$ and $(2,1)$ are different pairs. Basics: what a relation is

2The three properties

Reflexive: $(a,a)\in R$ for every $a\in A$ ⁠. Symmetric: $(a_1,a_2)\in R$ implies $(a_2,a_1)\in R$ ⁠. Transitive: $(a_1,a_2)\in R$ and $(a_2,a_3)\in R$ imply $(a_1,a_3)\in R$ ⁠. Basics: reflexive, symmetric, transitive

3How to disprove a "for all" statement

Each property claims something for every element or every pair. To show a property fails, it is enough to produce one specific case where it breaks, and to show the arithmetic. Basics: proving and disproving

Solution

List every pair in $R$

Go through each $a\in A$ and compute $b = a+1$ ⁠. Keep the pair only if $b$ is also in $A$ ⁠.

$a$ 1 2 3 4 5 6

$b = a+1$ 2 3 4 5 6 7

$b\in A$ ⁠? yes yes yes yes yes no

$R = \{(1,2), (2,3), (3,4), (4,5), (5,6)\}.$
So $R$ has 5 pairs, out of the $6\times 6 = 36$ pairs in $A\times A$ ⁠.

With only six elements, the safest way to answer every question about $R$ is to write $R$ out in full: then each property becomes a matter of looking for a pair in a short list. The case $a = 6$ gives no pair, because $6+1 = 7$ is not in $A$ ⁠, and a relation in $A$ may only use elements of $A$ ⁠.

A relation in $A$ is a subset of $A\times A$ (Basic 1). Both entries of every pair must come from $A$ ⁠.

The five pairs of $R$ are the five solid arrows, each from a number to the next one. The dashed arrows show two pairs that are not in $R$ ⁠: $(2,1)$ (an arrow backwards) and $(1,3)$ (a jump of two). There is no loop at any number.
Reflexive? No

Reflexive would need $(a,a)\in R$ for every $a\in A$ ⁠. Test $a = 1$ ⁠: the pair $(1,1)$ is in $R$ only if $1 = 1+1$ ⁠, that is $1 = 2$ ⁠, which is false. So $(1,1)\notin R$ ⁠, and $R$ is not reflexive.

In fact no element works: $(a,a)\in R$ would mean $a = a+1$ ⁠, and subtracting $a$ from both sides gives $0 = 1$ ⁠, which is impossible. None of the 6 pairs $(1,1),\dots,(6,6)$ is in $R$ ⁠.

"Reflexive" is a claim about every element of $A$ ⁠, so one element that is not related to itself is enough to disprove it. The general line ( $a = a+1 \Rightarrow 0 = 1$ ⁠) is extra: it shows the failure is complete, not just at one element. You can also see it in the list of Step 1: no pair has equal entries.

One counterexample disproves a "for every" statement (Basic 3). Here the counterexample is $a = 1$ ⁠, with the arithmetic $1+1 = 2 \ne 1$ ⁠.
Symmetric? No

Symmetric would need: whenever $(a,b)\in R$ ⁠, also $(b,a)\in R$ ⁠. Take $(1,2)$ ⁠, which is in $R$ because $2 = 1+1$ ⁠. Its reverse $(2,1)$ is in $R$ only if $1 = 2+1 = 3$ ⁠, which is false. So $(1,2)\in R$ but $(2,1)\notin R$ ⁠, and $R$ is not symmetric.

Again this happens for every pair: if $b = a+1$ ⁠, the reverse would need $a = b+1 = a+2$ ⁠, that is $0 = 2$ ⁠. So not one of the 5 pairs has its reverse in $R$ ⁠.

To break symmetry we need a pair that is in $R$ whose reverse is not. Choosing a pair from the list in Step 1 guarantees the first half. Then we test the reverse against the rule. Notice that the reverse of " $b$ is one more than $a$ " is " $a$ is one more than $b$ ", the opposite statement, and both cannot hold at once.

Symmetric is an "if … then" statement for all pairs. A counterexample must make the "if" part true and the "then" part false (Basic 3).
Transitive? No

Transitive would need: whenever $(a,b)\in R$ and $(b,c)\in R$ ⁠, also $(a,c)\in R$ ⁠. Take $(1,2)\in R$ and $(2,3)\in R$ (both from the list; $2 = 1+1$ and $3 = 2+1$ ⁠). Transitivity would demand $(1,3)\in R$ ⁠, that is $3 = 1+1 = 2$ ⁠, which is false. So $R$ is not transitive.

Every chain fails in the same way. The chains in $R$ are exactly
$\begin{aligned} &1\to2\to3, && 2\to3\to4,\\ &3\to4\to5, && 4\to5\to6,\end{aligned}$
and in each one the ends $(a, a+2)$ would need $a+2 = a+1$ ⁠, that is $2 = 1$ ⁠. None of $(1,3)$ ⁠, $(2,4)$ ⁠, $(3,5)$ ⁠, $(4,6)$ is in $R$ ⁠.

A counterexample to transitivity needs two linked pairs, $(a,b)$ and $(b,c)$ ⁠, with the same middle element $b$ ⁠, and then the direct pair $(a,c)$ missing. Here two steps forward take you two places on, while the rule only allows one. This is different from Q1(ii), where no two pairs link up at all: here the links do exist, they just do not close up.

For transitivity the second pair must start where the first one ends. A chain is $a \to b \to c$ ⁠; the conclusion is the shortcut $a\to c$ (Basic 2).
Conclude

$R$ fails all three tests: $(1,1)\notin R$ ⁠; $(1,2)\in R$ but $(2,1)\notin R$ ⁠; $(1,2),(2,3)\in R$ but $(1,3)\notin R$ ⁠. So $R$ is neither reflexive nor symmetric nor transitive.

The question asks about each property separately, so the answer must report on all three, each with its own counterexample. Failing one property says nothing about the others: Q1(iii) of this exercise, for instance, is reflexive and transitive but not symmetric.

$a$	1	2	3	4	5	6
$b = a+1$	2	3	4	5	6	7
$b\in A$ ⁠?	yes	yes	yes	yes	yes	no

Result

The relation $R$ ⁠, with its five pairs $(1,2),(2,3),(3,4),(4,5),(5,6)$ ⁠, is not reflexive ( $(1,1)\notin R$ since $1 \ne 2$ ⁠), not symmetric ( $(1,2)\in R$ but $(2,1)\notin R$ since $1\ne 3$ ⁠) and not transitive ( $(1,2),(2,3)\in R$ but $(1,3)\notin R$ since $3 \ne 2$ ⁠). (Textbook answer: "Neither reflexive nor symmetric nor transitive", which agrees.)

Check it with numbers

Count everything directly from the list of 5 pairs. Pairs of the form $(a,a)$ ⁠: 0 of the 6 needed. Pairs whose reverse is also present: 0 of 5. Chains $(a,b),(b,c)$ ⁠: there are exactly 4 (listed in Step 4), and the shortcut $(a,c)$ is present for 0 of them. The site's verification script repeats this count by brute force over all 36 pairs of $A\times A$ ⁠.

Common mistakes

Including $(6,7)$ ⁠. 7 is not in the set, so this pair is not in $R$ ⁠. Always check that both entries lie in $A$ ⁠.
Saying "not transitive" with no example. Name the two linked pairs and the missing pair: $(1,2)$ ⁠, $(2,3)$ and $(1,3)$ ⁠.
Using unlinked pairs as a transitivity counterexample. $(1,2)$ and $(3,4)$ do not form a chain (the second does not start at 2), so they say nothing about transitivity.
Reading $b = a+1$ backwards. The pair is $(a,b)$ with $b$ the larger number, so $(1,2)\in R$ ⁠, not $(2,1)$ ⁠.

What to take away

On a small finite set, list the relation first. Every property then becomes a search through a short list.
A "move by a fixed non-zero amount" relation ( $b = a + d$ ⁠, $d \ne 0$ ⁠) is never reflexive, is not symmetric once it contains a pair, and is not transitive once it contains a chain: the algebra $a = a+d$ ⁠, $a = a+2d$ ⁠, $a+2d = a+d$ always gives a contradiction. The conditions matter: in Q1(ii), $y = x+5$ with $x<4$ has no chain at all, so it is transitive.
Each failure needs its own explicit counterexample with the arithmetic shown.

Every fact used, and where it comes from

Fact	Used in	Source
A relation in $A$ is a subset of $A\times A$	Step 1	Section 1.2, opening paragraph (Lesson: relations)
Reflexive, symmetric, transitive	Steps 2–4	Definition 3, Section 1.2 (Lesson: types of relations)
One counterexample disproves a "for all" statement	Steps 2–4	Logic of quantifiers (Basics: proving and disproving)
$a = a+1$ ⁠, $a = a+2$ ⁠, $a+2 = a+1$ are impossible	Steps 2–4	Subtract $a$ from both sides
All pairs, chains and counts	Check	Brute force in the site's verification script

Found an error, or want more?

Tell us if something on this page is wrong or unclear, or if you would like a fuller explanation, another method or a new feature. Send feedback on this problem →

Exercise 1.1 · Q3: b=a+1b = a+1b=a+1 on {1, …, 6}

Basics you need

Solution

List every pair in RRR

Reflexive? No

Symmetric? No

Transitive? No

Conclude

Every fact used, and where it comes from

Exercise 1.1 · Q3: $b = a+1$ on {1, …, 6}

List every pair in $R$