13.3: Basic concepts in set theory

A set (in the mathematical sense) is a clearly-defined collection of things. We use braces, or “curly brackets”, to represent sets. So, for example, the denotation set of the word man in the simple model described above could be written as shown in (2a). This is a set which contains two elements, or members, both of which are men. If we focus on denotation sets of content words, the members of a set will normally all be the same kind of thing, as in (2a). For sets in general, however, this does not have to be the case. The set defined in (2b) contains four members which are very different from each other; but this is still a well-defined set.

(2) a. {King Henry VIII, Thomas More}
b. {Orwell’s novel 1984, Noam Chomsky, √2, Sally McConnell-Ginet’s breakfast muffin on 4-Sept-1988}²

The identity of a set is defined by its membership. If two sets have the same members, they are in fact the same set. When we list the members of a set, the order in which the members are listed is irrelevant; so all of the orderings shown in (3) describe the same set:

(3) {a,b,c} = {b,a,c} = {c,a,b} = {a,b,c,b,a}, etc.

We use the Greek letter epsilon to indicate that a certain element belongs to a given set. The formula “x ∈ B” can be read as: “x is a member (or element) of set B”. This would be true, for example, if B = {x,y,z}; but false if B = {w,y,z}. The formula “x < B” means that x is not a member of set B.

It is possible for a set to have an infinite number of members. Examples of such sets include the set of all integers; the set of all rational numbers (i.e., quotients of integers); the set of all finite strings of letters of the Roman alphabet; the set of all finite strings of words found in the Oxford English Dictionary; and the set of all real numbers. (The membership of this last set turns out to be a higher order of infinity than that of the other sets just mentioned; but that topic will not concern us here.)

It is possible for a set to have no members. In fact, there is exactly one set of this kind, and it is called the empty set (often symbolized as “∅”). The fact that there can be only one empty set follows from the principle that a set is defined by its membership. (If there were two sets, A and B, both of which had no members, then they would contain exactly the same members; and so by the principle stated above, they would be the same set.)

A set is distinct from any of its members. A set containing just one element is a different thing from the element itself. For example, the set consisting of a single individual, e.g. {Paul Kroeger}, is not the same thing as the individual himself. {Paul Kroeger} is an abstract concept, but Paul Kroeger is (at the time of writing) a living, breathing human being. To take another example, the empty set is not the same as nothing; it is a set that contains nothing. And the set containing the empty set is not itself empty; it has exactly one member, namely the empty set:

(4) {∅} ≠ ∅

The cardinality of a set is the number of members or elements which belong to that set. For example, the cardinality of the set {a,b,c} is 3, because it has three members. We use the symbol |B| to refer to the cardinality of set B; so |{a,b,c}| = 3. Some further examples are given below:

(5) |{a,b,c,d,f}| = 5
|∅| = 0
|{∅}| = 1

In order for a given collection of things to be a well-defined set, it must be possible to determine precisely what is and is not a member of the set. For example, the phrase the set of all sets that do not contain themselves does not identify a well-defined set. This is because its membership cannot be precisely determined. In fact, the proposed definition of the set gives rise to a paradox. Suppose that such a set exists. Does this set contain itself? If so, then it is not a “set that does not contain itself” and so should not be a member of the set. But if it is not a member of the set, then it does not contain itself, and so it must belong to the set.³

The membership of a set can be specified either by listing its members, as in (2– 3), or by stating a rule of membership (e.g., the set of all female British monarchs, the set of all months whose name includes the letter “r”, the set of all integers, etc.). A general notation for defining the membership of a set is illustrated in (6), which is one way of describing the set of all even numbers (we will call this set E): ‘the set of all numbers which are divisible by 2’. In this notation, the variable is assumed to be an element of the currently relevant universal set, or universe of discourse.⁴ The colon in this notation stands for ‘such that’. (Some authors use a vertical bar | instead of the colon.) If we assume that the currently relevant universal set is the set of all real numbers, then the set description in (6) can be read as: ‘the set of all real numbers x such that x/2 is an integer.’

(6) E = {x: x/2 is an integer}

13.3.1 Relations and functions

Up to this point all of our examples have involved sets of individuals: numbers, letters, people, etc. But we can also define sets of couples (or triples, quadruples, etc.) of individuals. For example, the set of all married couples who crossed the Atlantic ocean on the Mayflower in the autumn of 1620 is a well defined set. This set contained 18 members, and each member of the set was a pair of people: {Isaac & Mary Allerton, William & Dorothy Bradford, William & Mary Brewster, Myles & Rose Standish, Edward & Elizabeth Winslow, …}. Since the set is defined as a set of pairs, William Bradford (the first governor of the Plymouth Bay colony) was not himself a member of this set; but he was a member of a pair that did belong to the set.

