Relations and Functions

Types of Relations

Understand

If \(A\) and \(B\) are sets, a relation \(R\) from \(A\) to \(B\) is any subset of the Cartesian product \(A\times B\). If \((a,b)\in R\) we write \(a\,R\,b\) and say "\(a\) is related to \(b\)". A relation from \(A\) to itself is called a relation on \(A\).

Since \(A\times B\) has \(n(A)\cdot n(B)\) elements and every subset is a relation, there are \(2^{n(A)\,n(B)}\) relations from \(A\) to \(B\).

Two special relations

Empty relation \(R=\varnothing\): no element is related to any element.
Universal relation \(R=A\times A\): every element is related to every element.

Three properties of a relation on \(A\)

Property	Definition	How to test
Reflexive	\((a,a)\in R\) for every \(a\in A\)	Check every element of \(A\) is related to itself.
Symmetric	\((a,b)\in R\Rightarrow(b,a)\in R\)	Every pair must have its reverse.
Transitive	\((a,b)\in R\) and \((b,c)\in R\Rightarrow(a,c)\in R\)	Every two-step chain needs its shortcut.

To prove a property, argue for arbitrary elements. To disprove it, one counter-example is enough. For example, "\(a < b\)" on \(\mathbb{R}\) is transitive but not reflexive (\(2 < 2\) is false) and not symmetric (\(1 < 2\) but not \(2 < 1\)).

Key Concepts

Number of relations from \(A\) to \(B\): \(2^{mn}\) when \(n(A)=m,\ n(B)=n\).
Reflexivity is about every element of the set, not just the elements that appear in R.
A statement with a false "if" part is true – so the empty relation is symmetric and transitive.

Formula Bank

Number of relations

\[n(A)=m,\ n(B)=n \;\Rightarrow\; 2^{mn} \text{ relations from } A \text{ to } B\]

On a set with \(n\) elements there are \(2^{n^2}\) relations, \(2^{n^2-n}\) reflexive relations and \(2^{n(n+1)/2}\) symmetric relations.

Key Points

Proving vs disproving

Prove a property with arbitrary elements; disprove it with a single concrete counter-example.

Empty and universal relations

On a non-empty set, the empty relation is symmetric and transitive but not reflexive; the universal relation \(A\times A\) is an equivalence relation.

Common Mistakes

Checking reflexivity only on listed elements

For \(R=\{(1,1),(2,2)\}\) on \(A=\{1,2,3\}\), \(R\) is not reflexive because \((3,3)\) is missing.

Forgetting chains through the same element

In testing transitivity, \((1,2)\) and \((2,1)\) form a chain that requires \((1,1)\).

Practice & Topic Test

Topic Practice

A fresh set of questions from this topic. Change answers freely – solutions appear after you submit.

Start Practice

Topic Test

Timed: up to 10 questions in 15 minutes.

Start Test

Topic Summary

Relation = subset of a Cartesian product. Test reflexive, symmetric, transitive separately; prove with general elements, disprove with one counter-example.

Ready to practise this topic?

Create a free account to take practice sessions and tests, see detailed explanations and track your progress.

Create Student Account