Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 ยท Relations and Functions

Relations

Learn what a relation is as a set of ordered pairs, with domain, range, inverse and composition, shown as tables, arrow diagrams and Python code.

"Is less than", "is a parent of", "lives in the same city as", "divides": mathematics and everyday life are full of relationships between objects. Set theory captures every one of them with a single idea: a relation is a set of ordered pairs. Once you see relations this way, you can apply all the set operations you know to them.

Definition

A relation from A to B is a subset R โІ A ร— B. If (a, b) โˆˆ R we say "a is related to b" and write a R b. A relation on a set A is a relation from A to A, that is, a subset of A ร— A.

Example. Let A = {1, 2, 3, 4} and define R on A by a R b when a divides b. Then

Text
R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4) }

It has 8 pairs out of the 16 in A ร— A. The same relation can be shown in three ways.

As a set of pairs (above).

As a matrix, with 1 if the row element is related to the column element:

1 2 3 4
1 1 1 1 1
2 0 1 0 1
3 0 0 1 0
4 0 0 0 1

As an arrow diagram (a directed graph):

flowchart LR
    one["1"] --> two["2"]
    one --> three["3"]
    one --> four["4"]
    two --> four

Arrows for the divides relation, leaving out the loops a R a, which every number has.

Domain, range and image

For a relation R โІ A ร— B:

  • The domain is the set of first components: dom(R) = { a โˆˆ A : (a, b) โˆˆ R for some b }.
  • The range (or image) is the set of second components: ran(R) = { b โˆˆ B : (a, b) โˆˆ R for some a }.
  • The set B is sometimes called the codomain (the "target"). The range is always a subset of the codomain.

For the example above, domain and range are both {1, 2, 3, 4}. For S = {(1, 2), (1, 3), (2, 4)} we have dom(S) = {1, 2} and ran(S) = {2, 3, 4}.

The inverse relation

The inverse of R โІ A ร— B is the relation Rโปยน โІ B ร— A obtained by flipping every pair:

Text
Rโปยน = { (b, a) : (a, b) โˆˆ R }

For "divides", the inverse is "is a multiple of". The inverse of "is a parent of" is "is a child of". Also dom(Rโปยน) = ran(R) and ran(Rโปยน) = dom(R), and (Rโปยน)โปยน = R.

Composition

If R โІ A ร— B and S โІ B ร— C, the composition S โˆ˜ R โІ A ร— C connects a to c when there is a middle element b with a R b and b S c:

Text
S โˆ˜ R = { (a, c) : there is b with (a, b) โˆˆ R and (b, c) โˆˆ S }

The order is written right to left, like function composition. If R is "is a parent of" then R โˆ˜ R is "is a grandparent of".

Python Relations as sets of pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Operations on relations

Because relations are sets, you can use โˆช, โˆฉ, \ and complement on them. If R is "less than" and S is "equal to" on โ„, then R โˆช S is "less than or equal to". The complement of "less than" in โ„ ร— โ„ is "greater than or equal to". The identity relation Id = {(a, a) : a โˆˆ A} is "equals".

How many relations are there?

A relation on a set with n elements is any subset of an nยฒ-element product, so there are 2^(nยฒ) relations. For n = 3 that is 2โน = 512; for n = 4, 65,536. Only a few of them are interesting, and the next lessons will pick out the most important types.

Python Counting and enumerating relations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Relations in the wild

Relational databases take their name from this idea: a table with columns is a set of tuples, a subset of a Cartesian product of the column domains. A foreign key links one relation to another, and a SQL join is closely related to relational composition.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A relation from A to B is:

    A relation is any set of ordered pairs with first component in A and second in B.
  2. 2. For S = {(1, 2), (1, 3), (2, 4)}, what is the range?

    The range collects the second components: 2, 3 and 4.
  3. 3. What is the inverse of {(1, 2), (3, 4)}?

    The inverse flips each pair.
  4. 4. How many relations are there on a 3-element set?

    A relation is a subset of a 9-element product, so there are 2^9 = 512 of them.

Summary

  • A relation from A to B is a subset of A ร— B; a relation on A is a subset of A ร— A.
  • It can be drawn as a set of pairs, a matrix or an arrow diagram.
  • dom(R) is the set of first components, ran(R) of second components.
  • Rโปยน flips pairs; S โˆ˜ R chains two relations.
  • A set with n elements carries 2^(nยฒ) relations.

Next: Properties of Relations