Set Theory - Review

Recall that the notation:

refers to a set whose elements are the integers 12, 3, 20, 1, 8. Remember that the order in which the elements are listed is irrelevant and so the following all represent the same set:

Operations on Sets

Let A = {12, 3, 20, 1} and B = {22, 20, 8, 1} denote sets. We may perform the following, basic operations:

• UNION:

  A UNION B = {12, 3, 20, 1, 22, 8}. That is, the set that contains all the elements of A and B. We sometimes use the symbol "+" to denote the UNION operator.

• INTERSECTION:

  A INTERSECTION B = {20, 1}. That is, the set that contains those elements that are common to A and B

• DIFFERENCE:

  A DIFFERENCE B = {12, 3}. That is, the set that contains those elements that are in A and not in B. Notice that B DIFFERENCE A = {22, 8}. We sometimes use the symbol "-" to denote the DIFFERENCE operator.

• PRODUCT:

  A PRODUCT B = {(12, 22), (12, 20), (12, 8), (12, 1), (3, 22), (3, 20), (3, 8), (3, 1), (20, 22), (20, 20), (20, 8), (20, 1), (1, 22), (1, 20), (1, 8), (1, 1)}. That is, the set of all ordered pairs (a, b) where a is in A and b is in B. We sometimes use the symbol "X" to denote the PRODUCT operator.

  Note: We also use the term Cartesian product to refer to this operation and sometimes use the word tuple to refer to the pairs (a, b).

Relation

Given n sets A₁, A₂, ... , A_n, consider the Cartesian product A₁X A₂X ... , A_n. Any subset of this Cartesian product is referred to as an n-ary relation (where the term n-ary indicates the n sets involved in the product). For example the Cartesian product example above involves two sets A and B. Any subset of the sixteen elements of this set constitutes a binary relation. One such relation would be the following subset:

We sometimes present the relation in tabular form:

              -----------
               12  |  22 
                3  |  22 
                3  |   8 
               20  |  22 
                1  |   8 
                1  |   1 

where each row corresponds to a tuple.