Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 68 · Sets, Relations and Functions

Relations

Learn binary relations as sets of pairs, the properties reflexive, symmetric, antisymmetric and transitive, Python checkers and relation matrices.

"Is less than", "divides", "is a friend of", "is connected to", "has the same remainder as": all of these describe how two things are related. Mathematics captures every such idea with one simple object, a relation, which is nothing more than a set of ordered pairs.

Once relations are sets, you can ask structural questions about them: does everything relate to itself? If a relates to b, must b relate to a? These properties decide whether a relation behaves like equality, like ordering, or like neither, and they are the basis of the next lesson on equivalence relations and partial orders. They also describe databases (tables are relations!) and graphs.

Relations as sets of pairs

A binary relation R from a set A to a set B is a subset of the Cartesian product A × B. If the pair (a, b) is in R, we say "a is related to b" and often write a R b. When A and B are the same set, we call R a relation on A.

Take A = {1, 2, 3, 4} and the relation "divides", where a | b means b is a multiple of a. Listing all pairs where the first number divides the second gives:

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

In Python, a relation is a set of tuples, and the definition by rule is a set comprehension over the product. The empty relation and the full product A × A are both legal relations; so is any subset in between. For an n-element set there are 2^(n²) relations on it, because each of the n² possible pairs is either in or out.

Python A relation as a set 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.

The four key properties

Four properties of a relation R on a set A are used over and over. Read them as universally quantified statements, as in Predicates and Quantifiers.

Property Statement In words
Reflexive ∀a ∈ A: (a, a) ∈ R everything relates to itself
Symmetric ∀a, b: (a, b) ∈ R → (b, a) ∈ R relations run both ways
Antisymmetric ∀a, b: (a, b) ∈ R ∧ (b, a) ∈ R → a = b two-way links only between equal things
Transitive ∀a, b, c: (a, b) ∈ R ∧ (b, c) ∈ R → (a, c) ∈ R links chain together

A few examples to anchor each one, on the integers:

  • = is reflexive, symmetric, antisymmetric and transitive.
  • ≤ is reflexive, antisymmetric and transitive, but not symmetric (3 ≤ 5 but not 5 ≤ 3).
  • < is transitive and antisymmetric (vacuously: you can never have both a < b and b < a), but neither reflexive nor symmetric.
  • "has a common factor above 1 with" is symmetric but not transitive (2 and 6 share a factor, 6 and 3 do, but 2 and 3 do not).

Symmetric and antisymmetric are not opposites. A relation can be both (the equality relation, or the empty relation), or neither (for example {(1,2), (2,1), (2,3)} is not symmetric because (3,2) is missing, and not antisymmetric because of (1,2) and (2,1)).

Four properties of a relation

Reflexive Every element relates to itself.
Symmetric If a to b, then b to a.
Antisymmetric A two-way link forces equality.
Transitive A chain a to b to c gives a to c.

Each is a "for all" statement, so one counterexample breaks it.

1 / 2

Checking the properties in Python

Each property translates directly into all over the right pairs. For a finite relation stored as a set of tuples:

Python Property checkers

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.

Look at how the table of results separates the relations into families. "Same parity" is reflexive, symmetric and transitive, which makes it an equivalence relation. "Divides" and "less or equal" are reflexive, antisymmetric and transitive, making them partial orders. Both families are the subject of Equivalence Relations and Partial Orders.

Notice that is_transitive works by looking for chains a → b → d. It does a double loop over the pairs, so it takes time proportional to the square of the number of pairs. That is fine for small relations; large graphs use matrix tricks, shown next.

Relation matrices

A relation on a finite set can be stored as a square matrix of zeros and ones. Number the elements, and put a 1 in row i, column j when element i is related to element j. This is exactly the adjacency matrix of a directed graph, which you will see in Graphs: Terms and Representations.

The matrix makes the properties easy to read:

  • Reflexive: all ones on the diagonal.
  • Symmetric: the matrix equals its transpose.
  • Antisymmetric: no pair of ones placed symmetrically off the diagonal.

