数学基础系列:集合与数
本文旨在整理一些集合论中的基础概念与定理,主要出处见参考文献。
本文只列出特别简单的证明,略去复杂的证明。
1 集合论基础
首先,我们介绍Cartesian product(笛卡尔积、直积),就是从中、中各取一个元素组成的有序数对。如果是个集合,它们的Cartesian product就是一个-tuples:
所谓Relation(关系),是的任一子集,就叫a relation on set 。如果,则可写为。可能的性质有:
- Reflexive(自反性):;
- Symmetric(对称性):若则必有;
- Antisymmetric(反对称):若且,则必有;
- Transitive(传递性):若且,则必有。
Equivalence relation(等价关系),就是自反、对称、传递的关系。
给定上的一个equivalence relation ,那么中的元素的equivalence class(等价类),就是集合。若和是和的等价类,那么必有或。
自反、反对称、传递的relation,就叫partial ordering(偏序),可以用符号或表示。对于任意partial ordering,如果将其中的元素剔除,就变成了strict ordering,用符号或表示,这种relation不再是自反的和反对称的,但依旧有传递性。如果对于集合,每一对都满足、或这三种中的一种,那么称是linearly ordered。再进一步,定义集合的最小元素为,它满足(最大元素可类似定义),那么,如果linearly ordered的每一个子集都有一个最小元素,则称是well-ordered。
一个mapping/transformation/function定义为,这是一种将中的每个元素与中唯一一个元素联系起来的规则。称为domain(定义域),为codomain(到达域),集合称为graph of 。集合称为在下的image,对于,集合称为在下的inverse image。集合称为的range(值域),若则称该mapping为from onto ,中文叫满射,否则是into 。若每个都是唯一的的image,则该mapping是one-to-one,或记为-,中文叫单射。
当中的每个元素与中不一定唯一的元素对应起来的规则,称为correspendence,就是一个correspendence,但未必是mapping。若mapping是-且是onto的,则称该mapping为one-to-one correspendence。如果在和上都定义了partial ordering,那么如果对于一个mapping,当且仅当,就称该mapping为order-preserving。若是partial ordered,用表示,那么一个- mapping可以induce(诱导)在codomain上的一个partial ordering。若这个mapping还是onto,那么上的linear ordering可以induce一个上的linear ordering。
集合中的元素个数称为集合的cardinality或cardinal number(基数)。若与之间存在- correspondence,那么两个集合equipotent(等势)。
2 可数集合
将正自然数集合的cardinal number记为。如果一个无限集合中的元素,与中的元素存在 correspondence,那么称该集合为countable或denumerable(可数的)。
整数集是可数的,因为对于任意,让它对应于即可。
定理:有理数集可数。
定理:The union of a countable collection of countable sets is a countable set.
注:Collection有的地方翻译为“搜集”,可理解为允许有重复元素的集合。
3 实数连续统
定理:实数集是不可数的。
记的cardinal number为,则有。
定理:任意开区间不可数。
定理:任意开区间与是equipotent的。
对于开区间,将任意映射为可证。
定理:实数平面与是equipotent的。
定理:任意开区间都包含至少一个有理数。
对于开区间,不妨假设,取为比大的最小整数,取为比大的最小整数,则必有,而。
推论:Every collection of disjoint open intervals is countable.
因为每个开区间都至少包含一个有理数,这些不相连的开区间的collection可用其中每个开区间中的任一有理数建立对应关系,而有理数集是可数的。
下面再介绍一些有关集合的定义。集合的supremum,如果存在,就是对于任意都满足的最小的,可写为;反之可定义集合的infimum,写为。对于的某个子集,如果有上界,必有supremum,如果有下界,必有infimum。若定义extended real line (即将无穷大也看作一个元素),那么所有集合都有supremum和infimum。另外记。
4 集合的序列
Monotone sequence(单调序列)就是non-decreasing(指)或non-increasing指)的序列,也有严格的单调序列,即将包含关系换成严格包含关系和。
序列的limit(极限),就是对于non-decreasing序列的,或对于non-increasing序列的,分别可写为和,或一般地,,或。
对于任意集合序列,集合必为non-increasing序列,因此存在,称它为的superior limit,写为。反之,non-decreasing序列的极限,就是的inferior limit,写为。正式定义为
由De Morgan' s laws,。
其实就是infinitely many(无穷多)个中都含有的元素的集合,就是all but a finite number(除有限)个外,其他中都含有的元素的集合。
以上概念提供了一种集合序列的收敛准则:,若两个集合不相等,则说明不收敛。
5 子集的类
所有的子集的集合成为的power set(幂集),记为。对于一个countable set,认为它的power set有个元素。
定理:。
接下来,要研究的是给定集合的子集的一些性质。Power set一般对研究的问题来说会显得太大了,以下的一系列定义,目的是要定义出的某个子集,使得该子集对于研究的问题来说足够大,而其性质又让我们可以容易地处理。一般方法是,先选出一些已知性质的集合,组成一个基本的collection,再用一些特定操作,创造出新的集合加入其中。
定义 Ring(环):由集合的子集组成的非空类(nonempty class),若满足如下性质则为ring:
- ;
- 若且,则,,。
Ring对于union、intersection、difference的操作是closed(闭的)。但ring中不一定含有全集自身,若加入,就成了field(或algebra)定义:
定义 Field(域):由的子集组成的class,若满足如下性质则为field:
- ;
- 若,则;
- 若且,则。
如果给定了一个collection,将它理解为“种子”,去生成field,那么称最小的含有的field为field generated by 。
Ring和field的概念在概率论中应用起来还是会有些限制,因此引入以下定义:
定义 Semi-ring:由集合的子集组成的非空类(nonempty class),若满足如下性质则为semi-ring:
- ;
- 若且,则;
- 若、且,则,使得,其中且对于来说。
其中的第三个性质,简单来说就是中任意两个集合的的差,可以分解为有限个中集合的union。
再在semi-ring中加入自身,就变成了semi-algebra。
6 Sigma fields
上一节说到field对complement和finite union的操作是closed,我们接着将它的finite union操作扩展到极限处,这就有了如下概念。
定义 -field(sigma-algebra):由的子集组成的class,若满足如下性质则为sigma-field:
- ;
- 若,则;
- 若为中的集合的序列,则。
-field对于complement和countable union是closed。若给定一个collection,所有含有的-field的交集,就叫-field generated by ,可记为。
定理:若是一个finite collection,则也是finite,否则总是uncountable。
若取,,则就叫Borel field of ,一般可记为。许多不同的collection都可以生成出。若给定一个实区间,则称为the restnctlon of to ,或Borel field on 。事实上,可由生成。
对于两个-field的union不一定是-field,将最小的包含了两个-field和中所有元素的-field记为。但对于两个-field的intersection,它必定是-field,为了统一符号,可以写为,它就是保证元素同时属于和的最大的-field。这两个概念都可以推广到可数多个的情形。
概率论和测度论中,大量的工作都是在证明某个class of sets是-field。对于证明来说,-field定义中的三条性质,前两条都很容易验证,但最后一条要验证却很困难。为此我们定义一种monotone class(单调类),它也是由一些集合组成:若是monotone sequence,有极限,且,则,称这样的为monotone class。利用它和下面的定理,可以方便地证明一些class是-field。
定理:是-field,当且仅当是field且它是一个monotone class。
利用这个定理,在考虑一个class是不是-field时,我们只需要考虑monotone sequences的极限是否属于它即可。
另一个常用的技巧是Dynkin's - Theorem。对此需要先介绍两个概念做铺垫。
定义 -system:有一个class,若且,则,那么就是-system。
定义 -system:有一个class,若它满足以下性质,那么就是-system:
- ;
- 若、且,则;
- 若是non-decreasing sequence,且,则。
前两个条件说的是-system对于complement是closed。并且由于第二条意味着,所以第三条也说明了,中的disjoint sets的countable union依然在中。利用这点,有以下定理。
定理:一个class是-system,当且仅当:
- ;
- 若,则;
- 若是disjoint sequence,则。
-field必定是-system,同时是-system和-system的class必定是-field。
下面的定理用到了这些定义。
定理 Dynkin's - Theorem:若是一个-system,是一个-system,且,则。
参考文献
- Davidson, J., 1994. Stochastic limit theory: An introduction for econometricians. OUP Oxford.