Relations and functions · Definition

Binary relation

set theoryrelations and functions

Before you start you need to know

A binary relation formalizes statements such as “is less than” or “divides” as collections of ordered pairs.

Definition

A set of ordered pairs \((a,b)\) specifying which elements of \(A\) are related to which elements of \(B\).

\[R \subseteq A \times B\]

If \(R\) is a relation from \(A\) to \(B\), we write \((a,b)\in R\) to indicate that \(a\) is related to \(b\). When \(A=B\), \(R\) is called a relation on \(A\). The domain of \(R\) is the set of first components of its pairs, and the range is the set of second components. Since \(R\) is a set, two relations are equal exactly when they have the same pairs.

Worked example: let \(A=\{1,2,3\}\) and \(R=\{(a,b)\in A\times A : a\le b\}\). Then \(R=\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}\), with 6 of the 9 possible pairs in \(A\times A\). Its domain and its range are both \(A\).

Typical mistake: confusing \((a,b)\) with \(\{a,b\}\). In ordered pairs order matters: \((1,2)\neq(2,1)\), while \(\{1,2\}=\{2,1\}\). So a relation can contain \((a,b)\) without containing \((b,a)\). Properties such as symmetry or reflexivity are studied separately.

Think about it

How many distinct relations are there from \(A\) to \(A\) if \(|A|=3\)?

512, since \(A\times A\) has 9 pairs and \(2^9=512\)

Exercises 10

  1. What is a binary relation from \(A\) to \(B\)?
  2. How many pairs does \(A \times B\) have if \(|A|=2\) and \(|B|=3\)?
  3. If \(R=\{(1,2),(2,3)\}\), what is the domain of \(R\)?
  4. If \(R=\{(1,2),(2,3)\}\), what is the range of \(R\)?
  5. What is the usual notation for saying that \(a\) is related to \(b\) by \(R\)?
  6. Let \(A=\{1,2,3\}\). How many distinct relations are there from \(A\) to \(A\)?
  7. Let \(A=\{1,2,3\}\) and \(R=\{(a,b)\in A\times A : a\le b\}\). Which of these pairs is in \(A\times A\) but not in \(R\)?
  8. Let \(R=\{(a,b)\in \mathbb{N}\times\mathbb{N} : b=a+1\}\). Which of these pairs belongs to \(R\)?
  9. A relation \(R\) on \(A\) is reflexive if \((a,a)\in R\) for every \(a\in A\). With \(A=\{1,2,3\}\), how many reflexive relations on \(A\) are there?
  10. Let \(A=\{1,2,3,4\}\) and \(R=\{(a,b)\in A\times A : a+b \text{ is even}\}\). How many pairs does \(R\) have?

What comes next

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.