School of Engineering and Applied Science Department of Computer Science CSci 133 -- Algorithms and Data Structures I http://www.seas.gwu.edu/~csci133/spring05 Prof. Michael B. Feldman mfeldman@gwu.edu

Often sets are described mathematically simply by listing their members between braces, as in the set {a, b}, taken from the universe of English alphabetic characters. In general, there is no ordering associated with a set, so {a, b} and {b, a} usually describe the same set. Further, in general a given member appears in a set no more than once; we don't usually allow "duplicates". Two sets are said to be equal if they have exactly the same members. A set is said to be empty if it has no members.

Operations on Sets

What are the important operations associated with sets? Certainly inserting a member in a set and deleting a member from a set are essential; so are testing a set to see whether a given element is a member of it and testing a set to see whether it is empty. The last two operations are predicate operations; they return true/false values. The most important dyadic (binary  --  two operands) operations are

• the union of two sets S and T, which returns the set containing all of S's members and all of T's members;
• the intersection of S and T, which returns the set containing all elements which are members of both S and T;
• the difference S - T, which returns the set containing all elements which are members of S but not of T.

For example, if the universe is the alphabet letters, and S = {a, d, e, g} and T = {b, c, d, e, k}, then

• the union of S and T is {a, b, c, d, e, g, k};
• the intersection of S and T is {d, e};
• the difference S - T = {a, g} and T - S = {b, c, k}

Finally, two more predicate operations are commonly used:

• the improper subset operation, which returns true if and only if all members of S are also members of T. This includes the case where S = T.
  
• the proper subset operation, which returns true if and only if S is an improper subset of T and S is not equal to T; that is, at least one member of T is not a member of S.

For example, {b, c} is both a proper and an improper subset of {a, b, c, d, e}; {b, c} is not a subset of {c, e}. Also, {a, b} < {a, b}.

(end of article)