Skip to main content
Logo image

Discrete Math with SageMath: Learn math with open-source software

Section 5.1 Introduction to Relations

A relation \(R\) from set \(A\) to set \(B\) is any subset of the Cartesian product \(A \times B\text{,}\) indicating that \(R \subseteq A \times B\text{.}\) We can ask Sage to decide if \(R\) is a relation from \(A\) to \(B\text{.}\) First, construct the Cartesian product \(C = A \times B\text{.}\) Then, build the set \(S\) of all subsets of \(C\text{.}\) Finally, ask if \(R\) is a subset of \(S\text{.}\)
Recall the Cartesian product consists of all possible ordered pairs \((a, b)\text{,}\) where \(a \in A\) and \(b \in B\text{.}\) Each pair combines an element from set \(A\) with an element from set \(B\text{.}\)
In this example, an element in the set \(A\) relates to an element in \(B\) if the element from \(A\) is twice the element in \(B\text{.}\)

Subsection 5.1.1 Relation Composition

Let \(R\) be a relation from a set \(A\) to a set \(B\) and \(S\) a relation from \(B\) to a set \(C\text{.}\) The composite of \(R\) and \(S\) is the relation consisting of the ordered pairs \((a,c)\) where \(a \in A\) and \(c \in C\text{,}\) and for which there is a \(b \in B\) such that \((a,b) \in R\) and \((b,c) \in S\text{.}\) We denote the composite of \(R\) and \(S\) by \(S \! \circ \! R\text{.}\)
We can also use Sage to compose relations.

Subsection 5.1.2 Relations On a Set

When \(A = B\) we refer to the relation as a relation on \(A\text{.}\)
Consider the set \(A = \{2,3,4,6,8\}\text{.}\) Let’s define a relation \(R\) on \(A\) such that \(aRb\) if and only if \(a | b\) (\(a\) divides \(b\)). The relation \(R\) can be represented by the set of ordered pairs where the first element divides the second: