集合論(2):映射

文章目錄

• 集合論(2):映射
• • 一.函數 、映射
  • • 1.映射與函數的關系
    • • (1)定義
      • (2)基本術語
    • 2.映射與笛卡爾積
    • • (1)定義
    • 3.限制
    • • 定義
    • 4.特殊映射
    • • ①單射
      • • 定義：
      • ②滿射
      • • 定義：
      • ③雙射（一一對應）
      • • 定義
      • ④恒等映射
      • • 定義
      • ⑤部分映射
      • • 定義
      • ⑥特殊映射的一些定理
      • • 定理：
        • 定理：
      • ⑦映射集
      • • 定義
        • 性質
        • • （1）
          • （2）
    • 5.映射的一般性質
    • • ①映射的擴充
      • • 性質
      • ②原象的擴充
      • ③ 設 f : X → Y , C ⊆ Y , D ⊆ Y f:X\rightarrow Y,C\subseteq Y,D\subseteq Y f:X→Y,C⊆Y,D⊆Y,則：
      • ④設 f : X → Y , A ⊆ X , B ⊆ X f:X\rightarrow Y,A\subseteq X,B\subseteq X f:X→Y,A⊆X,B⊆X,則：
  • 二.抽屜原理
  • • 1.抽屜原理
    • 2.推廣形式之一
  • 三.映射的合成
  • • 1.定義
    • 2.性質
    • • ①
      • ②
      • ③
      • ④ ：③的反推
      • ⑤X→ X
  • 四.逆映射
  • • 1.定義（逆映射）
    • 2.定義（左右逆映射）
    • 3.定理（可逆充要條件）
    • 4.定理（逆映射相關）
  • 五.集合的特征函數
  • • 1.集合和函數的對應關系
    • 2.集合的性質與集合的特征函數的對應關系
    • • ①定義（特征函數）
      • ②定義（特征函數的集合）

一.函數 、映射

1.映射與函數的關系

(1)定義

設 X X X 與 Y Y Y是兩個非空集合，若根據某一法則 f f f，使X中每一個元素 x x x，使 X X X中的每一進制素 x x x總有 Y Y Y中的唯一确定的元素 y y y與之對應，則稱 f f f是集合 X X X到集合 Y Y Y的映射。

若** X X X 與 Y Y Y是兩個數集，就是函數的定義**

(2)基本術語

“ f f f是 X X X到 Y Y Y的映射”常記為 f ： X → Y f：X\rightarrow Y f：X→Y

設 x x x對應 y y y，常稱作 x x x在 f f f下的象為 y y y，常記作 f ( x ) f(x) f(x)， x x x是 y y y的原象

X X X稱為 f f f的定義域. 集合 { f ( x ) ∣ x ∈ X } \{f(x)|x\in X\} {f(x)∣x∈X}稱為 f f f的值域或象，記為 I m ( f ) I_m(f) Im​(f)

2.映射與笛卡爾積

(1)定義

設 X X X 和 Y Y Y是兩個非空集合，一個從 X X X到 Y Y Y的映射是一個滿足以下兩個條件的 X × Y X\times Y X×Y 的子集 f f f：

(1) 對 X X X的每一個元素 x x x, 存在一個 y ∈ Y y\in Y y∈Y, 使得

( x , y ) ∈ f (x,y)\in f (x,y)∈f;

