Sets are (arguably) the most fundamental of all mathematical objects. Quite simply, a set is
a collection things, the things belonging to the set are called members
or elements of the set.1 Other synonyms for the word “set,” are collection, class, family, and ensemble. We refer to a collection of people, family of functions, an ensemble of voters, and so on. We even consider sets whose members themselves are sets, such as the set of classes at a university, where each class consists of students. In mathematics, we might consider the set of all open intervals on the real line or the set of solutions of an equation.
If a set does not contain too many members, we can specify the set by simply writing down the members of the inside a pair of brackets, such as {3, 7, 31}, which denotes the first three Mersenne primes.2 Sometimes sets contain an infinite number of elements, like the natural numbers, where we might specify them by {1, 2, 3, …}, where the three dots after the 3 signify “and so on.”
We generally denote sets by capital letters such as A, B, C, … and members of sets by small letters, like a, b, c, …. If a is a member of a set A, we denote this by writing a ∈ A, and we say “a is a member of A” or “a belongs to A.” If an element does not belong to a set, we denote this by a ∉ A.
One can also specify a set by specifying defining properties of the member of the set, such as illustrated in Figure 2.1.which we read as “the set of all x in a set A that satisfies the proposition P(x).” The set of even integers could be denoted by
Some common sets in mathematics are listed in Table 2.1.
Table 2.1 Some common sets.
Common sets in mathematics |
The half‐open intervals (a, b] and [a, b) are defined similarly.
Some examples illustrating membership and nonmembership in sets are the following.
Sets are often illustrated visually by Venn diagrams, where sets are represented by circles or ovals and elements of a set as points inside the circle. Figure 2.2 shows a Venn diagram that might ring a bell for most students and illustrates A ⊆ B. The diagram also illustrates that A is not a subset of C.
The empty set is not is not nothing, it is something, it is just that it contains nothing. You might think of the empty set as a bag that has nothing in it. In this regard, it might be better to denote the empty set by { } rather than Ø. For example
which may seem a bit strange, but it makes a point. There is only one empty set regardless of how differently it is expressed.
A few power sets of some other sets are given in Table 2.2
Table 2.2 Typical power sets.
Set | Power set |
Ø | {Ø} |
{a} | {Ø, {a}} |
{a, b} | {Ø, {a}, {b}, {a, b}} |
{a, {b}} | {Ø, {a}, {{b}}, {a, {b}}} |
Later, we will prove that for any set of n elements, the power set contains 2n elements, which we will prove by induction.4
In arithmetic, we have the binary operations + and ×, whereas in logic, we have analogous binary operations of ∨ and ∧, and now for sets, we have the binary operations of union ∪ and intersection ∩.
Venn diagrams for subsets A, B of a universe U are shown in Figure 2.6. The universe is represented by the rectangle containing the sets.
Figure 2.7 illustrates Venn diagrams for three subsets of a universe U.
The properties of “∪” and “∩” in set theory have their counterparts in the properties of “∨” and “∧” in sentential logic. Table 2.3 illustrates these counterparts.
Table 2.3 Equivalence between some laws of logic and laws of sets.
Tautology | Set equivalence |
P ∨ Q ≡ Q ∨ P | A ∪ B = B ∪ A |
P ∧ Q ≡ Q ∧ P | A ∩ B = B ∩ A |
P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R | A ∪ (B ∪ C) = (A ∪ B) ∪ C |
P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R | A ∩ (B ∩ C) = (A ∩ B) ∩ C |
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) |
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
P ∧ P ≡ P | A ∩ A = A |
P ∨ P ≡ P | A ∪ A = A |
In sentential logic, we were introduced to the important tautologies
called De Morgan's laws. We now prove the set versions of these laws.
The second De Morgan law is left to the reader. See Problem 21.
We compare the set operations of union and intersection with the logical operations of “and” and “or,” and the arithmetic operations of + and + and × in Table 2.4.
Table 2.4 Sets, logic, and arithmetic.
Sets | Sentences | Arithmetic |
∪ | ∨ | + |
∩ | ∧ | × |
⊆ | ⇒ | ≤ |
∼P | − | |
= | ≡ | = |
Ø | F | 0 |
U | T | 1 |
Write the following sets in notation {x : P(x)}.
If A = {{a}, {b, c}, {d, e, f}}, tell if the following are true or false:
Which pair (∈, ⊆), , (∉, ⊆), of connectives describe the relationship between the quantity on the left with the set on the right. The answer to a) is since a is a member of {c, a, t} but not a subset.
Find the power set of the given sets.
Let A = {a1, a2, …}, where an is the remainder when n is divided by 5. List the elements of the set A.
If A = {a, b, c} are the following relations true or false?
The power set of a set can be interpreted as the set of all functions7 defined on the set whose values are 0 and 1. For example the functions defined on the set A = {a, b} with values 0 and 1 are
Show that the elements of the power set of A = {a, b, c} can be placed in this “one‐to‐one” correspondence with the functions on A whose values are either 0 or 1.
The second power set of a set A is the set of subsets of the set, or P(P(A)). What is the second power set of A = {a}?
Prove P(Ø) = {Ø}
Let A, B, and C be arbitrary subsets of a universe U. Prove the following.
The formula defines the difference between two sets in terms of the operations of intersection and complement. Can you find a formula for the union A ∪ B in terms of intersections and complements?
Prove A ∩ B = Ø ⇔ A − B = A.
Prove that if A, B, and C are sets, then “∪” distributes over “∩.” That is A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
Prove A ⊆ B ⇔ A ∪ B = B.
It is possible to prove identities of sets using truth tables. For example one of DeMorgan's laws
is verified from Table 2.5, replacing the union by “or,” the intersection by “and,” and set complementation by “not.”
Prove the following identities using truth tables.
Table 2.5 Verifying set relations with truth tables.
(1) | (2) | (3) | (4) | (5) | ||
x ∈ A | x ∈ B | A ∪ B | ||||
T | T | T | F | F | F | F |
T | F | T | F | F | T | F |
F | T | T | F | T | F | F |
F | F | F | T | T | T | T |
Same truth values |
Prove
Finite sets can be represented by vectors of 0s and 1s. For the set U = {a1, a2, … , an}, we can represent a subset S of this set by a bit string, where the ith bit is 1 if ai ∈ S and 0 if ai ∉ S. The following problems relate to this representation of sets. Take as the universe, the set U = {0, 1, 2, 3, 4, 5, 6, 7}.
Prove the De Morgan law .
There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward mathematical rigor, naive set theory, George Boole, power set of a set.
44.201.64.238