离散数学第七版2.1-2.6

1、Module #2:The Theory of Sets,Rosen 7th ed., 2.1-2.2,2 Basic Structures: Sets, Functions, Sequences , Sums and Matrices,2.1 Sets 2.2 Set Operations 2.3 Functions 2.4 Sequences and Summations 2.5 Cardinality of Sets 2.6 Matrices,Introduction to Set Theory 集合论(2.1),A set is a new type of structure, rep

2、resenting an unordered collection (group, plurality) of zero or more distinct (different) objects. Set theory deals with operations between, relations among, and statements about sets. Sets are ubiquitous in computer software systems. All of mathematics can be defined in terms of some form of set th

3、eory (using predicate logic).,Nave set theory,Basic premise: Any collection or class of objects (elements) that we can describe (by any means whatsoever) constitutes a set. But, the resulting theory turns out to be logically inconsistent! This means, there exist nave set theory propositions p such t

4、hat you can prove that both p and p follow logically from the axioms of the theory! The conjunction of the axioms is a contradiction! This theory is fundamentally uninteresting, because any possible statement in it can be (very trivially) “proved” by contradiction! More sophisticated set theories fi

5、x this problem.,Basic notations for sets,For sets, well use variables S, T, U, We can denote a set S in writing by listing all of its elements in curly braces: a, b, c is the set of whatever 3 objects are denoted by a, b, c. Set builder notation: For any proposition P(x) over any universe of discour

6、se, x|P(x) is the set of all x such that P(x).,Basic properties of sets,Sets are inherently unordered: No matter what objects a, b, and c denote, a, b, c = a, c, b = b, a, c =b, c, a = c, a, b = c, b, a. All elements are distinct (unequal);multiple listings make no difference! If a=b, then a, b, c =

7、 a, c = b, c = a, a, b, a, b, c, c, c, c. This set contains (at most) 2 elements!,Definition of Set Equality集合相等,Two sets are declared to be equal if and only if they contain exactly the same elements. In particular, it does not matter how the set is defined or denoted. For example: The set 1, 2, 3,

8、 4 = x | x is an integer where x0 and x0 and 25,Infinite Sets无限集,Conceptually, sets may be infinite (i.e., not finite, without end, unending). Symbols for some special infinite sets:N = 0, 1, 2, The Natural numbers.Z = , -2, -1, 0, 1, 2, The Zntegers.R = The “Real” numbers, such as 374.1828471929498

9、181917281943125 “Blackboard Bold” or double-struck font (,) is also often used for these special number sets. Infinite sets come in different sizes!,Venn Diagrams文氏图,0,-1,1,2,3,4,5,6,7,8,9,Integers from -1 to 9,Positive integers less than 10,Even integers from 2 to 9,Odd integers from 1 to 9,Primes

10、10,John Venn1834-1923,Basic Set Relations:Member of成员,xS (“x is in S”) is the proposition that object x is an lement or member of set S. e.g. 3N, “a”x | x is a letter of the alphabet Can define set equality in terms of relation:S,T: S=T (x: xS xT)“Two sets are equal iff they have all the same member

11、s.” xS : (xS) “x is not in S”,The Empty Set空集, (“null”, “the empty set”) is the unique set that contains no elements whatsoever. = = x|False No matter the domain of discourse,we have the axiom x: x.,Subset子集,ST (“S is a subset of T”) means that every element of S is also an element of T. ST x (xS xT

12、) S, SS.,Proper (Strict) Subsets真子集,ST (“S is a proper subset of T”) means that ST but .,S,T,Venn Diagram equivalent of ST,Example:1,2 1,2,3,Sets Are Objects, Too!,The objects that are elements of a set may themselves be sets. E.g. let S=x | x 1,2,3then S=, 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3 Note that 1

13、1 1 !,Very Important!,Cardinality and Finiteness基数,|S| (read “the cardinality of S”) is a measure of how many different elements S has. E.g., |=0, |1,2,3| = 3, |a,b| = 2, |1,2,3,4,5| = _ If |S|N, then we say S is finite.Otherwise, we say S is infinite. What are some infinite sets weve seen?,2,N,Z,R,

14、The Power Set 幂集Operation,The power set P(S) of a set S is the set of all subsets of S. P(S) : x | xS. E.g. P(a,b) = , a, b, a,b. Sometimes P(S) is written 2S.Note that for finite S, |P(S)| = 2|S|. It turns out S:|P(S)|S|, e.g. |P(N)| |N|.There are different sizes of infinite sets!,Review: Set Notat

