Introductory Discrete Mathematics V. K. Balakrishnan Pdf

Balakrishnan

Set Theory and Logic

0.1 INTRODUCTION TO SET THEORY

The concept of a set plays a very significant role in all branches of modern mathematics. In recent years set theory has become an important area of investigation because of the way in which it permeates so much of contemporary mathematical thought. A genuine understanding of any branch of modern mathematics requires a knowledge of the theory of sets for it is the common foundation of the diverse areas of mathematics. Sets are used to group distinct objects together. It is necessary that the objects which belong to a set are well-defined in the sense that there should be no ambiguity in deciding whether a particular object belongs to a set or not. Thus, given an object, either it belongs to a given set or it does not belong to it. For example, the first five letters of the English alphabet constitute a set which may be represented symbolically as the set {a, b, c, d, e}. An arbitrary object belongs to this set if and only if it is one of these five letters. These five distinct objects can appear in any order in this representation. In other words, this set can also be represented by {d, b, a, e, c}. The objects that belong to a set need not possess a common property. Thus the number 4, the letter x, and the word book can constitute a set S which may be represented as S = {x, book, 4}. A particular day may be cold for one person and not cold for another, so the collection of cold days in a month is not a clearly defined set. Similarly, the collection of large numbers and the collection of tall men are also not sets.

The term object has been used here without specifying exactly what an object is. From a mathematical point of view, set is a technical term that takes its meaning from the properties we assume that sets possess. This informal description of a set, based on the intuitive notion of an object, was first given by the German mathematician Georg Cantor (1845–1918) toward the end of the nineteenth century and the theory of sets based on his version is known as naive set theory. In Cantor's own words, a set is bringing together into a whole of definite well-defined objects of our perception and these objects are the elements of the set. The sets considered in this book can all be viewed in this framework of Cantor's theory.

Thus a set is a collection of distinct objects. The objects in a set are called the elements or members of the set. If x is an element of a set A, we say that x belongs to A, and this is expressed symbolically as x A denotes that y is not an element of the set A.

Finite and Infinite Sets

A set is finite if the number of elements in it is finite. Otherwise, it is an infinite set. The set of positive integers less than 100 is a finite set, whereas the set of all positive integers is an infinite set. If X is a finite set, the cardinality of X is the number of elements that belong to X, and this nonnegative integer is denoted by N(X). A set of cardinality 1 is called a singleton set.

If a set is finite and if its cardinality is not too large, we can describe it by enumerating all its elements. For example, the representation S = {a, e, i, o, u} describes the set of all vowels of the English alphabet. If the cardinality is too large, this enumerative method is not very convenient. In some cases, if there is no ambiguity we make this enumerative description more concise. For example, the set D of positive integers between 25 and 123 can be represented as D = {25, 26, 27, · · · , 121, 122, 123}. A better way of representing D is by stating the property for its membership. An object n is an element of this set D if and only if n is a positive integer that is at least 25 and at most 123. In other words, we write

D = {n : n is a positive integer, 24 < n < 124}

The infinite set N of all natural numbers can be represented unambiguously as N = {1, 2, 3, . . .} or as N = {n : n is a natural number} by stating its membership criterion. The notation of representing a set by stating the criteria of its membership as described above is called the set-builder notation.

Subsets of a Set and the Empty Set

A set P is a subset of a set Q if every element of P is an element of Q. We use the notation P ⊂ Q to denote that P is a subset of Q. A subset of a subset is no doubt a subset. When P is a subset of Q, we may say that Q contains P and that P is contained in Q. By our definition every set is a subset of itself. The set P is a proper subset of Q if (1) P is a subset of Q and (2) there is at least one element of Q that is not an element of P. The set of positive integers is a proper subset of the set of all real numbers.

If A is a subset of B, the relative complement of A in B is the set of elements in B that are not elements of A. The relative complement of A in B is denoted by B – A and it can be described by its membership criterion as

