5.  Relations

Definition 2.2 (Cartesian Product)

Let A and B be two sets. The set of all ordered pairs so that the first member of the ordered pair ∈ A and the second member of the ordered pair ∈ B is called the Cartesian Product. Accordingly:

A × B = { (x,y) | x ∈ A and y ∈ B }

are sets. The set of all n-tuples with , 1 ≤ i ≤ n, is denoted by

We write: = { ( | , 1 ≤ i ≤ n }

Examples:

• A byte is an 8-tuple of bits. Express the set of all bytes as an Cartesian product.

Definition 2.3 (Relation)

Let A and B be two sets. A relation from A to B is any set of pairs
(x,y), x∈ A and y ∈ B.

If (x,y) ∈ R we say x is R-related to y.

To express that R is a relation from A to B we write R: A ↔ B

Shorthand: (x,y) ∈ R == xRy

Examples:

• Cartesian product
• Let R be a relation defined for any (x,y) by the statement:
  xRy if x,y ∈ Nat and x )< y ≤ 2
  
  R = { (0,1), (0,2), (1,2) }
  
• A is a set of suppliers; B is a set of products.
  A = { S1, S2, S3 } and
  B = { P1, P2, P3 }
  

  A relation C can now be defined as a list of pairs (x,y) where x is a supplier and y is a product.

  C = { (S1, P1) , (S1, P3), (S2, P2), (S2, P3) }

  Relation in tabular form:

                         +---+----+----+----+
                         |   | P1 | P2 | P3 |
                         +---+----+----+----+
                         |S1 | 1  | 0  | 1  |
                         +---+----+----+----+
                         |S2 | 0  | 1  | 1  |
                         +---+----+----+----+
  

  A graphically representation of the relation → board

Last modified 22/May/97