本文旨在整理一些集合论中的基础概念与定理，主要出处见参考文献。
本文只列出特别简单的证明，略去复杂的证明。
1 集合论基础
首先，我们介绍Cartesian product（笛卡尔积、直积）(A imes B)，就是从(A)中、(B)中各取一个元素组成的有序数对。如果是(n)个集合，它们的Cartesian product就是一个(n)-tuples：
所谓Relation（关系），是(A imes A)的任一子集，就叫a relation (R) on set (A)。如果((x,y)in R)，则可写为(xRy)。(R)可能的性质有：
- Reflexive（自反性）：(xRx)；
- Symmetric（对称性）：若(xRy)则必有(yRx)；
- Antisymmetric（反对称）：若(xRy)且(yRx)，则必有(x=y)；
- Transitive（传递性）：若(xRy)且(yRz)，则必有(xRz)。
Equivalence relation（等价关系），就是自反、对称、传递的关系。
给定(A)上的一个equivalence relation (R)，那么(A)中的元素(x)的equivalence class（等价类），就是集合(E_x = {yin A:xRy})。若(E_x)和(E_y)是(x)和(y)的等价类，那么必有(E_xcap E_y=empty)或(E_x=E_y)。
自反、反对称、传递的relation，就叫partial ordering（偏序），可以用符号(geq)或(leq)表示。对于任意partial ordering，如果将其中的((x,x))元素剔除，就变成了strict ordering，用符号(gt)或(lt)表示，这种relation不再是自反的和反对称的，但依旧有传递性。如果对于集合(A)，每一对((x,y)in A imes A)都满足(xlt y)、(xgt y)或(x=y)这三种中的一种，那么称(A)是linearly ordered。再进一步，定义集合(A)的最小元素为(ain A)，它满足(forall xin A, aleq x)（最大元素可类似定义），那么，如果linearly ordered(A)的每一个子集都有一个最小元素，则称(A)是well-ordered。
一个mapping/transformation/function定义为(T:Xmapsto Y)，这是一种将(X)中的每个元素与(Y)中唯一一个元素联系起来的规则。(X)称为domain（定义域），(Y)为codomain（到达域），集合(G_T={(x,y):xin X,y=T(x)}subseteq X imes Y)称为graph of (T)。集合(T(A)={T(x):xin A}subseteq Y)称为(A)在(T)下的image，对于(Bsubseteq Y)，集合(T^{-1}(B)={x:T(x) in B}subseteq X)称为(B)在(T)下的inverse image。集合(T(X))称为(T)的range（值域），若(T(X)=Y)则称该mapping为from (X) onto (Y)，中文叫满射，否则是into (Y)。若每个(y)都是唯一的(xin X)的image，则该mapping是one-to-one，或记为(1)-(1)，中文叫单射。
当(X)中的每个元素与(Y)中不一定唯一的元素对应起来的规则，称为correspendence，(T^{-1})就是一个correspendence，但未必是mapping。若mapping是(1)-(1)且是onto的，则称该mapping为one-to-one correspendence。如果在(X)和(Y)上都定义了partial ordering，那么如果对于一个mapping，(T(x_1)leq T(x_2))当且仅当(x_1leq x_2)，就称该mapping为order-preserving。若(X)是partial ordered，用(leq)表示，那么一个(1)-(1) mapping可以induce（诱导）在codomain上的一个partial ordering。若这个mapping还是onto，那么(X)上的linear ordering可以induce一个(Y)上的linear ordering。
集合中的元素个数称为集合的cardinality或cardinal number（基数）。若(A)与(B)之间存在(1)-(1) correspondence，那么两个集合equipotent（等势）。
2 可数集合
将正自然数集合(N^+)的cardinal number记为(aleph)。如果一个无限集合中的元素，与(N^+)中的元素存在(1-1) correspondence，那么称该集合为countable或denumerable（可数的）。
整数集(Z)是可数的，因为对于任意(nin N^+)，让它对应于(lfloor n/2 floor (-1)^nin Z)即可。
定理：有理数集(Q)可数。
定理：The union of a countable collection of countable sets is a countable set.
注：Collection有的地方翻译为“搜集”，可理解为允许有重复元素的集合。
3 实数连续统
定理：实数集(R)是不可数的。
记(R)的cardinal number为(c)，则有(aleph<c)。
定理：任意开区间不可数。
定理：任意开区间与(R)是equipotent的。
对于开区间((a,b))，将任意(xin R)映射为(y=dfrac{a+b}{2}+dfrac{(b-a)x}{2(1+|x|)})可证。
定理：实数平面(R^2=R imes R)与(R)是equipotent的。
定理：任意开区间都包含至少一个有理数。
对于开区间((a,b))，不妨假设(ageq 0)，取(q)为比(1/(b-a))大的最小整数，取(p)为比(qb)大的最小整数，则必有((p-1)/q in (a,b))，而((p-1)/q in Q)。
推论：Every collection of disjoint open intervals is countable.
因为每个开区间都至少包含一个有理数，这些不相连的开区间的collection可用其中每个开区间中的任一有理数建立对应关系，而有理数集是可数的。
下面再介绍一些有关集合的定义。集合(Asubset R)的supremum，如果存在，就是对于任意(xin A)都满足(xleq y)的最小的(y)，可写为(sup A)；反之可定义集合(A)的infimum，写为(inf A)。对于(R)的某个子集，如果有上界，必有supremum，如果有下界，必有infimum。若定义extended real line (ar R=Rcup {-infty,+infty})（即将无穷大也看作一个元素），那么所有集合都有supremum和infimum。另外记(ar R^+=Rcup{+infty})。
4 集合的序列
Monotone sequence（单调序列）就是non-decreasing（指(forall n, A_nsubseteq A_{n+1})）或non-increasing指(forall n, A_{n}supseteq A_{n+1})）的序列，也有严格的单调序列，即将包含关系换成严格包含关系(subset)和(supset)。
序列的limit（极限）(A)，就是对于non-decreasing序列的(A=cup_{n=1}^{infty}A_n)，或对于non-increasing序列的(A=cap_{n=1}^{infty}A_n)，分别可写为(A_nuparrow A)和(A_ndownarrow A)，或一般地，(limlimits_{n oinfty}A_n = A)，或(A_n o A)。
对于任意集合序列({A_n})，集合(B_n=cup_{m=n}^{infty}A_m)必为non-increasing序列，因此(B=limlimits_{n oinfty}B_n)存在，称它为({A_n})的superior limit，写为(limsup_n A_n)。反之，non-decreasing序列(C_n=cap_{m=n}^{infty}A_m)的极限(C)，就是({A_n})的inferior limit，写为(liminf_n A_n)。正式定义为
由De Morgan' s laws，(liminf_n A_n = left(limsup_n A_n^c ight)^c)。
(limsup_n A_n)其实就是infinitely many（无穷多）个(A_n)中都含有的元素的集合，(liminf_n A_n)就是all but a finite number（除有限）个(A_n)外，其他(A_n)中都含有的元素的集合。
以上概念提供了一种集合序列的收敛准则：(liminf_n A_nsubseteq limsup_n A_n)，若两个集合不相等，则说明({A_n})不收敛。
5 子集的类
所有(X)的子集的集合成为(X)的power set（幂集），记为(2^X)。对于一个countable set，认为它的power set有(2^aleph)个元素。
定理：(2^aleph = c)。
接下来，要研究的是给定集合的子集的一些性质。Power set一般对研究的问题来说会显得太大了，以下的一系列定义，目的是要定义出(2^X)的某个子集，使得该子集对于研究的问题来说足够大，而其性质又让我们可以容易地处理。一般方法是，先选出一些已知性质的集合，组成一个基本的collection，再用一些特定操作，创造出新的集合加入其中。
定义 Ring（环）：由集合(X)的子集组成的非空类（nonempty class）(mathscr{R})，若满足如下性质则为ring：
- (emptyinmathscr{R})；
- 若(Ainmathscr{R})且(Binmathscr{R})，则(Acup Bin mathscr{R})，(Acap Bin mathscr{R})，(A- Bin mathscr{R})。
Ring对于union、intersection、difference的操作是closed（闭的）。但ring中不一定含有全集(X)自身，若加入(X)，就成了field（或algebra）定义：
定义 Field（域）：由(X)的子集组成的class(mathscr{F})，若满足如下性质则为field：
- (Xinmathscr{F})；
- 若(Ainmathscr{F})，则(A^cinmathscr{F})；
- 若(Ainmathscr{F})且(Binmathscr{F})，则(Acup Bin mathscr{F})。
如果给定了一个collection(mathscr{C})，将它理解为“种子”，去生成field，那么称最小的含有(mathscr{C})的field为field generated by (mathscr{C})。
Ring和field的概念在概率论中应用起来还是会有些限制，因此引入以下定义：
定义 Semi-ring：由集合(X)的子集组成的非空类（nonempty class）(mathscr{S})，若满足如下性质则为semi-ring：
- (emptyinmathscr{S})；
- 若(Ainmathscr{S})且(Binmathscr{S})，则(Acap Bin mathscr{S})；
- 若(Ainmathscr{S})、(Binmathscr{S})且(A subseteq B)，则(exist nlt infty)，使得(B-A=cup_{j=1}^{n} C_j)，其中(C_jinmathscr{S})且对于(j eq j')来说(C_jcap C_{j'}=empty)。
其中的第三个性质，简单来说就是(mathscr{S})中任意两个集合的的差，可以分解为有限个(mathscr{S})中集合的union。
再在semi-ring中加入(X)自身，就变成了semi-algebra。
6 Sigma fields
上一节说到field对complement和finite union的操作是closed，我们接着将它的finite union操作扩展到极限处，这就有了如下概念。
定义 (sigma)-field（sigma-algebra）：由(X)的子集组成的class(mathscr{F})，若满足如下性质则为sigma-field：
- (Xinmathscr{F})；
- 若(Ainmathscr{F})，则(A^cinmathscr{F})；
- 若({A_n,nin N^+})为(mathscr{F})中的集合的序列，则(cup_{n=1}^{infty} A_nin mathscr{F})。
(sigma)-field对于complement和countable union是closed。若给定一个collection(mathscr{C})，所有含有(mathscr{C})的(sigma)-field的交集，就叫(sigma)-field generated by (mathscr{C})，可记为(sigma(mathscr{C}))。
定理：若(mathscr{C})是一个finite collection，则(sigma(mathscr{C}))也是finite，否则(sigma(mathscr{C}))总是uncountable。
若取(X=R)，(mathscr{C}={(-infty,r]: rin Q})，则(sigma(mathscr{C}))就叫Borel field of (R)，一般可记为(mathscr{B})。许多不同的collection都可以生成出(mathscr{B})。若给定一个实区间(I)，则(mathscr{B}_I = {Bcap I: Binmathscr{B}})称为the restnctlon of (mathscr{B}) to (I)，或Borel field on (I)。事实上，(mathscr{B}_I)可由(mathscr{C}={(-infty,r]cap I: rin Q})生成。
对于两个(sigma)-field的union不一定是(sigma)-field，将最小的包含了两个(sigma)-field(mathscr{F})和(mathscr{G})中所有元素的(sigma)-field记为(mathscr{F}veemathscr{G})。但对于两个(sigma)-field的intersection(mathscr{F}capmathscr{G}={A:Ain mathscr{F} quad ext{and} quad A inmathscr{G}})，它必定是(sigma)-field，为了统一符号，可以写为(mathscr{F}wedgemathscr{G})，它就是保证元素同时属于(mathscr{F})和(mathscr{G})的最大的(sigma)-field。这两个概念都可以推广到可数多个的情形。
概率论和测度论中，大量的工作都是在证明某个class of sets是(sigma)-field。对于证明来说，(sigma)-field定义中的三条性质，前两条都很容易验证，但最后一条要验证却很困难。为此我们定义一种monotone class（单调类）(mathscr{M})，它也是由一些集合组成：若({A_n})是monotone sequence，有极限(A)，且(forall n, A_ninmathscr{M})，则(Ain mathscr{M})，称这样的(mathscr{M})为monotone class。利用它和下面的定理，可以方便地证明一些class是(sigma)-field。
定理：(mathscr{F})是(sigma)-field，当且仅当(mathscr{F})是field且它是一个monotone class。
利用这个定理，在考虑一个class是不是(sigma)-field时，我们只需要考虑monotone sequences的极限是否属于它即可。
另一个常用的技巧是Dynkin's (pi)-(lambda) Theorem。对此需要先介绍两个概念做铺垫。
定义 (pi)-system：有一个class(mathscr{P})，若(Ainmathscr{P})且(Binmathscr{P})，则(Acap B in mathscr{P})，那么(mathscr{P})就是(pi)-system。
定义 (lambda)-system：有一个class(mathscr{L})，若它满足以下性质，那么(mathscr{L})就是(lambda)-system：
- (Xin mathscr{L})；
- 若(Ainmathscr{L})、(Binmathscr{L})且(Bsubseteq A)，则(A-Binmathscr{L})；
- 若({A_ninmathscr{L}})是non-decreasing sequence，且(A_nuparrow A)，则(Ainmathscr{L})。
前两个条件说的是(lambda)-system对于complement是closed。并且由于第二条意味着(forall n, B_n=A_{n+1}-A_ninmathscr{L})，所以第三条也说明了，(mathscr{L})中的disjoint sets的countable union依然在(mathscr{L})中。利用这点，有以下定理。
定理：一个class(mathscr{L})是(lambda)-system，当且仅当：
- (Xin mathscr{L})；
- 若(Binmathscr{L})，则(B^cinmathscr{L})；
- 若({A_ninmathscr{L}})是disjoint sequence，则(cup_n A_ninmathscr{L})。
(sigma)-field必定是(lambda)-system，同时是(pi)-system和(lambda)-system的class必定是(sigma)-field。
下面的定理用到了这些定义。
定理 Dynkin's (pi)-(lambda) Theorem：若(mathscr{P})是一个(pi)-system，(mathscr{L})是一个(lambda)-system，且(mathscr{P}subseteq mathscr{L})，则(sigma(mathscr{P})subseteq mathscr{L})。
参考文献
- Davidson, J., 1994. Stochastic limit theory: An introduction for econometricians. OUP Oxford.