集合

发布时间:2019-07-02 作者:大扑棱蛾子 阅读次数:
版权声明:未经允许不得转载至微信公众号,转载至个人博客请注明出处。 阅读原文

集合基础

定义

集合
集合是对象的一个无序的聚集,对象也称为集合的元素(element)或成员(member)。集合包含(contain)它的元素。我们用aAa \in A来表示aa是集合AA中的一个元素。而记号aAa \notin A表示aa不是集合AA中的一个元素。
空集
不含任何元素的集合称为空集,用\varnothing表示

只有一个元素的的集合叫做单元素集

集合的三种表示方法:

  • 列举法或花名册方法(roster method)
  • 描述法或集合构造器(set builder)
  • 维恩(Veen)图或文氏图

常用集合

  • N={0,1,2,3,...}\bf{N} = \{0,1,2,3,...\},自然数集
  • N+={1,2,3,...}\bf{N}^+ = \{1,2,3,...\},正整数集,+表示大于0。
  • N={1,2,3,...}\bf{N}^* = \{1,2,3,...\},正整数集,*表示不包含0。
  • Z={...,3,2,1,0,1,2,3,...}\bf{Z} = \{...,-3,-2,-1,0,1,2,3,...\},整数集
  • Z+={1,2,3,...}\bf{Z}^+ = \{1,2,3,...\},正整数集
  • Q={pqpZ,qZ,q0}\displaystyle \bf{Q} = \{\frac{p}{q}\enspace|\enspace p\in{\bf{Z}},\enspace q\in{\bf{Z},\enspace \text{且}q \neq 0} \},自然数集
  • R\bf{R},实数集
  • R+\bf{R^+},正实数集
  • C\bf{C},复数集

区间表示

[a,b][a,b] 称为是从aabb的闭区间,而(a,b)(a,b)称为是从aabb的开区间。

集合相等

两个集合相等当且仅当它们拥有同样的元素。所以,如果AABB是集合,则AABB是相等的当且仅当x(xAxB)\enspace\forall{x(x\in{A} \leftrightarrow x\in{B})}。如果A{A}B{B}是相等的集,就记为A{A}=B{B}

子集

子集
集合AA是集合BB的自己当且仅当AA的每个元素也是BB的元素。我们用记号ABA\subseteq{B}表示集合AA是集合BB的子集。

ABA\subseteq{B} 当且仅当量化式x(xAxB)\forall{x(x\in{A} \rightarrow x\in{B})}

  • 证明AABB的子集: 要证明ABA\subseteq{B},需要证明如果xx属于AA则也属于BB
  • 证明AA不是是BB的子集: 要证明ABA\nsubseteq{B},需要找一个xAx\in A使得xBx \notin B
  • 证明两个集合相等: 要想证明两个集合AABB相等,就证明ABA \subseteq BBAB\subseteq A

对于任意集合SSS\varnothing\subseteq{S}SS\subseteq

证明S\varnothing\subseteq{S}
为了证明S\varnothing\subseteq{S},就必须证明x(xxS)\forall{x(x\in\varnothing \rightarrow x\in{S})}为真。因为空集没有元素,所以xx\in\varnothing总是假。因此xxSx\in\varnothing \rightarrow x\in{S}总是真。


真子集
集合AA是集合BB的子集但是ABA\neq B是,就写成ABA\subsetneqq{B},并说集合AA是集合BB的真子集。

x(xAxB)x(xBxA)\forall{x}(x \in A \rightarrow x \in B) \land \exist\: x(x \in B \land x \notin A)


集合的大小

SS为集合。如果SS中恰好有nn个不同的元素,这里nn是非负整数,我们就说SS是有限集,而nnSS的技术。SS的基数记为S|S|

幂集

给定集合SSSS的幂集(power set)是集合幂集所有子集的集合。SS的幂集记为P(S)\mathcal{P}(S)

集合{0,1,2}\{0,1,2\}的幂集是什么?

幂集P({0,1,2})\mathcal{P}(\{0,1,2\}){0,1,2}\{0,1,2\}所有子集的集合。
因此P({0,1,2})={,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}\mathcal{P}(\{0,1,2\})=\{\varnothing,\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\}\}

集合的幂集是一个集合

P()={}P({})={,{}}\mathcal{P}(\varnothing) = \{\varnothing\}\\ \mathcal{P}(\{\varnothing\}) = \{\varnothing,\{\varnothing\}\}

笛卡儿积

