
	Trending ▼ ICSE CBSE 10th ISC CBSE 12th CTET GATE UGC NET Vestibulares ResFinder

Title

85 pages, 0 questions, 0 questions with responses, 0 total responses,

	nage19	+Fave Message
	Profile Timeline Uploads

Home > nage19 >

Formatting page ...

Discrete Mathematics, Chapters 2 and 9: Sets, Relations and Functions, Sequences, Sums, Cardinality of Sets Richard Mayr University of Edinburgh, UK Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 1 / 74 Outline 1 Sets 2 Relations 3 Functions 4 Sequences 5 Cardinality of Sets Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 2 / 74 Set Theory Basic building block for types of objects in discrete mathematics. Set operations in programming languages: Issues about data structures used to represent sets and the computational cost of set operations. Set theory is the foundation of mathematics. Many different systems of axioms have been proposed. Zermelo-Fraenkel set theory (ZF) is standard. Often extended by the axiom of choice to ZFC. Here we are not concerned with a formal set of axioms for set theory. Instead, we will use what is called naive set theory. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 3 / 74 Sets A set is an unordered collection of objects, e.g., students in this class; air molecules in this room. The objects in a set are called the elements, or members of the set. A set is said to contain its elements. The notation x S denotes that x is an element of the set S. If x is not a member of S, write x / S. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 4 / 74 Describing a Set: Roster Method S = {a, b, c, d}. Order not important S = {a, b, c, d} = {b, c, a, d}. Each distinct object is either a member or not; listing more than once does not change the set. S = {a, b, c, d} = {a, b, c, b, c, d}. Dots . . . may be used to describe a set without listing all of the members when the pattern is clear. S = {a, b, c, d, . . . , z} or S = {5, 6, 7, . . . , 20}. Do not overuse this. Patters are not always as clear as the writer thinks. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 5 / 74 Some Important Sets B = Boolean values = {true, false} N = natural numbers = {0, 1, 2, 3, . . . } Z = integers = {. . . , 3, 2, 1, 0, 1, 2, 3, . . . } Z+ = Z 1 = positive integers = {1, 2, 3, . . . } R = set of real numbers R+ = R>0 = set of positive real numbers C = set of complex numbers Q = set of rational numbers Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 6 / 74 Set Builder Notation Specify the property (or properties) that all members of the set must satisfy. S = {x | x is a positive integer less than 100} S = {x | x Z+ x < 100} S = {x Z+ | x < 100} A predicate can be used, e.g., S = {x | P(x)} where P(x) is true iff x is a prime number. Positive rational numbers Q+ = {x R | p, q Z+ x = p/q} Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 7 / 74 Interval Notation Used to describe subsets of sets upon which an order is defined, e.g., numbers. [a, b] = {x | a x b} [a, b) = {x | a x < b} (a, b] = {x | a < x b} (a, b) = {x | a < x < b} closed interval [a, b] open interval (a, b) half-open intervals [a, b) and (a, b] Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 8 / 74 Universal Set and Empty Set The universal set U is the set containing everything currently under consideration. I I Content depends on the context. Sometimes explicitly stated, sometimes implicit. The empty set is the set with no elements. Symbolized by or {}. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 9 / 74 Russell s Paradox (After Bertrand Russell (1872 1970); Logician, mathematician and philosopher. Nobel Prize in Literature 1950.) Naive set theory contains contradictions. Let S be the set of all sets which are not members of themselves. S = {S 0 | S 0 / S0} Is S a member of itself? , i.e., S S ? Related formulation: The barber shaves all people who do not shave themselves, but no one else. Who shaves the barber? Modern formulations (such as Zerlemo-Fraenkel) avoid such obvious problems by stricter axioms about set construction. However, it is impossible to prove in ZF that ZF is consistent (unless ZF is inconsistent). Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 10 / 74 Things to remember Sets can be elements of other sets, e.g., {{1, 2, 3}, a, {u}, {b, c}} The empty set is different from the set containing the empty set = 6 { } Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 11 / 74 Subsets and Set Equality Definition Set A is a subset of set B iff every element of A is also an element of B. Formally: A B x(x A x B) In particular, S and S S for every set S. Definition Two sets A and B are equal iff they have the same elements. Formally: A = B A B B A. E.g., {1, 5, 5, 5, 3, 3, 1} = {1, 3, 5} = {3, 5, 1}. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 12 / 74 Proper Subsets Definition A is a proper subset of B iff A B and A 6= B. This is denoted by A B. A B can be expressed by x(x A x B) x(x B x / A) Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 13 / 74 Set Cardinality Definition If there are exactly n distinct elements in a set S, where n is a nonnegative integer, we say that S is finite. Otherwise it is infinite. Definition The cardinality of a finite set S, denoted by |S|, is the number of (distinct) elements of S. Examples: | | = 0 Let S be the set of letters of the English alphabet. Then |S| = 26. |{1, 2, 3}| = 3 |{ }| = 1 The set of integers Z is infinite. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 14 / 74 Power Sets Definition The set of all subsets of a set S is called the power set of S. It is denoted by P(S) or 2S . Formally: P(S) = {S 0 | S 0 S} In particular, S P(S) and P(S). Example: P({a, b}) = { , {a}, {b}, {a, b}} If |S| = n then |P(S)| = 2n . Proof by induction on n; see later Chapters. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 15 / 74 Tuples The ordered n-tuple (a1 , a2 , . . . , an ) is the ordered collection of n elements, where a1 is the first, a2 the second, etc., and an the n-th (i.e., the last). Two n-tuples are equal iff their corresponding elements are equal. (a1 , a2 , . . . , an ) = (b1 , b2 , . . . , bn ) a1 = b1 a2 = b2 an = bn 2-tuples are called ordered pairs. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 16 / 74 Cartesian Product Definition The Cartesian product of two sets A and B, denoted by A B, is the set of all ordered pairs (a, b) where a A and b B. A B = {(a, b) | a A b B} Definition The Cartesian product of n sets A1 , A2 . . . , An , denoted by A1 A2 An , is the set of all tuples (a1 , a2 , . . . , an ) where ai Ai for i = 1, . . . , n. A1 A2 An = {(a1 , a2 , . . . , an ) | ai Ai for i = 1, 2, . . . , n} Example: What is A B C where A = {0, 1}, B = {1, 2} and C = {0, 1, 2}. Solution: 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, 1, 2)} Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 17 / 74 Truth Sets and Characteristic Predicates We fix a domain U. Let P(x) be a predicate on U. The truth set of P is the subset of U where P is true. {x U | P(x)} Let S U be a subset of U. The characteristic predicate of S is the predicate P that is true exactly on S, i.e., P(x) x S Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 18 / 74 Set Operations: Union, Intersection, Complement Given a domain U and two sets A, B. The union of two sets A, B is defined by A B = {x | x A x B}. General union of several sets: A1 An = {x | x A1 x An } The intersection of two sets A, B is defined by A B = {x | x A x B}. General intersection of several sets: A1 An = {x | x A1 x An } The complement of A w.r.t. U is defined by A = {x U | x / A} Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 19 / 74 Set Difference Definition The difference between sets A and B, denoted A B is the set containing the elements of A that are not in B. Formally: A B = {x | x A x / B} = A B A B is also called the complement of B w.r.t. A. Definition The symmetric difference between sets A and B, denoted A4B is the set containing the elements of A that are not in B or vice-versa. Formally: A4B = {x | x A xor x B} = (A B) (B A) A4B = (A B) (A B). Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 20 / 74 Cardinality of Finite Derived Sets |A B| = |A| + |B| |A B| In particular, |A B| |A| + |B|. |A B| |A| |A B| |B| |A B| |A| |A4B| = ? Clicker 1 |A| + |B| 2 |A| + |B| |A B| 3 |A| + |B| 2|A B| 4 |A| + |B| + |A B| 5 |A| + |B| + 2|A B| 6 |A| + |B| |A B| Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 21 / 74 Cardinality of Finite Derived Sets |A B| = |A| + |B| |A B| In particular, |A B| |A| + |B|. |A B| |A| |A B| |B| |A B| |A| |A4B| = ? Clicker 1 |A| + |B| 2 |A| + |B| |A B| 3 |A| + |B| 2|A B| 4 |A| + |B| + |A B| 5 |A| + |B| + 2|A B| 6 |A| + |B| |A B| |A| + |B| 2|A B| Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 21 / 74 Set Identities Identity laws A =A A U =A A U =U A = A A=A A A=A Domination laws Idempotent laws Complementation law (A) = A Complement laws A A= Richard Mayr (University of Edinburgh, UK) A A=U Discrete Mathematics. Chapters 2 and 9 22 / 74 Set Identities (cont.) Commutative laws A B =B A A B =B A Associative laws A (B C) = (A B) C A (B C) = (A B) C Distributive laws A (B C) = (A B) (A C) A (B C) = (A B) (A C) Absorption laws A (A B) = A A (A B) = A De Morgan s laws A B =A B Richard Mayr (University of Edinburgh, UK) A B =A B Discrete Mathematics. Chapters 2 and 9 23 / 74 Relations Definition Given sets A1 , . . . , An , a subset R A1 An is an n-ary relation. Example: Database R contains tuples (Street name, House number, currently inhabited flag), i.e., R Strings N B. So R is a 3-ary relation. Definition Given sets A and B, R A B is a binary relation from A to B. The property (x, y ) R is also written as xRy . Example: R R Z where (x, y ) R iff y = bxc (rounding down). Definition R A A is called a relation on A. Example: Z Z is the less or equal relation on the integers. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 24 / 74 Relations and Matrices A binary relation R A B can be described by a boolean matrix (and vice-versa). Define a boolean matrix M. Index its rows over set A and its columns of set B. Let M(a, b) = T iff (a, b) R. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 25 / 74 Properties of Binary Relations A binary relation R A A is called Reflexive iff x (x, x) R Symmetric iff x, y ((x, y ) R (y , x) R) Antisymmetric iff x, y ((x, y ) R (y , x) R x = y ) Transitive iff x, y , z ((x, y ) R (y , z) R (x, z) R). Examples: and = are reflexive, but < is not. = is symmetric, but is not. is antisymmetric. Note: = is also antisymmetric, i.e., = is symmetric and antisymmetric. < is also antisymmetric, since the precondition of the implication is always false. However, R = {(x, y ) | x + y 3} is not antisymmetric, since (1, 2), (2, 1) R. All three, =, and < are transitive. R = {(x, y ) | y = 2x} is not transitive. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 26 / 74 Binary Relations: Example Let R = {(x, y ) Z+ Z+ | k Z+ y = kx} Clicker: Is R 1 reflexive, symmetric, transitive 2 not reflexive, antisymmetric, not transitive 3 reflexive, not antisymmetric, transitive 4 reflexive, symmetric, not transitive 5 reflexive, antisymmetric, transitive 6 reflexive, not symmetric, not transitive Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 27 / 74 Combining Relations Since relations are sets, they can be combined with normal set operations, e.g., < = is equal to , and is equal to =. Moreover, relations can be composed. Definition Let R1 A B and R2 B C. Then R1 is composable with R2 . The composition is defined by R1 R2 = {(x, z) A C | y B ((x, y ) R1 (y , z) R2 )} Sometimes R1 R2 is simply written as R1 R2 . Example: If A, B, C = Z then > >= . However if A, B, C = R then > >= Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 28 / 74 Combining Relations Since relations are sets, they can be combined with normal set operations, e.g., < = is equal to , and is equal to =. Moreover, relations can be composed. Definition Let R1 A B and R2 B C. Then R1 is composable with R2 . The composition is defined by R1 R2 = {(x, z) A C | y B ((x, y ) R1 (y , z) R2 )} Sometimes R1 R2 is simply written as R1 R2 . Example: If A, B, C = Z then > > = {(x, y ) Z Z | x y + 2}. However if A, B, C = R then > >= Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 28 / 74 Combining Relations Since relations are sets, they can be combined with normal set operations, e.g., < = is equal to , and is equal to =. Moreover, relations can be composed. Definition Let R1 A B and R2 B C. Then R1 is composable with R2 . The composition is defined by R1 R2 = {(x, z) A C | y B ((x, y ) R1 (y , z) R2 )} Sometimes R1 R2 is simply written as R1 R2 . Example: If A, B, C = Z then > > = {(x, y ) Z Z | x y + 2}. However if A, B, C = R then > >= > Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 28 / 74 Powers of a Relation Definition Given a relation R A A on A, its powers are defined inductively by Base step: R 1 = R Induction step: R n+1 = R n R If R is a transitive relation, then its powers are contained in R itself. Moreover, the reverse implication also holds. Theorem A relation R on a set A is transitive iff R n R for all n = 1, 2, . . . . Proof by induction on n. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 29 / 74 Equivalence Relations Definition A relation R on a set A is called an equivalence relation iff it is reflexive, symmetric and transitive. Example: Let be the set of strings over alphabet . Let R be a relation on strings defined as follows. R = {(s, t) | |s| = |t|}. I.e., two strings are in relation iff they have the same length. Verify that R is an equivalence relation. Prove that it is reflexive, symmetric and transitive. Example: Let R = {(a, b) Z+ Z+ | a divides b}. This is not an equivalence relation. It is reflexive and transitive, but not symmetric. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 30 / 74 Congruence modulo m Let m > 1 be an integer. Show that the relation R = {(a, b) | a b( mod m)} is an equivalence on the set of integers. Proof: Recall that a b( mod m) iff m divides a b. Reflexivity: a a( mod m) since a a = 0 is divisible by m. Symmetry: Suppose (a, b) R. Then m divides a b. Thus there exists some integer k s.t. a b = km. Therefore b a = ( k )m. So m divides b a and thus b a( mod m), and finally (b, a) R. Transitivity: If (a, b) R and (b, c) R then a b( mod m) and b c( mod m). So m divides both a b and b c. Hence there exist integers k , l with a b = km and b c = lm. By adding these two equations we obtain a c = (a b) + (b c) = km + lm = (k + l)m. Therefore, a c( mod m) and (a, c) R. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 31 / 74 Equivalence Classes Definition Let R be an equivalence relation on a set A and a A an element of A. Let [a]R = {s | (a, s) R} be the equivalence class of a w.r.t. R, i.e., all elements of A that are R-equivalent to a. If b [a]R then b is called a representative of the equivalence class. Every member of the class can be a representative. Theorem Let R be an equivalence on A and a, b A. The following three statements are equivalent. 1 aRb 2 [a] = [b] 3 [a] [b] 6= . Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 32 / 74 Partitions of a Set Definition A partition of a set A is a collection of disjoint, nonempty subsets that have A as their union. In other words, the collection of subsets Ai A with i I (where I is an index set) forms a partition of A iff 1 Ai 6= for all i I. 2 Ai Aj = for i 6= j S i I Ai = A 3 Theorem If R is an equivalence on A, then the equivalence classes of R form a partition of A. Conversely, given a partition {Ai | i I} of A there exists an equivalence relation R that has exactly the sets Ai , i I, as its equivalence classes. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 33 / 74 Partial Orders Definition A relation R on a set A is called a partial order iff it is reflexive, antisymmetric and transitive. If R is a partial order, we call (A, R) a partially ordered set, or poset. Example: is a partial order, but < is not (since it is not reflexive). Example: Let a|b denote the fact that a divides b. Formally: k Z ak = b. Show that the relation | is a partial order, i.e., (Z+ , |) is a poset. Example: Set inclusion is partial order, i.e., (2A , ) is a poset. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 34 / 74 Comparability and Total Orders Definition Two elements a and b of a poset (S, R) are called comparable iff aRb or bRa holds. Otherwise they are called incomparable. Definition If (S, R) is a poset where every two elements are comparable, then S is called a totally ordered or linearly ordered set and the relation R is called a total order or linear order. A totally ordered set is also called a chain. Given a poset (S, R) and S 0 S a subset in which all elements are pairwise incomparable. Then S 0 is called an antichain. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 35 / 74 Extending Orders to Tuples/Vectors: Standard Let (S, 4) be a poset and S n = S S S (n times). The standard extension of the partial order to tuples in S n is defined by (x1 , . . . , xn ) 4 (y1 , . . . , yn ) i {1, . . . , n} xi 4 yi Exercise: Prove that this defines a partial order. Note: Even if (S, 4) is totally ordered, the extension to S n is not necessarily a total order. Consider (N, ). Then (2, 1) (1, 2) (2, 1). Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 36 / 74 Extending Orders to Tuples/Vectors: Lexicographic Let (S, 4) be a poset and S n = S S S (n times). The lexicographic order on tuples in S n is defined by (x1 , . . . , xn ) lex (y1 , . . . , yn ) i {1, . . . , n} k < i xk = yk xi yi Let (x1 , . . . , xn ) 4lex (y1 , . . . , yn ) iff (x1 , . . . , xn ) lex (y1 , . . . , yn ) or (x1 , . . . , xn ) = (y1 , . . . , yn ). Lemma If (S, 4) is totally ordered then (S n , 4lex ) is totally ordered. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 37 / 74 Functions as Relations Definition Let A, B be nonempty sets. A relation f A B is called a partial function from A to B iff it satisfies the function condition (a, b) f (a, c) f b = c I.e., f assigns every element a A at most one element in B. Partial functions from A to B are denoted as f : A B, and we write f (a) = b instead of (a, b) f . Functions are also called mappings or transformations. Definition A partial function f : A B is called a total function iff every element in A is assigned an element in B, i.e., a A b B (a, b) f . Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 38 / 74 Terminology about Functions Let f : A B be a function from A to B. We say that f maps A to B. A is called the domain of f . B is called the codomain of f . If f (a) = b then b is the image of a under f and a is the preimage of b. f (A) := {b B | a A f (a) = b} is called the range of f . (Note the difference between the range and the codomain.) Two functions f : A B and g : A0 B 0 are equal iff A = A0 , B = B 0 and a A f (a) = g(a). Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 39 / 74 Representing Functions Functions can be specified in different ways: Explicit statement of assignments, e.g., f (2) = 4, f (3) = 1, f (4) = 17. A formula, e.g., f (x) = 5x 2 3x + 12. An algorithm/program, e.g., If x is odd and x > 17 then f (x) = 5 else if x is even then f (x) = x/2, otherwise f (x) = 3x. General conditions on a function that have just one unique solution. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 40 / 74 Injections, Surjections, Bijections Definition A function f : A B is injective ( one-to-one ) iff f (a) = f (b) a = b. Then f is called an injection. Definition A function f : A B is surjective ( onto ) iff b B a A f (a) = b. Then f is called a surjection. A function f : A B is surjective iff f (A) = B, i.e., the range is equal to the codomain. Definition A function f : A B is bijective iff it is injective and surjective. Then f is called a bijection or one-to-one correspondence. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 41 / 74 Reasoning about Injections, Surjections Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 42 / 74 Inverse Function Definition If f : A B is a bijection then the inverse of f , denoted by f 1 is defined as the function f 1 : B A s.t. f 1 (b) = a iff f (a) = b. If f is not a bijection then the inverse does not exist. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 43 / 74 Examples Does the inverse of the following functions exist? Why (not)? f : R R, f (x) = x + 1 f : R R, f (x) = x 2 f : N N, f (x) = 2x f : R R, f (x) = 2x Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 44 / 74 Function Composition Definition Let f : B C and g : A B. The composition function f g is defined by f g : A C with f g(a) = f (g(a)). (The common notation differs between functions and relations. For functions f g normally means first apply g, then apply f . For relations it is vice-versa: R1 R2 means first R1 , then R2 ; see above.) Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 45 / 74 Floor and Ceiling Functions Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 46 / 74 Proving Properties of Functions Example: Prove that if x is a real number, then b2xc = bxc + bx + 1/2c. Solution: Let x = n + , where n is an integer and 0 < 1. Case 1: < 1/2. 2x = 2n + 2 and b2xc = 2n, since 0 2 < 1. bx + 1/2c = n, since x + 1/2 = n + (1/2 + ) and 0 1/2 + < 1. Hence, b2xc = 2n and bxc + bx + 1/2c = n + n = 2n. Case 2: 1/2 2x = 2n + 2 = (2n + 1) + (2 1) and b2xc = 2n + 1, since 0 2 1 < 1. bx + 1/2c = bn + (1/2 + )c = bn + 1 + ( 1/2)c = n + 1 since 0 1/2 < 1. Hence, b2xc = 2n + 1 and bxc + bx + 1/2c = n + (n + 1) = 2n + 1. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 47 / 74 Factorial Function Definition The factorial function f : N N, denoted as f (n) = n! assigns to n the product of the first n positive integers. f (0) = 0! = 1 and f (n) = n! = 1 2 (n 1) n Can be approximated by Stirling s formula: n n g(n) = 2 n e We have approximately n! g(n) in the sense that limn n!/g(n) = 1 and 2 nn+1/2 e n n! e nn+1/2 e n Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 48 / 74 Closure Definition A closure operator on a set S is a function C : 2S 2S that satisfies the following conditions for all X , Y S. Extensive: X C(X ) Monotone: X Y C(X ) C(Y ) Idempotent: C(C(X )) = C(X ) A set X is called closed under C iff X = C(X ). Often closure operators are derived from (one or several) operations on the elements of a set. E.g., the closure under addition is defined as C(X ) := X {a1 + + ak | a1 , . . . , ak X } N is closed under addition, but not under subtraction. 3 7 = 4 / N. R is closed under multiplication, but not under division. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 49 / 74 Closure Definition A closure operator on a set S is a function C : 2S 2S that satisfies the following conditions for all X , Y S. Extensive: X C(X ) Monotone: X Y C(X ) C(Y ) Idempotent: C(C(X )) = C(X ) A set X is called closed under C iff X = C(X ). Often closure operators are derived from (one or several) operations on the elements of a set. E.g., the closure under addition is defined as C(X ) := X {a1 + + ak | a1 , . . . , ak X } N is closed under addition, but not under subtraction. 3 7 = 4 / N. R is closed under multiplication, but not under division. 1/0 / R. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 49 / 74 Closure (cont.) Closure operators can also be defined by properties of sets. Let P : 2S {T, F} a property of sets. Let C(X ) be the smallest set Y s.t. X Y and P(Y ), i.e., the smallest extension of X that satisfies property P. This yields a closure operator only if such a smallest Y actually exists. Example: Binary relations R S S are subsets of S S. Define the transitive closure of relations C : 2S S 2S S by C(R) := The smallest transitive relation R 0 with R R 0 The transitive closure of relations does exist, because the intersection of T transitive relations is transitive. Thus C(R) := R R 0 ,R 0 transitive R 0 . Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 50 / 74 Sequences Sequences are ordered lists of elements, e.g., 2, 3, 5, 7, 11, 13, 17, 19, . . . or a, b, c, d, . . . . Definition A sequence over a set S is a function f from a subset of the integers (typically N or N {0}) to the set S. If the domain of f is finite then the sequence is finite. Example: Let f : N {0} Q be defined by f (n) := 1/n. This defines the sequence 1 1 1 1, , , , . . . 2 3 4 Let an = f (n). Then the sequence is also written as a1 , a2 , a3 , . . . or as {an }n N {0} Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 51 / 74 Geometric vs. Arithmetic Progression A geometric progression is a sequence of the form a, ar , ar 2 , ar 3 , . . . , ar n , . . . where both the initial element a and the common ratio r are real numbers. An arithmetic progression is a sequence of the form a, a + d, a + 2d, a + 3d, . . . , a + nd, . . . where both the initial element a and the common difference d are real numbers. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 52 / 74 Recurrence Relations Definition A recurrence relation for the sequence {an }n N is an equation that expresses an in terms of (one or more of) the previous elements a0 , a1 , . . . , an 1 of the sequence. Typically the recurrence relation expresses an in terms of just a fixed number of previous elements, e.g., an = g(an 1 , an 2 ) = 2an 1 + an 2 + 7. The initial conditions specify the first elements of the sequence, before the recurrence relation applies. A sequence is called a solution of a recurrence relation iff its terms satisfy the recurrence relation. Example: Let a0 = 2 and an = an 1 + 3 for n 1. Then a1 = 5, a2 = 8, a3 = 11, etc. Generally the solution is f (n) = 2 + 3n. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 53 / 74 Fibonacci Sequence The Fibonacci sequence is described by the following linear recurrence relation. f (0) = 0, f (1) = 1 and f (n) = f (n 1) + f (n 2) for n 2. You obtain the sequence 0, 1, 1, 2, 3, 5, 8, 13, . . . . How to solve general recurrence with f (0) = a, f (1) = b, f (n) = c f (n 1) + d f (n 2) ? Linear algebra. Matrix multiplication. Base transforms. Diagonal form., etc. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 54 / 74 Solving Recurrence Relations Finding a formula for the n-th term of the sequence generated by a recurrence relation is called solving the recurrence relation. Such a formula is called a closed formula. Various methods for solving recurrence relations will be covered in Chapter 8 where recurrence relations will be studied in greater depth. Here we illustrate by example the method of iteration in which we need to guess the formula. The guess can be proved correct by the method of induction (Chapter 5). Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 55 / 74 Iterative Solution Example 1 Method 1: Working upward, forward substitution. Let an be a sequence that satisfies the recurrence relation an = an 1 + 3 for n 2 and suppose that a1 = 2. a2 = 2 + 3 a3 = (2 + 3) + 3 = 2 + 3 2 a4 = (2 + 2 3) + 3 = 2 + 3 3 an = an 1 + 3 = (2 + 3 (n 2)) + 3 = 2 + 3(n 1) Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 56 / 74 Iterative Solution Example 2 Method 2: Working downward, backward substitution. Let an be a sequence that satisfies the recurrence relation an = an 1 + 3 for n 2 and suppose that a1 = 2. an = an 1 + 3 = (an 2 + 3) + 3 = an 2 + 3 2 = (an 3 + 3) + 3 2 = an 3 + 3 3 = a2 + 3(n 2) = (a1 + 3) + 3(n 2) = 2 + 3(n 1) Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 57 / 74 Common Sequences See also The On-Line Encyclopedia of Integer Sequences (OEIS) at http://oeis.org/ Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 58 / 74 Summations Given a sequence {an }. The sum of the terms am , am+1 , . . . , an is written as am + am+1 + + an n X aj j=m X aj m j n The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n. More generally for an index set S one writes X aj j S Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 59 / 74 Useful Summation Formulae Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 60 / 74 Products Given a sequence {an }. The product of the terms am , am+1 , . . . , an is written as am am+1 an n Y aj j=m Y aj m j n More generally for an index set S one writes Y aj j S Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 61 / 74 Counting: Finite Sequences Given a finite set S with |S| = k . How many different sequences over S of length n are there? Clicker 1 k n 2 k +n 3 nk 4 kn 5 n kn 6 k nk Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 62 / 74 Counting: Finite Sequences Given a finite set S with |S| = k . How many different sequences over S of length n are there? Answer: For each of the n elements of the sequence there are k possible choices. So the answer is k k k (n times). In other words, we get Y k = kn 1 j n How many sequences over S of length n are there? Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 63 / 74 Counting: Finite Sequences Given a finite set S with |S| = k . How many different sequences over S of length n are there? Answer: For each of the n elements of the sequence there are k possible choices. So the answer is k k k (n times). In other words, we get Y k = kn 1 j n How many sequences over S of length n are there? Sum over the (non-overlapping!) cases of length j = 0, 1, 2, . . . , n. n X j=0 kj = k n+1 1 k 1 (By the sum formula of the previous slide.) Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 63 / 74 Counting: Relations and Functions on Finite Sets Let A and B be finite sets, i.e., |A| and |B| are finite. What is the size of A B ? How many binary relations R A B from A to B are there? How many total functions f : A B from A to B are there? Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 64 / 74 Counting: Relations and Functions on Finite Sets Let A and B be finite sets, i.e., |A| and |B| are finite. What is the size of A B ? |A B| = |A| |B| How many binary relations R A B from A to B are there? How many total functions f : A B from A to B are there? Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 64 / 74 Counting: Relations and Functions on Finite Sets Let A and B be finite sets, i.e., |A| and |B| are finite. What is the size of A B ? |A B| = |A| |B| How many binary relations R A B from A to B are there? The number of relations from A to B is the number of subsets of A B. Thus the answer is 2|A| |B| . How many total functions f : A B from A to B are there? Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 64 / 74 Counting: Relations and Functions on Finite Sets Let A and B be finite sets, i.e., |A| and |B| are finite. What is the size of A B ? |A B| = |A| |B| How many binary relations R A B from A to B are there? The number of relations from A to B is the number of subsets of A B. Thus the answer is 2|A| |B| . How many total functions f : A B from A to B are there? A total function f assigns exactly one element from B to every element of A. Thus for every element of a A there are |B| possible choices for f (a) B. Thus the answer is |B||A| . Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 64 / 74 Counting: Relations and Functions on Finite Sets Let A and B be finite sets, i.e., |A| and |B| are finite. What is the size of A B ? |A B| = |A| |B| How many binary relations R A B from A to B are there? The number of relations from A to B is the number of subsets of A B. Thus the answer is 2|A| |B| . How many total functions f : A B from A to B are there? A total function f assigns exactly one element from B to every element of A. Thus for every element of a A there are |B| possible choices for f (a) B. Thus the answer is |B||A| . The set of all total functions f : A B from A to B is denoted by BA Thus we get that |B A | = |B||A| . Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 64 / 74 Cardinality of (Infinite) Sets The sizes of finite sets are easy to compare. But what about infinite sets? Can one infinite set be larger than another? Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 65 / 74 Cardinality of (Infinite) Sets The sizes of finite sets are easy to compare. But what about infinite sets? Can one infinite set be larger than another? Definition Two sets A and B have the same cardinality, written |A| = |B| iff there exists a bijection from A to B. We say |A| |B| iff there exists an injection from A to B. A has lower cardinality than B, written |A| < |B| iff |A| |B| and |A| = 6 |B|. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 65 / 74 Cardinality of (Infinite) Sets The sizes of finite sets are easy to compare. But what about infinite sets? Can one infinite set be larger than another? Definition Two sets A and B have the same cardinality, written |A| = |B| iff there exists a bijection from A to B. We say |A| |B| iff there exists an injection from A to B. A has lower cardinality than B, written |A| < |B| iff |A| |B| and |A| = 6 |B|. Note that this definition applies to general sets, not only to finite ones. An infinite set (but not a finite one) can have the same cardinality as a strict subset. Example: The set of natural numbers N and the set of even numbers even := {2n | n N} have the same cardinality, because f : N even with f (n) = 2n is a bijection. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 65 / 74 Countable Sets Definition A set S is called countably infinite, iff it has the same cardinality as the natural numbers, |S| = |N|. A set is called countable iff it is either finite or countably infinite. A set that is not countable is called uncountable. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 66 / 74 Hilbert s Grand Hotel The Grand Hotel (example due to David Hilbert) has countably infinite number of rooms, each occupied by a guest. We can always accommodate a new guest at this hotel. How is this possible? Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 67 / 74 The Positive Rational Numbers are Countable Construct a bijection f : N Q+ . List fractions p/q with q = n in the n-th row. f traverses this list in the following order. For n = 1, 2, 3, . . . do visit all p/q with p + q = n. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 68 / 74 Finite Strings Theorem The set of all finite strings over a finite alphabet is countably infinite. Proof. First define an (alphabetical) ordering on the symbols in . Show that the strings can be listed in a sequence. First all strings of length 0 in lexicographic order. Then all strings of length 1 in lexicographic order. Then all strings of length 2 in lexicographic order, etc. This implies a bijection from N to . In particular, the set of all Java-programs is countable, since every program is just a finite string. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 69 / 74 Combining Countable Sets Theorem The union S1 S2 of two countably infinite sets S1 , S2 is countably infinite. Proof. (Sketch) Since S1 , S2 are countably infinite, there must exist bijections f1 : N S1 and f2 : N S2 . Consider the disjoint parts S1 and S2 S1 . If S2 S1 is finite then consider this part separately and build a bijection f : N S1 S2 by shifting f1 by |S2 S1 |. Otherwise, construct bijections between the two parts and the even/odd natural numbers, respectively. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 70 / 74 Uncountable Sets Theorem The set of infinite binary strings is uncountable. Proof. Assume by contraposition that a bijection f : N InfiniteStrings exists. Let dn be the n-th symbol of string f (n). We define a string x such that the n-th symbol of x is dn + 1 mod 2. Thus n N x 6= f (n) and f is not a surjection. Contradiction. Similarly for the infinite decimal strings (over digits {0, 1, 2, . . . , 9}). Just use modulo 10 instead of modulo 2. The technique used in the proof above is called diagonalization. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 71 / 74 The Real Numbers are Uncountable A similar diagonalization argument shows uncountability of R. Theorem The real numbers in the interval (0, 1) R are uncountable. Proof. (Sketch) Construct a bijection between (0, 1) and the set of infinite binary strings. E.g., a string 10011 . . . means the number 0.10011 . . . . Some slight problem arises because the same number can be represented by different infinite strings. Also infinite strings can be eventually constant. Handle these cases separately. Theorem The real numbers R are uncountable. Proof. Find a bijection between (0, 1) and R. E.g., f (x) = tan( x /2). Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 72 / 74 Cantor s Theorem (Georg Cantor, 1845-1918) Theorem Let S be a set and 2S be its powerset (the set of all subsets of S). There does not exist any surjection f : S 2S . Proof. Assume, by contraposition, that such a surjection f exists. We define the set G S as follows. G := {x S | x / f (x)}. Since f is a surjection, there must exist an s S s.t. G = f (s). Now there are two cases: 1 If s G then, by def. of G, s / f (s) = G. Contradiction. 2 If s / G = f (s) then s / f (s). Thus, by def. of G, s G. Contradiction. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 73 / 74 Implications of Cantor s Theorem By Cantor s Theorem there cannot exist any bijection f : S 2S . However, an injection is trivial to find. Let f (x) := {x}. By the definition of Cardinality this means that |S| < |2S |, i.e., a powerset has strictly larger cardinality than its base set. Thus 2N is not countable. (It can also be shown that |R| = |2N |.) The Continuum hypothesis claims there there does not exist any set S with |N| < |S| < |R|, i.e., nothing strictly between. This problem was 1st on the list of Hilbert s 23 problems presented in 1900. It was shown to be independent of ZFC (Zermelo-Fraenkel set theory) by G del/Cohen in 1963, i.e., it cannot be (dis)proven in ZFC. There exists an infinite hierarchy of sets of ever larger cardinality. Let S0 := N and Si+1 := 2Si . Then |Si | < |Si+1 | for all i. The existence of even larger cardinals beyond his hierarchy is a problem of axiomatics beyond ZFC. See Large Cardinals . Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 9 74 / 74

Formatting page ...

nage19 chat

Horizontal lines at:
Guest Horizontal lines at:
AutoRM Data:
Box geometries: