Discrete Mathematics and its Applications Textbook PDF

C H A P T E R Basic Structures: Sets, Functions, 2 Sequences, Sums, and Matrices 2.1 Sets 2.2 Set Operations M uch of discrete mathematics is devoted to the study of discrete structures, used to rep- resent discrete objects. Many important discrete structures are built using sets, which are collections of objects. Among the discrete structures built from sets are combinations, un- 2.3 Functions ordered collections of objects used extensively in counting; relations, sets of ordered pairs that represent relationships between objects; graphs, sets of vertices and edges that connect vertices; 2.4 Sequences and and ﬁnite state machines, used to model computing machines. These are some of the topics we Summations will study in later chapters. 2.5 Cardinality of The concept of a function is extremely important in discrete mathematics. A function as- Sets signs to each element of a ﬁrst set exactly one element of a second set, where the two sets are not necessarily distinct. Functions play important roles throughout discrete mathematics. They 2.6 Matrices are used to represent the computational complexity of algorithms, to study the size of sets, to count objects, and in a myriad of other ways. Useful structures such as sequences and strings are special types of functions. In this chapter, we will introduce the notion of sequences, which represent ordered lists of elements. Furthermore, we will introduce some important types of sequences and we will show how to deﬁne the terms of a sequence using earlier terms. We will also address the problem of identifying a sequence from its ﬁrst few terms. In our study of discrete mathematics, we will often add consecutive terms of a sequence of numbers. Because adding terms from a sequence, as well as other indexed sets of numbers, is such a common occurrence, a special notation has been developed for adding such terms. In this chapter, we will introduce the notation used to express summations. We will develop formulae for certain types of summations that appear throughout the study of discrete mathematics. For instance, we will encounter such summations in the analysis of the number of steps used by an algorithm to sort a list of numbers so that its terms are in increasing order. The relative sizes of inﬁnite sets can be studied by introducing the notion of the size, or cardinality, of a set. We say that a set is countable when it is ﬁnite or has the same size as the set of positive integers. In this chapter we will establish the surprising result that the set of rational numbers is countable, while the set of real numbers is not. We will also show how the concepts we discuss can be used to show that there are functions that cannot be computed using a computer program in any programming language. Matrices are used in discrete mathematics to represent a variety of discrete structures. We will review the basic material about matrices and matrix arithmetic needed to represent relations and graphs. The matrix arithmetic we study will be used to solve a variety of problems involving these structures. 2.1 Sets 2.1.1 Introduction In this section, we study the fundamental discrete structure on which all other discrete structures are built, namely, the set. Sets are used to group objects together. Often, but not always, the objects in a set have similar properties. For instance, all the students who are currently enrolled in your school make up a set. Likewise, all the students currently taking a course in discrete mathematics at any school make up a set. In addition, those students enrolled in your school who are taking a course in discrete mathematics form a set that can be obtained by taking the elements common to the ﬁrst two collections. The language of sets is a means to study such 121 122 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices collections in an organized fashion. We now provide a deﬁnition of a set. This deﬁnition is an intuitive deﬁnition, which is not part of a formal theory of sets. Deﬁnition 1 A set is an unordered collection of distinct objects, called elements or members of the set. A set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A. The notation a ∉ A denotes that a is not an element of the set A. It is common for sets to be denoted using uppercase letters. Lowercase letters are usually used to denote elements of sets. There are several ways to describe a set. One way is to list all the members of a set, when this is possible. We use a notation where all members of the set are listed between braces. For example, the notation {a, b, c, d} represents the set with the four elements a, b, c, and d. This way of describing a set is known as the roster method. EXAMPLE 1 The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}. ◂ EXAMPLE 2 The set O of odd positive integers less than 10 can be expressed by O = {1, 3, 5, 7, 9}. ◂ EXAMPLE 3 Although sets are usually used to group together elements with common properties, there is nothing that prevents a set from having seemingly unrelated elements. For instance, {a, 2, Fred, New Jersey} is the set containing the four elements a, 2, Fred, and New Jersey. ◂ Sometimes the roster method is used to describe a set without listing all its members. Some members of the set are listed, and then ellipses (…) are used when the general pattern of the elements is obvious. EXAMPLE 4 The set of positive integers less than 100 can be denoted by {1, 2, 3, … , 99}. ◂ Another way to describe a set is to use set builder notation. We characterize all those Extra elements in the set by stating the property or properties they must have to be members. The Examples general form of this notation is {x ∣ x has property P} and is read “the set of all x such that x has property P.” For instance, the set O of all odd positive integers less than 10 can be written as O = {x ∣ x is an odd positive integer less than 10}, or, specifying the universe as the set of positive integers, as O = {x ∈ Z+ ∣ x is odd and x < 10}. We often use this type of notation to describe sets when it is impossible to list all the elements of the set. For instance, the set Q+ of all positive rational numbers can be written as Q+ = {x ∈ R ∣ x = pq , for some positive integers p and q}. Beware that mathe- These sets, each denoted using a boldface letter, play an important role in discrete mathe- maticians disagree matics: whether 0 is a natural number. We consider it N = {0, 1, 2, 3, …}, the set of all natural numbers quite natural. Z = {… , −2, −1, 0, 1, 2, …}, the set of all integers Z+ = {1, 2, 3, …}, the set of all positive integers Q = {p∕q ∣ p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers R, the set of all real numbers 2.1 Sets 123 R+ , the set of all positive real numbers C, the set of all complex numbers. (Note that some people do not consider 0 a natural number, so be careful to check how the term natural numbers is used when you read other books.) Among the sets studied in calculus and other subjects are intervals, sets of all the real numbers between two numbers a and b, with or without a and b. If a and b are real numbers with a ≤ b, we denote these intervals by [a, b] = {x | a ≤ x ≤ b} [a, b) = {x | a ≤ x < b} (a, b] = {x | a < x ≤ b} (a, b) = {x | a < x < b}. Note that [a, b] is called the closed interval from a to b and (a, b) is called the open interval from a to b. Each of the intervals [a, b], [a, b), (a, b], and (a, b) contains all the real numbers strictly between a and b. The ﬁrst two of these contain a and the ﬁrst and third contain b. Remark: Some books use the notations [a, b[, ]a, b], and ]a, b[ for [a, b), (a, b], and (a, b), re- spectively. Sets can have other sets as members, as Example 5 illustrates. EXAMPLE 5 The set {N, Z, Q, R} is a set containing four elements, each of which is a set. The four elements of this set are N, the set of natural numbers; Z, the set of integers; Q, the set of rational numbers; and R, the set of real numbers. ◂ Remark: Note that the concept of a datatype, or type, in computer science is built upon the con- cept of a set. In particular, a datatype or type is the name of a set, together with a set of opera- tions that can be performed on objects from that set. For example, boolean is the name of the set {0, 1}, together with operators on one or more elements of this set, such as AND, OR, and NOT. Because many mathematical statements assert that two diﬀerently speciﬁed collections of objects are really the same set, we need to understand what it means for two sets to be equal. Deﬁnition 2 Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B). We write A = B if A and B are equal sets. Links GEORG CANTOR (1845–1918) Georg Cantor was born in St. Petersburg, Russia, where his father was a successful merchant. Cantor developed his interest in mathematics in his teens. He began his university studies in Zurich in 1862, but when his father died he left Zurich. He continued his university studies at the University of Berlin in 1863, where he studied under the eminent mathematicians Weierstrass, Kummer, and Kronecker. He received his doctor’s degree in 1867, after having written a dissertation on number theory. Cantor assumed a position at the University of Halle in 1869, where he continued working until his death. Cantor is considered the founder of set theory. His contributions in this area include the discovery that the set of real numbers is uncountable. He is also noted for his many important contributions to analysis. Cantor Source: Library of Congress also was interested in philosophy and wrote papers relating his theory of sets with metaphysics. Prints and Photographs Cantor married in 1874 and had six children. His melancholy temperament was balanced by his wife’s Division [LC-USZ62-74393] happy disposition. Although he received a large inheritance from his father, he was poorly paid as a professor. To mitigate this, he tried to obtain a better-paying position at the University of Berlin. His appointment there was blocked by Kronecker, who did not agree with Cantor’s views on set theory. Cantor suﬀered from mental illness throughout the later years of his life. He died in 1918 from a heart attack. 124 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices EXAMPLE 6 The sets {1, 3, 5} and {3, 5, 1} are equal, because they have the same elements. Note that the order in which the elements of a set are listed does not matter. Note also that it does not matter if an element of a set is listed more than once, so {1, 3, 3, 3, 5, 5, 5, 5} is the same as the set {1, 3, 5} because they have the same elements. ◂ THE EMPTY SET There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by ∅. The empty set can also be denoted by { } (that is, we represent the empty set with a pair of braces that encloses all the elements in this set). Often, a set of elements with certain properties turns out to be the null set. For instance, the set of all positive integers that are greater than their squares is the null set. A set with one element is called a singleton set. A common error is to confuse the empty {∅} has one more element than ∅. set ∅ with the set {∅}, which is a singleton set. The single element of the set {∅} is the empty set itself! A useful analogy for remembering this diﬀerence is to think of folders in a computer ﬁle system. The empty set can be thought of as an empty folder and the set consisting of just the empty set can be thought of as a folder with exactly one folder inside, namely, the empty folder. NAIVE SET THEORY Note that the term object has been used in the deﬁnition of a set, Links Deﬁnition 1, without specifying what an object is. This description of a set as a collection of objects, based on the intuitive notion of an object, was ﬁrst stated in 1895 by the German mathematician Georg Cantor. The theory that results from this intuitive deﬁnition of a set, and the use of the intuitive notion that for any property whatever, there is a set consisting of exactly the objects with this property, leads to paradoxes, or logical inconsistencies. This was shown by the English philosopher Bertrand Russell in 1902 (see Exercise 50 for a description of one of these paradoxes). These logical inconsistencies can be avoided by building set theory beginning with axioms. However, we will use Cantor’s original version of set theory, known as naive set theory, in this book because all sets considered in this book can be treated consistently using Cantor’s original theory. Students will ﬁnd familiarity with naive set theory helpful if they go on to learn about axiomatic set theory. They will also ﬁnd the development of axiomatic set theory much more abstract than the material in this text. We refer the interested reader to [Su72] to learn more about axiomatic set theory. 2.1.2 Venn Diagrams Sets can be represented graphically using Venn diagrams, named after the English mathemati- cian John Venn, who introduced their use in 1881. In Venn diagrams the universal set U, which contains all the objects under consideration, is represented by a rectangle. (Note that the univer- sal set varies depending on which objects are of interest.) Inside this rectangle, circles or other geometrical ﬁgures are used to represent sets. Sometimes points are used to represent the par- Assessment ticular elements of the set. Venn diagrams are often used to indicate the relationships between sets. We show how a Venn diagram can be used in Example 7. EXAMPLE 7 Draw a Venn diagram that represents V, the set of vowels in the English alphabet. Solution: We draw a rectangle to indicate the universal set U, which is the set of the 26 letters of the English alphabet. Inside this rectangle we draw a circle to represent V. Inside this circle we indicate the elements of V with points (see Figure 1). ◂ 2.1 Sets 125 U a u e V o i FIGURE 1 Venn diagram for the set of vowels. 2.1.3 Subsets It is common to encounter situations where the elements of one set are also the elements of a second set. We now introduce some terminology and notation to express such relationships between sets. Deﬁnition 3 The set A is a subset of B, and B is a superset of A, if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B. If, instead, we want to stress that B is a superset of A, we use the equivalent notation B ⊇ A. (So, A ⊆ B and B ⊇ A are equivalent statements.) We see that A ⊆ B if and only if the quantiﬁcation ∀x(x ∈ A → x ∈ B) is true. Note that to show that A is not a subset of B we need only ﬁnd one element x ∈ A with x ∉ B. Such an x is a counterexample to the claim that x ∈ A implies x ∈ B. We have these useful rules for determining whether one set is a subset of another: Showing that A is a Subset of B To show that A ⊆ B, show that if x belongs to A then x also belongs to B. Showing that A is Not a Subset of B To show that A ⊈ B, ﬁnd a single x ∈ A such that x ∉ B. EXAMPLE 8 The set of all odd positive integers less than 10 is a subset of the set of all positive integers less than 10, the set of rational numbers is a subset of the set of real numbers, the set of all computer Links BERTRAND RUSSELL (1872–1970) Bertrand Russell was born into a prominent English family active in the progressive movement and having a strong commitment to liberty. He became an orphan at an early age and was placed in the care of his father’s parents, who had him educated at home. He entered Trinity College, Cambridge, in 1890, where he excelled in mathematics and in moral science. He won a fellowship on the basis of his work on the foundations of geometry. In 1910 Trinity College appointed him to a lectureship in logic and the philosophy of mathematics. Russell fought for progressive causes throughout his life. He held strong paciﬁst views, and his protests against World War I led to dismissal from his position at Trinity College. He was imprisoned for 6 months in Source: Library of 1918 because of an article he wrote that was branded as seditious. Russell fought for women’s suﬀrage in Great Congress Prints and Britain. In 1961, at the age of 89, he was imprisoned for the second time for his protests advocating nuclear Photographs Division [LC-USZ62-49535] disarmament. Russell’s greatest work was in his development of principles that could be used as a foundation for all of mathematics. His most famous work is Principia Mathematica, written with Alfred North Whitehead, which attempts to deduce all of mathematics using a set of primitive axioms. He wrote many books on philosophy, physics, and his political ideas. Russell won the Nobel Prize for Literature in 1950. 126 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices science majors at your school is a subset of the set of all students at your school, and the set of all people in China is a subset of the set of all people in China (that is, it is a subset of itself). Each of these facts follows immediately by noting that an element that belongs to the ﬁrst set in each pair of sets also belongs to the second set in that pair. ◂ EXAMPLE 9 The set of integers with squares less than 100 is not a subset of the set of nonnegative integers because −1 is in the former set [as (−1)2 < 100], but not the latter set. The set of people who have taken discrete mathematics at your school is not a subset of the set of all computer science majors at your school if there is at least one student who has taken discrete mathematics who is not a computer science major. ◂ Theorem 1 shows that every nonempty set S is guaranteed to have at least two subsets, the empty set and the set S itself, that is, ∅ ⊆ S and S ⊆ S. THEOREM 1 For every set S, (i ) ∅ ⊆ S and (ii ) S ⊆ S. Proof: We will prove (i ) and leave the proof of (ii ) as an exercise. Let S be a set. To show that ∅ ⊆ S, we must show that ∀x(x ∈ ∅ → x ∈ S) is true. Because the empty set contains no elements, it follows that x ∈ ∅ is always false. It follows that the conditional statement x ∈ ∅ → x ∈ S is always true, because its hypothesis is always false and a conditional statement with a false hypothesis is true. Therefore, ∀x(x ∈ ∅ → x ∈ S) is true. This completes the proof of (i). Note that this is an example of a vacuous proof. When we wish to emphasize that a set A is a subset of a set B but that A ≠ B, we write A ⊂ B and say that A is a proper subset of B. For A ⊂ Bto be true, it must be the case that A ⊆ B and there must exist an element x of B that is not an element of A. That is, A is a proper subset of B if and only if ∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∉ A) is true. Venn diagrams can be used to illustrate that a set A is a subset of a set B. We draw the universal set U as a rectangle. Within this rectangle we draw a circle for B. Because A is a subset of B, we draw the circle for A within the circle for B. This relationship is shown in Figure 2. Recall from Deﬁnition 2 that sets are equal if they have the same elements. A useful way to show that two sets have the same elements is to show that each set is a subset of the other. In other words, we can show that if A and B are sets with A ⊆ B and B ⊆ A, then A = B. That is, A = B if and only if ∀x(x ∈ A → x ∈ B) and ∀x(x ∈ B → x ∈ A) or equivalently if and only if ∀x(x ∈ A ↔ x ∈ B), which is what it means for the A and B to be equal. Because this method of showing two sets are equal is so useful, we highlight it here. Links JOHN VENN (1834–1923) John Venn was born into a London suburban family noted for its philanthropy. He attended London schools and got his mathematics degree from Caius College, Cambridge, in 1857. He was elected a fellow of this college and held his fellowship there until his death. He took holy orders in 1859 and, after a brief stint of religious work, returned to Cambridge, where he developed programs in the moral sciences. Besides his mathematical work, Venn had an interest in history and wrote extensively about his college and family. Venn’s book Symbolic Logic clariﬁes ideas originally presented by Boole. In this book, Venn presents a systematic development of a method that uses geometric ﬁgures, known now as Venn diagrams. Today these Alpha c Historica/Alamy diagrams are primarily used to analyze logical arguments and to illustrate relationships between sets. In addition Stock Photo to his work on symbolic logic, Venn made contributions to probability theory described in his widely used textbook on that subject. 2.1 Sets 127 U A B FIGURE 2 Venn diagram showing that A is a subset of B. Showing Two Sets are Equal To show that two sets A and B are equal, show that A ⊆ B and B ⊆ A. Sets may have other sets as members. For instance, we have the sets A = {∅, {a}, {b}, {a, b}} and B = {x ∣ x is a subset of the set {a, b}}. Note that these two sets are equal, that is, A = B. Also note that {a} ∈ A, but a ∉ A. 2.1.4 The Size of a Set Sets are used extensively in counting problems, and for such applications we need to discuss the sizes of sets. Deﬁnition 4 Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a ﬁnite set and that n is the cardinality of S. The cardinality of S is denoted by |S|. Remark: The term cardinality comes from the common usage of the term cardinal number as the size of a ﬁnite set. EXAMPLE 10 Let A be the set of odd positive integers less than 10. Then |A| = 5. ◂ EXAMPLE 11 Let S be the set of letters in the English alphabet. Then |S| = 26. ◂ EXAMPLE 12 Because the null set has no elements, it follows that |∅| = 0. ◂ We will also be interested in sets that are not ﬁnite. Deﬁnition 5 A set is said to be inﬁnite if it is not ﬁnite. EXAMPLE 13 The set of positive integers is inﬁnite. ◂ Extra We will extend the notion of cardinality to inﬁnite sets in Section 2.5, a challenging topic Examples full of surprising results. 128 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.1.5 Power Sets Many problems involve testing all combinations of elements of a set to see if they satisfy some property. To consider all such combinations of elements of a set S, we build a new set that has as its members all the subsets of S. Deﬁnition 6 Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by (S). EXAMPLE 14 What is the power set of the set {0, 1, 2}? Extra Solution: The power set ({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence, Examples ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}. Note that the empty set and the set itself are members of this set of subsets. ◂ EXAMPLE 15 What is the power set of the empty set? What is the power set of the set {∅}? Solution: The empty set has exactly one subset, namely, itself. Consequently, (∅) = {∅}. The set {∅} has exactly two subsets, namely, ∅ and the set {∅} itself. Therefore, ({∅}) = {∅, {∅}}. ◂ If a set has n elements, then its power set has 2n elements. We will demonstrate this fact in several ways in subsequent sections of the text. 2.1.6 Cartesian Products The order of elements in a collection is often important. Because sets are unordered, a diﬀerent structure is needed to represent ordered collections. This is provided by ordered n-tuples. Deﬁnition 7 The ordered n-tuple (a1 , a2 , … , an ) is the ordered collection that has a1 as its ﬁrst element, a2 as its second element, … , and an as its nth element. We say that two ordered n-tuples are equal if and only if each corresponding pair of their elements is equal. In other words, (a1 , a2 , … , an ) = (b1 , b2 , … , bn ) if and only if ai = bi , for i = 1, 2, … , n. In particular, ordered 2-tuples are called ordered pairs. The ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d. Note that (a, b) and (b, a) are not equal unless a = b. 2.1 Sets 129 Many of the discrete structures we will study in later chapters are based on the notion of the Cartesian product of sets (named after René Descartes). We ﬁrst deﬁne the Cartesian product of two sets. Deﬁnition 8 Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence, A × B = {(a, b) ∣ a ∈ A ∧ b ∈ B}. EXAMPLE 16 Let A represent the set of all students at a university, and let B represent the set of all courses Extra oﬀered at the university. What is the Cartesian product A × B and how can it be used? Examples Solution: The Cartesian product A × B consists of all the ordered pairs of the form (a, b), where a is a student at the university and b is a course oﬀered at the university. One way to use the set A × B is to represent all possible enrollments of students in courses at the university. Furthermore, observe that each subset of A × B represents one possible total enrollment conﬁguration, and (A × B) represents all possible enrollment conﬁgurations. ◂ EXAMPLE 17 What is the Cartesian product of A = {1, 2} and B = {a, b, c}? Solution: The Cartesian product A × B is A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. ◂ Note that the Cartesian products A × B and B × A are not equal unless A = ∅ or B = ∅ (so that A × B = ∅) or A = B (see Exercises 33 and 40). This is illustrated in Example 18. EXAMPLE 18 Show that the Cartesian product B × A is not equal to the Cartesian product A × B, where A and B are as in Example 17. Links RENÉ DESCARTES (1596–1650) René Descartes was born into a noble family near Tours, France, about 130 miles southwest of Paris. He was the third child of his father’s ﬁrst wife; she died several days after his birth. Because of René’s poor health, his father, a provincial judge, let his son’s formal lessons slide until, at the age of 8, René entered the Jesuit college at La Flèche. The rector of the school took a liking to him and permitted him to stay in bed until late in the morning because of his frail health. From then on, Descartes spent his mornings in bed; he considered these times his most productive hours for thinking. Descartes left school in 1612, moving to Paris, where he spent 2 years studying mathematics. He earned a law degree in 1616 from the University of Poitiers. At 18 Descartes became disgusted with studying and Stock c Montage/Archive decided to see the world. He moved to Paris and became a successful gambler. However, he grew tired of Photos/Getty Images bawdy living and moved to the suburb of Saint-Germain, where he devoted himself to mathematical study. When his gambling friends found him, he decided to leave France and undertake a military career. However, he never did any ﬁghting. One day, while escaping the cold in an overheated room at a military encampment, he had several feverish dreams, which revealed his future career as a mathematician and philosopher. After ending his military career, he traveled throughout Europe. He then spent several years in Paris, where he studied mathemat- ics and philosophy and constructed optical instruments. Descartes decided to move to Holland, where he spent 20 years wandering around the country, accomplishing his most important work. During this time he wrote several books, including the Discours, which contains his contributions to analytic geometry, for which he is best known. He also made fundamental contributions to philosophy. In 1649 Descartes was invited by Queen Christina to visit her court in Sweden to tutor her in philosophy. Although he was reluctant to live in what he called “the land of bears amongst rocks and ice,” he ﬁnally accepted the invitation and moved to Sweden. Unfortunately, the winter of 1649–1650 was extremely bitter. Descartes caught pneumonia and died in mid-February. 130 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices Solution: The Cartesian product B × A is B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}. This is not equal to A × B, which was found in Example 17. ◂ The Cartesian product of more than two sets can also be deﬁned. Deﬁnition 9 The Cartesian product of the sets A1 , A2 , … , An , denoted by A1 × A2 × ⋯ × An , is the set of ordered n-tuples (a1 , a2 , … , an ), where ai belongs to Ai for i = 1, 2, … , n. In other words, A1 × A2 × ⋯ × An = {(a1 , a2 , … , an ) ∣ ai ∈ Ai for i = 1, 2, … , n}. EXAMPLE 19 What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2}? Solution: The Cartesian product A × B × C consists of all ordered triples (a, b, c), where a ∈ A, b ∈ B, and c ∈ C. Hence, A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}. ◂ Remark: Note that when A, B, and C are sets, (A × B) × C is not the same as A × B × C (see Exercise 41). We use the notation A2 to denote A × A, the Cartesian product of the set A with itself. Similarly, A3 = A × A × A, A4 = A × A × A × A, and so on. More generally, An = {(a1 , a2 , … , an ) ∣ ai ∈ A for i = 1, 2, … , n}. EXAMPLE 20 Suppose that A = {1, 2}. It follows that A2 = {(1, 1), (1, 2), (2, 1), (2, 2)} and A3 = {(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)}. ◂ A subset R of the Cartesian product A × B is called a relation from the set A to the set B. The elements of R are ordered pairs, where the ﬁrst element belongs to A and the second to B. For example, R = {(a, 0), (a, 1), (a, 3), (b, 1), (b, 2), (c, 0), (c, 3)} is a relation from the set {a, b, c} to the set {0, 1, 2, 3}, and it is also a relation from the set {a, b, c, d, e} to the set {0, 1, 3, 4). (This illustrates that a relation need not contain a pair (x, y) for every element x of A.) A relation from a set A to itself is called a relation on A. EXAMPLE 21 What are the ordered pairs in the less than or equal to relation, which contains (a, b) if a ≤ b, on the set {0, 1, 2, 3}? Solution: The ordered pair (a, b) belongs to R if and only if both a and b belong to {0, 1, 2, 3} and a ≤ b. Consequently, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. ◂ We will study relations and their properties at length in Chapter 9. 2.1 Sets 131 2.1.7 Using Set Notation with Quantiﬁers Sometimes we restrict the domain of a quantiﬁed statement explicitly by making use of a par- ticular notation. For example, ∀x ∈ S(P(x)) denotes the universal quantiﬁcation of P(x) over all elements in the set S. In other words, ∀x ∈ S(P(x)) is shorthand for ∀x(x ∈ S → P(x)). Simi- larly, ∃x ∈ S(P(x)) denotes the existential quantiﬁcation of P(x) over all elements in S. That is, ∃x ∈ S(P(x)) is shorthand for ∃x(x ∈ S ∧ P(x)). EXAMPLE 22 What do the statements ∀x ∈ R (x2 ≥ 0) and ∃x ∈ Z (x2 = 1) mean? Solution: The statement ∀x ∈ R(x2 ≥ 0) states that for every real number x, x2 ≥ 0. This state- ment can be expressed as “The square of every real number is nonnegative.” This is a true statement. The statement ∃x ∈ Z(x2 = 1) states that there exists an integer x such that x2 = 1. This statement can be expressed as “There is an integer whose square is 1.” This is also a true state- ment because x = 1 is such an integer (as is −1). ◂ 2.1.8 Truth Sets and Quantiﬁers We will now tie together concepts from set theory and from predicate logic. Given a predicate P, and a domain D, we deﬁne the truth set of P to be the set of elements x in D for which P(x) is true. The truth set of P(x) is denoted by {x ∈ D ∣ P(x)}. EXAMPLE 23 What are the truth sets of the predicates P(x), Q(x), and R(x), where the domain is the set of integers and P(x) is “|x| = 1,” Q(x) is “x2 = 2,” and R(x) is “|x| = x.” Solution: The truth set of P, {x ∈ Z ∣ |x| = 1}, is the set of integers for which |x| = 1. Because |x| = 1 when x = 1 or x = −1, and for no other integers x, we see that the truth set of P is the set {−1, 1}. The truth set of Q, {x ∈ Z ∣ x2 = 2}, is the set of integers for which x2 = 2. This is the empty set because there are no integers x for which x2 = 2. The truth set of R, {x ∈ Z ∣ |x| = x}, is the set of integers for which |x| = x. Because |x| = x if and only if x ≥ 0, it follows that the truth set of R is N, the set of nonnegative integers. ◂ Note that ∀xP(x) is true over the domain U if and only if the truth set of P is the set U. Likewise, ∃xP(x) is true over the domain U if and only if the truth set of P is nonempty. Exercises 1. List the members of these sets. 3. Which of the intervals (0, 5), (0, 5], [0, 5), [0, 5], (1, 4], a) {x ∣ x is a real number such that x2 = 1} [2, 3], (2, 3) contains b) {x ∣ x is a positive integer less than 12} a) 0? b) 1? c) {x ∣ x is the square of an integer and x < 100} c) 2? d) 3? d) {x ∣ x is an integer such that x2 = 2} e) 4? f ) 5? 2. Use set builder notation to give a description of each of 4. For each of these intervals, list all its elements or explain these sets. why it is empty. a) {0, 3, 6, 9, 12} a) [a, a] b) [a, a) b) {−3, −2, −1, 0, 1, 2, 3} c) (a, a] d) (a, a) c) {m, n, o, p} e) (a, b), where a > b f ) [a, b], where a > b 132 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 5. For each of these pairs of sets, determine whether the ﬁrst 18. Use a Venn diagram to illustrate the relationships A ⊂ B is a subset of the second, the second is a subset of the ﬁrst, and A ⊂ C. or neither is a subset of the other. 19. Suppose that A, B, and C are sets such that A ⊆ B and a) the set of airline ﬂights from New York to New Delhi, B ⊆ C. Show that A ⊆ C. the set of nonstop airline ﬂights from New York to 20. Find two sets A and B such that A ∈ B and A ⊆ B. New Delhi b) the set of people who speak English, the set of people 21. What is the cardinality of each of these sets? who speak Chinese a) {a} b) {{a}} c) the set of ﬂying squirrels, the set of living creatures c) {a, {a}} d) {a, {a}, {a, {a}}} that can ﬂy 22. What is the cardinality of each of these sets? 6. For each of these pairs of sets, determine whether the ﬁrst a) ∅ b) {∅} is a subset of the second, the second is a subset of the ﬁrst, c) {∅, {∅}} d) {∅, {∅}, {∅, {∅}}} or neither is a subset of the other. 23. Find the power set of each of these sets, where a and b a) the set of people who speak English, the set of people are distinct elements. who speak English with an Australian accent a) {a} b) {a, b} c) {∅, {∅}} b) the set of fruits, the set of citrus fruits c) the set of students studying discrete mathematics, the 24. Can you conclude that A = B if A and B are two sets with set of students studying data structures the same power set? 7. Determine whether each of these pairs of sets are equal. 25. How many elements does each of these sets have where a) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1} a and b are distinct elements? b) {{1}}, {1, {1}} c) ∅, {∅} a) ({a, b, {a, b}}) 8. Suppose that A = {2, 4, 6}, B = {2, 6}, C = {4, 6}, and b) ({∅, a, {a}, {{a}}}) D = {4, 6, 8}. Determine which of these sets are subsets c) ((∅)) of which other of these sets. 26. Determine whether each of these sets is the power set of 9. For each of the following sets, determine whether 2 is an a set, where a and b are distinct elements. element of that set. a) ∅ b) {∅, {a}} a) {x ∈ R | x is an integer greater than 1} c) {∅, {a}, {∅, a}} d) {∅, {a}, {b}, {a, b}} b) {x ∈ R | x is the square of an integer} 27. Prove that (A) ⊆ (B) if and only if A ⊆ B. c) {2,{2}} d) {{2},{{2}}} 28. Show that if A ⊆ C and B ⊆ D, then A × B ⊆ C × D e) {{2},{2,{2}}} f ) {{{2}}} 29. Let A = {a, b, c, d} and B = {y, z}. Find 10. For each of the sets in Exercise 9, determine whether {2} is an element of that set. a) A × B. b) B × A. 11. Determine whether each of these statements is true or 30. What is the Cartesian product A × B, where A is the set false. of courses oﬀered by the mathematics department at a a) 0 ∈ ∅ b) ∅ ∈ {0} university and B is the set of mathematics professors at c) {0} ⊂ ∅ d) ∅ ⊂ {0} this university? Give an example of how this Cartesian e) {0} ∈ {0} f ) {0} ⊂ {0} product can be used. g) {∅} ⊆ {∅} 31. What is the Cartesian product A × B × C, where A is the 12. Determine whether these statements are true or false. set of all airlines and B and C are both the set of all cities a) ∅ ∈ {∅} b) ∅ ∈ {∅, {∅}} in the United States? Give an example of how this Carte- c) {∅} ∈ {∅} d) {∅} ∈ {{∅}} sian product can be used. e) {∅} ⊂ {∅, {∅}} f ) {{∅}} ⊂ {∅, {∅}} 32. Suppose that A × B = ∅, where A and B are sets. What g) {{∅}} ⊂ {{∅}, {∅}} can you conclude? 13. Determine whether each of these statements is true or 33. Let A be a set. Show that ∅ × A = A × ∅ = ∅. false. 34. Let A = {a, b, c}, B = {x, y}, and C = {0, 1}. Find a) x ∈ {x} b) {x} ⊆ {x} c) {x} ∈ {x} a) A × B × C. b) C × B × A. d) {x} ∈ {{x}} e) ∅ ⊆ {x} f ) ∅ ∈ {x} c) C × A × B. d) B × B × B. 14. Use a Venn diagram to illustrate the subset of odd inte- 35. Find A2 if gers in the set of all positive integers not exceeding 10. a) A = {0, 1, 3}. b) A = {1, 2, a, b}. 15. Use a Venn diagram to illustrate the set of all months of the year whose names do not contain the letter R in the 36. Find A3 if set of all months of the year. a) A = {a}. b) A = {0, a}. 16. Use a Venn diagram to illustrate the relationship A ⊆ B 37. How many diﬀerent elements does A × B have if A has m and B ⊆ C. elements and B has n elements? 17. Use a Venn diagram to illustrate the relationships A ⊂ B 38. How many diﬀerent elements does A × B × C have if A and B ⊂ C. has m elements, B has n elements, and C has p elements? 2.2 Set Operations 133 39. How many diﬀerent elements does An have when A has 48. Find the truth set of each of these predicates where the m elements and n is a positive integer? domain is the set of integers. 40. Show that A × B ≠ B × A, when A and B are nonempty, a) P(x): x3 ≥ 1 b) Q(x): x2 = 2 unless A = B. c) R(x): x < x 2 ∗ 49. The deﬁning property of an ordered pair is that two or- 41. Explain why A × B × C and (A × B) × C are not the same. dered pairs are equal if and only if their ﬁrst elements are 42. Explain why (A × B) × (C × D) and A × (B × C) × D are equal and their second elements are equal. Surprisingly, not the same. instead of taking the ordered pair as a primitive con- 43. Prove or disprove that if A and B are sets, then (A × B) = cept, we can construct ordered pairs using basic notions (A) × (B). from set theory. Show that if we deﬁne the ordered pair 44. Prove or disprove that if A, B, and C are nonempty sets (a, b) to be {{a}, {a, b}}, then (a, b) = (c, d) if and only and A × B = A × C, then B = C. if a = c and b = d. [Hint: First show that {{a}, {a, b}} = {{c}, {c, d}} if and only if a = c and b = d.] 45. Translate each of these quantiﬁcations into English and ∗ 50. This exercise presents Russell’s paradox. Let S be the determine its truth value. set that contains a set x if the set x does not belong to a) ∀x ∈ R (x2 ≠ −1) b) ∃x ∈ Z (x2 = 2) itself, so that S = {x ∣ x ∉ x}. c) ∀x ∈ Z (x > 0) 2 d) ∃x ∈ R (x2 = x) a) Show the assumption that S is a member of S leads to 46. Translate each of these quantiﬁcations into English and Links a contradiction. determine its truth value. b) Show the assumption that S is not a member of S leads a) ∃x ∈ R (x3 = −1) b) ∃x ∈ Z (x + 1 > x) to a contradiction. c) ∀x ∈ Z (x − 1 ∈ Z) d) ∀x ∈ Z (x2 ∈ Z) By parts (a) and (b) it follows that the set S cannot be de- 47. Find the truth set of each of these predicates where the ﬁned as it was. This paradox can be avoided by restricting domain is the set of integers. the types of elements that sets can have. a) P(x): x2 < 3 b) Q(x): x2 > x ∗ 51. Describe a procedure for listing all the subsets of a c) R(x): 2x + 1 = 0 ﬁnite set. 2.2 Set Operations 2.2.1 Introduction Two, or more, sets can be combined in many diﬀerent ways. For instance, starting with the set of mathematics majors at your school and the set of computer science majors at your school, we can form the set of students who are mathematics majors or computer science majors, the set of students who are joint majors in mathematics and computer science, the set of all students not Links majoring in mathematics, and so on. Deﬁnition 1 Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set that contains those elements that are either in A or in B, or in both. An element x belongs to the union of the sets A and B if and only if x belongs to A or x belongs to B. This tells us that A ∪ B = {x ∣ x ∈ A ∨ x ∈ B}. The Venn diagram shown in Figure 1 represents the union of two sets A and B. The area that represents A ∪ B is the shaded area within either the circle representing A or the circle repre- senting B. We will give some examples of the union of sets. EXAMPLE 1 The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5}; that is, {1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}. ◂ 134 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices U U A B A B A ∪ B is shaded. A ∩ B is shaded. FIGURE 1 Venn diagram of the FIGURE 2 Venn diagram of the union of A and B. intersection of A and B. EXAMPLE 2 The union of the set of all computer science majors at your school and the set of all mathe- matics majors at your school is the set of students at your school who are majoring either in mathematics or in computer science (or in both). ◂ Deﬁnition 2 Let A and B be sets. The intersection of the sets A and B, denoted by A ∩ B, is the set con- taining those elements in both A and B. An element x belongs to the intersection of the sets A and B if and only if x belongs to A and x belongs to B. This tells us that A ∩ B = {x ∣ x ∈ A ∧ x ∈ B}. The Venn diagram shown in Figure 2 represents the intersection of two sets A and B. The shaded area that is within both the circles representing the sets A and B is the area that represents the intersection of A and B. We give some examples of the intersection of sets. EXAMPLE 3 The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3}; that is, {1, 3, 5} ∩ {1, 2, 3} = {1, 3}. ◂ EXAMPLE 4 The intersection of the set of all computer science majors at your school and the set of all mathematics majors is the set of all students who are joint majors in mathematics and computer science. ◂ Deﬁnition 3 Two sets are called disjoint if their intersection is the empty set. EXAMPLE 5 Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}. Because A ∩ B = ∅, A and B are disjoint. ◂ We are often interested in ﬁnding the cardinality of a union of two ﬁnite sets A and B. Note that |A| + |B| counts each element that is in A but not in B or in B but not in A exactly once, and Be careful not to overcount! each element that is in both A and B exactly twice. Thus, if the number of elements that are in both A and B is subtracted from |A| + |B|, elements in A ∩ B will be counted only once. Hence, |A ∪ B| = |A| + |B| − |A ∩ B|. The generalization of this result to unions of an arbitrary number of sets is called the principle of inclusion–exclusion. The principle of inclusion–exclusion is an important technique used in enumeration. We will discuss this principle and other counting techniques in detail in Chapters 6 and 8. 2.2 Set Operations 135 There are other important ways to combine sets. Deﬁnition 4 Let A and B be sets. The diﬀerence of A and B, denoted by A − B, is the set containing those elements that are in A but not in B. The diﬀerence of A and B is also called the complement of B with respect to A. Remark: The diﬀerence of sets A and B is sometimes denoted by A∖B. An element x belongs to the diﬀerence of A and B if and only if x ∈ A and x ∉ B. This tells us that A − B = {x ∣ x ∈ A ∧ x ∉ B}. The Venn diagram shown in Figure 3 represents the diﬀerence of the sets A and B. The shaded area inside the circle that represents A and outside the circle that represents B is the area that represents A − B. We give some examples of diﬀerences of sets. EXAMPLE 6 The diﬀerence of {1, 3, 5} and {1, 2, 3} is the set {5}; that is, {1, 3, 5} − {1, 2, 3} = {5}. This is diﬀerent from the diﬀerence of {1, 2, 3} and {1, 3, 5}, which is the set {2}. ◂ EXAMPLE 7 The diﬀerence of the set of computer science majors at your school and the set of mathematics majors at your school is the set of all computer science majors at your school who are not also mathematics majors. ◂ Once the universal set U has been speciﬁed, the complement of a set can be deﬁned. Deﬁnition 5 Let U be the universal set. The complement of the set A, denoted by A, is the complement of A with respect to U. Therefore, the complement of the set A is U − A. Remark: The deﬁnition of the complement of A depends on a particular universal set U. This deﬁnition makes sense for any superset U of A. If we want to identify the universal set U, we would write “the complement of A with respect to the set U.” An element belongs to A if and only if x ∉ A. This tells us that A = {x ∈ U ∣ x ∉ A}. In Figure 4 the shaded area outside the circle representing A is the area representing A. We give some examples of the complement of a set. EXAMPLE 8 Let A = {a, e, i, o, u} (where the universal set is the set of letters of the English alphabet). Then A = {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}. ◂ EXAMPLE 9 Let A be the set of positive integers greater than 10 (with universal set the set of all positive integers). Then A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. ◂ It is left to the reader (Exercise 21) to show that we can express the diﬀerence of A and B as the intersection of A and the complement of B. That is, A − B = A ∩ B. 136 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices U U A B A A – B is shaded. A is shaded. FIGURE 3 Venn diagram for FIGURE 4 Venn diagram for the diﬀerence of A and B. the complement of the set A. 2.2.2 Set Identities Table 1 lists the most important identities of unions, intersections, and complements of sets. We will prove several of these identities here, using three diﬀerent methods. These methods are presented to illustrate that there are often many diﬀerent approaches to the solution of a Set identities and propositional problem. The proofs of the remaining identities will be left as exercises. The reader should note equivalences are just the similarity between these set identities and the logical equivalences discussed in Section 1.3. special cases of (Compare Table 6 of Section 1.6 and Table 1.) In fact, the set identities given can be proved identities for Boolean directly from the corresponding logical equivalences. Furthermore, both are special cases of algebra. identities that hold for Boolean algebra (discussed in Chapter 12). TABLE 1 Set Identities. Identity Name A∩U =A Identity laws A∪∅=A A∪U =U Domination laws A∩∅=∅ A∪A=A Idempotent laws A∩A=A (A) = A Complementation law A∪B=B∪A Commutative laws A∩B=B∩A A ∪ (B ∪ C) = (A ∪ B) ∪ C Associative laws A ∩ (B ∩ C) = (A ∩ B) ∩ C A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive laws A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A∩B=A∪B De Morgan’s laws A∪B=A∩B A ∪ (A ∩ B) = A Absorption laws A ∩ (A ∪ B) = A A∪A=U Complement laws A∩A=∅ 2.2 Set Operations 137 Before we discuss diﬀerent approaches for proving set identities, we brieﬂy discuss the role of Venn diagrams. Although these diagrams can help us understand sets constructed using two or three atomic sets (the sets used to construct more complicated combinations of these sets), they provide far less insight when four or more atomic sets are involved. Venn diagrams for four or more sets are quite complex because it is necessary to use ellipses rather than circles to represent the sets. This is necessary to ensure that every possible combination of the sets is represented by a nonempty region. Although Venn diagrams can provide an informal proof for some identities, such proofs should be formalized using one of the three methods we will now This identity says that describe. the complement of the One way to show that two sets are equal is to show that each is a subset of the other. Recall intersection of two sets that to show that one set is a subset of a second set, we can show that if an element belongs to is the union of their the ﬁrst set, then it must also belong to the second set. We generally use a direct proof to do complements. this. We illustrate this type of proof by establishing the ﬁrst of De Morgan’s laws. EXAMPLE 10 Prove that A ∩ B = A ∪ B. Extra Solution: We will prove that the two sets A ∩ B and A ∪ B are equal by showing that each set is Examples a subset of the other. First, we will show that A ∩ B ⊆ A ∪ B. We do this by showing that if x is in A ∩ B, then it must also be in A ∪ B. Now suppose that x ∈ A ∩ B. By the deﬁnition of complement, x ∉ A ∩ B. Using the deﬁnition of intersection, we see that the proposition ¬((x ∈ A) ∧ (x ∈ B)) is true. By applying De Morgan’s law for propositions, we see that ¬(x ∈ A) or ¬(x ∈ B). Using the deﬁnition of negation of propositions, we have x ∉ A or x ∉ B. Using the deﬁnition of the complement of a set, we see that this implies that x ∈ A or x ∈ B. Consequently, by the deﬁnition of union, we see that x ∈ A ∪ B. We have now shown that A ∩ B ⊆ A ∪ B. Next, we will show that A ∪ B ⊆ A ∩ B. We do this by showing that if x is in A ∪ B, then it must also be in A ∩ B. Now suppose that x ∈ A ∪ B. By the deﬁnition of union, we know that x ∈ A or x ∈ B. Using the deﬁnition of complement, we see that x ∉ A or x ∉ B. Consequently, the proposition ¬(x ∈ A) ∨ ¬(x ∈ B) is true. By De Morgan’s law for propositions, we conclude that ¬((x ∈ A) ∧ (x ∈ B)) is true. By the deﬁnition of intersection, it follows that ¬(x ∈ A ∩ B). We now use the deﬁnition of complement to conclude that x ∈ A ∩ B. This shows that A ∪ B ⊆ A ∩ B. Because we have shown that each set is a subset of the other, the two sets are equal, and the identity is proved. ◂ We can more succinctly express the reasoning used in Example 10 using set builder nota- tion, as Example 11 illustrates. EXAMPLE 11 Use set builder notation and logical equivalences to establish the ﬁrst De Morgan law A ∩ B = A ∪ B. Solution: We can prove this identity with the following steps. A ∩ B = {x ∣ x ∉ A ∩ B} by deﬁnition of complement = {x ∣ ¬(x ∈ (A ∩ B))} by deﬁnition of does not belong symbol = {x ∣ ¬(x ∈ A ∧ x ∈ B)} by deﬁnition of intersection = {x ∣ ¬(x ∈ A) ∨ ¬(x ∈ B)} by the ﬁrst De Morgan law for logical equivalences = {x ∣ x ∉ A ∨ x ∉ B} by deﬁnition of does not belong symbol = {x ∣ x ∈ A ∨ x ∈ B} by deﬁnition of complement = {x ∣ x ∈ A ∪ B} by deﬁnition of union =A∪B by meaning of set builder notation 138 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices Note that besides the deﬁnitions of complement, union, set membership, and set builder notation, this proof uses the second De Morgan law for logical equivalences. ◂ Proving a set identity involving more than two sets by showing each side of the identity is a subset of the other often requires that we keep track of diﬀerent cases, as illustrated by the proof in Example 12 of one of the distributive laws for sets. EXAMPLE 12 Prove the second distributive law from Table 1, which states that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) for all sets A, B, and C. Solution: We will prove this identity by showing that each side is a subset of the other side. Suppose that x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ B ∪ C. By the deﬁnition of union, it follows that x ∈ A, and x ∈ B or x ∈ C (or both). In other words, we know that the compound proposition (x ∈ A) ∧ ((x ∈ B) ∨ (x ∈ C)) is true. By the distributive law for conjunction over disjunction, it follows that ((x ∈ A) ∧ (x ∈ B)) ∨ ((x ∈ A) ∧ (x ∈ C)). We conclude that either x ∈ A and x ∈ B, or x ∈ A and x ∈ C. By the deﬁnition of intersection, it follows that x ∈ A ∩ B or x ∈ A ∩ C. Using the deﬁnition of union, we conclude that x ∈ (A ∩ B) ∪ (A ∩ C). We con- clude that A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C). Now suppose that x ∈ (A ∩ B) ∪ (A ∩ C). Then, by the deﬁnition of union, x ∈ A ∩ B or x ∈ A ∩ C. By the deﬁnition of intersection, it follows that x ∈ A and x ∈ B or that x ∈ A and x ∈ C. From this we see that x ∈ A, and x ∈ B or x ∈ C. Consequently, by the deﬁnition of union we see that x ∈ A and x ∈ B ∪ C. Furthermore, by the deﬁnition of intersection, it follows that x ∈ A ∩ (B ∪ C). We conclude that (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C). This completes the proof of the identity. ◂ Set identities can also be proved using membership tables. We consider each combination of the atomic sets (that is, the original sets used to produce the sets on each side) that an element can belong to and verify that elements in the same combinations of sets belong to both the sets in the identity. To indicate that an element is in a set, a 1 is used; to indicate that an element is not in a set, a 0 is used. (The reader should note the similarity between membership tables and truth tables.) EXAMPLE 13 Use a membership table to show that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Solution: The membership table for these combinations of sets is shown in Table 2. This table has eight rows. Because the columns for A ∩ (B ∪ C) and (A ∩ B) ∪ (A ∩ C) are the same, the identity is valid. ◂ TABLE 2 A Membership Table for the Distributive Property. A B C B∪C A ∩ (B ∪ C) A∩B A∩C (A ∩ B) ∪ (A ∩ C) 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2.2 Set Operations 139 Once we have proved set identities, we can use them to prove new identities. In particular, we can apply a string of identities, one in each step, to take us from one side of a desired identity to the other. It is helpful to explicitly state the identity that is used in each step, as we do in Example 14. EXAMPLE 14 Let A, B, and C be sets. Show that A ∪ (B ∩ C) = (C ∪ B) ∩ A. Solution: We have A ∪ (B ∩ C) = A ∩ (B ∩ C) by the ﬁrst De Morgan law = A ∩ (B ∪ C) by the second De Morgan law = (B ∪ C) ∩ A by the commutative law for intersections = (C ∪ B) ∩ A by the commutative law for unions. ◂ We summarize the three diﬀerent ways for proving set identities in Table 3. TABLE 3 Methods of Proving Set Identities. Description Method Subset method Show that each side of the identity is a subset of the other side. Membership table For each possible combination of the atomic sets, show that an element in exactly these atomic sets must either belong to both sides or belong to neither side Apply existing identities Start with one side, transform it into the other side using a sequence of steps by applying an established identity. 2.2.3 Generalized Unions and Intersections Because unions and intersections of sets satisfy associative laws, the sets A ∪ B ∪ C and A ∩ B ∩ C are well deﬁned; that is, the meaning of this notation is unambiguous when A, B, and C are sets. That is, we do not have to use parentheses to indicate which operation comes ﬁrst because A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C. Note that A ∪ B ∪ C contains those elements that are in at least one of the sets A, B, and C, and that A ∩ B ∩ C con- tains those elements that are in all of A, B, and C. These combinations of the three sets, A, B, and C, are shown in Figure 5. EXAMPLE 15 Let A = {0, 2, 4, 6, 8}, B = {0, 1, 2, 3, 4}, and C = {0, 3, 6, 9}. What are A ∪ B ∪ C and A ∩ B ∩ C? Solution: The set A ∪ B ∪ C contains those elements in at least one of A, B, and C. Hence, A ∪ B ∪ C = {0, 1, 2, 3, 4, 6, 8, 9}. The set A ∩ B ∩ C contains those elements in all three of A, B, and C. Thus, A ∩ B ∩ C = {0}. ◂ 140 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices U U A B A B C C U U (a) A U B U C is shaded. (b) A B C is shaded. FIGURE 5 The union and intersection of A, B, and C. We can also consider unions and intersections of an arbitrary number of sets. We introduce these deﬁnitions. Deﬁnition 6 The union of a collection of sets is the set that contains those elements that are members of at least one set in the collection. We use the notation ⋃ n A1 ∪ A2 ∪ ⋯ ∪ An = Ai i=1 to denote the union of the sets A1 , A2 , … , An. Deﬁnition 7 The intersection of a collection of sets is the set that contains those elements that are members of all the sets in the collection. We use the notation ⋂ n A1 ∩ A2 ∩ ⋯ ∩ An = Ai i=1 to denote the intersection of the sets A1 , A2 , … , An. We illustrate generalized unions and inter- sections with Example 16. EXAMPLE 16 For i = 1, 2, …, let Ai = {i, i + 1, i + 2, … }. Then, Extra Examples ⋃ n ⋃ n Ai = {i, i + 1, i + 2, … } = {1, 2, 3, … }, i=1 i=1 and ⋂ n ⋂ n Ai = {i, i + 1, i + 2, … } = {n, n + 1, n + 2, … } = An. i=1 i=1 ◂ 2.2 Set Operations 141 We can extend the notation we have introduced for unions and intersections to other families of sets. In particular, to denote the union of the inﬁnite family of sets A1 , A2 , … , An , …, we use the notation ⋃ ∞ A 1 ∪ A2 ∪ ⋯ ∪ An ∪ ⋯ = Ai. i=1 Similarly, the intersection of these sets is denoted by ⋂ ∞ A1 ∩ A2 ∩ ⋯ ∩ An ∩ ⋯ = Ai. i=1 ⋂ ⋃ More generally, when I is a set, the notations i∈I Ai and i∈I Ai are used ⋂ to denote the intersection and union⋃ of the sets Ai for i ∈ I, respectively. Note that we have i∈I Ai = {x ∣ ∀i ∈ I (x ∈ Ai )} and i∈I Ai = {x ∣ ∃i ∈ I (x ∈ Ai )}. EXAMPLE 17 Suppose that Ai = {1, 2, 3, … , i} for i = 1, 2, 3, …. Then, ⋃ ∞ ⋃ ∞ Ai = {1, 2, 3, … , i} = {1, 2, 3, …} = Z+ i=1 i=1 and ⋂ ∞ ⋂ ∞ Ai = {1, 2, 3, … , i} = {1}. i=1 i=1 To see that the union of these sets is the set of positive integers, note that every positive integer n is in at least one of the sets, because it belongs to An = {1, 2, … , n}, and every element of the sets in the union is a positive integer. To see that the intersection of these sets is the set {1}, note that the only element that belongs to all the sets A1 , A2 , … is 1. To see this note that A1 = {1} and 1 ∈ Ai for i = 1, 2, …. ◂ 2.2.4 Computer Representation of Sets There are various ways to represent sets using a computer. One method is to store the elements of the set in an unordered fashion. However, if this is done, the operations of computing the union, intersection, or diﬀerence of two sets would be time consuming, because each of these operations would require a large amount of searching for elements. We will present a method for storing elements using an arbitrary ordering of the elements of the universal set. This method of representing sets makes computing combinations of sets easy. Assume that the universal set U is ﬁnite (and of reasonable size so that the number of elements of U is not larger than the memory size of the computer being used). First, specify an arbitrary ordering of the elements of U, for instance a1 , a2 , … , an. Represent a subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A and is 0 if ai does not belong to A. Example 18 illustrates this technique. EXAMPLE 18 Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in in- creasing order; that is, ai = i. What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the subset of integers not exceeding 5 in U? 142 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices Solution: The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, has a one bit in the ﬁrst, third, ﬁfth, seventh, and ninth positions, and a zero elsewhere. It is 10 1010 1010. (We have split this bit string of length ten into blocks of length four for easy reading.) Similarly, we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10}, by the string 01 0101 0101. The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is represented by the string 11 1110 0000. ◂ Using bit strings to represent sets, it is easy to ﬁnd complements of sets and unions, inter- sections, and diﬀerences of sets. To ﬁnd the bit string for the complement of a set from the bit string for that set, we simply change each 1 to a 0 and each 0 to 1, because x ∈ A if and only if x ∉ A. Note that this operation corresponds to taking the negation of each bit when we associate a bit with a truth value—with 1 representing true and 0 representing false. EXAMPLE 19 We have seen that the bit string for the set {1, 3, 5, 7, 9} (with universal set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) is 10 1010 1010. What is the bit string for the complement of this set? Solution: The bit string for the complement of this set is obtained by replacing 0s with 1s and vice versa. This yields the string 01 0101 0101, which corresponds to the set {2, 4, 6, 8, 10}. ◂ To obtain the bit string for the union and intersection of two sets we perform bitwise Boolean operations on the bit strings representing the two sets. The bit in the ith position of the bit string of the union is 1 if either of the bits in the ith position in the two strings is 1 (or both are 1), and is 0 when both bits are 0. Hence, the bit string for the union is the bitwise OR of the bit strings for the two sets. The bit in the ith position of the bit string of the intersection is 1 when the bits in the corresponding position in the two strings are both 1, and is 0 when either of the two bits is 0 (or both are). Hence, the bit string for the intersection is the bitwise AND of the bit strings for the two sets. EXAMPLE 20 The bit strings for the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9} are 11 1110 0000 and 10 1010 1010, respectively. Use bit strings to ﬁnd the union and intersection of these sets. Solution: The bit string for the union of these sets is 11 1110 0000 ∨ 10 1010 1010 = 11 1110 1010, which corresponds to the set {1, 2, 3, 4, 5, 7, 9}. The bit string for the intersection of these sets is 11 1110 0000 ∧ 10 1010 1010 = 10 1010 0000, which corresponds to the set {1, 3, 5}. ◂ 2.2 Set Operations 143 2.2.5 Multisets Sometimes the number of times that an element occurs in an unordered collection matters. A multiset (short for multiple-membership set) is an unordered collection of elements where an element can occur as a member more than once. We can use the same notation for a multiset as we do for a set, but each element is listed the number of times it occurs. (Recall that in a set, an element either belongs to a set or it does not. Listing it more than once does not aﬀect the membership of this element in the set.) So, the multiset denoted by {a, a, a, b, b} is the multiset that contains the element a thrice and the element b twice. When we use this notation, it must be clear that we are working with multisets and not ordinary sets. We can avoid this ambiguity by using an alternate notation for multisets. The notation {m1 ⋅ a1 , m2 ⋅ a2 , … , mr ⋅ ar } denotes the multiset with element a1 occurring m1 times, element a2 occurring m2 times, and so on. The numbers mi , i = 1, 2, … , r, are called the multiplicities of the elements ai , i = 1, 2, … , r. (Elements not in a multiset are assigned 0 as their multiplicity in this set.) The cardinality of a multiset is deﬁned to be the sum of the multiplicities of its elements. The word multiset was introduced by Nicolaas Govert de Bruijn in the 1970s, but the concept dates back to the 12th century work of the Indian mathematician Bhaskaracharya. Let P and Q be multisets. The union of the multisets P and Q is the multiset in which the multiplicity of an element is the maximum of its multiplicities in P and Q. The intersection of P and Q is the multiset in which the multiplicity of an element is the minimum of its multiplicities in P and Q. The diﬀerence of P and Q is the multiset in which the multiplicity of an element is the multiplicity of the element in P less its multiplicity in Q unless this diﬀerence is negative, in which case the multiplicity is 0. The sum of P and Q is the multiset in which the multiplic- ity of an element is the sum of multiplicities in P and Q. The union, intersection, and diﬀer- ence of P and Q are denoted by P ∪ Q, P ∩ Q, and P − Q, respectively (where these operations should not be confused with the analogous operations for sets). The sum of P and Q is denoted by P + Q. EXAMPLE 21 Suppose that P and Q are the multisets {4 ⋅ a, 1 ⋅ b, 3 ⋅ c} and {3 ⋅ a, 4 ⋅ b, 2 ⋅ d}, respectively. Find P ∪ Q, P ∩ Q, P − Q, and P + Q. Solution: We have P ∪ Q = {max(4, 3) ⋅ a, max(1, 4) ⋅ b, max(3, 0) ⋅ c, max(0, 2) ⋅ d} = {4 ⋅ a, 4 ⋅ b, 3 ⋅ c, 2 ⋅ d}, P ∩ Q = {min(4, 3) ⋅ a, min(1, 4) ⋅ b, min(3, 0) ⋅ c, min(0, 2) ⋅ d} = {3 ⋅ a, 1 ⋅ b, 0 ⋅ c, 0 ⋅ d} = {3 ⋅ a, 1 ⋅ b}, Links BHASKARACHARYA (1114–1185) Bhaskaracharya was born in Bijapur in the Indian state of Karnataka. (Bhaskaracharya’s name was actually Bhaskara, but the title Acharya, which means teacher, was added honorif- ically.) His father was a well-known scholar and a famous astrologer. Bhaskaracharya was head of the astronom- ical observatory at Ujjain, the leading Indian mathematical center of the day. He is considered to be the greatest mathematician of medieval India. Bhaskaracharya made discoveries in many parts of mathematics, including geometry, plane and spherical trigonometry, algebra, number theory, and combinatorics. Bhaskaracharya de- scribed the principles of diﬀerential calculus, which he applied to astronomical problems, predating the works of Newton and Leibniz by more than 500 years. In number theory he made many discoveries about Diophantine Dinodia c Photos/Alamy equations, the study of the solution in integers of equations, which were rediscovered more than 600 years later. Stock Photo His greatest work is the Crown of Treatises (Siddhanta Shiromani), which includes four main parts, covering arithmetic, algebra, mathematics of the planets, and spheres. 144 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices P − Q = {max(4 − 3, 0) ⋅ a, max(1 − 4, 0) ⋅ b, max(3 − 0, 0) ⋅ c, max(0 − 2, 0) ⋅ d} = {1 ⋅ a, 0 ⋅ b, 3 ⋅ c, 0 ⋅ d} = {1 ⋅ a, 3 ⋅ c}, and P + Q = {(4 + 3) ⋅ a, (1 + 4) ⋅ b, (3 + 0) ⋅ c, (0 + 2) ⋅ d} = {7 ⋅ a, 5 ⋅ b, 3 ⋅ c, 2 ⋅ d}. ◂ Exercises 1. Let A be the set of students who live within one mile of 13. Prove the second absorption law from Table 1 by show- school and let B be the set of students who walk to classes. ing that if A and B are sets, then A ∩ (A ∪ B) = A. Describe the students in each of these sets. 14. Find the sets A and B if A − B = {1, 5, 7, 8}, B − A = a) A ∩ B b) A ∪ B {2, 10}, and A ∩ B = {3, 6, 9}. c) A − B d) B − A 15. Prove the second De Morgan law in Table 1 by showing 2. Suppose that A is the set of sophomores at your school that if A and B are sets, then A ∪ B = A ∩ B and B is the set of students in discrete mathematics at a) by showing each side is a subset of the other side. your school. Express each of these sets in terms of A b) using a membership table. and B. 16. Let A and B be sets. Show that a) the set of sophomores taking discrete mathematics in your school a) (A ∩ B) ⊆ A. b) A ⊆ (A ∪ B). b) the set of sophomores at your school who are not tak- c) A − B ⊆ A. d) A ∩ (B − A) = ∅. ing discrete mathematics e) A ∪ (B − A) = A ∪ B. c) the set of students at your school who either are 17. Show that if A and B are sets in a universe U then A ⊆ B sophomores or are taking discrete mathematics if and only if A ∪ B = U. d) the set of students at your school who either are not 18. Given sets A and B in a universe U, draw the Venn dia- sophomores or are not taking discrete mathematics grams of each of these sets. 3. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find a) A → B = {x ∈ U | x ∈ A → x ∈ B} a) A ∪ B. b) A ∩ B. b) A ↔ B = {x ∈ U | x ∈ A ↔ x ∈ B} c) A − B. d) B − A. 19. Show th

Discrete Mathematics and its Applications Textbook PDF

Document Details

Tags

Related

Summary

Full Transcript