定义7
有序nn元组(ordered n-tuple) (a1,a2,...,an)(a_1,a_2,\:...\:,a_n)是以a1a_1为第1个元素,a2a_2为第2个元素,…,ana_n为第n个元素的有序聚集。

两个有序nn元组是相等的当且仅当每一对对应的元素都相等。换言之(a1,a2,...,an)=(b1,b2,...,bn)(a_1,a_2,\:...\:,a_n) = (b_1,b_2,\:...\:,b_n)当且仅当对于i=1,2,...,ni=1,2,...,nai=bia_i=b_i。特别地,有序二元组称为序偶(ordered pair)。

有序二元组是只有两个元素的有序集合。

定义8
AABB为集合。AABB的笛卡尔积(Cartesian product)用A×BA \times B表示,是所有序偶(a,b)(a,b)的集合,其中aAa \in AbBb \in B。于是,

A×B={(a,b)aAbB}A \times B = \{(a, b)\: |\: a \in A \land b \in B \}

A={1,2}A = \{1,2\}B={a,b,c}B=\{a, b, c\}的笛卡儿积是什么?

A×B={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}A \times B = \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}

定义9
集合A1,A2,...,AnA_1,A_2,\:...\:,A_n的笛卡尔积用A1×A2×...×AnA_1\times A_2\times\:...\:\times A_n表示,是有序n元组(a1,a2,...,an)(a_1,a_2,\:...\:,a_n) 的集合,其中aiAi,i=1,2,3,...,na_i \in A_i, i=1,2,3,...,n。换言之,

A1×A2×...×An={(a1,a2,...,an)aiAi,i=1,2,3,...,n}A_1\times A_2\times\:...\:\times A_n=\{(a_1,a_2,\:...\:,a_n)\: |\: a_i \in A_i,\:i=1,2,3,...,n\}

使用带两次的集合符号

有时我们通过特定的符号来显式地限定一个量化命题的论域。

  • xS(P(x))\forall\: x \in S(P(x))表示P(x)P(x)在集合SS所有元素上的全称量化。换句话说,xS(P(x))\forall\: x \in S(P(x))\:x(xSP(x))\:\forall\: x (x \in S \to P(x))的简写。

  • xS(P(x))\exist\: x \in S(P(x))表示P(x)P(x)在集合SS所有元素上的存在量化。即xS(P(x))\exist\: x \in S(P(x))\:x(xSP(x))\exist\: x(x \in S \land P(x))\:的简写。

这里的PP是一个命题,P(x)P(x)PP关于xx的命题。

语句xR(x20)\forall\: x \in R(x^2 \geq 0)声称对任意实数x,x20x, x^2 \geq 0。这个语句可以表达为“任意实数的平方是非负的”。这是一个真语句。
语句xZ(x2=1)\exist\: x \in Z(x^2 = 1)声称存在一个整数xx使得x2=1x^2=1。这个语句可以表达为“有某个整数,其平方是1”。这个语句也是一个真语句。

真值集合量词

给定谓词PP和论域DD,定义PP真值集(truth set)为DD中是P(x)P(x)为真的元素x组成的集合。P(x)P(x)的真值集记为{xDP(x)}\{x \in D | P(x)\}

例:PP的真值集{xZx=1}\{x \in \bf{Z}\enspace|\enspace|x| = 1\}是满足x=1|x|=1的整数集合。当x=1x=1x=1x=-1时有x=1|x|=1,而没有其他整数xx能满足,因此PP的真值集是{1,1}\{-1,1\}

集合运算

集合的基本运算

并集
AABB为集合,集合AABB的并集,用ABA\cup B表示,是一个集合,它包含AABB中或同时在AABB中的元素。

一个元素xx属于AABB的并集当且仅当xx属于AAxx属于BB。这说明

AB={xxAxB}A\cup B = \{x \enspace | \enspace x \in A \lor x \in B \}

交集
AABB为集合,集合AABB的交集,用ABA\cap B表示,是一个集合,它包含同时在AABB中的那些元素。

一个元素xx属于集合AABB的交集当且仅当xx属于AA并且xx属于BB。这说明

AB={xxAxB}A\cap B = \{x \enspace | \enspace x \in A \land x \in B \}

两个集合称为不相交的,如果它们的交集为空集。

集合基数的计算AB=A+BAB|A \cup B| = |A| + |B| - |A \cap B|。把这一结果推广到任意多个集合的并集就是所谓的包含排斥原理或简称容斥原理。容斥原理是枚举中的一项重要技术。

差集
AABB为集合,集合AABB的差集,用ABA - B表示,是一个集合,它包含属于AA而不属于BB的元素。AABB的差集也称为B相对于A的补集。

