6.2. Basic Set Theory

Since the constraints in step 6 make substantial use of sets and set operations, let’s first review some basic set theory. To provide a comprehensive summary of the required background, some ideas met earlier are included.

Intuitively, a set is a well-defined collection of items. The items may be concrete (e.g., people, computers) or abstract (e.g., numbers, points) and are called elements or members of the set. Sets themselves are abstract. They are numerically definite in the sense that each has a definite number of elements. A type is a set of possible items, understood as sharing some common characteristics (possibly unstated).

The members of a set collectively constitute the extension of the set. While a set may contain members, it does not consist of those members. For example, the set of Martian moons is an abstraction over and above its members (Phobos and Deimos) and consequently has no physical properties such as mass or volume. Although sets (unlike heaps) are not to be equated with their members, they are determined by their members, since two sets are identical or equal just in case they have the same extension. Using “iff” for “if and only if”, the Law of Extensionality may be stated thus:

Given any sets A and B, A = B iff A and B have the same members.

Since sets are determined by their members, one simple way of defining a set is to enumerate or list the elements of the set. In so doing, braces are used as delimiters and commas as item separators (e.g., A = {3, 6}). Here A is defined as the set containing just the elements 3 and 6.

One consequence of the Law of Extensionality is that a set is unchanged by repeating any of its members. For instance, if A = {3, 6} and B = {3, 6, 6} it follows that A = B, since both sets contain precisely the same members (3 and 6). The cardinality of a set A, written #A, is the number of different elements in A. For example, #{3, 6} = #{3,6,6} = 2.

When enumerating sets, it is usual not to repeat the members. However it is sometimes useful to permit this. For example, when stating general results about the set variable {x, y} it may be handy to include the case x = y. Sometimes repetition of members occurs undetected. For instance, some people do not realize that the entity set {Morning Star, Evening Star} contains just one member (the planet Venus). Of course, the value set {‘Morning Star’, ‘Evening Star’} contains two members.

If repetition is made significant, we have a bag or multiset. To distinguish between bags and sets, we use different delimiters. We use square brackets for bags, and braces for sets. The cardinality of a bag equals its number of elements, including duplicates. For instance #[3, 6] = 2, but #[3, 6, 6] =3. One use of bags is in collecting values for statistical work. For example, the set {3, 6, 6} has an average of 4.5 but the bag [3, 6, 6] has an average of 5. Bags are frequently used with languages such as SQL.

Another consequence of the Law of Extensionality is that the order in which elements are listed is irrelevant. For example, if A = {3, 6} and B ={6, 3} then A = B, since each set contains the same members. Bags are also insensitive to order, as in [3, 6] = [6, 3]. If order is made significant, we have an “ordered set”.

Usually, when order is made significant, so is repetition. In this case we have a sequence (also called a list or permutation or tuple). Thus a sequence is an ordered bag. Sequences are often delimited by parentheses or angle brackets, e.g., (1, 2) or 〈1, 2〉. The sequence (6, 3, 6) has three members and differs from the sequence (3, 6, 6). The cardinality of a sequence is its member count, including duplicates. For example, #(3, 6, 6) = 3. In practice, several different delimiting notations are used. For example, “[”, “]” are used as set delimiters in Pascal and list delimiters in Prolog.

If a set is enumerated in full, the ordering does not matter. However, a natural ordering often provides an obvious pattern: in such cases a partial enumeration can define the set. For example, the set of decimal digits may be shown as {0..9}, where the “..” indicates the missing digits. Here 0..9 is often called a range. Infinite sets may be represented with “..” at one or both ends. For example, the set of natural numbers may be shown as {1, 2, 3..}.

The preceding set definitions enumerate, wholly or partially, the extension of the set and are thus examples of an extensional definition. A set may also be defined by an intensional definition. Here the intension or meaning is declared using a property that applies to just the members of the set. That is, a description is given that constitutes both a necessary and a sufficient condition (an “iff condition”) for an item to belong to the set.

For example, the set A, defined extensionally as {1, 2, 3}, may be defined intensionally as: A = the set of natural numbers less than 4. This definition may be recast in set builder notation as {x: x is a natural number less then 4} or more briefly as {x: x ∊ N & x < 4}, where “∊” abbreviates “is a member of and N is the set of natural numbers. In set builder notation, a stroke “|” may be used instead of a colon, for example, {x| x<4}.

Some set operations result in propositions, while others result in sets. Note the following proposition-forming operators: =, ≠, ⊆, ⊂, ⊇, and ⊃. These are read respectively as “equals”, “is not equal to”, “is a subset of,” is a proper subset of, “is a superset of, and” is a proper superset of.

