Mastering Algorithms with C

Description of Sets

Sets are unordered collections of related members in which no members occur more than once. Formally, sets are written with braces around them. Thus, if S is a set containing the members 1, 2, and 3, then S = {1, 2, 3}. Of course, because a set is unordered, this is the same as writing S = {3, 2, 1}. If a member, m, is in a set, S, then membership is indicated by writing m ∈ S ; otherwise, m ∉ S. For example, in the set S = {1, 2, 3}, 2 ∈ S, but 4 ∉ S. To effectively use sets, we should be familiar with some definitions, basic operations, and properties.

Definitions

1. A set containing no members is the empty set. The set of all possible members is the universe. (Of course, sometimes the universe is difficult to determine!) In set notation:

   

2. Two sets are equal if they contain exactly the same members. For example, if S ₁ = {1, 2, 3}, S ₂ = {3, 2, 1}, and S ₃ = {1, 2, 4}, then S ₁ is equal to S ₂, but S ₁ is not equal to S ₃. In set notation:

   

3. One set, S ₁, is a subset of another set, S ₂, if S ₂ contains all of the members of S ₁. For example, if S ₁ = {1, 3}, S ₂ = {1, 2, 3}, and S ₃ = {1, 2}, then S ₁ is a subset of S ₂, but S ₁ is not a subset of S ₃. In set notation,