集合AABB的差集有时也记为 ABA \setminus B

一个元素xx属于AABB的差集当且仅当xAx \in AxBx \notin B,这说明

AB={xxAxB}A - B = \{x \enspace | \enspace x \in A \land x \notin B\}

补集
UU为全集。集合AA的补集,用A\overline{A}表示,是AA相对于UU的补集。所以集合AA的补集是UAU-A。补集也可以写成U\complement{_U}

一个元素x属于A当且仅当xAx \notin A。这说明

UA=A={xUxA}\complement{_U}{A} = \overline{A} = \{x \in U | x \notin A\}

{xUxA}\{x \in U | x \notin A\}是一个真值集,意为满足 xAx \notin A并且 xUx \in U的所有元素的集合。

集合恒等式

恒等式 名称
AU=A,A=AA \cap U = A,\enspace A\cup\varnothing = A 恒等率
AU=U,A=UA \cup U = U,\enspace A\cap\varnothing = U 支配率
AA=A,AA=AA \cap A = A,\enspace A\cup A = A 幂等率
(A)\overline{(\overline{A})} 补率
AB=BA,AB=BAA \cap B = B\cap A,\enspace A \cup B = B\cup A 交换率
A(BC)=(AB)CA(BC)=(AB)CA\cup(B\cup C)=(A\cup B)\cup C\\A\cap(B\cap C)=(A\cap B)\cap C 结合率
A(BC)=(AB)(AC)A(BC)=(AB)(AC)A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\\A\cap(B\cup C)=(A\cap B)\cup(A\cap C) 分配率
AB=ABAB=AB\overline{A\cap{B}}=\overline{A}\cup{\overline{B}}\\\overline{A\cup{B}}=\overline{A}\cap{\overline{B}} 德摩根率
A(AB)=AA(AB)=AA\cup(A\cap B)=A\\A\cap(A\cup B)=A 吸收率
AA=UAA=A\cup\overline{A}=U\\A\cap\overline{A}=\varnothing 互补率

分配率证明:
A(BC)=(AB)(AC)A\cup(B\cap C)=(A\cup B)\cap(A\cup C)

此题证明主要用到了逻辑运算中的分配率p(qr)=(pq)(pr)p \lor(q\land r) = (p \lor q)\land(p\lor r)

A(BC)={xxAx(BC)}={xxA(xBxC)}={x(xAxB)(xAxC)}={xxABxAC}=(AB)(AC)\begin{array}{lll} A\cup(B\cap C) &=\{x \enspace | \enspace x \in A \lor x \in(B \cap C)\}\\ &= \{x \enspace | \enspace x \in A \lor (x \in B \land x\in C)\}\\ &= \{x \enspace | \enspace (x \in A \lor x \in B)\land(x\in A \lor x \in C) \}\\ &= \{x \enspace | \enspace x \in A\cup B \land x \in A\cup C\}\\ &= (A\cup{B})\land(A\cup{C}) \end{array}

A(BC)=(AB)(AC)A\cap(B\cup C)=(A\cap B)\cup(A\cap C)的证明与上面类似。

德摩根率证明:

AB={xxAB}补集的定义={x¬(xAB)}不属于符号的含义={x¬(xAxB)}交集的定义={x¬(xA)¬(xB)}逻辑等价式的第一德摩根率={xxAxB}不属于符号的含义={xxAxB}补集的定义={xxAB}并集的定义=AB集合构造器记号的含义\begin{array}{lll} \overline{A \cap B} &= \{x \enspace | \enspace x \notin A\cap B\} & \small\text{补集的定义}\\ &= \{x \enspace | \enspace \lnot( x \in A\cap B)\} & \small\text{不属于符号的含义}\\ &= \{x \enspace | \enspace \lnot( x \in A \land x \in B)\} & \small\text{交集的定义}\\ &= \{x \enspace | \enspace \lnot(x \in A) \lor \lnot(x \in B) \} & \small\text{逻辑等价式的第一德摩根率}\\ &= \{x \enspace | \enspace x \notin A \lor x \notin B\} & \small\text{不属于符号的含义}\\ &= \{x \enspace | \enspace x \in \overline{A} \lor x \in \overline{B}\} & \small\text{补集的定义}\\ &= \{x \enspace | \enspace x \in \overline{A}\cup\overline{B}\} & \small\text{并集的定义}\\ &=\overline{A}\cup\overline{B} & \small\text{集合构造器记号的含义} \end{array}

扩展的并集和交集

