形式化1：集合相关的概念和表示

概念和表示"/>

形式化1：集合相关的概念和表示

集合

• a ∈ A a \in A a∈A：元素a是集合A的元素
• A ⊆ B A \subseteq B A⊆B：集合A是集合B的子集，即A的元素都是B的元素
• A ⊂ B A \subset B A⊂B：集合A是集合B的真子集，即A的元素都是B的元素，且A与B不相等
• A = B A = B A=B：集合A和集合B相等
• A ≠ B A \ne B A​=B：集合A和集合B不相等
• P ( A ) = { a ∣ a ⊆ A } \mathcal{P}(A)=\{a|a \subseteq A\} P(A)={a∣a⊆A}：A的幂集，即由A的全体子集形成的集合， ∣ P ( A ) ∣ = 2 n |\mathcal{P}(A)|=2^n ∣P(A)∣=2n
  例如： A = 1 , 2 A={1,2} A=1,2，则 P ( A ) = { { 1 } , { 2 } , { 1 , 2 } , ϕ } \mathcal{P}(A)=\{\{1\},\{2\},\{1,2\},\phi \} P(A)={{1},{2},{1,2},ϕ}

关系和映射

• 有序对：两元素 ( a , b ) (a,b) (a,b)按一定次序组成的二元组，并满足基本性质：
  ( a 1 , b 1 ) = ( a 2 , b 2 ) ⟺ a 1 = a 2 且 b 1 = b 2 (a_1,b_1)=(a_2,b_2) \iff a_1=a_2 且 b_1=b_2 (a1​,b1​)=(a2​,b2​)⟺a1​=a2​且b1​=b2​
• 笛卡尔积：集合A和集合B的笛卡尔积 A × B A \times B A×B，是由如下有序对构成的集合
  A × B = { ( a , b ) ∣ a ∈ A 且 b ∈ B } A \times B=\{(a,b)|a \in A 且b \in B\} A×B={(a,b)∣a∈A且b∈B}
  • 有序对笛卡尔积可推广到n个元素或集合的情况，即A
    A × B × C = { ( a , b , c ) ∣ a ∈ A , b ∈ B , c ∈ C } A \times B \times C=\{(a,b,c)|a \in A, b \in B, c \in C\} A×B×C={(a,b,c)∣a∈A,b∈B,c∈C}
  • 用 A n A^n An表示 n ( n ≥ 1 ) n(n \ge 1) n(n≥1)个集合 A A A的笛卡尔积，并规定 A 0 = ϕ A^0=\phi A0=ϕ
• 二元关系：对于任意集合A和B，称其笛卡尔积的任意子集（即 R ⊆ A × B R \subseteq A \times B R⊆A×B）为集合A和B上的二元关系，简称关系。若 A = B A=B A=B，则称集合R为集合A上的二元关系。
  • 对于集合A和B上的关系R，我们称集合A是关系R的前域，集合B是关系R的后域。
  • 记 C = { a ∣ a ∈ A , 存 在 b ∈ B ， 使 得 ( a , b ) ∈ R } C=\{a|a \in A, 存在b \in B，使得(a,b) \in R\} C={a∣a∈A,存在b∈B，使得(a,b)∈R}为关系R的定义域，记为 d o m ( R ) dom(R) dom(R)，例如 A = { 1 , 2 } , B = { a , b } , R = { { 1 , a } , { 2 , b } } A=\{1,2\},B=\{a,b\},R=\{\{1,a\},\{2,b\}\} A={1,2},B={a,b},R={{1,a},{2,b}}，那么定义域为 { 1 , 2 } \{1,2\} {1,2}
  • 记 D = { b ∣ b ∈ B , 存 在 a ∈ A ， 使 得 ( a , b ) ∈ R } D=\{b|b \in B, 存在a \in A，使得(a,b) \in R\} D={b∣b∈B,存在a∈A，使得(a,b)∈R}为关系R的值域，记为 r a n ( R ) ran(R) ran(R)，在上例中值域为 { a , b } \{a,b\} {a,b}
  • 记 f l d ( R ) = d o m ( R ) ∪ r a n ( R ) fld(R)=dom(R) \cup ran(R) fld(R)=dom(R)∪ran(R)为关系R的域
• 函数：函数是一种特殊的关系，即对于A中的两个相等的值 x = y x=y x=y，那么必定有 R ( x ) = R ( y ) R(x)=R(y) R(x)=R(y)，也就是说，函数是种一对一的映射
  • 全函数：对于定义域中的所有值都有映射的函数，即 d o m ( F ) = A dom(F)=A dom(F)=A
  • 偏函数：定义域中的某些值不存在映射
• 等价关系：若集合A上的二元关系R满足，则称R为集合A上的等价关系
  1. 自反性：对于任意 x ∈ A x \in A x∈A，有 ( x , x ) ∈ R (x,x) \in R (x,x)∈R
  2. 对称性：对于任意 x , y ∈ A x,y \in A x,y∈A，若 ( x , y ) ∈ R (x,y) \in R (x,y)∈R，则 ( y , x ) ∈ R (y,x) \in R (y,x)∈R
  3. 传递性：对于任意 x , y , z ∈ A x,y,z \in A x,y,z∈A，若 ( x , y ) ∈ R 且 ( y , z ) ∈ R (x,y) \in R且(y,z) \in R (x,y)∈R且(y,z)∈R，则 ( x , z ) ∈ R (x,z) \in R (x,z)∈R
• 等价元素：若R是集合A上的等价关系，且 ( a , b ) ∈ R (a,b) \in R (a,b)∈R，则称元素a和b等价，记作 a ∼ b a \sim b a∼b
• 等价类：集合A中与元素a等价的所有元素组成的集合，称为a由关系R生成的等价类，记作
  [ a ] R = { x ∣ x ∈ A 且 x ∼ a } [a]_R=\{x|x \in A且x \sim a\} [a]R​={x∣x∈A且x∼a}
  例如整数中模二相等的等价类， R = Z × Z R=Z \times Z R=Z×Z，其中 Z Z Z为整数集合，那么 [ 0 ] R = { . . . , − 2 , 0 , 2 , . . . } [0]_R=\{...,-2,0,2,...\} [0]R​={...,−2,0,2,...}