集合论

[TOC]

Set Theory

extension（外延）：像是列举法

intension（内涵）:像是描述法

empty set :空集

universal set :全集

Cardinality : 基数

​ Card(A): the number of elements of set A

几个概念:

a family of sets 集合族：A is a family set of sets over S if each element in A is a subset of S.

$\bigcup{A}$：A的广义并：$\bigcup{A}={x:(\exist{z})(z\in{A}\and{x\in{z})}}$

$\bigcap{A}$：A的广义交：$\bigcap{A}={x:(\forall{z})(z\in{A}\rightarrow{x\in{z}})}$

*注：$\bigcap{\empty}$ is undefined while $\bigcup{\empty}=\empty$

power set :幂集

相关结论：

(1) $A \subseteq B \Leftrightarrow 2^A \subseteq 2^B$

(2) $2^A \in 2^B \Rightarrow A \in B$：$\Leftarrow$的反例：

(3) $2^A \cap 2^B=2^{A \cap B}$

(4) $2^A \cup 2^B \subseteq 2^{A \cup B}$：（比如$A={1,2,3,4}$$B={1,2,5,6}$很显然$2^A \cup 2^B$ 和$2^{A \cup B}$不一样大

Transitive Set(传递集):

相关性质：

证明

有序对:

1.$\langle x, y\rangle:={{x},{x, y}}$

2.$\langle a, b, c, d\rangle=\langle\langle a, b, c\rangle, d\rangle=\langle\langle\langle a, b\rangle, c\rangle, d\rangle$

3.Cartisian Product (笛卡尔积)

4.

5.$A \times B \subseteq C \times D$ iff $A \subseteq C$ and $B \subseteq D$ Proof

关系

1.<a,b>$\in$R $\Leftrightarrow$aRb

2.Identity Relation（恒等关系）：

3.Universal Relation（全域关系）：

4.Empty Relation（空关系）：

5.$\operatorname{fld}(R)=\bigcup \bigcup R$ –证明

6.某个关系的一些运算：

7.结论

(1) $R \circ(S \cup W)=(R \circ S) \cup(R \circ W)$ (2) $(R \cup S) \circ W=(R \circ W) \cup(S \circ W)$ (3) $R \circ(S \cap W) \subseteq(R \circ S) \cap(R \circ W)$ (4) $(R \cap S) \circ W \subseteq(R \circ W) \cap(S \circ W)$

8.关系的一些性质：

性质：—proof

(1) If $R_1, R_2 \subseteq A \times A$ are reflexive, then $R_1^{-1}, R_1 \cap R_2, R_1 \cup R_2$ are reflexive. (2) If $R_1, R_2 \subseteq A \times A$ are symmetric, then $R_1^{-1}, R_1 \cap R_2, R_1 \cup R_2$ are symmetric. (3) If $R_1, R_2 \subseteq A \times A$ are transitive, then $R_1^{-1}, R_1 \cap R_2$ are transitive. (4) If $R_1, R_2 \subseteq A \times A$ are antisymmetric, then $R_1^{-1}, R_1 \cap R_2$ are antisymmetric.

闭包

性质：proof

(1) If $R$ is symmetric/reflexive/transitive, then $s(R)=R$ or $r(R)=R$ or $t(R)=R$. (2) If $R_1 \subseteq R_2$, then $r\left(R_1\right) \subseteq r\left(R_2\right), s\left(R_1\right) \subseteq s\left(R_2\right)$ and $t\left(R_1\right) \subseteq t\left(R_2\right)$ (3) $r\left(R_1\right) \cup r\left(R_2\right)=r\left(R_1 \cup R_2\right)$ (4) $s\left(R_1\right) \cup s\left(R_2\right)=s\left(R_1 \cup R_2\right)$ (5) $t\left(R_1\right) \cup t\left(R_2\right) \subseteq t\left(R_1 \cup R_2\right)$

more: proof

