Mathematical-Reasoning · Unit 27 · Video 1 · Interactive Practice

Reflexive, Symmetric and Transitive Relations

IKey Formulas

Property of $R$ on $A$	Definition	Fails exactly when
Reflexive on $A$	$(\forall x \in A)\,(x \mathrel{R} x)$	$(\exists x \in A)\,\big((x, x) \notin R\big)$ : one missing loop
Symmetric	$(\forall x, y \in A)\,(x \mathrel{R} y \to y \mathrel{R} x)$	$(\exists x, y \in A)\,\big((x, y) \in R \wedge (y, x) \notin R\big)$ : one arrow with no return
Transitive	$(\forall x, y, z \in A)\,\big((x \mathrel{R} y \wedge y \mathrel{R} z) \to x \mathrel{R} z\big)$	$(\exists x, y, z \in A)\,\big((x, y), (y, z) \in R \wedge (x, z) \notin R\big)$ : one chain with no direct link

Key Insight: Each property is a universal statement, so its negation $\neg(\forall x)\,P(x) \equiv (\exists x)\,\neg P(x)$ asks for a single witness, and $\neg(P \to Q) \equiv P \wedge \neg Q$ says what that witness looks like.

IIOne Witness Is Enough

A property holds only if every case passes; it fails as soon as one witness turns up.

Relation on {1, 2, 3, 4}

IIIPredict, Then Check

Decide each property for a relation on $\{1, 2, 3\}$ before the witness search runs.

💡 One relation in the deck has no pairs at all. Symmetry and transitivity are conditionals whose hypotheses never hold for it, so they hold vacuously.

IVQuiz Questions

Problem 1 · Negating Symmetry

Given: a relation $R$ on a nonempty set $A$ . Which statement means exactly that $R$ is not symmetric?

✅ Correct! The

\forall

becomes

\exists

, and

\neg(x \mathrel{R} y \to y \mathrel{R} x)

becomes

x \mathrel{R} y \wedge y \not\mathrel{R} x

: one pair whose reverse is missing.

❌ Not quite. This says every pair loses its reverse, which is far stronger than failing symmetry. Negating a

\forall

statement gives an

\exists

statement.

❌ Not quite. A pair that has its reverse is what symmetry asks for; it is no witness against it. The witness has

x \mathrel{R} y

and

y \not\mathrel{R} x

❌ Not quite. The quantifier must change to

\exists

. As written, taking

x = y

demands

x \mathrel{R} x

and

x \not\mathrel{R} x

at once, so the statement is false for every relation.

❌ Not quite. Negate the quantifier and the conditional separately.

Show solution

Symmetric is the statement $(\forall x, y \in A)\,(x \mathrel{R} y \to y \mathrel{R} x)$ . Its negation is

\neg(\forall x, y \in A)\,(x \mathrel{R} y \to y \mathrel{R} x) \equiv (\exists x, y \in A)\,\neg(x \mathrel{R} y \to y \mathrel{R} x).

Since $\neg(P \to Q) \equiv P \wedge \neg Q$ , this is $(\exists x, y \in A)\,(x \mathrel{R} y \wedge y \not\mathrel{R} x)$ : some pair $(x, y)$ is in $R$ while $(y, x)$ is not. Other pairs may still have their reverses.

Problem 2 · Finding the Witness

Given: on $A = \{1, 2, 3, 4\}$ , the relation $R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (2,3), (3,2)\}$ . Which statement is a witness that $R$ is not transitive?

✅ Correct! The path

1 \to 2 \to 3

has no shortcut

1 \to 3

, so the conditional's hypothesis holds and its conclusion fails.

❌ Not quite.

(1, 1)

is in

R

, so this chain from

1

back to

1

has its shortcut.

❌ Not quite. Missing pairs alone prove nothing: a witness against transitivity needs two pairs

(x, y), (y, z) \in R

with

(x, z) \notin R

❌ Not quite. An element related only to itself creates no two-step chain without a shortcut; the only chain through

4

4 \to 4 \to 4

, whose shortcut

(4, 4)

is present.

❌ Not quite. Look for a two-step path

x \to y \to z

whose direct arrow

x \to z

is missing.

Show solution

A witness against transitivity is a choice of $x, y, z$ with $(x, y) \in R$ , $(y, z) \in R$ and $(x, z) \notin R$ .

Take $x = 1$ , $y = 2$ , $z = 3$ : $(1, 2) \in R$ and $(2, 3) \in R$ , but $(1, 3) \notin R$ . So $R$ is not transitive. (The path $3 \to 2 \to 1$ is a second witness, but one is enough.)

$R$ is reflexive on $A$ (all four loops are present) and symmetric (the arrows $1 \leftrightarrow 2$ and $2 \leftrightarrow 3$ come in pairs), so transitivity is the only property it fails.

Problem 3 · Almost Every Loop

Given: on $A = \{1, 2, 3\}$ , the relation $R = \{(1,1), (2,2), (1,2)\}$ . Which statement is true?

✅ Correct! Every two-step chain in

R

uses a loop, so its shortcut is

(1, 2)

(1, 1)

(2, 2)

, all in

R

❌ Not quite. Reflexive on

A

needs a loop at every element of

A

;

(3, 3) \notin R

is a witness against it.

❌ Not quite.

(1, 2) \in R

but

(2, 1) \notin R

❌ Not quite. A missing reverse is a witness against symmetry, not transitivity. A witness against transitivity needs a two-step chain with no direct link.

❌ Not quite. Check each property against its own definition.

Show solution

Reflexive: $(3, 3) \notin R$ , so $R$ is not reflexive on $A$ .

Symmetric: $(1, 2) \in R$ and $(2, 1) \notin R$ , so $R$ is not symmetric.

Transitive: list every pair of pairs $(x, y), (y, z) \in R$ :

$(1, 1), (1, 1)$ gives $(1, 1) \in R$ ; $\ (1, 1), (1, 2)$ gives $(1, 2) \in R$ ;
$(1, 2), (2, 2)$ gives $(1, 2) \in R$ ; $\ (2, 2), (2, 2)$ gives $(2, 2) \in R$ .

Every required pair is present, so $R$ is transitive.

Problem 4 · The Empty Relation

Given: the empty relation $R = \emptyset$ on $A = \{1, 2, 3\}$ . Which properties does it have?

✅ Correct!

(1, 1) \notin R

is a witness against reflexivity, but a witness against symmetry or transitivity would need a pair in

R

, and there is none.

❌ Not quite. To fail symmetry, some

(x, y)

must be in

R

. With no pairs, the hypotheses of the two conditionals never hold, so both are true.

❌ Close, but… Reflexivity is not a conditional: it asserts

(x, x) \in R

for each

x \in A

, and

(1, 1) \notin \emptyset

❌ Not quite. Reflexivity is the one property

\emptyset

fails: it needs the pairs

(1,1)

(2,2)

and

(3,3)

to be present.

❌ Not quite. Ask what a witness of failure would need for each property.

Show solution

Reflexive: the statement $(\forall x \in A)\,(x \mathrel{R} x)$ is false, with witness $x = 1$ : $(1, 1) \notin \emptyset$ .

Symmetric: a witness would be $x, y$ with $(x, y) \in R$ and $(y, x) \notin R$ . No pair is in $R$ , so no witness exists and the property holds (vacuously).

Transitive: a witness would need $(x, y) \in R$ and $(y, z) \in R$ . Again no pair is in $R$ , so the property holds.

Solved: 0 / 4