In this example, the members of each pair can be distinguished by the title “Mr.” vs. “Mrs.”, no matter which one is mentioned first; but this is not always the case. As we will see, it is often useful to define sets of pairs of things in which the members of each pair are distinguished by specifying the order in which they occur. We refer to such pairs as ordered pairs, using the notation ⟨x,y⟩ to represent the pair which consists of x followed by y. Unlike sets, two ordered pairs may have the same members but still be distinct, if those members occur in different orders. So ⟨x,y⟩ and ⟨y,x⟩ are two distinct ordered pairs, but {x,y} and {y,x} are two different ways of representing the same set.

A set of ordered pairs is called a relation. The domain of the relation is the set of all the first elements of each pair and its range is the set of all the second elements. So, referring to the two sets defined in (7), the domain of A is the set {a,c,f}, while the range of A is the set {3,4,6,7}. The domain of B is the set {2,3,4,5,6,7}, while the range of B is the set {2,3,4,7}.

(7) A = {⟨a,3⟩, ⟨f,4⟩, ⟨c,6⟩, ⟨a,7⟩}
B = {⟨2,3⟩, ⟨3,2⟩, ⟨4,7⟩, ⟨5,2⟩, ⟨6,7⟩, ⟨7,4⟩}

A set of ordered pairs defines a mapping, or correspondence, from the domain onto the range. The mappings defined by sets A and B are shown in (8):

A function is a relation (= a set of ordered pairs) in which each element of the domain is mapped to a single, unique value in the range. The relation which corresponds to set A above is not a function, because A contains two distinct ordered pairs which have the same first element (⟨a,3⟩ and ⟨a,7⟩). The relation which corresponds to set B is a function, even though B contains distinct ordered pairs which have the same second element (⟨3,2⟩ and ⟨5,2⟩; ⟨4,7⟩ and ⟨6,7⟩). What matters is that each member of the domain occurs in just one ordered pair.

The function B is defined in (7) by listing all the ordered pairs which belong to it. Another way of defining this same function is shown in (9). The first member of each ordered pair is called an argument of the function, while the second member of each ordered pair is called a value. The information in (9) is equivalent to that in (8b), showing how the function maps each argument onto a unique value. The format in (9) is more convenient for stating the value which corresponds to a single argument, when we do not need to list the entire set.

(9) B(2) = 3
B(3) = 2
B(4) = 7
B(5) = 2
B(6) = 7
B(7) = 4

The membership of any set S can be expressed as a function which maps the elements of S onto the set {1,0}. In this context, 1 represents “True” and 0 represents “False”. Functions of this kind are called the characteristic functions (or, sometimes, “membership functions”). For example, the characteristic function of set C (members of the Beatles, as specified in 10a), is the function f₁ as defined in (11a). The characteristic function of set D (numbers between 10 and 20, as specified in 10b) is the function f₂ as defined in (11b). (The abbreviation “iff” stands for “if and only if”.)

(10) a. C = {John, Paul, George, Ringo}
b. D = {x: 10 < x < 20}

(11) a. f₁(John) = 1
f₁(Paul) = 1
f₁(George) = 1
f₁(Ringo) = 1
in all other cases, f₁(x) = 0

b. f₂(x) = 1 iff 10 < x < 20
in all other cases, f₂(x) = 0

13.3.2 Operations and relations on sets

When we use set concepts and terminology as a tool for interpreting sentences, we will often want to say something about the relationship between two sets, or to combine two or more sets in certain ways to define a new set. In order for this to be possible, we must assume that the elements of each of the sets under discussion are drawn from the same universal set. This universal set is referred to as U.

A very important relation which may hold between two sets is the subset relation, also referred to as set inclusion. We say that set A is a subset of set B (written “A⊆B”) if A is included in B; that is, if all the elements which are members of A are also members of B. We can illustrate this situation using the sets defined in (12). The universal set U is assumed to be the set of all integers between 1 and 10. By comparing the elements in set A with those in set B, we see that all the elements which are members of A are also members of B; so in this context, “A⊆B” is a true proposition. However, “B⊆A” would be false in this context, because there are some members of B which are not members of A, namely 2, 5, and 7.

(12) U = {1,2,3,4,5,6,7,8,9,10}
A = {3,4,6}
B = {2,3,4,5,6,7}

Figure 13.1 illustrates the subset relation in the form of a diagram, where each oval represents one of the sets.⁵ Additional examples in standard set notation are provided in (13).

Figure 13.1: Set inclusion (the subset relation)

