# 4.7 Relations

- Page ID
- 10907

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 *n *and *m *when *n *≤ *m *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 *x*, *y*, and *z *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, *A *and *B*, is defined to be a subset of *A *× *B*. Since a function from *A *to *B *is defined, formally, as a subset of *A *× *B *that satisfies certain properties, a function is a relation. However, relations are more general than functions, since any subset of *A *× *B *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 *A*, *B*, and *C *is a subset of *A*×*B*×*C*.

For example, if *P *is the set of people and *B *is the set of books owned by a library, then we can define a relation R on the sets *P *and *B *to be the set R ={(*p*, *b*) ∈ *P *× *B *| *p *has *b *out on loan}. The fact that a particular (*p*, *b*) ∈ 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 *A *is a set and R is a relation on the sets *A *and *A *(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 *A *is a subset of *A** *× *A*. The relation consisting of all ordered pairs (*c*, *p*) of people such that *c *is a child of *p *is a binary relation on the set of people. The set {(*n*,*m*) ∈ N×N|*n *≤ *m*} is a binary relation on N. Similarly, we define a **ternary relation** on a set *A *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 integer

*n*, to be a subset of

*A*×

*A*× · · · ×

*A*, where

*A*occurs

*n*times in the cross product.

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