A relation on a set A is a subset of A × A: a set of ordered pairs, each recording that one element is related to another. The empty relation contains no pairs; the universal relation contains all of them.
In everyday language, two things are related if some connection links them: “is a sibling of”, “is older than”, “lives in the same town as”. In mathematics, a relation records only which pairs are connected, not what the connection means.
Each connection is recorded as an ordered pair. If a is related to b, the pair (a, b) is included. The order matters: (a, b) says a is related to b, which need not mean b is related to a. A relation is the set of all such pairs.
For a set A, the Cartesian product A × A is the set of all ordered pairs (a, b) with a ∈ A and b ∈ A. If A has n elements, A × A has n² pairs.
A relation R on A is any subset of A × A. If (a, b) ∈ R, we say “a is related to b” and write a R b.
A relation can be given by a rule, such as “b = a + 1”, or by listing its pairs. Either way, the relation is the set of pairs. Two rules that pick out the same pairs define the same relation.
A relation is a subset of A × A. From all the ordered pairs that A × A contains, a relation includes some. The included pairs are the related ones.
Let A = {1, 2, 3} and R = {(a, b) : b = a + 1}. List the pairs in R, and explain why R is a relation on A.
For a = 1, b = 2: (1, 2) is in R. For a = 2, b = 3: (2, 3) is in R. For a = 3, b would be 4, which is not in A, so there is no pair. R = {(1, 2), (2, 3)}.
Both pairs have both entries in A, so R ⊆ A × A. That is the definition of a relation on A. The rule was only a way of choosing the pairs.
A relation can be any subset of A × A, including the smallest and the largest.
The empty relation is R = ∅. No element is related to any element. On A = {1, 2, 3, 4}, the rule “a R b if a − b = 10” gives the empty relation, because no two elements of A differ by 10.
The universal relation is R = A × A. Every element is related to every element. The rule “a R b if |a − b| ≥ 0” gives the universal relation, because an absolute value is never negative.
These two are called trivial relations. The relations used in practice lie between them, and the next sessions describe the properties that make them useful.
On A = {1, 2, 3}, consider the rule “a R b if a + b > 0”. Is R empty, universal, or neither?
It is the universal relation, R = A × A.
Every element of A is at least 1, so every sum a + b is at least 2, which is greater than 0. Every one of the 9 pairs satisfies the rule.
Whether a relation is trivial depends on which pairs it contains on the given set, not on how the rule is written. On the set {−3, 1}, the same rule would exclude (−3, −3) and (−3, 1).
1A relation on a set A is…
2If (a, b) is in a relation R, we write a ____ b.
3For A = {1, 2, 3}, R = {(a, b) : b = a + 1} is…
4The empty relation on A is…
5The universal relation on A is…
6On {1, 2, 3}, the relation “a R b if a − b = 10” is…
Next: three properties a relation can have — reflexive, symmetric and transitive.
Noescio