Given any sets A and B, we say that A is a subset of B iff every member of A is also a member of B. For example, {1, 3} ⊆ {1, 2, 3}. An equivalent definition is: A is a subset of B iff A has no members that are not in B. This second definition makes it easy to see that the null set is a subset of every set. The null or empty set has no members and may be represented as { } or ∅.

Every set is a subset of itself. For example, {1, 3} ⊆ {1, 3}. We say that A is a proper subset of B if and only if A is a subset of B but not equal to B. For instance, {1, 3} ⊂ {1, 2, 3}. We say that A is a superset of B iff B is a subset of A, and that A is a proper superset of B iff B is a proper subset of A. For example, {1, 2, 3} is both a superset and a proper superset of {1, 3}.

Comparison relationships between two sets are often depicted by Euler diagrams. As developed by the Swiss mathematician Leonhard Euler (1707-1783 CE), these were spatial and existential. Each set is pictured as a set of points inside an ellipse. This enables the relationship between the sets to be “seen” by the spatial arrangement of the ellipses. For example, placing ellipse A inside B shows that A is a proper subset of B (see Figure 6.1). Here we see that every element of A is also an element of B (so A is a subset of B). The existential viewpoint implies that each of the regions in the Euler diagram contains some elements. So B has some elements not in A. Hence A is a proper subset of B.

To show that A is a subset of B on standard Euler diagrams, we use a disjunction of two diagrams, as in Figure 6.2. The right-hand diagram caters for the case A = B.

The notion of subsethood is more useful than proper subsethood. Partly to depict such relationships on a single diagram, we use Hypothetical Euler Diagrams (HEDs). In a HED, an asterisk is placed in a region to show something exists there, while shading the region indicates that it is empty. If a region is unmarked, the question of whether any elements exist there is left open or hypothetical. Figure 6.3 shows the HEDs for the six most important comparisons between two sets.

Figure 6.3(a) shows equality or identity (e.g., A = B = {1, 2}). In Figure 6.3(b), A and B are disjoint or mutually exclusive; that is they have no members in common (e.g., A = {1}, B = {2}). In Figure 6.3(c), A is a subset of B (equivalently, B is a superset of A). In Figure 6.3(d), A is a proper subset of B (so B is a proper superset of A). For example both A = {1}, B = {1, 2} and A = {1}, B = {1} are instances of subsethood, but only the former is an instance of proper subsethood. Figure 6.3(e) shows overlap: the sets have some members in common. Figure 6.3(f) shows proper overlap: the sets have common as well as extra members. For example, both A = {1, 2}, B = {2, 3} and A = {1}, B = {1, 2} are instances of overlap but only the former is a case of proper overlap.

Let’s now consider set-forming operations, where the result is a set. Given any sets A and B, we define A ∪ B (i.e., A union B) to be the set of all elements in A or B, reading “or” in the inclusive sense. A ∩ B (i.e., A intersect B) is the set of all elements common to both A and B. Each of these operations is commutative, so the order of the operands doesn’t matter. That is, A ∪ B = B ∪ A, and A ∩ B = B ∩ A.

The set difference (or relative complement) operation is defined thus: A – B (i.e., A minus B) is the set of all elements that are in A but not in B. This operation does not commute (i.e., cases may arise where A − B ≠ B − A). If we let U = the universal set (i.e., the set of all elements under consideration), we define the complement of A as A′ = U − A. The symmetric difference between A and B is the set of elements in just one of A or B (i.e., the union minus the intersection).

The three most important set-forming operations are union, intersection, and difference. These are depicted in Figure 6.4 by means of Venn diagrams, named after their inventor, the English logician John Venn (1834-1923 CE). Here shading indicates the result of the operation.

Unlike in Euler diagrams, Venn diagram ellipses always overlap. Like HEDs, Venn diagrams adopt the hypothetical viewpoint. As examples of these operations, if A = {1,2} and B= {2, 4}, then A ∪ B = {1, 2, 4}, A ∩ B = {2}, A−B= {1}, and B − A = {4}.

Venn diagrams are sometimes used to discuss comparisons between two sets. For example, Figure 6.5(a) indicates that A ⊂ B, using line fill and “*”, respectively, for empty and non-empty regions. However, Venn diagrams become extremely unwieldy as soon as the number of sets exceeds three—consider the Venn diagram for four sets in Figure 6.5(b). Euler diagrams have a similar scalability problem. Section 6.5 introduces a directed graph notation for diagramming subtype connections that enables many compatible object types to be related without incurring the jumble of line crossings that Euler and Venn diagrams would produce for such cases.