15、ions So Far,Variable objects x, y, z; sets S, T, U. Literal set a, b, c and set-builder x|P(x). relational operator, and the empty set . Set relations =, , , , , , etc. Venn diagrams. Cardinality |S| and infinite sets N, Z, R. Power sets P(S).,Nave Set Theory is Inconsistent,There are some nave set

16、descriptions that lead to pathological structures that are not well-defined. (That do not have self-consistent properties.) These “sets” mathematically cannot exist. E.g. let S = x | xx . Is SS? Therefore, consistent set theories must restrict the language that can be used to describe sets. For purp

17、oses of this class, dont worry about it!,Bertrand Russell1872-1970,Ordered n-tuples 有序n元组,These are like sets, except that duplicates matter, and the order makes a difference. Ordered pairs 序偶 For nN, an ordered n-tuple or a sequence or list of length n is written (a1, a2, , an). Its first element i

18、s a1, etc. Note that (1, 2) (2, 1) (2, 1, 1). Empty sequence, singlets, pairs, triples, quadruples, quintuples, , n-tuples.,Contrast withsets ,Cartesian Products of Sets迪卡尔集,For sets A, B, their Cartesian productAB : (a, b) | aA bB . E.g. a,b1,2 = (a,1),(a,2),(b,1),(b,2) Note that for finite A, B, |

19、AB|=|A|B|. Note that the Cartesian product is not commutative: i.e., AB: AB=BA. Extends to A1 A2 An.,Ren Descartes (1596-1650),Definition of relations,Let A and B be two sets. A binary relation R from A to B is a subset of A B. Note that the order of the two sets matters. More generally, let A1, A2,

20、 ., An be n sets. An n-ary relation R on these sets is a subset of A1 A2 . An. The sets Ai are known as the domains of the relation, and n as its degree Again, the order of the domains matters.,Review of 2.1,Sets S, T, U Special sets N, Z, R. Set notations a,b,., x|P(x) Set relation operators xS, ST

21、, ST, S=T, ST, ST. (These form propositions.) Finite vs. infinite sets. Set operations |S|, P(S), ST.,Start 2.2: 集合运算The Union Operator并,For sets A, B, theirnion AB is the set containing all elements that are either in A, or (“”) in B (or, of course, in both). Formally, A,B: AB = x | xA xB. Note tha

22、t AB is a superset of both A and B (in fact, it is the smallest such superset): A, B: (AB A) (AB B),a,b,c2,3 = a,b,c,2,3 2,3,53,5,7 = 2,3,5,3,5,7 =2,3,5,7,Union Examples,The Intersection Operator交,For sets A, B, their intersection AB is the set containing all elements that are simultaneously in A an

23、d (“”) in B. Formally, A,B: AB=x | xA xB. Note that AB is a subset of both A and B (in fact it is the largest such subset): A, B: (AB A) (AB B),a,b,c2,3 = _ 2,4,63,4,5 = _,Intersection Examples,4,Disjointedness 互斥,Two sets A, B are calleddisjoint (i.e., unjoined)iff their intersection isempty. (AB=)

24、 Example: the set of evenintegers is disjoint withthe set of odd integers.,Inclusion-Exclusion Principle容斥原理,How many elements are in AB? |AB| = |A| |B| |AB| Example: How many students are on our class email list? Consider set E I M, I = s | s turned in an information sheetM = s | s sent the TAs the

25、ir email address Some students did both! |E| = |IM| = |I| |M| |IM|,Subtract out items in intersection, to compensate for double-counting them!,Set Difference差,For sets A, B, the difference of A and B, written AB, is the set of all elements that are in A but not B. Formally: A B : x xA xB x xA xB Als

26、o called: The complement of B with respect to A.,Set Difference Examples,1,2,3,4,5,6 2,3,5,7,9,11 = _ Z N , 1, 0, 1, 2, 0, 1, = x | x is an integer but not a nat. # = x | x is a negative integer = , 3, 2, 1,1,4,6,Set Difference - Venn Diagram,AB is whats left after B“takes a bite out of A”,Set A,Set

27、 B,Set Complements补,The universe of discourse can itself be considered a set, call it U. When the context clearly defines U, we say that for any set AU, the complement of A, written , is the complement of A w.r.t. U, i.e., it is UA. E.g., If U=N,More on Set Complements,An equivalent definition, when

28、 U is clear:,A,U,Set Identities特性,Identity: A = A = AU Domination: AU = U , A = Idempotent: AA = A = AA Double complement: Commutative: AB = BA , AB = BA Associative: A(BC)=(AB)C , A(BC)=(AB)C,DeMorgans Law for Sets,Exactly analogous to (and provable from) DeMorgans Law for propositions.,Proving Set

