0.1 Discrete structures relation  (Page 2/13)

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.

Definition of n-ary relation

Here we are going to formally define general n-ary relation using the concept of ordered n-tuple.

Definition (ordered n-tuple): An ordered n-tuple is a set of n objects with an order associated with them. If n objects are represented by x1, x2, ..., xn, then we write the ordered n-tuple as<x1, x2, ..., xn>.

Definition (Cartesian product): Let A1, ..., An be n sets. Then the set of all ordered n-tuples<x1, ..., xn>, where xi ∈Ai for all i, 1 ≤i ≤n , is called the Cartesian product of A1, ..., An, and is denoted by A1 ×... ×An .

Definition (equality of n-tuples): Two ordered n-tuples<x1, ..., xn>and<y1, ..., yn>are equal if and only if xi = yi for all i, 1 ≤i ≤n.

For example the ordered 3-tuple<1, 2, 3>can be equal to only<1, 2, 3>and nothing else. It is not equal to the ordered n-tuple<2, 3, 1>for example.

Definition (n-ary relation): An n-ary relation on sets A1, ..., An is a set of ordered n-tuples<a1, ..., an>where ai is an element of Ai for all i, 1 ≤i ≤n . Thus an n-ary relation on sets A1, ..., An is a subset of Cartesian product A1 ×... ×An .

Example 1: Let A1 be a set of names, A2 a set of addresses, and A3 a set of telephone numbers. Then a set of 3-tuples<name, address, telephone number>such as {<Amy Angels, 35 Mediterranean Ave, 224-1357>,<Barbara Braves, 221 Atlantic Ave, 301-1734>,<Charles Cubs, 312 Baltic Ave, 223-9876>}, is a 3-ary (ternary) relation over A1, A2 and A3.

Example 2: Let A1 be a set of names. Then a set of 1-tuples such as {<Amy>,<Barbara>,<Charles>}, is a 1-ary (unary) relation over A1.

A unary relation represents a property/characteristic, such as tall, rich etc., shared by the members of A1 listed in the relation.

Special relations

The empty set is certainly a set of ordered n-tuples. Therefore it is a relation. It is called the empty relation.