南京大学：《计算机问题求解》课程教学资源（课件讲稿）集合论（III）函数 Function（简版）

1-10 Set Theory (III):Functions 魏恒峰 hfwei@nju.edu.cn 2019年12月10日 Hengfeng Wei (hfweinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日1/40

1-10 Set Theory (III): Functions 魏恒峰 hfwei@nju.edu.cn 2019 年 12 月 10 日 Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 1 / 40

Set Theory Foundation A Branch of Math- of Math- ematics ematies (Loglc) (a,b) A→B N,R ) AxB RC AxB Hengfeng Wei (bfweiinju.edu.cn1-10 Set Theory (III:Functions 2019年12月10日2/40

Set Theory A Branch of Math￾ematics N, R ℵ0 ω Foundation of Math￾ematics (+ Logic) (a, b) {} A × B R ⊆ A × B f : A → B Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 2 / 40

Functions AIMS PROOF! Hengfeng Wei (hfweiinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日3/40

Functions PROOF! Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 3 / 40

Definition of Functions Hengfeng Wei bfweiinju.edu.cn1-10 Set Theory (III:Functions 2019年12月10日4/40

Definition of Functions Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 4 / 40

RCAXB is a relation from A to B Hengfeng Wei (hfweiinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日5/40

R ⊆ A × B is a relation from A to B Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 5 / 40

Definition (Function) RC A x B is a function from A to B if a∈A:3b∈B:(a,b)∈f. f:A→B dom(f)=A cod(f)=B ran(f)=f(A)C B f:a→b f(a)b Hengfeng Wei (hfweiinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日6/40

Definition (Function) R ⊆ A × B is a function from A to B if ∀a ∈ A : ∃!b ∈ B : (a, b) ∈ f. f : A → B dom(f) = A cod(f) = B ran(f) = f(A) ⊆ B f : a 7→ b f(a) ≜ b Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 6 / 40

Definition (Function) RC A x B is a function from A to B if a∈A:3b∈B:(a,b)∈f: For Proof: Va∈A: a∈A:3b∈B:(a,b)∈f 3b∈B: ∀b,b∈B:(a,b)∈f∧(a,b)∈f→b=b Hengfeng Wei (hfweiinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日7/40

Definition (Function) R ⊆ A × B is a function from A to B if ∀a ∈ A : ∃!b ∈ B : (a, b) ∈ f. For Proof: ∀a ∈ A : ∀a ∈ A : ∃b ∈ B : (a, b) ∈ f ∃!b ∈ B : ∀b, b′ ∈ B : (a, b) ∈ f ∧ (a, b′ ) ∈ f =⇒ b = b ′ Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 7 / 40

Definition The set of all functions from X to Y: Yx={f|f:X→Y} Yx={f∈P(X×Y)|f:X→Y} X and Y are finite sets with x and y elements,respectively. IXI=z IYI=y,IYx=y Hengfeng Wei (hfweinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日8/40

Definition The set of all functions from X to Y : Y X = {f | f : X → Y } Y X = {f ∈ P(X × Y ) | f : X → Y } X and Y are finite sets with x and y elements, respectively. |X| = x |Y | = y, |Y X| = y x Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 8 / 40

Definition The set of all functions from X to Y: Yx={fIf:X→Y} y:y0={0 0={0 X≠0：0x=0 Hengfeng Wei (hfweiinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日9/40

Definition The set of all functions from X to Y : Y X = {f | f : X → Y } ∀Y : Y ∅ = {∅} ∅ ∅ = {∅} ∀X ̸= ∅ : ∅ X = ∅ Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 9 / 40

Definition The set of all functions from X to Y: Yx={fIf:X→Y} 2X={0,1}X≈P(X) n- in out in OM比Ou比 Hengfeng Wei (hfweiinju.edu.cn)1-10 Set Theory (III):Functions 2019年12月10日10/40

Definition The set of all functions from X to Y : Y X = {f | f : X → Y } 2 X = {0, 1} X ∼= P(X) Hengfeng Wei (hfwei@nju.edu.cn) 1-10 Set Theory (III): Functions 2019 年 12 月 10 日 10 / 40