Fundamentals of Computing: Properties of Relations: Reflexive, Symmetric and Transitive

Lesson overview

Classify relations by formal properties.

CourseFundamentals of Computing

Topic strandRelations

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

Test whether a relation is reflexive.
Test whether a relation is symmetric.
Test whether a relation is transitive.

Learning outcomes

By the end of this lesson, you can test whether a relation is reflexive.
By the end of this lesson, you can test whether a relation is symmetric.
By the end of this lesson, you can test whether a relation is transitive.

Key vocabulary

What this lesson is about

Reflexive, symmetric and transitive are properties of relations. Reflexive means every object relates to itself, symmetric means relationships go both ways, and transitive means two linked relationships imply a third.

This lesson is about checking definitions with quantifiers, not relying on whether a diagram looks balanced or intuitive.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

ReflexiveRelation property. Every object in the set is related to itself.

SymmetricRelation property. Whenever a is related to b, b is also related to a.

TransitiveRelation property. Whenever a is related to b and b is related to c, a must be related to c.

CounterexampleProof term. One valid case that disproves a universal claim.

Formal notation and definitions

Reflexive: \foralla \in A, aRa. Symmetric: \foralla,b \in A, aRb \Rightarrow bRa. Transitive: \foralla,b,c \in A, (aRb \land bRc) \Rightarrow aRc.

How to read the symbols

$\forall a\in A,\ aRa$ Reflexive: every object is related to itself.

$aRb\Rightarrow bRa$ Symmetric: every relation arrow has a matching reverse arrow.

$(aRb\land bRc)\Rightarrow aRc$ Transitive: a two-step connection forces the direct connection.

Use the quantified definitions literally. To prove a property, cover all relevant elements; to disprove it, give one valid counterexample.

Degree-level reasoning

Relations are central to databases, graphs, equivalence classes and ordering problems. The same ordered-pair definition supports several computing representations.

Property checks require quantifiers. One missing pair can disprove reflexivity, symmetry or transitivity, but proving the property needs all relevant cases.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

The relation 'has the same student ID as' is reflexive, symmetric and transitive; the relation 'follows on a social network' usually is not.

Objects: the base set A, arbitrary elements a, b and c, and the ordered pairs that make up relation R.

Model cue: Use a directed graph: reflexivity appears as a loop at every vertex, symmetry appears as paired arrows, and transitivity appears when two-step paths require a direct arrow.

2. Mathematical working

A=\{1,2,3\},\quad R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}

\forall a\in A,\ aRa\quad\text{so R is reflexive}

1R2\Rightarrow2R1\quad\text{but no pair involving 3 is required for symmetry beyond existing arrows}

Plain text version

Reflexive: ∀a ∈ A, aRa.
Symmetric: ∀a,b ∈ A, aRb ⇒ bRa.
Transitive: ∀a,b,c ∈ A, (aRb ∧ bRc) ⇒ aRc.

Worked use: For the relation 'has the same student ID as', every student has the same ID as themselves, if a has the same ID as b then b has the same ID as a, and if a matches b and b matches c then a matches c. The relation is reflexive, symmetric and transitive.

3. How to read the working

Read A first so the property checks have a domain: every quantified variable must be an element of A.
For reflexivity, check that every element has its loop pair: (1,1), (2,2) and (3,3).
For symmetry, check only arrows that exist: since (1,2) is present, (2,1) must also be present.
Do not infer transitivity from the diagram's appearance. Use the definition with aRb and bRc to test required direct pairs.

4. Computing meaning and check

The properties are quantified claims. A diagram may suggest a property, but ordered-pair checks or a general argument decide it.

Now check: Give a relation that is symmetric but not transitive. Use ordered pairs to justify your answer.

Worked example

From scenario to formal reasoning

Scenario: The relation 'has the same student ID as' is reflexive, symmetric and transitive; the relation 'follows on a social network' usually is not.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

For the relation 'has the same student ID as', every student has the same ID as themselves, if a has the same ID as b then b has the same ID as a, and if a matches b and b matches c then a matches c. The relation is reflexive, symmetric and transitive.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from Reflexive: ∀a ∈ A, aRa.
Apply: Use the relevant definition from relations; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is using one positive example as proof. A universal property needs every relevant case or a general argument.

Guided practice

Give a relation on {1,2,3} that is symmetric but not transitive.
Use ordered pairs to show the matching reverse arrows required for symmetry.
Identify the two-step path that fails transitivity.
Write a one-sentence distinction between proving a relation property and disproving it.

Quick checks

1. Which property requires every existing arrow aRb to have bRa?

ReflexiveSymmetricTransitive

2. What disproves transitivity?

A two-step path aRb and bRc with no aRc.A missing self-loop only.One pair whose reverse is absent.

Digital exam practice

Example exam task

Give a relation on {1,2,3} that is symmetric but not transitive. Justify your answer with quantified property language and ordered pairs.

Notation toolkit

\forall a\in A\ (aRa)

Means: reflexivity: every element relates to itself

How to use: Use it to check required loop pairs.

aRb\Rightarrow bRa

Means: symmetry: every arrow has its reverse

How to use: Use it to test pairs in both directions.

(aRb\land bRc)\Rightarrow aRc

Means: transitivity: two linked steps require a direct link

How to use: Use it to find missing required pairs.

What a good answer is expected to show

A strong answer for this lesson defines the base set A, arbitrary elements a, b and c, and the ordered pairs that make up relation R, applies the relations method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read A first so the property checks have a domain: every quantified variable must be an element of A.
For reflexivity, check that every element has its loop pair: (1,1), (2,2) and (3,3).
For symmetry, check only arrows that exist: since (1,2) is present, (2,1) must also be present.
Do not infer transitivity from the diagram's appearance. Use the definition with aRb and bRc to test required direct pairs.

Model answer

Reveal model answer

\text{symmetric: }\forall a,b\in A\ (aRb\Rightarrow bRa)

\text{transitive: }\forall a,b,c\in A\ ((aRb\land bRc)\Rightarrow aRc)

1R2\land2R3\land\neg(1R3)\Rightarrow R\text{ is not transitive}

Take R = {(1,2), (2,1), (2,3), (3,2)} on {1,2,3}. It is symmetric because every listed pair has its reverse. It is not transitive because 1R2 and 2R3 hold, but 1R3 is missing. One failed required pair disproves transitivity.

Practise next

Give a relation on {1,2,3} that is symmetric but not transitive.
Use ordered pairs to show the matching reverse arrows required for symmetry.

Self-marking criteria

Provides a concrete relation.
Checks every present arrow has a reverse for symmetry.
Identifies a two-step path missing its required direct pair.
Uses one counterexample to disprove transitivity.
Avoids relying on the diagram alone.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Equivalence Relations and Partitions.