由于集合的交集和并集满足结合律,所以只要AABBCC为集合,则ABCA\cup{B}\cup{C}ABCA\cap{B}\cap{C}均有定义,即这样的记号是无二义性的。我们不需要用括号来指明哪个运算在前。

  • ABCA\cup{B}\cup{C}包含那些至少属于AABBCC为中一个集合的元素。
  • ABCA\cap{B}\cap{C}包含那些属于AABBCC全部3个集合中的元素。
多个集合的并集
一组集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合。
我们用下列记号

A1A2...An=i=1nAiA_1 \cup A_2 \cup ... \cup A_n = \bigcup_{i=1}^{n}A_i

表示集合A1A2...AnA_1 \cup A_2 \cup ... \cup A_n的并集。

多个集合的交集
一组集合的交集是包含那些属于这组集合中所有成员集合的元素的集合。
我们用下列记号

A1A2...An=i=1nAiA_1 \cap A_2 \cap ... \cap A_n = \bigcap_{i=1}^{n}A_i

表示集合A1A2...AnA_1 \cap A_2 \cap ... \cap A_n的交集。

例题:Ai={i,i+i,i+2,...}A_i = \{i, i+i, i+2, ...\}i=1,2,3,...i=1,2,3,...。那么,

i=1nAi=i=1n{i,i+i,i+2,...}={1,2,3,...}\bigcup_{i=1}^{n}A_i=\bigcup_{i=1}^{n} \{i, i+i, i+2, ...\}=\{1,2,3,...\} \\

i=1nAi=i=1n{i,i+i,i+2,...}={n,n+1,n+2,...}=An\bigcap_{i=1}^{n}A_i=\bigcap_{i=1}^{n}\{i, i+i, i+2, ...\}=\{n, n+1,n+2,...\}=A_n

我们可以将并集和交集的记号扩展到其他系列的集合。

A1A2...An...=i=1AiA1A2...An...=i=1AiA_1 \cup A_2 \cup ... \cup A_n\cup ... = \bigcup_{i=1}^{\infty}A_i\\ A_1 \cap A_2 \cap ... \cap A_n\cap ... = \bigcap_{i=1}^{\infty}A_i

更一般地,当  I  \;I\;是一个集合时,可以用记号iIAi\bigcap_{i\in{I}} A_iiIAi\bigcup_{i\in{I}} A_i分别表示对于iIi \in I 的集合AiA_i的交集和并集。注意我们有

iIAi={xiI(xAi)}iIAi={xiI(xAi)}\textstyle\bigcap_{i\in{I}} A_i = \{x \enspace | \enspace \forall\: i \in I (x \in A_i)\} \text{和} \bigcup_{i\in{I}} A_i=\{x \enspace | \enspace \exist\: i \in I (x \in A_i)\}

例题: 假设对于i=1,2,3,...i=1,2,3,...,集合 Ai={1,2,3,...,i}A_i = \{1, 2, 3, ...,i\}。那么,

i=1Ai=i=1{1,2,3,,i}={1,2,3,}=Z+\bigcup_{i=1}^{\infty}A_i=\bigcup_{i=1}^{\infty} \{1,2,3,\dots,i\} = \{1,2,3,\dots\} = Z^+\\

i=1Ai=i=1{1,2,3,,i}={1}\bigcap_{i=1}^{\infty}A_i=\bigcap_{i=1}^{\infty} \{1,2,3,\dots,i\} = \{1\}\\

集合的计算机表示

利用二进制的位运算可以快速对集合进行各种运算。

U={1,2,3,4,5,6,7,8,9,10}U=\{1,2,3,4,5,6,7,8,9,10\},集合A={1,3,5,7,9}A = \{1,3,5,7,9\}B={2,4,6,8,10}B = \{2,4,6,8,10\},将集合元素在全集中的位置标记为A,不在的位置标记为0,则

A=1010101010B=0101010101AB=10101010100101010101=1111111111=UAB=10101010100101010101=0000000000=A=¬1010101010=0101010101=B\begin{array}{ll} A &= 10\: 1010\: 1010\\ B &= 01\: 0101\: 0101\\ A\cup{B} &= 10\: 1010\:1010 \lor01\: 0101\: 0101=11\: 1111\: 1111 = U\\ A\cap{B} &= 10\: 1010\:1010 \land01\: 0101\: 0101=00\: 0000\: 0000 = \varnothing\\ \overline{A} &= \lnot 10\: 1010\: 1010 = 01\: 0101\: 0101 = B \end{array}

评论

Power by 不蒜子
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×