Relation

Definition of Binary Relation

### Subjects to be Learned

- ordered pair (review)
- equality of ordered pair (review)
- binary relation
- Cartesian product (review)

### Contents

Here we are going to define **relation** formally,
first **binary relation**,
then **general n-ary relation**.
A relation in everyday life shows an association of objects of a set with objects of
other sets (or the same set) such as John owns a red Mustang, Jim has a green Miata etc. The essence of
relation is these associations. A collection of these individual associations is a relation,
such as the ownership relation between peoples and automobiles. To represent these individual associations, a set of
"related" objects, such as John and a red Mustang, can be used. However, simple sets such as **{** John,
a red Mustang **}** are not sufficient
here.
The order of
the objects must also be taken into account, because John owns a red Mustang but the red Mustang
does not own John, and simple sets do not deal with orders. Thus sets with an order on its members
are needed to describe
a relation.
Here the concept of **ordered pair**
and, more generally, that of
**ordered n-tuple** are going to be defined first. A relation is then defined as
a set of ordered pairs or ordered n-tuples.

**Definition (ordered pair):**

An **ordered pair** is a set of a pair of objects with an order
associated with them.

If objects are represented by *x* and *y*, then we write an ordered pair
as **<***x, y*> or **<***y, x*>. In general **<***x, y*>
is different from **<***y, x*>.

**Definition (equality of ordered pairs):**

Two ordered pairs **<***a, b*> and **<***c, d*> are
**equal
**
if and only if *a* = *c* and *b* = *d*.

For example, if the ordered pair **<***a, b*> is equal to **<***1, 2*>,
then *a* = *1*, and *b* = *2*.
**<***1, 2*>
is not equal to the ordered pair **<***2, 1*>.

**Definition (binary relation):**

A **binary relation** from a set *A* to a set
*B* is a set
of ordered pairs **<***a, b*> where *a* is an element of *A* and
*b* is an element of *B*.

When an ordered pair **<***a, b*> is in a relation *R*, we write
*a R b*, or **<***a, b*>
*R*.
It means that element *a* is related to element *b* in relation *R*.

When *A* = *B*, we call a relation from *A* to *B* a (binary)** relation on ***A*
.

**Definition (Cartesian product):**

The set of all ordered pairs **<***a, b*>, where *a* is an element of
*A* and *b* is an element of *B*,
is called the **Cartesian product** of *A* and *B*
and is denoted by *A*
*B*.

Thus a binary relation from *A* to *B* is a subset of Cartesian product
*A*
*B*.

**Examples:**

If *A* = {*1, 2, 3*} and *B* = {*4, 5*}, then **{***<1, 4>,
<2, 5>,
<3, 5>*}, for example,
is a binary
relation from *A* to *B*.

However,
**{***<1, 1>, <1, 4>, <3, 5>*} is not a binary relation from *A* to *B*
because *1* is not in *B*.

The parent-child relation is a binary relation on the set of people. *<John, John Jr.>*,
for example, is an element of the parent-child relation if John is the father of John Jr.

### Test Your Understanding of Binary Relation

Indicate which of the following statements are correct and which are not.

Click Yes or No , then Submit. There are two sets of questions.

**
Next -- Definition of Relation (general relation) **

Back to Schedule

Back to Table of Contents