(2) 若 ( x , y ) , ( x , y ′ ) ∈ f (x,y),(x,y')\in f (x,y),(x,y′)∈f, 則 y = y ′ y=y' y=y′

3.限制

定義

​ 設 f : X → Y , A ⊆ X , f:X\rightarrow Y,A\subseteq X, f:X→Y,A⊆X, 當把 f f f的定義域限制在 A A A上時, , 就得到了一個: φ : A → Y , ∀ x ∈ A , φ ( x ) = f ( x ) , φ \varphi:A\rightarrow Y,\forall x\in A,\varphi (x)=f(x),\varphi φ:A→Y,∀x∈A,φ(x)=f(x),φ被稱為 f f f在A上的限制，且常用 f ∣ A f|A f∣A來代替 φ \varphi φ，反過來，我們說 f f f是 φ \varphi φ在 X X X上的擴張。

4.特殊映射

①單射

定義：

設 f : X → Y f:X\rightarrow Y f:X→Y,如果 ∀ x , x ′ ∈ X \forall x,x'\in X ∀x,x′∈X,隻要 x ≠ x ′ x \ne x' x​=x′，就有 f ( x ) ≠ f ′ ( x ) f(x)\ne f'(x) f(x)​=f′(x),則稱f為從X到Y的單射

②滿射

定義：

設 f : X → Y f:X\rightarrow Y f:X→Y,如果 ∀ y ∈ Y \forall y\in Y ∀y∈Y, ∃ x ∈ X \exists x\in X ∃x∈X,使得 f ( x ) = y f(x)=y f(x)=y則稱 f f f為從 X X X到 Y Y Y的滿射

③雙射（一一對應）

定義

設 f : X → Y f:X\rightarrow Y f:X→Y,若 f f f既是單射又是漫射，則 f f f是雙射或稱為一一對應，也稱 X X X與 Y Y Y對等，記為 X ∼ Y X\sim Y X∼Y

④恒等映射

定義

設 f : X → X f:X\rightarrow X f:X→X,如果 ∀ x ∈ X , f ( x ) = x \forall x\in X,f(x)=x ∀x∈X,f(x)=x,則稱 f f f為 X X X上的恒等映射。 X X X上的恒等映射常記為 I x I_x Ix​或者 l x l_x lx​

X X X上的恒等映射隻有一個，恒等映射是雙射

⑤部分映射

定義

設 f : A → Y , A ⊆ X , f:A\rightarrow Y,A\subseteq X, f:A→Y,A⊆X,則 f f f是 X X X上的一個部分映射

⑥特殊映射的一些定理

定理：

​ 設 A A A和 B B B為有限集， f : A → B f:A\rightarrow B f:A→B

(1) 如果 f f f是滿射的，則 ∣ A ∣ ≥ ∣ B ∣ |A|\geq |B| ∣A∣≥∣B∣；

(2) 如果 f f f是單射，則 ∣ A ∣ ≤ ∣ B ∣ |A|\leq |B| ∣A∣≤∣B∣；

定理：

設 A A A和 B B B是有限集， ∣ A ∣ = ∣ B ∣ |A|=|B| ∣A∣=∣B∣，則 f : A → B f:A\rightarrow B f:A→B是單射    ⟺    \iff ⟺ f f f是滿射

⑦映射集

定義

從 X X X到 Y Y Y的所有映射之集記為 Y X Y^X YX ，即: Y X = { f ∣ f : X → Y } Y^X=\{f|f:X \rightarrow Y\} YX={f∣f:X→Y}

性質

（1）

設 X , Y X,Y X,Y均為有窮集合, ∣ X ∣ = n , ∣ Y ∣ = m , |X|=n,|Y|=m, ∣X∣=n,∣Y∣=m,且 n ≥ 1 , m ≥ 1 n≥1,m≥1 n≥1,m≥1, 則 ∣ Y X ∣ = m n |Y^X |=m^n ∣YX∣=mn

（2）

設 X X X為有窮集合, , ∣ X ∣ = n |X|=n ∣X∣=n, 且 n ≥ 1 n\geq 1 n≥1,則從 X X X到 X X X共有 n ！ n！ n！個雙射

5.映射的一般性質

①映射的擴充

若 A ⊆ X A\subseteq X A⊆X ,那麼由 f f f和 A A A就唯一地确定了 Y Y Y的一個子集, 記為 f ( A ) f(A) f(A): f ( A ) = { f ( x ) ∣ x ∈ A } f(A)=\{f(x)|x\in A \} f(A)={f(x)∣x∈A}

f ( A ) f(A) f(A)稱為 A A A在 f f f下的象，利用此法，由 f f f就确定了一個從 2 X 2^X 2X到 2 Y 2^Y 2Y的映射，習慣上此映射仍記為 f f f

f ( ∅ ) = ∅ , f ( X ) = I m f f(\empty)=\empty,f(X)=I_mf f(∅)=∅,f(X)=Im​f

性質

（1） f f f是 X X X到 Y Y Y 的滿射當且僅當 f ( X ) = Y f(X)=Y f(X)=Y

（2）如果 A ⊆ B ⊆ X A\subseteq B\subseteq X A⊆B⊆X，則 f ( A ) ⊆ f ( B ) f(A)\subseteq f(B) f(A)⊆f(B)

②原象的擴充

若 B ⊆ Y B\subseteq Y B⊆Y ,那麼由 f f f和 B B B就唯一地确定了 X X X的一個子集, 記為 f − 1 ( B ) f^{-1}(B) f−1(B): f − 1 ( B ) = { x ∣ f ( x ) ∈ B , x ∈ X } f^{-1}(B)=\{x|f(x)\in B,x\in X \} f−1(B)={x∣f(x)∈B,x∈X}

f − 1 ( B ) f^{-1}(B) f−1(B)稱為在 f f f下 B B B的原象， f − 1 ( B ) f ^{-1}(B) f−1(B) 是 X X X中在 f f f下的象落在 B B B裡的那些元素組成的

利用此法，由 f f f就确定了一個從 2 Y 2^Y 2Y到 2 X 2^X 2X的映射，記為 f − 1 f^{-1} f−1

③ 設 f : X → Y , C ⊆ Y , D ⊆ Y f:X\rightarrow Y,C\subseteq Y,D\subseteq Y f:X→Y,C⊆Y,D⊆Y,則：

（1） f − 1 ( C ∪ D ) = f − 1 ( C ) ∪ f − 1 ( D ) f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D) f−1(C∪D)=f−1(C)∪f−1(D)

