# 4.7: Relations

In Section 4.4, we saw that ‘mother of’ is a functional relationship because every person has one and only one mother, but that ‘child of’ is not a functional relationship, because a person can have no children or more than one child. However, the relationship expressed by ‘child of’ is certainly one that we have a right to be interested in and one that we should be able to deal with mathematically.

There are many examples of relationships that are not functional relationships. The relationship that holds between two natural numbers and when ≤ is an example in mathematics. The relationship between a person and a book that that person has on loan from the library is another. Some relationships involve more than two entities, such as the relationship that associates a name, an address, and a phone number in an address book or the relationship that holds among three real numbers xy, and if $$x^{2}+y^{2}+z^{2}=1$$. Each of these relationships can be represented mathematically by what is called a ‘relation’.

A relation on two sets, and B, is defined to be a subset of × B. Since a function from to is defined, formally, as a subset of × that satisfies certain properties, a function is a relation. However, relations are more general than functions, since any subset of × is a relation. We also define a relation among three or more sets to be a subset of the cross product of those sets. In particular, a relation on AB, and is a subset of A×B×C.

For example, if is the set of people and is the set of books owned by a library, then we can define a relation R on the sets and to be the set R ={(pb) ∈ × has out on loan}. The fact that a particular (pb) ∈ R is a fact about the world that the library will certainly want to keep track of. When a collection of facts about the world is stored on a computer, it is called a database. We’ll see in the next section that relations are the most common means of representing data in databases.

If is a set and R is a relation on the sets and (that is, on two copies of A), then R is said to be a binary relation on A. That is, a binary relation on the set is a subset of A × A. The relation consisting of all ordered pairs (cp) of people such that is a child of is a binary relation on the set of people. The set {(n,m) ∈ N×N|≤ m} is a binary relation on N. Similarly, we define a ternary relation on a set to be a subset of $$A \times A \times A .$$ The set $$\left\{(x, y, z) \in \mathbb{R} \times \mathbb{R} \times \mathbb{R} | x^{2}+y^{2}+z^{2}=1\right\}$$ is a ternary relation on $$\mathbb{R}$$ For complete generality, we can define an n-ary relation on A, for any positive integern, to be a subset of × × · · · × A, where occurs times in the cross product.

For the rest of this section, we will be working exclusively with binary relations. Sup- pose that R ⊆ × A. That is, suppose that R is a binary relation on a set A. If (ab) ∈ R, then we say that is related to by R. Instead of writing “(ab) ∈ R”, we will often write “b”. This notation is used in analogy to the notation ≤ to express the relation that is less than or equal to m. Remember that is just an alternative way of writing(ab) ∈ R. In fact, we could consider the relation ≤ to be a set of ordered pairs and write(n,m) ∈≤ in place of the notation ≤ m.