Matrices also give an algebra of relations. The composition of R and S (first R, then S) corresponds to a Boolean matrix product. Composing a relation with itself, R∘R, lists the pairs reachable in exactly two steps, and R is transitive exactly when R∘R is a subset of R.

Python Relation matrices and composition

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 chain example shows why {(1,2), (2,3)} is not transitive: its square contains the pair (1,3), which is not in the relation. Adding the missing shortcuts repeatedly produces the transitive closure, the smallest transitive relation that contains R. It answers reachability questions ("can I get from a to z by following links?") and turns up in Paths, Cycles and Connectivity.

Counting relations and functions

Because a relation on a finite set is a subset of the Cartesian product, counting relations is a counting problem you can solve with the product rule. A relation on an n-element set is a choice, for each of the n² ordered pairs, of "in" or "out", so there are 2^(n²) relations in total. Each property fixes some of those choices:

Kind of relation on n elements Count Why
All relations 2^(n²) each of the n² pairs is in or out
Reflexive 2^(n² - n) the n diagonal pairs are forced in; the other n² - n are free
Symmetric 2^(n(n+1)/2) choose the n diagonal pairs and one pair from each of the n(n-1)/2 mirrored couples
Antisymmetric 2^n · 3^(n(n-1)/2) diagonal free; each couple {a, b} has 3 options: none, only (a,b), only (b,a)
Equivalence relations Bell number B_n each one is a partition of the set

The last row connects relations to partitions: an equivalence relation is the same thing as splitting the set into blocks. The Bell numbers run 1, 1, 2, 5, 15, 52, 203, ... and satisfy B_{n+1} = Σ C(n, k) · B_k.

Functions are special relations (each input has exactly one output). For a function from an n-element set A to an m-element set B:

  • All functions: m^n (each of the n inputs picks one of m outputs).
  • Injective (one-to-one): m!/(m - n)! when n ≤ m, else 0 (each input needs a fresh output).
  • Bijective: n! when n = m.
  • Surjective (onto): Σ (-1)^k C(m, k) (m - k)^n, by inclusion-exclusion.
Python Brute-force counts against the formulas

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 brute-force search is only feasible for tiny n (there are already 65,536 relations on 4 elements, and over 33 million on 5), which is exactly why we want formulas: they let you count what you could never list.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A relation on A is a subset of which set?

    A binary relation on A is a set of ordered pairs of elements of A, which is a subset of the Cartesian product A × A.
  2. 2. Which relation on the integers is reflexive and transitive but not symmetric?

    a ≤ a always holds and a ≤ b ≤ c gives a ≤ c, but 3 ≤ 5 does not give 5 ≤ 3. Equality is symmetric, < is not reflexive, and ≠ is not reflexive or transitive.
  3. 3. The relation {(1,2), (2,1)} on {1,2} is...

    It is symmetric, since both (1,2) and (2,1) are present. It is not reflexive (no (1,1)), not antisymmetric (1 and 2 are related both ways yet differ), and not transitive (1→2→1 would need (1,1)).
  4. 4. How many binary relations exist on a set with 3 elements?

    There are 3 × 3 = 9 possible ordered pairs, and each is in or out of the relation, so there are 2^9 = 512 relations.

Summary

  • A binary relation on A is a subset of A × A; any rule that pairs elements defines one, and a set with n elements has 2^(n²) relations.
  • Reflexive, symmetric, antisymmetric and transitive are all "for all" statements, so a single counterexample refutes them.
  • Symmetric and antisymmetric are not opposites; a relation can be both or neither.
  • In Python, each property is an all(...) over pairs; in a 0/1 matrix, reflexive means ones on the diagonal and symmetric means equal to its transpose.
  • Composition is a Boolean matrix product, and a relation is transitive exactly when R∘R is inside R.

Next: Equivalence Relations and Partial Orders, the two most important families of relations.