Sets, Operations

Operations

Set S is a subset of T, written S ⊆ T, if every member of S is a member of T. Write S ⊄ T when S is not a subset of T.

Set S is a superset of T, written S ⊇ T, if T is a subset of S.

The sets S and T are the same iff S is a subset of T and T is a subset of S. In other words, they have the same members.

The set S is a proper subset of T, written S ⊂ T, if S ⊆ T and T ⊄ S. In other words, S is a subset of T, but is not equal to T.

The power set of S is the set of all subsets of S. The power set of (1,2,3) has 8 elements as follows.

(∅,(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3))

Union and intersection are binary operations on sets. An element x is a member of S∪T if x is a member of S or T. An element x is a member of S∩T if x is a member of S and T. Various axioms guarantee that union, intersection, complement, subset, and power set, when appplied to sets, actualy produce more sets. These are described on the next page.

Union and intersection are commutative, associative, and distributive over each other. These properties can be proved by considering the general member x. The set operators inherit these properties from their underlying boolean counterparts.

If the complement of S and T are well defined, relative to a larger set that is a superset of S and T, then Demorgan's laws apply.

The complement of (S∪T) is the complement of S intersect the complement of T.

The complement of (S∩T) is the complement of S union the complement of T.

This follows directly from the boolean formulations shown below, which can be verified by a simple truth table. To map this back to sets, let x mean "is a member of S", and let y mean "is a member of T".

~(x|y) = ~x & ~y

~(x&y) = ~x | ~y