Relational Theory for Computer Professionals

Appendix C. Set Theory

The Joy of Sets

—Anon.: Where Bugs Go

An understanding of set theory can be very helpful in dealing with databases; indeed, as mentioned in Chapter 7, the relational model is directly based on certain aspects of that theory. In this appendix, therefore, I offer a brief tutorial on set theory basics.

What’s a set?

I’ll begin with a definition:

• Definition: A set S is a collection of distinct elements, or members, such that, given an arbitrary object x, it can be determined whether or not x is contained in S (i.e., is an element of S). Note the terminology: A set is said to contain its members.

  Here’s an example:

  { 2 , 3 , 5 , 7 }

As this example suggests, the standard “on paper” representation of a set is as a commalist, enclosed in braces, of symbols denoting the elements of the set in question. Points arising:

• Sets never contain duplicate elements. Thus, if duplicate symbols appear in the “on paper” representation (which by convention they usually don’t), they can simply be ignored. For example, the following—

  { 2 , 2 , 3 , 5 , 5 , 5 , 7 , 7 }

  —is another possible, albeit unlikely, “on paper” representation of the set {2,3,5,7}.

• Sets have no ordering to their elements. Thus, for example, the following—

  { 7 , 2 , 5 , 3 }

  —is another possible “on paper” representation of that same set.

• A set can contain no elements at all, in which case it’s the (unique) empty set, written { }, or sometimes Ø.

• There’s another unique set called the universal set, which is the set that contains ...