《关于数理逻辑的课件》由会员分享，可在线阅读，更多相关《关于数理逻辑的课件（63页珍藏版）》请在金锄头文库上搜索。
1、Set TheorySet Theory 2014 CopyRight 2014 CopyRightHengming Zou, Ph.D.Hengming Zou, Ph.D.Mathematic Logic SJTUMathematic Logic SJTU2 2ContentSetsOperations with Sets 集合及其运算Closure OperationsPartitionCover of Sets3 3SetsA set is a collection of distinct objects, which are called elements. The elements
2、 of a set can be just about anything: numbers, points in space, or even other sets. The conventional way to write down a set is to list the elementsFor example, here are some sets: N = 0,1,2,3,.the natural numbers C = red, blue, yellowprimary colors D = Nifty, Friend, Horatio, PrettyPretty dead pets
3、 P = a, b ,a, c ,b, ca set of sets 4 4Sets and SequencesThe elements of a set are required to be distinctA set can not contain multiple copies of the same element.The order of elements is not significantso x, y and y, x are the same set written two different waysThe expression eS asserts that e is a
4、n element of set SFor example, 7N and blueC, but WilburDSets are simple, flexible, and everywhereAll Chinese can be considered a setAll of your friends is another set5 5Notation of SetsEnumerative：List every member of the set in arbitrary order:Example：A=2,a,b,9, B=4,5,6,7,8Descriptive：Specify a con
5、dition P(x)，iff P(a) holds for element a，aAThe general form is: A=a| P(a)For example:Set B given above can be expressed as B=a| aN and 4a8C=2i| iZ+，i.e. C=20,21,22,23,D=2x| xZ+and x50，i.e. D=0,2,4,6,98,1006 6Some Popular SetsMathematicians have special symbols to represent some common setssymbol set
6、 elements the empty set none N natural numbers 0,1,2,3,.Z integers .,3,2,1,0,1,2,3,.Qrational numbers 1/2, 5/3, 16, etc. R real numbers , e, 9, etc. C complex numbers i, 19/2, sqrt(2)-2i, etc. A superscript + restricts a set to its positive elementsfor example, R+is the set of positive real numbers7
7、 7Cardinality of SetsThe number of distinct members of set A is the cardinality of ADenote as |A|For example :For the sets given in previous page:|A|=4，|B| =5，|D| =51C has infinite number of members, the cardinality of C is infinityif|A|is finite, then A is finite set, otherwise A is infinite.For ex
8、ample:N, Z+, I, R are all infinite sets8 8Relations between SetsSubset and equivalence are two basic relationships of setsFor set A、B，if every member of A is also member of BThen A is a subset of B，denote ABIf A is not a subset of B，we denote A!BFor example :if A=a, b, c, d, B=a, e, x, y, z, C=a, xt
9、hen CB ，C!BN Z (every natural number is an integer) and Q R (every rational number is a real number), but C Z (not every complex number is an integer)9 9Equivalence of SetsIf AB and BA , then A and B are equivalentDenote as: A=BExample: Let: A=x | xN 且 x|24，B=1, 2, 3, 4, 6, 8, 12, 24 Then: A=BAlso:a
10、, b, c b, c, a a, b, c, c a, b, c a, b, c a, b, c 1010Relations between SetsAs a memory trick, notice that the points to the smaller set, just like a sign points to the smaller numberActually, this connection goes a little further: there is a symbol analogous to 注意：有序n元组与n个元素的集合，是不相同的Example:a, b, c
11、, d=b, c, d, a=d, a, c, b 4, 4, 3, 2=4, 3, 2But 3535Ordered n-tuple有序n元组Let: and be ordered n-tupleIf: ai=bi, i=1,2,.,n. Then, the two ordered n-tuple are equal and is denoted as:= When n=2, ordered n-tuple is also called ordered pairs序偶3636Cartesian ProductIf A and B are sets, then the Cartesian Pr
12、oduct of A and B is denoted as:AB, and is defined as:AB=| aA, bBExample:Let: A=1,2 , B=a, b,c, ThenAB=,BA =,3737Cartesian ProductIn general we have: ABBA A=A=The Cartesian Product AA is denoted as A2:A2=| aiA, ajAIf Aa1,a2,am, Bb1,b2,bnThen:|AB|=|BA|=|A|B|=mn3838Properties of Cartesian ProductLet A、
13、B、C be any set, we have:A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB) (AC)(BC)A=(BA) (CA)3939Properties of Cartesian ProductWe prove the first one：A(BC)=(AB)(AC), we have:A(BC) (xA)(yBC) (xA)(yByC) (xAyB)(xAyC) (AB)(AC) (AB)(AC)Therefore A(BC)=(AB)(AC)4040Properties of Cartesian ProductWe prove the first o
14、ne：A(BC)=(AB)(AC)Let A(BC)Then we have: x A and yBCWhich is: xA and (yB or yC)Thus: (x A, y B) or (xA, yC)于是： AB 或 AC即： (AB)(AC)因此： A(BC)(AB)(AC)同理可证明： A(BC)(AB)(AC)因此： A(BC)=(AB)(AC)4141Properties of Cartesian Product定理: 若C，则：AB(AC)(B C) (CA)(C B)定理: 设A、B、C、D是任意非空集合，则有:ABCD (AC)(CD)例3 设A、B、C、D是任意集合，判断下列等式是否成立1: (AB)(CD)= (AC)(BD)2: (AB)(CD)= (AC)(BD)4242Properties of Cartesian ProductThe first equation holdsBecause , we have:(AB)(CD) x(AB)y(CD) (xA)(xB)(yC)(yD) (xA)(yC)(xB)(yD) (AC)(BD) (AC)(BD)4343Properties of Cartesian ProductThe second one does not