29、 Identities,To prove statements about sets, of the form E1 = E2 (where the Es are set expressions), here are three useful techniques: 1. Prove E1 E2 and E2 E1 separately. 2. Use set builder notation relations (ch. 6).,Functions,A function f: A B can also be defined as a subset of AB (a relation). Th

30、is subset is restricted to be a relation where no two elements of the relation have the same first element. Specifically, a function f from A to B contains one, and only one ordered pair (a, b) for every element a A. and,Graphical Representations,Functions can be represented graphically in several w

31、ays:,A,B,a,b,f,f,x,y,Plot,Bipartite Graph,Like Venn diagrams,A,B,Functions Weve Seen So Far,A proposition can be viewed as a function from “situations” to truth values T,F A logic system called situation theory. p=“It is raining.”; s=our situation here,now p(s)T,F. A propositional operator can be vi

32、ewed as a function from ordered pairs of truth values to truth values: e.g., (F,T) = T.,Another example: (T,F) = F.,More functions so far,A predicate can be viewed as a function from objects to propositions (or truth values): P : “is 7 feet tall”; P(Mike) = “Mike is 7 feet tall.” = False. A bit stri

33、ng B of length n can be viewed as a function from the numbers 1,n(bit positions) to the bits 0,1.E.g., B=101 B(3)=1.,Still More Functions,A set S over universe U can be viewed as a function from the elements of U toT, F, saying for each element of U whether it is in S. S=3 S(0)=F, S(3)=T. A set oper

34、ator such as , can be viewed as a function from pairs of setsto sets. Example: (1,3,3,4) = 3,A Neat Trick,Sometimes we write YX to denote the set F of all possible functions f:XY. This notation is especially appropriate, because for finite X, Y, we have |F| = |Y|X|. If we use representations F0, T1,

35、 2:0,1=F,T, then a subset TS is just a function from S to 2, so the power set of S (set of all such fns.) is 2S in this notation.,Some Function Terminology,If it is written that f:AB, and f(a)=b (where aA f is strictly (or monotonically) decreasing iff xy f(x)f(y) for all x,y in domain; If f is eith

36、er strictly increasing or strictly decreasing, then f is one-to-one. E.g. x3 Converse is not necessarily true. E.g. 1/x,Onto (Surjective) Functions,A function f:AB is onto or surjective or a surjection iff its range is equal to its codomain (bB, aA: f(a)=b). Think: An onto function maps the set A on

37、to (over, covering) the entirety of the set B, not just over a piece of it. E.g., for domain give me any 2-digit number n, and Ill add all the numbers from 1 to n in my head in just a few seconds.” I.e., Evaluate the summation: There is a simple closed-form formula for the result, discovered by Eule

38、r at age 12! And frequently rediscovered by many,LeonhardEuler(1707-1783),Eulers Trick, Illustrated,Consider the sum:1+2+(n/2)+(n/2)+1)+(n-1)+n We have n/2 pairs of elements, each pair summing to n+1, for a total of (n/2)(n+1).,n+1,n+1,n+1,Symbolic Derivation of Trick,For case where n is even,Conclu

39、ding Eulers Derivation,So, you only have to do 1 easy multiplication in your head, then cut in half. Also works for odd n (prove this at home).,Example: Geometric Progression,A geometric progression is a series of the form a, ar, ar2, ar3, , ark, where a,rR. The sum of such a series is given by: We

40、can reduce this to closed form via clever manipulation of summations.,Herewego.,Geometric Sum Derivation,Derivation example cont.,Concluding long derivation.,Nested Summations,These have the meaning youd expect. Note issues of free vs. bound variables, just like in quantified expressions, integrals,

41、 etc.,Some Shortcut Expressions,Geometric series.,Eulers trick.,Quadratic series.,Cubic series.,Using the Shortcuts,Example: Evaluate . Use series splitting. Solve for desiredsummation. Apply quadraticseries rule. Evaluate.,Some Useful Summation Formulae,Later we will prove some of these by inductio

42、n.,Proof in text (requires calculus),Geometric Series: We just proved this.,Summations: Conclusion,You need to know: How to read, write the generating function is bijective.,The Positive Rational Numbers are Countable,Constructing the List First list p/q with p + q = 2. Next list p/q with p + q = 3

43、And so on.,First row q = 1. Second row q = 2. etc.,1, , 2, 3, 1/3,1/4, 2/3, .,Uncountable Sets: Example,Theorem: The open interval of reals0,1) : rR| 0 r 1 is uncountable. Proof by diagonalization: (Cantor, 1891) Assume there is a series ri = r1, r2, . containing all elements r0,1). Consider listing

