集合的概念及运算

容斥原理
设\(A_1\cdots A_n\)是有限集合。则
\[|\bigcup_{i=1}^n A_i| = \sum |A_i| - \sum |A_i\cap A_j| + \cdots + (-1)^{n-1} |A_1\cap \cdots \cap A_n|\]

集合列的上、下极限
\[\overline{\lim}A_n = \bigcap_n\bigcup_{k\ge n} A_k\]\[\underline{\lim}A_n = \bigcup_n\bigcap_{k\ge n} A_k\]


集合的特征函数
\[\chi_A(x)=\begin{cases}1,& x\in A\\ 0, & x\not \in A\end{cases}\]
特征函数的一些性质：
(1) \(\chi_{A\cap B} = \chi_A\cdot \chi_B\)
(2) \(\chi_{\bar A} = 1-\chi_A\)
(3) \(\chi_{A\cup B} = \chi_A + \chi_B - \chi_A\cdot \chi_B\)
(4) \(\chi_{A\oplus B} = |\chi_A - \chi_B|\)

对于多重集合，\(\chi_A(x)\)表示元素x在集合A中的重数。我们有：
(1) \(\chi_{A\cap B} = \min\{\chi_a, \chi_B\}\)
(2) \(\chi_{A\oplus B} = |\chi_A - \chi_B|\)

    所属分类：离散数学     发表于2022-03-24