Two sets are disjoint if they have no elements in common. On the other hand, two sets are equal if they have the same elements. We write X = Y when the sets X and Y are equal. Obviously, two sets are equal if and only if each is a subset of the other. For instance, if X = {r : r is a root of the x² – 5x + 6 = 0} and Y = {2, 3}, then X = Y.

A set is empty if it has no elements. A fact emerges that some people find surprising: there is only one empty set. (Suppose that E and F are two empty sets. If they are not the same, they are not equal. So one of them should have at least one element that does not belong to the other. So one of the two sets is not empty. This contradicts the assumption that both E and F are empty.) The unique empty set (or null set) is denoted by ϕ. The fact that the empty set is a subset of any set is established by vacuous reasoning: If it were not a subset of a given set S, there should be at least one element in the empty set that is not in S. In particular, there should be at least one element in the empty set that is a contradiction. Of course, a set is empty if and only if its cardinality is zero.

In some cases we will be considering sets that are all subsets of a set U which is called the universal set. For example, if the sets under consideration are A, B, and C, where A = {3, 8, 6, 7, x}, B = {8, 4, y, t, 5}, and C = {3, 4, x, t, 9}, then any set containing the set D = {3, 8, 6, 7, x, 4, y, t, 5, 9} can be considered as a universal set as far as A, B, C, and D are concerned. Once the universal set U is fixed, the relative complement of a subset A in U is called the absolute complement of A and is denoted by Ac. Thus if the universe is the set of all nonnegative integers and E is the set of all even numbers, then Ec is the set of all odd numbers. Observe that the absolute complement of the absolute complement of any set A is the set A itself.

The Power Set of a Set

A set can have other sets as its elements. For instance, the set S consisting of the letter x, the set {a, b} and the number 4 is represented as S = {x, {a, b}, 4}. A set of subsets is also known as a class or family of sets. The class of all subsets of a given set X is called the power set of X and is denoted by P(X). For example, if X = {1, 2}, the elements of P(X) are the empty set, the singleton set {1}, the singleton set {2}, and the set X. Thus P(X) = {ϕ, {1}, {2}, {1, 2}}.

Cartesian Products of Sets

The ordered n-tuple (a1, a2, a3, . . . , an) is a collection of the n objects a1, a2, . . . , an in which a1 is the first element, a2 is the second element, . . . , and an is the nth element. In an ordered n-tuple, the elements need not be distinct. A set with n elements is thus an unordered n-tuple of n distinct elements, since in a set the order in which the elements are considered is irrelevant. An ordered 2-tuple is called an ordered pair. Two ordered n-tuples (a1, a2, . . . , an) and (b1, b2, . . . , bn) are said to be equal if ai = bi for i = 1, 2, . . . , n. The set of all ordered pairs (a, b), where a is an element of a set A and b is an element of a set B, is called the cartesian product of A and B and is denoted by A × B. In other words,

A × B = {(a, b) : a A and b B}

For example, if A = {1, 2} and B = {1, 3}, then the cartesian product A × B is the set {(1, 1), (1, 3), (2, 1), (2, 3)}. More generally, the cartesian product of the sets A1, A2, . . . , An denoted by A1 × A2 × · · · × An is the set of all ordered n-tuples of the form (a1, a2, . . . , an), where ai is any element of Ai (i = 1, 2, . . . , n).

Intersections and Unions of Sets

There are two important constructions that can be applied to subsets of a set to yield new subsets. Suppose that A and B are two subsets of a set X. The set consisting of all elements common to both A and B is called the intersection of A and B and is denoted by A ∩ B. Obviously, the intersection of a set and the empty set is the empty set and the intersection of any set A and A is A. Also, the intersection of a set and its absolute complement is empty since no element can be simultaneously in A and not in A. Moreover, it follows from the definition that set intersection has the commutative property: The intersection of A and B is equal to the intersection of B and A.

