Sets, Relations, and Languages PDF

1 Sets, Relations, and La nguages 1.1 SETS They say that mathematics is the language of science - it is certainly the lan- guage of the theory of computation, the scientific discipline we shall be studying in this book. And the language of mathematics deals with sets, and the com- plex...

1 Sets, Relations, and La nguages 1.1 SETS They say that mathematics is the language of science - it is certainly the lan- guage of the theory of computation, the scientific discipline we shall be studying in this book. And the language of mathematics deals with sets, and the com- plex ways in which they overlap, intersect, and in fact take part themselves in forming new sets. A set is a collection of objects. For example, the collection of the four letters a, b, c, and d is a set, which we may name L; we write L = {a, b, c, d}. The objects comprising a set are called its elements or members. For example, b is an element of the set L; in symbols, bEL. Sometimes we simply say that b is in L, or that L contains b. On the other hand, z is not an element of L, and we write z ~ L. In a set we do not distinguish repetitions of the elements. Thus the set {red, blue, red} is the same set as {red, blue}. Similarly, the order of the elements is immaterial; for example, {3, 1, 9}, {9, 3,1}, and {I, 3, 9} are the same set. To summarize: Two sets are equal (that is, the same) if and only if they have the same elements. The elements of a set need not be related in any way (other than happening to be all members of the same set); for example, {3, red, {d, blue}} is a set with three clements, one of which is itself a set. A set may have only one element; it is then called a singleton. For example, {I} is the set with 1 as its only element; thus {1} and 1 are quite different. There is also a set with no element at all. Naturally, there can be only one such set: it is called the empty set, and is denoted by 0. Any set other than the empty set is said to be nonempty. So far we have specified sets by simply listing all their elements, separated by commas and included in braces. Some sets cannot be written in this way, 5 6 Chapter 1: SETS. RELATIONS. AND LANGUAGES because they are infinite. For example, the set N of natural numbers is infinite; we may suggest its elements by writing N = {D, 1, 2,... }, using the three dots and your intuition in place of an infinitely long list. A set that is not infinite is finite. Another way to specify a set is by referring to other sets and to properties that elements mayor may not have. Thus if I = {l, 3, 9} and G = {3,9}, G may be described as the set of elements of I that are greater than 2. We write this fact as follows. G = {x : x E I and x is greater than 2}. In general, if a set A has been defined and P is a property that elements of A mayor may not have, then we can define a new set B = {x: x E A and x has property Pl. As another example, the set of odd natural numbers is 0= {x : x E N and x is not divisible by 2}. A set A is a subset of a set B --in symbols, A ~ B- if each element of A is also an element of B. Thus 0 ~ N, since each odd natural number is a natural number. Note that any set is a subset of itself. If A is a subset of B but A is not the same as B, we say that A is a proper subset of B and write A C B. Also note that the empty set is a subset of every set. For if B is any set, then 0 ~ B, since each element of 0 (of which there are none) is also an element of B. To prove that two sets A and B are equal, we may prove that A ~ Band B ~ A. Every element of A must then be an element of B and vice versa, so that A and B have the same elements and A = B. Two sets can be combined to form a third by various set operations, just as numbers are eombined by arithmetic operations such as addition. One set operation is union: the union of two sets is that set having as elements the objects that are elements of at least one of the two given sets, and possibly of both. We use the symbol U to denote union, so that A U B = {x : x E A or x E B}. For example, {l, 3, 9} u {3, 5, 7} = {I, 3, 5, 7, 9}. The intersection of two sets is the eollection of all elements the two sets have in common; that is, An B = {x : x E A and x E B}. 1.1: Sets 7 For example, {I, 3, 9} n {3, 5, 7} = {3}, and {1,3,9} n {a,b,c,d} = 0. Finally, the difference of two sets A and B, denoted by A - B, is the set of all elements of A that are not elements of B. A - B = {x: x E A and x ~ B}. For example, {I, 3, 9} - {3, 5, 7} = {I, 9}. Certain properties of the set operations follow easily from their definitions. For example, if A, B, and C are sets, the following laws hold. Idempotency AUA=A AnA=A Commutativity AUB=BUA AnB=BnA Associativity (A U B) U C = AU (B U C) (A n B) n C = An (B n C) Distributivity (A U B) n C = (A n C) U (B n C) (A n B) U C = (A U C) n (B U C) Absorption (A U B) nA = A (AnB) UA = A DeMorgan's laws A - (B U C) = (A - B) n (A - C) A - (B n C) = (A - B) U (A - C) Example 1.1.1: Let us prove the first of De Morgan's laws. Let L = A - (B U C) and R = (A - B) n (A - C); we are to show that L = R. We do this by showing (a) L ~ R and (b) R ~ L. (a) Let x be any element of L; then x E A, but x ~ B and x ~ C. Hence x is an element of both A - B and A - C, and is thus an element of R. Therefore L ~ R. ( b) Let x E R; then x is an element of both A - B and A - C, and is therefore in A but in neither B nor C. Hence x E A but x ~ B U C, so x E L.  8 Chapter 1: SETS, RELATIONS, AND LANGUAGES Therefore R ~ L, and we have established that L = R.O Two sets are disjoint if they have no element in common, that is, if their intersection is empty. It is possible to form intersections and unions of more than two sets. If S is any collection of sets, we write U S for the set whose elements are the elements of all the sets in S. For example, if S = {{a, b}, {b, c}, {c, d}} then US = {a, b, c, d}; and if S = {{ n} : n EN}, that is, the collection of all the singleton sets with natural numbers as elements, then US = N. In general, u S = {x : x E P for some set PES}. Similarly, n S = {x : x E P for each set PES}. The collection of all subsets of a set A is itself a set, called the power set of A and denoted 2A. For example, the subsets of {c, d} are {c, d} itself, the singletons {c} and {d} and the empty set 0, so 2{c,d} = {{c,d},{c},{d},0}. A partition of a non empty set A is a subset II of 2A such that 0 is not an element of II and such that each element of A is in one and only one set in II. That is, II is a partition of A if II is a set of subsets of A such that (1) each element of II is nonempty; (2) distinct members of II are disjoint; (3) UII = A. For example, {{a, b}, {c}, {d}} is a partition of {a, b, c, d}, but {{b, c}, {c, d} } is not. The sets of even and odd natural numbers form a partition of N. Problems for Section 1.1 1.1.1. Determine whether each of the following is true or false. (a) 0~ 0 (b) 0 E 0 (c) 0 E {0} (d) 0 ~ {0} (e) {a,b} E {a,b,c,{a,b}} (f) {a, b} ~ {a, b, {a, b}} (g) {a,b} ~ 2{a,b,{a,b}} (h) {{a, b}} E 2{a,b,{a,b}} (i) {a,b,{a,b}}-{a,b}={a,b}  1.2: Relations and Functions 9 1.1.2. '\'hat are these sets? Write them using braces, commas, and numerals only. (a) ({1,3,5}U{3,1})n{3,5,7} (b) U{ {3}, {3, 5}, n{ {5, 7}, {7, 9}}} (c) ({1,2,5} - {5, 7,9})U ({5, 7,9} - {l,2,5}) (d) 2{7,8,9} _ 2{7,9} (e) 20 1.1.3. Prove each of the following. (a) AU(BnC)=(AUB)n(AUC) (b) An (B U C) = (A n B) U (A n C) (c) A n (A U B) = A (d) AU(AnB)=A (e) A - (B n C) = (A - B) U (A - C) 1.1.4. Let S = {a, b, c, d}. (a) What partition of S has the fewest members? The most members? (b) List all partitions of S with exactly two members. liiJ RELATIONS AND FUNCTIONS Mathematics deals with statements about objects and the relations between them. It is natural to say, for example, that "less than" is a relation between objects of a certain kind -namely, numbers- which holds between 4 and 7 but does not hold between 4 and 2, or between 4 and itself. But how can we express relations between objects in the only mathematical language we have available at this point -that is to say, the language of sets? We simply think of a relation as being itself a set. The objects that belong to the relation are, in essence, the combinations of individuals for which that relation holds in the intuitive sense. So the less-than relation is the set of all pairs of numbers such that the first number is less than the second. But we have moved a bit quickly. In a pair that belongs to a relation, we need to be able to distinguish the two parts of the pair, and we have not explained how to do so. We cannot write these pairs as sets, since {4, 7} is the same thing as {7, 4}. It is easiest to introduce a new device for grouping objects called an ordered pair. t We write the ordered pair of two objects a and b as (a, b); a and b are called the components of the ordered pair (a, b). The ordered pair (a, b) is not the same as the set {a,b}. First, the order matters: (a,b) is different from (b,a), t True fundamentalists would see the ordered pair (a, b) not as a new kind of object, but as identical to {a, {a,b}}. 10 Chapter 1: SETS, RELATIONS, AND LANGUAGES whereas {a, b} = {b, a}. Second, the two components of an ordered pair need not be distinct; (7,7) is a valid ordered pair. Note that two ordered pairs (a, b) and (c, d) are equal only when a = c and b = d. The Cartesian product of two sets A and B, denoted by A x B, is the set of all ordered pairs (a, b) with a E A and b E B. For example, { 1, 3, 9} x {b, c, d} = {( 1, b), (1, c), (1, d), (3, b), (3 , c), (3, d), (9, b), (9 , c), (9, d)}. A binary relation on two sets A and B is a subset of Ax B. For example, {(1,b),(1,c),(3,d),(9,d)} is a binary relation on {1,3,9} and {b,c,d}. And {(i,j) : i,j EN and i < j} is the less-than relation; it is a subset of N x N ---often the two sets related by a binary relation are identical. More generally, let n be any natural number. Then if aI,... , an are any n objects, not necessarily distinct, (al"'" an) is an ordered tuple; for each i = 1,... ,n, ai is the ith component of (al,... ,an ). An ordered m-tuple (bl,... ,b m ), where m is a natural number, is the same as (al,... ,an ) if and only ifm = nand ai = bi , for i = 1,... ,n. Thus (4,4), (4,4,4), ((4,4),4), and (4, (4,4)) are all distinct. Ordered 2-tuples are the same as the ordered pairs discussed above, and ordered 3-, 4-, 5-, and 6-tuples are called ordered triples, quadruples, quintuples, and sextuples, respectively. On the other hand, a sequence is an ordered n-tuple for some unspecified n (the length of the sequence). If AI,... , An are any sets, then the n-fold Cartesian product Al x '" x An is the set of all ordered n-tuples (al,... , an), with ai E Ai, for each i = 1,... , n. In case all the Ai, are the same set A, the n-fold Cartesian product A x... x A of A with itself is also written An. For example, N 2 is the set of ordered pairs of natural numbers. An n-ary relation on sets AI,... , An is a subset of Al x... x An; 1-, 2-, and 3-ary relations are called unary, binary, and ternary relations, respectively. Another fundamental mathematical idea is that of a function. On the intu- itive level, a function is an association of each object of one kind with a unique object of another kind: of persons with their ages, dogs with their owners, num- bers with their successors, and so on. But by using the idea of a binary relation as a set of ordered pairs, we can replace this intuitive idea by a concrete defini- tion. A function from a set A to a set B is a binary relation R on A and B with the following special property: for each element a E A, there is exactly one ordered pair in R with first component a. To illustrate the definition, let C be the set of cities in the United States and let 51 be the set of states; and let RI = {(x,y) : x E C,y E 51, and x is a city in state y}, R2 = {(x,y): x E S,y E C, and y is a city in state x}. 1.2: Relations and Functions 11 Then Rl is a function, since each city is in one and only one state, but R2 is not a function, since some states have more than one city.t In general, we use letters such as I, g, and h for functions and we write I : A I-t B to indicate that I is a function from A to B. We call A the domain of f. If a is any element of A we write I(a) for that element b of B such that (a, b) E I; since I is a function, there is exactly one b E B with this property, so I(a) denotes a unique object. The object I(a) is called the image of a under f. To specify a function I : A I-t B, it suffices to specify I (a) for each a E A; for example, to specify the function RI above, it suffices to specify, for each city, the state in which it is located. If I : A I-t B and AI is a subset of A, then we define J[A'l = {/(a) : a E A'} (that is, {b: b = I(a) for some a E A'}). We call J[A'l the image of AI under f. The range of I is the image of its domain. Ordinarily, if the domain of a function is a Cartesian product, one set of parentheses is dropped. For example, if I : N x N I-t N is defined so that the image under I of an ordered pair (m, n) is the sum of m and n, we would write I(m, n) = m+n rather than I((m, n)) = m+n, simply as a matter of notational convenience. If I: Al x A2 X... x An I-t B is a function, and I(al,... ,an) = b, where ai E Ai for i = 1,... , nand b E B, then we sometimes call al,··., an the arguments of I and b the corresponding value of I. Thus I may be specified by giving its value for each n-tuple of arguments. Certain kinds of functions are of special interest. A function I : A I-t B is one-to-one if for any two distinct elements a, a' E A, I(a) ::f:- I(a ' ). For example, if C is the set of cities in the United States, 5 is the set of states, and g : 5 I-t C is specified by g( s) = the capital of state s for each s E 5, then g is one-to-one since no two states have the same capital. A function I : A I-t B is onto B if each element of B is the image under I of some element of A. The function g just specified is not onto C, but the function RI defined above is onto 5 since each state contains at least one city. Finally a mapping I : A I-t B is a bijection between A and B if it is both one-to-one and onto B; for example, if Co is the set of capital cities, then the function g: 5 I-t Co specified, as before, by g( s) = the capital of state s is a bijection between 5 and Co. t We consider Cambridge, Massachusetts, and Cambridge, Maryland, not the same city, but different cities that happen to have the same name. 12 Chapter 1: SETS, RELATIONS, AND LANGUAGES The inverse of a binary relation R t:;;; A x B, denoted R- 1 t:;;; B x A, is simply the relation {(b, a) : (a, b) E R}. For example, the relation R2 defined above is the inverse of R 1 Thus, the inverse of a function need not be a function. In the case of Rl its inverse fails to be a function since some states have more than one city; that is, there are distinct cities Cl and C2 such that Rl (Cl) = Rl (C2). A function I : A f-t B may also fail to have an inverse if there is some element b E B such that I(a) ::f:- b for all a E A. If I: A f-t B is a bijection, however, neither of these eventualities can occur, and 1-1 is a function -indeed, a bijection between B and A. Moreover I-l(f(a)) = a for each a E A, and l(f-l(b)) = b for each bE B. When a particularly simple bijection between two sets has been specified, it is sometimes possible to view an object in the domain and its image in the range as virtually indistinguishable: the one may be seen as a renaming or a way of rewriting the other. For example, singleton sets and ordered I-tuples are, strictly speaking, different, but not much harm is done if we occasionally blur the distinction, because of the obvious bijection I such that I ({ a}) = (a) for any singleton {a}. Such a bijection is called a natural isomorphism; of course this is not a formal definition since what is "natural" and what distinctions can be blurred depend on the context. Some slightly more complex examples should make the point more clearly. Example 1.2.1: For any three sets A, B, and C, there is a natural isomorphism of Ax B x C to (A x B) x C, namely I(a,b,c) = ((a,b),c) for any a E A, bE B, and c E C.O Example 1.2.2: For any sets A and B, there is a natural isomorphism ¢ from that is, the set of all binary relations on A and B, to the set {I : I is a function from A to 2B}. Namely, for any relation R t:;;; A x B, let ¢(R) be that function I : A f-t 2B such that I(a) = {b: bE Band (a,b) E R}. For example, if S is the set of states and R t:;;; S x S contains any ordered pair of states with a common border, then the naturally associated function I : S f-t 25 is specified by I (s) = {s' : s' E Sand s' shares a border with s}. 0  1.3: Special Types of Binary Relations 13 Example 1.2.3: Sometimes we regard the inverse of a function I : A f--t B as a function even when I is not a bijection. The idea is to regard 1-1 t::;; B x A as a function from B to 2A, using the natural isomorphism described under Example 1.2.2. Thus 1-1 (b) is, for any b E B, the set of all a E A such that I(a) = b. For example, if Rl is as defined above -the function that assigns to each city the state in which it is located- then Rll (s), where s is a state, is the set of all cities in that state. If Q and R are binary relations, then their composition Q 0 R, or simply QR, is the relation {(a, b) : for some c, (a, c) E Q and (c, b) E R}. Note that the composition of two functions I : A f--t Band g : B f--t C is a function h from A to C such that h(a) = g(f(a)) for each a E A. For example, if I is the function that assigns to each dog its owner and g assigns to each person his or her age, then log assigns to each dog the age of its owner. Problems for Sectior 1.2 1.2.1. Write each of the following explicitly. (a) {I} x {1,2} x {1,2,3} (b) 0 x {1,2} (c) 2{1,2} x {I, 2} 1.2.2. Let R = {(a, b), (a, c), (c, d), (a, a), (b, a)}. What is R 0 R, the composition of R with itself? What is R- 1 , the inverse of R? Is R, R 0 R, or R- 1 a function? 1.2.3. Let I : A f--t Band g : B f--t C. Let h : A f--t C be their composition. In each of the following cases state necessary and sufficient conditions on I and g for h to be as specified. (a) Onto. (b) One-to-one. (c) A bijection. 1.2.4. If A and B are any sets, we write BA for the set of all functions from A to B. Describe a natural isomorphism between {O, l}A and 2A. liiJ SPECIAL TYPES OF BINARY RELATIONS Binary relations will be found over and over again in these pages; it will be helpful to have convenient ways of representing them and some terminology for discussing their properties. A completely "random" binary relation has no significant internal structure; but many relations we shall encounter arise out 14 Chapter 1: SETS, RELATIONS, AND LANGUAGES of specific contexts and therefore have important regularities. For example, the relation that holds between two cities if they belong to the same state has certain "symmetries" and other properties that are worth noting, discussing, and exploiting. In this section we study relattons that exhibit these and similar regularities. We shall deal only with binary relations on a set and itself. Thus, let A be a set, and R t::;: A x A be a relation bn A. The relation R can be represented by a directed graph. Each element of A is represented by a small circle-what we call a node of the directed graph~ and an arrow is drawn from a to b if and only if (a, b) E R. The arrows are the edges of the directed graph. For example, the relation R = {(a,b),(b,a), (a,d),(d,c),(c,c),(c,a)} is represented by the graph in Figure 1-1. Note in particular the loop from c to itself, corresponding to the pair (c, c) E R. From a node of a graph to another there is either no edge, or one edge ~we do not allow "parallel arrows." a b ~--~ d Figure 1-1 There is no formal distinction between binary relations on a set A and di- rected graphs with nodes from A. We use the term directed graph when we want to emphasize that the set on which the relation is defined is of no independent interest to us, outside the context of this particular relation. Directed graphs, as well as the undirected graphs soon to be introduced, are useful as models and abstractions of complex systems (traffic and communication networks, compu- tational structures and processes, etc.). In Section 1.6, and in much more detail in Chapters 6 and 7, we shall discuss many interesting computational problems arising in connection with directed graphs. For another example of a binary relation/directed graph, the less-than-or- equal-to relation::; defined on the natural numbers is illustrated in Figure 1-2. Of course, the entire directed graph cannot be drawn, since it would be infinite. A relation R t::;: A x A is reflexive if (a, a) E R for each a E A. The directed graph representing a reflexive relation has a loop from each node to itself. For example, the directed graph of Figure 1-2 represents a reflexive relation, but that of Figure 1-1 does not. A relation R t::;: A x A is symmetric if (b, a) E R whenever (a, b) E R. 1.3: Special Types of Binary Relations 15 Figure 1-2 In the corresponding directed graph, whenever there is an arrow between two nodes, there are arrows between those nodes in both directions. For exam- ple, the directed graph of Figure 1-3 represents a symmetric relation. This directed graph might depict the relation of "friendship" among six people, since whenever x is a friend of y, y is also a friend of x. The relation of friendship is not reflexive, since we do not regard a person as his or her own friend. Of course, a relation could be both symmetric and reflexive; for exam- ple, {(a, b) : a and b are persons with the same father} is such a relation. a f ~: Figure 1-3 A symmetric relation without pairs of the form (a, a) is represented as an undirected graph, or simply a graph. Graphs are drawn without arrowheads, combining pairs of arrows going back' and forth between the same nodes. For example, the relation shown in Figure 1-3 could also be represented by the graph in Figure 1-4. A relation R is antisymmetric if whenever (a, b) E R and a and bare distinct, then (b, a) ~ R. For example, let P be the set of all persons. Then {(a,b) : a,b E P and a is the father of b}  ao-r 16 Chapter 1: SETS, RELATIONS, AND LANGUAGES IC 10--1 Figure 1-4 d is antisymmetric. A relation may be neither symmetric nor antisymmetric; for example, the relation {( a, b) ; a, b E P and a is the brother of b} and the relation represelrted in Figure 1-1 are neither. A binary relation R is transitive if whenever (a, b) E Rand (b, c) E R, then (a, c) E R. The relation {(a, b) ; a, b E P and a is an ancestor of b} is transitive, since if a is an ancestor of band b is an ancestor of c, then a is an ancestor of c. So is the less-than-or-equal relation. In terms of the directed graph representation, transitivity is equivalent to the requirement that whenever there is a sequence of arrows leading from an element a to an element z, there is an arrow directly from a to z. For example, the relation illustrated in Figure 1-5 is transitive. aK77( b~C Figure 1-5 A relation that is reflexive, symmetric, and transitive is called an equiva- lence relation. The representation of an equivalence relation by an undirected graph consists of a number of clusters; within each cluster, each pair of nodes is connected by a line (see Figure 1-6). The "clusters" of an equivalence relation are called its equivalence classes. We normally write [aJ for the equivalence class containing an element a, provided the equivalence relation R is under- stood by the context. That is, [aJ = {b ; (a, b) E R}, or, since R is symmetric, [aJ = {b ; (b, a) E R}. For example, the equivalence relation in Figure 1-6 has three equivalence classes, one with four elements, one with three elements, and one with one element. 1.3: Special Types of Binary Relations 17 Q Figure 1-6 Theorem 1.3.1: Let R be an equivalence relation on a nonempty set A. Then the equivalence classes of R constitute a partition of A. Proof: Let II = {raj : a E A}. We must show that the sets in II are non empty, disjoint, and together exhaust A. All equivalence classes are nonempty, since a E [aJ for all a E A, by reflexivity. To show that they are disjoint, consider any two distinct equivalence classes [aJ and [bJ, and suppose that [aJ n [bJ f::. 0. Thus there is an element c such that c E [aJ and c E [bJ. Hence (a, c) E Rand (c, b) E R; since R is transitive, (a, b) E R; and since R is symmetric, (b, a) E R. But now take any element dE raj; then (d, a) E R and, by transitivity, (d, b) E R. Hence d E [b], so that [aJ