集合的基数
基数的定义
集合A,B若存在双射\(f:A\to B\),则称A,B等势(基数相同),记为\(A\sim B\).
A的基数记为\(|A|\).
自然数集\(N\)的基数记为\(|N|=\aleph_0\). 与N等势的集合称为可列集。可列个可列集之并仍可列。
实数集\(R\)的基数记为\(\aleph_1\). 任何区间与R等势。
基数的比较
设集合A,B。若存在从A到B的单射,则称A的基数小于等于B的基数,记为\(|A|\le |B|\). 若还已知\(|A|\ne |B|\), 则记为\(|A| < |B|\).
定理1. 若\(|A|\le |B|, |B|\le |A|\)则\(|A|=|B|\).
定理2. 对任意集合A,B:\[|A| > |B|, |A|=|B|, |B| > |A|\]三者恰有一个成立。
定理3.(选择公理) 设集合族\(A=\{A_a|a\in S\}\)中的元素都是非空集。则存在定义在S上的函数\(f\), 对\(\forall a\in S\), 有\(f(a)\in A_a\).
定理4.(Cantor)任意集合A,必有\[|A| < |\rho(A)|.\]
基数的运算
定义. 设\(\kappa,\lambda\)是两个基数。
(a) \(\kappa+\lambda:= |K\cup L|\). 这里\(K\cap L =\emptyset,|K|=\kappa, |L|=\lambda\).
(b) \(\kappa\cdot\lambda := |K\times L|\).
(c) \(\kappa^\lambda:= |{}^{L}\!K|\). 这里\({}^L\! K\)表示从L到K的所有映射组成的集合。
定理5. 设\(K_1\sim K_2, L_1\sim L_2\).
(a) 若\(K_i\cap L_i= \emptyset\), 则\(K_1\cup L_1\sim K_2\cup L_2\).
(b) \(K_1\times L_1\sim K_2\sim L_2\).
(c) \({}^{L_1}\! K_1\sim {}^{L_2}\! K_2\).
定理6. 基数的运算性质。设\(\kappa, \lambda, \mu\)是三个基数。则
(1) 加法/乘法交换律;
(2) 加法/乘法结合律;
(3) 分配律;
(4) \(\kappa^{\lambda+\mu} = \kappa^\lambda \cdot \kappa^\mu\);
(5) \((\kappa\cdot\lambda)^\mu = \kappa^\mu\cdot \lambda^\mu\);
(6) \((\kappa^\lambda)^\mu = \kappa^{\lambda\cdot \mu}\).
定理7. 设\(\kappa, \lambda, \mu\)是三个基数, \(\kappa\le \lambda\)。则
(1) \(\kappa+ \mu \le \lambda+\mu\);
(2) \(\kappa\cdot \mu \le \lambda\cdot \mu\);
(3) \(\kappa^\mu\le \lambda^\mu\);
(4) \(\mu^\kappa\le \mu^\lambda\).
定理8. 设\(\kappa\)为任意无穷基数。则\(\kappa\cdot\kappa = \kappa\).
推论9. 设\(\kappa\)为任意无穷基数,则\(\kappa^\kappa = 2^\kappa\).
推论10. 设\(\kappa_1 < \lambda_1, \kappa_2 < \lambda_2\). 则
(1) \(\kappa_1+\kappa_2 < \lambda_1 + \lambda_2\);
(2) \(\kappa_1\cdot\kappa_2 < \lambda_1 \cdot \lambda_2\).
    所属分类:离散数学     发表于2022-03-27