Discrete Mathematics · Quick Reference

Relations Cheat Sheet

Discrete Mathematics · Lesson 3/9

In one line: a relation describes how elements from one set connect to elements of another — the mathematical way of expressing 'is related to'.

Key Ideas

1Definition. A relation from set A to set B is a set of ordered pairs (a,b), where a is in A and b is in B.

2Domain and Range. The domain is the set of all first elements (a-values) used in the relation; the range is the set of all second elements (b-values).

3Reflexive. A relation on set A is reflexive if every element is related to itself: (a,a) is in the relation for all a in A.

4Symmetric. A relation is symmetric if whenever (a,b) is in the relation, (b,a) is too.

5Transitive. A relation is transitive if whenever (a,b) and (b,c) are both in the relation, (a,c) must be too.

Worked Examples

Let R = {(1,1),(2,2),(3,3),(1,2),(2,1)} on set {1,2,3}. Is R reflexive?

Yes, R is reflexive

Using the same R, is it symmetric?

Yes, R is symmetric

Let R = {(1,2),(2,3)} on {1,2,3}. Is R transitive?

No, R is not transitive

Practice Yourself

Find the domain of R = {(1,2),(3,4),(5,6)}.

{1,3,5}

Find the range of R = {(1,2),(3,4),(5,6)}.

{2,4,6}

Is R = {(1,1),(2,2)} on {1,2} reflexive?

Yes

Is R = {(1,2)} on {1,2} symmetric?

No, since (2,1) is not in R