（2） f − 1 ( C ∩ D ) = f − 1 ( C ) ∩ f − 1 ( D ) f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D) f−1(C∩D)=f−1(C)∩f−1(D)

（3） f − 1 ( C Δ D ) = f − 1 ( C ) Δ f − 1 ( D ) f^{-1}(C\Delta D)=f^{-1}(C)\Delta f^{-1}(D) f−1(CΔD)=f−1(C)Δf−1(D)

（4） f − 1 ( C c ) = ( f − 1 ( C ) ) c f^{-1}(C^ c)=(f^{-1}(C))^c f−1(Cc)=(f−1(C))c

④設 f : X → Y , A ⊆ X , B ⊆ X f:X\rightarrow Y,A\subseteq X,B\subseteq X f:X→Y,A⊆X,B⊆X,則：

(1) f ( A ∪ B ) = f ( A ) ∪ f ( B ) f(A\cup B)=f(A)\cup f(B) f(A∪B)=f(A)∪f(B)

(2) f ( A ∩ B ) ⊆ f ( A ) ∩ f ( B ) f(A\cap B)\subseteq f(A)\cap f(B) f(A∩B)⊆f(A)∩f(B)

(3) f ( A Δ B ) ⊇ f ( A ) Δ f ( B ) f(A\Delta B)\supseteq f(A)\Delta f(B) f(AΔB)⊇f(A)Δf(B)

二.抽屜原理

1.抽屜原理

如果把 n + 1 n+1 n+1個物體放到 n n n抽屜裡，則必有一個抽屜裡至少放了兩個物體。

2.推廣形式之一

設 k k k和 n n n都是任意的正整數，若至少有 k n + 1 kn+1 kn+1隻鴿子配置設定在 n n n個鴿巢裡，則至少存在一個鴿巢中有不少于 k + 1 k+1 k+1隻鴿子

三.映射的合成

1.定義

設 f : X → Y f:X\rightarrow Y f:X→Y, g : Y → Z g:Y\rightarrow Z g:Y→Z，一個從 X X X到 Z Z Z的映射 h h h稱為 f f f與 g g g的合成,如果 ∀ x ∈ X , h ( x ) = g ( f ( x ) ) ∀ x ∈ X , h ( x ) = g ( f ( x ) ) , ∀ x ∈ X , h ( x ) = g ( f ( x ) ) ∀x∈X,h(x)=g(f(x)) \forall x \in X,h(x) = g(f(x)),∀x∈X,h(x)=g(f(x)) ∀x∈X,h(x)=g(f(x))∀x∈X,h(x)=g(f(x)),∀x∈X,h(x)=g(f(x))."映射f與g的合成"h記作 g ∘ f g\circ f g∘f,或者 g f gf gf.

2.性質

①

設 f : X → Y f:X\rightarrow Y f:X→Y, g : Y → Z ， h : X → W g:Y\rightarrow Z，h:X\rightarrow W g:Y→Z，h:X→W,則: h ( g f ) = ( h g ) f h(gf)=(hg)f h(gf)=(hg)f