(13) a. {a,b,c} ⊆ {a,b,c,d,f}
b. {a,b,c} ⊈ {c,d,f}
c. {a,b,c} ⊆ {a,b,c}
d. ∀S (where S is a set), ∅ ⊆ S

Every set is a subset of itself, because all the elements which are members of set A are by definition members of set A. For this reason, the proposition “A⊆A” will be true whenever A is a well-defined set, as illustrated in (13c). If we want to specify that set A is a subset of set B, but that the two sets are not equal, we can write “A⊂B”. This symbol means that set A is a proper subset of set B. The proposition “A⊂A” will be false for any set A.

Since the elements of every set must be members of the current universal set U, “A⊆U” must always be true. If “U⊆A” is true, than it must be the case that A=U.

The intersection of two sets, written “A∩B”, is defined as the set consisting of all elements which are both members of A and members of B. We can illustrate this situation using the sets defined in (14). By comparing the elements in set A with those in set B, we see that the two sets share only the following elements in common: 3, 4, and 6; so A∩B = {3,4,6}.

(14) U = {1,2,3,4,5,6,7,8,9,10}
A = {2,3,4,6}
B = {3,4,5,6,7,8}

Figure 13.2 illustrates set intersection in the form of a diagram: the ovals represent two sets, labeled A and B, while the shaded portion which is included in both ovals represents the intersection of the two sets (A∩B). Another example in standard set notation is provided in (15).

Figure 13.2: : Set intersection

(15) {a,b,c} ∩ {c,d,f} = {c}

The union of two sets, written “A∪B”, is the set consisting of all elements which are either members of A or members of B. Returning to the sets defined in (14), the union of the two sets is formed by combining all the elements from both, which yields the following result: A∪B = {2,3,4,5,6,7,8}. Figure 13.3 illustrates this in the form of a diagram, and another example in standard set notation is provided in (16).

Figure 13.3: Set union

(16) {a,b,c} ∪ {c,d,f} = {a,b,c,d,f}

The complement of set A, written as A or A ′ , is defined as the set which contains all the elements of U that are not elements of A. Some simple examples are shown in (17). Here, the only elements of U which are not in A are 1 and 5, so A = {1,5}. Similarly, the elements of U which are not in B are 1, 2, 5, and 6; so B = {1,2,5,6}.

(17) U = {1,2,3,4,5,6}
A = {2,3,4,6}
A = {1,5}
B = {3,4}
B = {1,2,5,6}

This basic notion of complement set involves complements relative to the universal set U. It is often useful to refer to the complement of one set relative to some other set. The complement of A relative to B, written “B–A”, is the set consisting of all elements which are members of B but not members of A.6 Another way of expressing this definition is the following: B–A = B∩A. Figure 13.4 illustrates this in the form of a diagram, and several examples in standard set notation are provided in (18).

Figure 13.4: Set complementation

(18) {a,b,c} – {b,c} = {a}
{a,b,c,d,f} – {a,b,c,j,k,p} = {d,f}
A – ∅ = A
∅ – A = ∅
U – A = A

To summarize, we have defined three basic operations on sets (intersection, union, and complement or “difference”), and one relation between sets, namely inclusion (the subset relation). The three operations provide ways of combining two existing sets to define a new set. It is important to note that “A∩B”, “A∪B”, and “B–A” are names of sets; but “A⊆B” is a proposition, a claim about the membership of the two sets, which could be true or false.

More precise definitions of set intersection, union, complementation, and inclusion (the subset relation) are provided in (19). These definitions will help us to understand, for example, why the interpretation of an “and” statement frequently involves the intersection of two sets while the interpretation of an “or” statement frequently involves the union of two sets.

(19) ∀x [x ∈ (A∩B) ↔ ((x∈A) ∧ (x∈B))] [intersection]
∀x [x ∈ (A∪B) ↔ ((x∈A) ∨ (x∈B))] [union]
∀x [x ∈ (A–B) ↔ ((x∈A) ∧ (x<B))] [complement]
(A ⊆ B) ↔ ∀x [(x∈A) → (x∈B)] [subset]

---

² This example is taken from Cherchia & McConnell-Ginet (1990: 431).

³ This puzzle is a version of “Russell’s paradox”, which Bertrand Russell discovered in 1901 and described in a letter to Frege on June 16, 1902. Apparently it had also been noticed by Ernst Zermelo a few years earlier. It posed a major challenge to Frege’s work on the foundations of mathematics.

⁴ See Chapter 4.

⁵ This way of representing sets is called a Venn diagram.

⁶ This operation is sometimes referred to as “set subtraction.”