44、 the elements of ri in decimal notation (although any base will do) in order of increasing index: . (continued on next slide),Georg Cantor 1845-1918,Uncountability of Reals, contd,A postulated enumeration of the reals:r1 = 0.d1,1 d1,2 d1,3 d1,4 d1,5 d1,6 d1,7 d1,8r2 = 0.d2,1 d2,2 d2,3 d2,4 d2,5 d2,6

45、 d2,7 d2,8r3 = 0.d3,1 d3,2 d3,3 d3,4 d3,5 d3,6 d3,7 d3,8r4 = 0.d4,1 d4,2 d4,3 d4,4 d4,5 d4,6 d4,7 d4,8.,Now, consider a real number generated by takingall the digits di,i that lie along the diagonal in this figure and replacing them with different digits.,That real doesnt appear in the list!,Uncount

46、ability of Reals, fin.,E.g., a postulated enumeration of the reals:r1 = 0.301948571r2 = 0.103918481r3 = 0.039194193r4 = 0.918237461 OK, now lets add 1 to each of the diagonal digits (mod 10), that is changing 9s to 0. 0.4103 cant be on the list anywhere!,Transfinite Numbers超限数,The cardinalities of i

47、nfinite sets are not natural numbers, but are special objects called transfinite cardinal numbers. The cardinality of the natural numbers, 0:|N|, is the first transfinite cardinal number. (There are none smaller.) The continuum hypothesis claims that |R|=1, the second transfinite cardinal.,Proven im

48、possible to prove or disprove!,Do Uncountable Sets Really Exist?,The set of objects that can be defined using finite-length strings of symbols (“descriptions”) is only countable. Therefore, any uncountable set must consist primarily of elements which individually have no finite descriptions. Lwenhei

49、m-Skolem theorem: No consistent theory can ever force an interpretation involving uncountables. The “constructivist school” asserts that only objects constructible from finite descriptions exist. (e.g. R) Most mathematicians are happy to use uncountable sets anyway, because postulating their existen

50、ce has not led to any demonstrated logical contradictions (so far).,Countable vs. Uncountable,You should: Know how to define “same cardinality” in the case of infinite sets. Know the definitions of countable and uncountable. Know how to prove (at least in easy cases) that sets are either countable o

51、r uncountable.,作业, 2.3 8, 20, 24, 33, 64 2.4 16,26, 30, 34 2.5 2，10,2.6 Matrices,A matrix is a rectangular array of objects (usually numbers). An mn (“m by n”) matrix has exactly m horizontal rows, and n vertical columns. Plural of matrix = matrices (say MAY-trih-sees) An nn matrix is called a squar

52、e matrix,whose order or rank is n.,a 32 matrix,Applications of Matrices,Tons of applications, including: Solving systems of linear equations Computer Graphics, Image Processing Models within many areas of Computational Science & Engineering Quantum Mechanics, Quantum Computing Many, many more,Matrix

53、 Equality,Two matrices A and B are considered equal iff they have the same number of rows, the same number of columns, and all their corresponding elements are equal.,Row and Column Order,The rows in a matrix are usually indexed 1 to m from top to bottom. The columns are usually indexed 1 to n from

54、left to right. Elements are indexed by row, then column.,Matrices as Functions,An mn matrix A = ai,j of members of a set S can be encoded as a partial function fA: NNS, such that for im, jn, fA(i, j) = ai,j. By extending the domain over which fA is defined, various types of infinite and/or multidime

55、nsional matrices can be obtained.,Matrix Sums,The sum A+B of two matrices A, B (which must have the same number of rows, and the same number of columns) is the matrix (also with the same shape) given by adding corresponding elements of A and B. A+B = ai,j+bi,j,Matrix Products,For an mk matrix A and

56、a kn matrix B, the product AB is the mn matrix: I.e., the element of AB indexed (i,j) is given by the vector dot product of the ith row of A and the jth column of B (considered as vectors). Note: Matrix multiplication is not commutative!,Illustration of Matrix Multiplication,The Product of A = aij a

57、nd B = bij,Matrix Product Example,An example matrix multiplication to practice in class:,n,n,Identity Matrices,The identity matrix of order n, In, is the rank-n square matrix with 1s along the upper-left to lower-right diagonal, and 0s everywhere else.,Kronecker Delta,1i,jn,Review: Matrices, so far,Matrix sums and products: A+B = ai,j