The set consisting of all elements that belong to either A or to B or to both A and B is called the union of A and B and is denoted by A ∪ B. The union of a set A and the empty set is the set A and the union of A and A is also A. Set union also is commutative: A ∪ B = B ∪ A. More generally, the intersection of a class of sets is the set of elements (if any) that belong to every set of the class. The union of a class of sets is the set of those elements that belong to at least one set in the class. It is an immediate consequence of the definition that both set intersection and set union possess the associative property: (1) A ∩ (B ∩ C) = (A ∩ B) ∩ C and (2) A ∪ (B ∪ C) = (A ∪ B) ∪ C. So the former can be written as A ∩ B ∩ C and the latter as A ∪ B ∪ C unambiguously.

Two sets are disjoint if and only if their intersection is empty. A class of sets is pairwise disjoint if the intersection of any two sets in the class is empty. A class C(X) of subsets of a set X is called a partition of X if (1) C(X) is pairwise disjoint, and (2) the union of the sets in C(X) is the set X. For instance, the class {{2, 4}, (1, 3, 5}, {6}} is a partition of the set {1, 2, 3, 4, 5, 6}.

Venn Diagrams of Sets

A very useful and simple device to represent sets graphically for illustrating relationship between them is the Venn diagram, named after the English logician John Venn (1834–1923). In a Venn diagram, the universal set U that contains all the objects under consideration is usually represented by a rectangle, and inside this rectangle subsets of the universal set are represented by circles, rectangles, or some other geometrical figures. In the Venn diagram shown in Figure 0.1.1, we have three sets A, B, and C which are subsets of the universal set U. The drawing of the ellipse that represents the set A inside the ellipse that represents the set B indicates that A is a subset of B. The fact that A and C are disjoint is made clear by representing them by two nonintersecting ellipses. The fact that the intersection of B and C is nonempty is made obvious by showing that the two ellipses which represent these two sets overlap each other. The region in the rectangle (which represents the universal set) that is outside the ellipses that represent the three sets is the absolute complement of the union of these three sets.

FIGURE 0.1.1

Distributive Laws and De Morgan's Laws

We conclude this section on sets with the following two theorems related to set operations involving intersections, unions, and taking absolute complements. These theorems can easily be established by drawing Venn diagrams. However, it is instructive to prove them without the aid of Venn diagrams, for in many cases it may not be possible to represent the sets under consideration by such diagrams, as we will see later in the book.

THEOREM 0.1.1 (Distributive Laws)

(a) A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ).

(b) A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ).

Proof:

(a) One way of showing that two sets are equal is by establishing that each is contained in the other. Let t be an element of A ∩ (B ∪ C). Then t is an element of A and t is either an element of B or an element of C. In either case, t is an element of A ∩ B or A ∩ C. In other words, A ∩ (B ∪ C) is a subset of (A ∩ B) ∪ (A ∩ C). Next, suppose that t is an element of (A ∩ B) ∪ (A ∩ C). This implies that t is either in A ∩ B or in A ∩ C. So t is necessarily in A and it is in at least one of the two sets B or C. Thus t is in A and also in either B or in C. In other words, t belongs to the intersection of A and to B ∪ C. Thus (A ∩ B) ∪ (A ∩ C) is a subset of A ∩ (B ∪ C).

