Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Sets, Relations and Functions

Relations and Their Properties

Understand binary relations as sets of pairs, test reflexive, symmetric, antisymmetric and transitive properties, and compute closures and compositions in Python.

A binary relation from a set A to a set B is a subset R โІ A ร— B. We write a R b when (a, b) โˆˆ R. "Is less than" on numbers, "divides" on integers, "is a friend of" in a social network and "is a foreign key of" in a database are all relations. When A = B we say R is a relation on A.

Because a relation is just a set of pairs, every operation from the previous lesson applies: you can unite two relations, intersect them or take complements.

Representing relations

You can store a relation as a set of tuples, as a Boolean matrix, or as a directed graph where an arrow goes from a to b if a R b. The three views are interchangeable and each makes different questions easy.

flowchart LR
    1 --> 2
    2 --> 3
    1 --> 3
    3 --> 3

The relation {(1,2), (2,3), (1,3), (3,3)} drawn as a directed graph. The loop at 3 is the pair (3,3).

Python Three views of one relation

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.

The four classic properties

For a relation R on a set A:

  • Reflexive: a R a for all a โˆˆ A. (Every vertex has a loop.)
  • Symmetric: if a R b then b R a.
  • Antisymmetric: if a R b and b R a then a = b.
  • Transitive: if a R b and b R c then a R c.

These are independent. "โ‰ค" on integers is reflexive, antisymmetric and transitive but not symmetric. "Is a sibling of" is symmetric and, if you do not allow being your own sibling, neither reflexive nor transitive. The empty relation is symmetric, antisymmetric and transitive but is reflexive only on the empty set. Note that symmetric and antisymmetric are not opposites: equality is both.

Related properties: irreflexive (a R a never holds), asymmetric (a R b forbids b R a) and total/connex (every pair is related one way or the other).

Python Testing properties by brute force

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.

Composition and inverse

The inverse Rโปยน = {(b, a) : (a, b) โˆˆ R} flips every arrow. The composition of R โІ A ร— B and S โІ B ร— C is S โˆ˜ R = {(a, c) : there is b with a R b and b S c}. Two steps in the graph: first follow R, then S. This is exactly how a database join works, and we use it again in relational algebra.

R is transitive precisely when R โˆ˜ R โІ R. That one-line test is a good way to remember what transitivity means.

Closures

Sometimes a relation lacks a property and you want the smallest extension that has it. The reflexive closure adds all missing (a, a). The symmetric closure is R โˆช Rโปยน. The transitive closure Rโบ adds a pair (a, c) whenever there is a path from a to c. Transitive closure answers "which nodes are reachable?" and is computed by Warshall's algorithm: for each intermediate element k, for each pair (i, j), add (i, j) if (i, k) and (k, j) are both present.

Python Composition and Warshall's transitive closure

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.

In Warshall's algorithm the intermediate element k must be the outermost loop. Putting it inside gives wrong answers on longer chains.

n-ary relations and databases

A relation does not have to be binary. A subset of Aโ‚ ร— Aโ‚‚ ร— โ€ฆ ร— Aโ‚™ is an n-ary relation, and a database table is exactly that: each row is one tuple, and the schema names the columns. The SQL operations SELECT, JOIN and UNION are set operations on these tuples.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A relation is a

    A binary relation from A to B is by definition a subset of A ร— B.
  2. 2. Which pair of properties does the divides relation on the positive integers have?

    Every n divides itself, if a divides b and b divides a then a = b, and divisibility chains. It is not symmetric.
  3. 3. R is transitive exactly when

    Any two-step path a R b R c must already be a direct pair (a, c), which is the statement R โˆ˜ R โІ R.
  4. 4. What does the transitive closure of a relation compute?

    Rโบ contains (a, c) whenever a path of one or more R-steps leads from a to c.

Summary

  • A binary relation is a set of ordered pairs; it can be written as pairs, a matrix or a digraph.
  • Reflexive, symmetric, antisymmetric and transitive are independent properties; test them directly on finite relations.
  • Inverse flips pairs; composition chains two relations and underlies database joins.
  • Closures give the smallest extension with a property; Warshall's algorithm computes the transitive closure with k in the outer loop.

Next: Equivalence Relations and Partitions