Sets, Relations and Functions

Relations and Functions

The cross product is a binary operation on sets. The ordered pair x1,x2 is a member of S1 cross S2 if x1 ∈ S1 and x2 ∈ S2.

If you want to be rigorous, establish a convention for describing ordered pairs. Make sure x1,x2 is different from x2,x1. A typical construction builds the ordered pair on x and y as ((x),(x,y)). In other words, we build the set containing both the set containing x and the set containing x and y. When x = y the structure collapses to ((x)), the set containing the set containing x. Extract the first element x by looking for the member that contains only one element. Extract the second by finding the member with two elements, then find the element in that set that is not x. Write a separate clause if there is but one set, whence the ordered pair is x,x. This is a lot of work for a concept as simple as ordered pairs, but it can all be done via set membership.

Apply the above recursively to build ordered n-tuples. A triple, for instance, is an ordered pair that joins the first two elements, as an ordered pair, with the third.

A relation is a subset of a cross product (only some tuples included). For example, consider the "ownership" relation, when S1 = people and S2 = pets. The relation contains Dick,Spot, since Dick owns spot. It does not contain Jane,Spot, but it does contain Jane,Puff.

A relation is considered a function if no member of S1 is repeated. If the "ownership" relation above were a function, nobody could own more than one pet.

   Dick → Spot
   Jane → Puff
   Tim → Lassy
   Fred → Spot   (this function is not invertible)
   Clinton → Sox
   Nixon → Checkers

When a function is derived from S1 cross S2, S1 is called the domain and S2 is called the range. If x is a member of S1, f(x) is the corresponding member of S2, as determine by the function f. We sometimes say f maps S1 into S2.