THEOREM 0.1.2 (De Morgan's Laws)

(a) ( A ∩ B ) c = A c ∪ B c .

(b) ( A ∪ B ) c = A c ∩ B c .

Proof:

(a) Let t be an element of (A ∪ B)c. Then t belongs to neither A nor B. So t is necessarily in both Ac and Bc. Thus (A ∪ B)c is a subset of the intersection of Ac and Bc. On the other hand, if t is in the intersection of Ac and Bc, it is neither in A nor in B. This implies that t is not in the union of A and B. Hence the intersection of Ac and Bc is contained in the complement of A ∪ B.

0.2 FUNCTIONS AND RELATIONS

In this section a brief review of the basic ideas involving functions and relations is presented. The concept of a function is pivotal in mathematics.

The Domain and the Range of a Function

Let X and Y be two nonempty sets. A function f from X into Y, denoted by f: X → Y, is a rule that assigns to every element in X a unique element in Y. The set X is the domain of the function and the set Y is its codomain. If y is the unique element in Y assigned by the function f to the element x, we say that y is the image of x and x is a preimage of y and we write y = f(x). The set f(A) of all images of the elements of a subset A of X is called the image of the set A. The set f(X) is called the range of the function. The range of a function is a subset of its codomain. If y is an element in the range of f, the set of all the preimages of y is denoted by f–1 (y). If A is a subset of the range f(X), the inverse image of the set A is the set {x : x is in X and f(x) is in A}, which is denoted by f–1(A). If f is a function from X to Y, it is customary to say that f maps the set X into Y.

Example 0.2.1

Let R be the set of all real numbers.

(a) Let f: R → R be the function that assigns the real number x + 1 to each real number x. In other words, f(x) = x + 1. Here the domain, codomain, and range of f is R.

(b) Let f: R → R be the function defined by f(x) = x². So every real number is assigned to its square. Here the domain and codomain of f are R and its range is the set of all nonnegative numbers.

Example 0.2.2

Let A = {a, b, c} and B = {1, 2, 3, 4}. Then the rule f defined by f(a) = 1, f(b) = 1, f(c) = 4, and f(d) = 2 is a function f from A to B. The range of f is {1, 2, 4}, which is a proper subset of its codomain B.

Surjections, Injections, and Bijections

A function f: X → Y is called a surjection if f(X) = Y and we say that f is function from X onto Y. A function f: X → Y is called an injection (or a one-to-one mapping) if two different elements in X have two different images in Y. A function f: X → Y is a bijection if it is both a surjection and an injection. The bijection from a set X onto itself that maps every element in the set into itself is called the identity mapping ix on X. Two sets are equivalent if there is a bijection from one to the other. It is evident that two finite sets are equivalent if and only if they both have the same cardinality.

Example 0.2.3

(a) Let X = {a, b, c}, Y = {p, q}, and f: X → Y, where f(a) = p, f(b) = q, and f(c) = p. Then f is a surjection and f maps X onto Y. Here f is not an injection.

(b) If X = {a, b, c}, Y = {p, q, r, s} and if g(a) = p, g(b) = q, g(c) = r, then g is an injection but not a surjection. The range g(X) = {p, q, r} is a proper subset of the codomain Y.

(d) If R is the set of real numbers and f: R → R the function defined by f(x) = x², then f is neither a surjection, because no negative number has a preimage, nor an injection, because the image of x and the image of –x are both equal.

The Inverse of a Function

Let f: X → Y be a bijection. The inverse function of f is the bijection f–1: Y → X defined as follows: For each y in Y, we find that unique element x in X such that f(x) = y. Then we define x = f–1(y). A function f: X → Y is said to be invertible whenever its inverse exists.

Example 0.2.4

If X = {1, 2}, Y = {p, q}, f(1) = p, and f(2) = q, then f is a bijection from X onto Y and its inverse f–1 is the bijection from Y onto X that maps p into 1 and q into 2.

A function f whose domain X and codomain Y are subsets of the set R of real numbers is strictly increasing if f(x) < f(y) whenever x < y and strictly decreasing if f(x) > f(y) whenever x < y. It follows from the definition that both strictly increasing functions and strictly decreasing functions are injections.

Compositions of Functions

Let g : X → Y and f: Y → Z. The composition of f and g, defined by f ○ g, is a function from X to Z defined by (f ○ g)(x) = f(g(x)). In other words, the function f ○ g assigns to an element x in X that unique element assigned by f to g(x).

Example 0.2.5

(a) Let X = {a, b, c}, Y = {p, q, r, s}, and Z = {1, 2, 3}. Let g(a) = p, g(b) = q, and g(c) = r, so that g(X) = {p, q, r}. Then if f: g(X) → Z is defined by f(p) = 1, f(q) = 2, and f(r) = 3, we have

(b) Let f and g be functions from the set of integers to the set of integers. If f(x) = 4x + 3 and g(x) = 2x + 5, then

(f ○ g)(x) = f(g(x)) = f(2x + 5) = 4(2x + 5) + 3 = 8x + 23

(g ○ f)(x) = g(f(x)) = g(4x + 3) = 2(4x + 3) + 5 = 8x + 11

If f is a bijection from X onto Y, its inverse is a bijection from Y to X. If y = f(x), then f–1(y) = x. Thus f–1(f(x) = f–1(y) = x and f(f–1(y)) = f(x) = y. In other words, the composition of a bijection from X onto Y and its inverse is the identity mapping from Y onto itself.

Sequences, Strings, and Languages

A sequence is a function whose domain is a set of consecutive integers. If the domain X is a finite set of n integers, we may take X = {1, 2, 3, . . . , n} or {0, 1, 2, . . . , n – 1}. Otherwise, we may take X as the set of natural numbers or as the set of nonnegative integers. If f: X → Y is a sequence, the image f(i) of the integer i is sometimes written as fi and is called the i th term of the sequence.

Notice that in representing a sequence s, the order in which the images under s appear is important. This is not so in the case of a function. For example, if f is the function from X = {1, 2, 3} to Y = {p, q}, where f(1) = f(2) = p and f(3) = q, the collection of the images of the three elements of X under f can be represented as p, p, q in any order. But the sequence f is represented as (f(1)f(2)f(3)) or as (ppq). A sequence whose domain is finite consisting of n consecutive integers and whose codomain is Y defines a string of length n in Y or word of length n in Y. In fact, any such sequence is an n-tuple.

Example 0.2.6

(a) Let X = {1, 2, 3, . . .} and R the set of real numbers. Consider the sequence f: X → R defined by f(n) = 1/n. Then the nth term of the sequence denoted by fn is the image f(n) of the element n in X. This sequence is also denoted by {1/n : n = 1, 2, 3, . . .}.

(b) Let X = {1, 2, 3, 4, 5} and Y = {a, b, c, d} and consider the sequence f: X → Y defined by f(1) = a, f(2) = b, f(3) = a, f(4) = c, and f(5) = b. Then this sequence is the string abacb of length 5 in Y which is also the 5-tuple (abacb).

Any mapping f from A × A into A is called a binary operator on A. For instance, if R is the set of real numbers, the mapping f: R × R → R defined by f(a, b) = a + b (which is, in fact, the addition operator) is an example of a binary operator on R.

If S is any nonempty set, we denote by Sn the set of all strings of length n in S and S* the set of all strings (including the null string with no elements). Any subset of S* is called a language over the alphabet S. The union and intersection of two languages over an alphabet are also languages over the same alphabet. If u = (u1u2u3 · · · um) and v = (v1v2 · · · vn) are two strings of lengths m and n, respectively in S* then the concatenation of u and v is the string uv in S* of length m + n defined as uv = (u1u2u3 · · · umv1v2 · · · vn). The mapping c: S* × S* → S* defined by c(u, v) = uv where uv is the concatenation of u and v is a binary operator on S*.

Relations

We conclude this section with a brief comment on the concept of a relation, which is more general than that of a function. If A and B are two sets, any subset of A × B is called a relation from A to B. For example, if A = {a, b, c} and B = {1, 2, 3, 4}, then R = {(a, 2), (a, 3), (b, 4), (c, 3)} is a relation from A to B. By definition, in each ordered pair in a relation from A to B, the first element is an element in A and the second element is an element in B. A function from A to B therefore defines a special kind of relation R from A to B such that whenever (a, b) and (a, b′) are in the relation R, then b = b′. In other words, f: A → B defines the cartesian product {(x, f(x)) : x is in A}, which is a subset of A × B.

A relation R from a finite set A with m