②

設 f : X → Y f:X\rightarrow Y f:X→Y,則 f I X = I Y f fI_X=I_Yf fIX​=IY​f

③

f : X → Y f:X\rightarrow Y f:X→Y, g : Y → Z g:Y\rightarrow Z g:Y→Z，則

（1）若f與g都是單射的，則gf也是單射的

（2）若f與g都是滿射的，則gf也是滿射的

（3）若f與g都是雙射的，則gf也是雙射的

④ ：③的反推

（1）若gf是單射的，則f是單射的

（2）若gf是滿射的，則g是滿射的

（3）若gf是雙射的，則f是單射的且g是滿射的

⑤X→ X

設f與g都是X 到X的映射,則 I m ( f ) ⊆ I m ( g ) I_m(f)\subseteq I_m(g) Im​(f)⊆Im​(g)充要條件為 ∃ h : X → X \exists h:X\rightarrow X ∃h:X→X使得 f = g h f = gh f=gh.

四.逆映射

1.定義（逆映射）

設 f : X → Y f : X → Y f:X→Y如果存在一個映射 g : Y → X g : Y → X g:Y→X使得 f g = I Y , 且 g f = I X fg=I_Y,且gf=I_X fg=IY​,且gf=IX​，則稱映射f是可逆的，而g稱為f的逆映射

2.定義（左右逆映射）

設 f : X → Y f : X → Y f:X→Y如果存在一個映射 g : Y → X g : Y → X g:Y→X使得 g f = I X gf=I_X gf=IX​，則稱映射f是左可逆的，g稱為f的左逆映射

設 f : X → Y f : X → Y f:X→Y如果存在一個映射 h : Y → X h : Y → X h:Y→X使得 f h = I Y fh=I_Y fh=IY​，則稱映射f是右可逆的，h稱為f的右逆映射

3.定理（可逆充要條件）

設 f : X → Y f : X → Y f:X→Y，則 f f f是可逆的充分必要條件是 f f f為雙射的

4.定理（逆映射相關）

（1）設 f : X → Y f:X\rightarrow Y f:X→Y, 則如果 f f f是可逆的, 則 f f f的逆映射是唯一的。 f f f的逆記作 f − 1 f^{-1} f−1

（2）設 f : X → Y f:X\rightarrow Y f:X→Y, g : Y → Z g:Y\rightarrow Z g:Y→Z,都是可逆的，則 g f gf gf也可逆且 ( g f ) − 1 = f − 1 g − 1 , ( f − 1 ) − 1 = f (gf)^{-1}=f^{-1}g^{-1},(f^{-1})^{-1}=f (gf)−1=f−1g−1,(f−1)−1=f

（3）設 X → Y X\rightarrow Y X→Y,則：

​ f左可逆的充分必要條件是f 為單射；

​ f右可逆的充分必要條件是f 為滿射

五.集合的特征函數

1.集合和函數的對應關系

一個子集唯一确定一個函數，反過來，一個這樣的函數也唯一确定一個子集

2.集合的性質與集合的特征函數的對應關系

①定義（特征函數）

設 X X X是一個集合， E ⊆ X E\subseteq X E⊆X 。從 X X X到

{0,1} 的如下的一個映射 χ E \chi_E χE​稱為 E E E的特征函數:

∀ x ∈ X , χ E ( x ) = { 1 , 如 果 x ∈ E 0 , 如 果 x ∉ E \forall x\in X , \chi_E(x)=\left\{\begin{matrix}1,如果x\in E \\0,如果x\notin E\end{matrix}\right. ∀x∈X,χE​(x)={1,如果x∈E0,如果x∈/​E​

集合E和特征函數 χ E \chi_E χE​之間互相唯一确定

②定義（特征函數的集合）

C h ( X ) = { χ ∣ χ : X → { 0 , 1 } } Ch(X)=\{\chi|\chi:X\rightarrow\{0,1\}\} Ch(X)={χ∣χ:X→{0,1}}

C h ( X ) Ch(X) Ch(X)是 X X X中所有子集構成的特征函數的集合， C h ( X ) Ch(X) Ch(X)與 X X X的幂集 2 X 2^X 2X存在一一對應