(1) If $R$ is reflexive, then $s(R)$ and $t(R)$ are also reflexive. (2) If $R$ is symmetric, then $r(R)$ and $t(R)$ are also symmetric. (3) If $R$ is transitive, then $r(R)$ is also transitive.

other:

(1) $r(s(R))=s(r(R))$ (2) $r(t(R))=t(r(R))$ (3) $s(t(R)) \subseteq t(s(R))$

等价关系：Equivalence Relation

1.一些概念

相容关系：Tolerance Relation

1.reflexive and symmetric

2.tolerance class 相容类

3.maximal tolerance class 最大相容类

覆盖：cover

1. definition

偏序： Partial Order

1.poset 偏序集 ：$<A,R>$

2.we say y covers x if :

$(x \leq y) \wedge(x \neq y) \wedge \neg(\exists z)(z \in A \wedge x \leq z \wedge z \leq y \wedge z \neq x \wedge z \neq y)$

3.$\operatorname{cov}_R(A)={\langle x, y\rangle \in R: y$ covers $x}$

4.Hasse Diagram(哈斯图)

5.一些概念 (都是一些元素)

• the least element (最小元) of $B$ if $(\forall y)(y \in B \rightarrow x \leq y)$

• the greatest element (最大元) of $B$ if $(\forall y)(y \in B \rightarrow y \leq x)$
• a minimal element (极小元) of $B$ if $(\forall y)(y \in B \wedge y \leq x \rightarrow x=y)$
• a maximal element (极大元) of $B$ if $(\forall y)(y \in B \wedge x \leq y \rightarrow x=y)$
• the upper bound (上界) of $B$ if $(\forall y)(y \in B \rightarrow y \leq x)$
• the lower bound (下界) of $B$ if $(\forall y)(y \in B \rightarrow x \leq y$ )
• least upper bound (最小上界/上确界)
• greatest lower bound (最大下界/下确界)

函数：Function

1. 写法：$f: A \rightarrow B, f: x \mapsto y$
2. all functions from A to B: $A_B ={f:(f : A \rightarrow B)}$
3. Indicator Function (特征函数): Let $A \subseteq E$. Then $\mathcal{X}_A: E \rightarrow{0,1}$ is defined by $\mathcal{X}_A(x)=1$ iff $x \in A$.
4. • injection (单射): if $\left(\forall x_1 \in A\right)\left(\forall x_2 \in A\right)\left(x_1 \neq x_2 \rightarrow f\left(x_1\right) \neq f\left(x_2\right)\right)$
   • surjection (满射) : if $\operatorname{ran}(f)=B$
   • bijection (双射): if it is both an injection and a surjection.

5. only when f is a bijection, we have that $f^{-1} : B \rightarrow A$ is a function, and we call $f^{-1}$ the inverse function (逆函数)

6. (1) If $f$ and $g$ are bijections (respectively, injections or surjections), then $f \circ g$ is also a bijection (respectively, injection or surjection). (2) If $f \circ g$ is a surjection, then $f$ is a surjection. (3) If $f \circ g$ is an injection, then $g$ is an injection. (4)IF $f \circ g$ is an bijection, then $f,g$ are both bijections.

基数和等势

2.无穷的大小：

• $

  \mathbb{N}

  =\aleph_0$, where $\aleph_0$ is called the Aleph Zero (阿列夫零);

• If $\left

  A_k\right

  =\aleph_k$, then $\left

  2^{A_k}\right

  =\aleph_{k+1}$, where $\aleph_k$ is called the Aleph $k$ (阿列夫 $k$ ).

3.dominated（支配）：A is dominated by B means $A\preceq B$

​ we say $A\prec B$ : if $A \preceq B$ and $A\not\approx B $

4.Theorem: Schröder-Berstein’s Theorem If $A \preceq B$ and $B \preceq A$, then $A \approx B$.

5.for any set A, we have $A\not\approx2^{A}$

6.$2^{\N}\approx \R$