跳到主要内容

2.1. 集合

这一节我们将研究最基本的离散结构--集合，所有其他离散结构都建立与集合之上。集合可用于把对象聚集在一起。通常，一个集合中的对象都有相似的性质。

DEFINITION 集合

集合是对象的一个无序的聚集，对象也称为集合的元素（element）或成员（member）。集合包含（contain）它的元素。我们用a∈Aa \in A来表示aa是集合AA中的一个元素。而记号a∉Aa \notin A表示aa不是集合AA中的一个元素。

DEFINITION 空集

不含任何元素的集合称为空集，用∅\varnothing表示

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

在同一个集合中的诸元素中并不一定存在确定的关系。

为了体系的严谨性，我们规定：对于任意集合AA都有A∉AA \notin A

集合的三种表示方法：​

  • 列举法或花名册方法（roster method） 或外延表示法：{1,2,3...}\{1,2,3...\}
  • 描述法或集合构造器（set builder） {x∣P(x)}\{x | P(x)\}
  • 维恩（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={pq∣p∈Z,q∈Z,且q≠0}\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] 称为是从aa到bb的闭区间，而(a,b)(a,b)称为是从aa到bb的开区间。

集合相等​

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

子集​

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

A⊆BA\subseteq{B} 当且仅当量化式∀x(x∈A→x∈B)\forall{x(x\in{A} \rightarrow x\in{B})}

  • 证明AA是BB的子集： 要证明A⊆BA\subseteq{B}，需要证明如果xx属于AA则也属于BB
  • 证明AA不是是BB的子集： 要证明A⊈BA\nsubseteq{B}，需要找一个x∈Ax\in A使得x∉Bx \notin B
  • 证明两个集合相等： 要想证明两个集合AA和BB相等，就证明A⊆BA \subseteq B和B⊆AB\subseteq A

对于任意集合SS，∅⊆S\varnothing\subseteq{S}和S⊆SS\subseteq{S}

证明∅⊆S\varnothing\subseteq{S}
为了证明∅⊆S\varnothing\subseteq{S}，就必须证明∀x(x∈∅→x∈S)\forall{x(x\in\varnothing \rightarrow x\in{S})}为真。因为空集没有元素，所以x∈∅x\in\varnothing总是假。因此x∈∅→x∈Sx\in\varnothing \rightarrow x\in{S}总是真。

真子集
集合AA是集合BB的子集但是A≠BA\neq B是，就写成A⫋BA\subsetneqq{B}，并说集合AA是集合BB的真子集。
∀x(x∈A→x∈B)∧∃ x(x∈B∧x∉A)\forall{x}(x \in A \rightarrow x \in B) \land \exist\: x(x \in B \land x \notin A)

集合的大小​

令SS为集合。如果SS中恰好有nn个不同的元素，这里nn是非负整数，我们就说SS是有限集，而nn是SS的技术。SS的基数或势（cardinality）记为∣S∣|S|或#A\#A或card(A)card(A)

若∣A∣<∞|A| < \infty，则称AA为有限集或有穷集(finite set)，否则称A为无限集或无穷集(infinite set)

∣{a,b,a,1,2}∣=4|\{a, b, a, 1, 2\}| = 4 按照集合的定义，两个aa是同一个元素，所以计数只记1.

幂集​

给定集合SS，SS的幂集（power set）是集合幂集所有子集的集合。SS的幂集记为P(S)\mathcal{P}(S)或P(S)\mathscr{P}(S)（都是字母P，不同的教材使用不同的格式表示）

集合{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({∅})={∅,{∅}}\begin{array}{rl} \mathcal{P}(\varnothing) &= \{\varnothing\}\\ \mathcal{P}(\{\varnothing\}) &= \{\varnothing,\{\varnothing\}\} \end{array}

笛卡儿积​

定义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,...,n有ai=bia_i=b_i。特别地，有序二元组称为序偶（ordered pair）。

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

定义8
令AA和BB为集合。AA和BB的笛卡尔积（Cartesian product）用A×BA \times B表示，是所有序偶(a,b)(a,b)的集合，其中a∈Aa \in A 且 b∈Bb \in B。于是，
A×B={(a,b) ∣ a∈A∧b∈B}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) 的集合，其中ai∈Ai,i=1,2,3,...,na_i \in A_i, i=1,2,3,...,n。换言之，
A1×A2× ... ×An={(a1,a2, ... ,an) ∣ ai∈Ai, 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\}

使用带两次的集合符号​

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

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

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

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

语句∀ x∈R(x2≥0)\forall\: x \in R(x^2 \geq 0)声称对任意实数x,x2≥0x, x^2 \geq 0。这个语句可以表达为“任意实数的平方是非负的”。这是一个真语句。
语句∃ x∈Z(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)的真值集记为{x∈D∣P(x)}\{x \in D | P(x)\}。

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