三、预备知识
1.集合的基本概念
·集合(set):集合是数学中最基本的概念之一,不能以更简单的概念来定义(define),只能给出它的描述(description)。一些对象的整体就称为一个集合,这个整体的每个对象称为该集合的一个元素(member或element)。
·用大写字母A, B, C等表示集合,用小写字母a, b, c等表示集合的元素
·aÎA表示:a是集合A的元素,或说a属于集合A
·aÏA表示:a不是集合A的元素,或说a不属于集合A
·集合中的元素是无序的,不重复的。通常使用两种方法来给出一个集合:
·列元素法:列出某集合的所有元素,如:
·A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于10的自然数所构成的集合
·B = {a, b, …, z} 表示所有小写英文字母所构成的集合
·性质概括法:使用某个性质来概括集合中的元素,如:
·A = { n | n 是小于10的自然数}
·C = { n | n 是质数} 表示所有质数所构成的集合
·集合由它的元素所决定,换句话说,两个集合A和B相等,记为A = B,如果A和B具有相同的元素,即a属于集合A当且仅当a属于集合B。
·子集(subset):说集合A是集合B的子集,记为AÍB,如果a属于集合A则a也属于集合B。因此A=B当且仅当AÍB且BÍA。说集合A是集合B的真子集(proper subset),如果AÍB且A不等于B(A ¹ B)。
·空集(empty set):约定存在一个没有任何元素的集合,称为空集,记为f,有时也用{}来表示。按子集的定义,空集是任何集合的子集(为什么?)。
·幂集(power set):集合A的幂集,记为P(A),是A的所有子集所构成的集合,即:
·P(A) = { B | B Í A }
·例如,A = {0, 1},则P(A) = { {}, {0}, {1}, {0, 1} }
·显然,对任意集合A,有fÎ P(A)和AÎP(A)
·补集(complement set):集合A的补集,记为A,是那些不属于集合A的元素所构成的集合,即A = {x | xÏA}。通常来说,是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。
·集合的并(union):集合A和B的并AÈB定义为:AÈB = {x | xÎA或者xÎB},集合的并可推广到多个集合,设A1, A2, …, An都是集合,它们的并定义为:
A1ÈA2…ÈAn = {x | 存在某个i,使得xÎAi}
·集合的交(intersection):集合A和B的并AÇB定义为:AÇB = {x | xÎA而且xÎB},集合的交也可推广到多个集合,设A1, A2, …, An都是集合,它们的交定义为:
A1ÈA2…ÈAn = {x | 对所有的i,都有xÎAi}
·集合的差(difference):集合A和B的差A-B定义为:A-B = {x | xÎA而且xÏB}。
2.关系和函数的基本概念
·有序对(ordered pair):设A和B是两个集合,aÎA, bÎB是两个元素,a和b的有序对,记为<a, b>,定义为集合{{a}, {a, b}}。
·设<a1, b1>和<a2, b2>是两个有序对,可以证明<a1, b1> = <a2, b2>当且仅当a1 = a2且b1 = b2。(如何证?)
·有序对可推广到n个元素,设A1, A2, …, An是集合,a1ÎA1, a2ÎA2, …, anÎAn是元素,定义有序n元组(ordered n-tuple)<a1, a2, …, an>为<<a1, a2, …, an-1>, an>,注意这是一个归纳(inductive)定义,将有序n元组的定义归结为有序n-1元组的定义。
·显然有<a1, a2, …, an> = <b1, b2, …, bn>当且仅当a1 = b1且a2 = b2且…且an = bn。
·集合的笛卡尔积(cartesian product):两个集合A和B的笛卡尔积A´B定义为:
A´B = {<a, b> | aÎA且bÎB}
·例如,设A = {a, b, c},B = {1, 2},则:
A´B = {<a, 1>, <a, 2>, <b, 1>, <b, 2>, <c, 1>, <c, 2>}
·笛卡尔积可推广到多个集合的情况,集合A1, A2, …, An的笛卡尔积定义为:
A1´A2´…´An = {<a1, a2, …, an> | a1ÎA1且a2ÎA2且…且anÎAn}
·集合之间的关系(relation):定义n个集合A1, A2, …, An之间的一个n元关系R为集合A1, A2, …, An的笛卡尔积A1´A2´…´An的一个子集。设<a1, a2, …, an>ÎA1´A2´…´An,若<a1, a2, …, an>ÎR,则称a1, a2, …, an间具有关系R,否则称它们不具有关系R。特别地:
·当A1 = A2 = … = An = A时,称R为A上的n元关系。
·当n = 2时,有RÍA1´A2,称R为A1与A2间的一个二元关系(binary relation)。这时若<a1, a2>ÎR则简记为a1Ra2,否则(即<a1, a2>ÏR)记为a1Ra2。通常研究得最多的是二元关系,n元关系的许多性质可从二元关系的性质扩充而得到。如果没有特别指明的话,说R是一个关系则是指R是一个二元关系。
·当n = 1时,这时可认为R是集合A上满足某种性质的子集。
·关系的一些性质:设R是A上的二元关系:
·说R是自反的(reflexive),如果对任意的aÎA有aRa。
·说R是反自反的(irreflexive),如果对任意的aÎA有aRa。
·说R是对称的(symmetric),如果对任意的a, bÎA有若aRb则bRa。
· 说R是反对称的(antisymmetric),如果对任意的a, bÎA有若aRb且bRa则a = b。
·说R是传递的(transitive),如果对任意的a, b, c ÎA有若aRb且bRc则aRc。
·说R是等价关系(equivalence),如果R是自反的、对称的和传递的。
·集合之间的函数(function,或说映射mapping):定义集合A到B的函数f是A和B的笛卡尔积A´B的一个子集,且满足若<x, y>Îf及<x, z>Îf则y = z。因此函数是A和B之间的一个特殊的二元关系。通常记集合A到B的函数f为f : A®B。
·函数f : A®B的定义域(domain)dom(f )定义为:
dom(f ) = {x | 存在某个yÎB使得<x, y>Îf }
·函数f : A®B的值域(range)ran(f )定义为:
ran(f ) = {y | 存在某个xÎA使得<x, y>Îf }
·若<x, y>Îf,通常记y为f(x),并称y为x在函数f下的像(image),x为y在函数f下的原像。
·函数也可推广到n元的情形:f : A1´A2´…´An®B,意味着:
·f是A1´A2´…´An´B的一个子集,且
·<x1, x2, …, xn, y>Î f且<x1, x2, …, xn, z>Î f则y = z。
·函数的一些性质:设f : A®B是集合A到B的函数:
·说f是全函数(total function),若dom(f )=A,否则称f是偏函数(partial function)。下面如果没有特别指明的话,都是指全函数。
·说f是满射(surjection, 或说f maps A onto B),如果ran(f ) = B,即对任意的yÎB都有原像。
·说f是单射(injection,或说f is one-one),如果有f (x1) = f(x2)则x1 = x2,即对任意的yÎB,如果它有原像的话,则有唯一的原像。
·说f是双射(bijection,或说f是一一对应),如果f既是满射,又是单射,即对任意的yÎB,都有唯一的原像,同样根据全函数的定义,对于任意xÎA都有唯一的像。这时可以定义f的逆函数(inverse function),记为f -1 : B®A,f -1(y) = x当且仅当f(x) = y。显然f -1也是双射。
·集合的基数(cardinal number)或说势:集合A的基数记为|A|,且有:
·对于有限集合A,令A的基数为A中元素的个数。
·定义无限集合,不直接定义基数,而是通过定义两个集合之间的等势关系来刻划集合的基数或势,说集合A和集合B是等势的(equipotent),如果存在一个从A到B的双射。根据双射的性质,可以证明等势是集合上的一个等价关系。
·称与自然数集等势的集合为可列集(enumerable),有限集和可列集统称为可数集(countable)。
·设A和B是有限集合,有|P(A)| = 2|A|,|A´B| = |A| ´ |B|。