离散数学-8函数

8.1 函数的定义与性质

定义8.1 设 F 为二元关系, 若x∈domF 都存在唯一的y∈ranF 使 xFy 成立, 则称 F 为函数 对于函数F, 如果有 xFy, 则记作 y=F(x), 并称 y 为F 在 x 的值.

定义8.2 设F, G 为函数, 则

 F=G FG∧GF

如果两个函数F 和 G 相等, 一定满足下面两个条件：

(1) domF=domG

(2) x∈domF=domG 都有F(x)=G(x)

定义8.3 设A, B为集合, 如果

f 为函数, domf=A, ranfB,

则称 f 为从A到B的函数, 记作 f：A→B.

定义8.4 所有从A到B的函数的集合记作B^A, 符号化表示为

 B^A = { f | f：A→B }

|A|=m, |B|=n, 且m, n>0, |B^A|=n^m

A=, 则B^A=B^={}

A≠且B=, 则B^A=^A= 

定义8.5 设函数 f：A→B, A₁A, B₁B

(1) A₁在 f 下的像 f(A₁) = { f(x) | x∈A₁}, 函数的像 f(A)= { f(x) | x∈A}

(2) B₁在 f 下的完全原像 f ^1(B₁)={x|x∈A∧f(x)∈B₁}

定义8.6 设 f：A→B,

(1) 若 ranf=B, 则称 f:A→B是满射的

(2) 若 y∈ranf 都存在唯一的 x∈A 使得 f(x)=y, 则称 f:A→B 是单射的

(3) 若 f:A→B 既是满射又是单射的, 则称 f:A→B是双射的

定义8.7

(1)设 f:A→B, 如果存在c∈B使得对所有的 x∈A都有 f(x)=c, 则称 f:A→B是常函数.

(2) 称 A上的恒等关系I_A为A上的恒等函数, 对所有的x∈A都 有I_A(x)=x.

(3) 设<A, ≼>, <B, ≼>为偏序集，f:A→B，如果对任意的 x₁, x₂∈A, x₁≺x₂, 就有 f(x₁)≼ f(x₂), 则称 f 为单调递增的；如 果对任意的x₁, x₂∈A, x₁≺x₂, 就有f(x₁) ≺f(x₂), 则称 f 为严格单调递增的. 类似的也可以定义单调递减和严格单调递 减的函数

(4) 设A为集合, 对于任意的A'A, A'的特征函数

_A ' :A→{0,1}定义为

_A'(a)=1, a∈A'

_A'(a)=0, a∈AA'

(5) 设R是A上的等价关系, 令

 g:A→A/R

g(a)=[a], a∈A

称 g 是从 A 到商集 A/R 的自然映射

8.2 函数的复合与反函数

定理8.1 设F, G是函数, 则F_G也是函数, 且满足

(1) dom(F_G)={x|x∈domF∧F(x)∈domG}

(2) x∈dom(F_G)有F_G(x)=G(F(x))

推论1 设F, G, H为函数, 则(F_G)_H和F_(G_H)都是函数, 且

(F_G)_H=F_(G_H)

推论2 设 f:A→B, g:B→C, 则 f_g:A→C, 且x∈A都有

f_g(x)=g(f(x))

定理8.2 设f:A→B, g:B→C 

(1) 如果 f:A→B, g:B→C是满射的, 则 f_g:A→C也是满射的

(2) 如果 f:A→B, g:B→C是单射的, 则 f_g:A→C也是单射的 

(3) 如果 f:A→B, g:B→C是双射的, 则 f_g:A→C也是双射的  

定理8.3 设 f:AB, 则 f = f I_B = I_Af

定理8.4 设 f:A→B是双射的, 则f ^1:B→A也是双射的.

定理5.8 设f: AB是双射的，则f ^-1是函数，并且是从B到A的双射函数。称双射函数f: AB是可逆的，并称f ⁻¹为f的反函数。

任何关系都存在逆关系，作为满足一定条件的二元关系，函数的逆关系不一定都是函数。

反函数存在的条件

(1) 任给函数F, 它的逆F ^1不一定是函数, 只是一个二元关系.

(2) 任给单射函数 f:A→B, 则f ^1是函数, 且是从ranf 到A的双

射函数, 但不一定是从B到A的双射函数

(3) 对于双射函数 f:A→B, f ^1:B→A是从B到A的双射函数.

定理8.5

(1) 设 f:A→B是双射的, 则 f ^1_f = I_B, f _f ^1 = I_A

(2) 对于双射函数 f:A→A, 有 f ^1_f = f _ f ^1 = I_A

8.3 双射函数与集合的基数

定义8.8 设A, B是集合, 如果存在着从A到B的双射函数（A到B是单射和满射）, 就称A和B是等势的, 记作A≈B. 如果A不与B 等势, 则记作A≉B.

定理8.6 设A, B,C是任意集合，

(1) A≈A

(2) 若A≈B，则B≈A

(3) 若A≈B，B≈C，则A≈C.

等势结果

• N ≈ Z ≈ Q ≈ N×N
• 任何实数区间都与实数集合R等势

  不等势的结果:

  定理8.7 (康托定理)

  (1) N ≉ R； (2) 对任意集合A都有A≉P(A)

  定义8.9 (1) 设A, B是集合, 如果存在从A到B的单射函数, 就称B优势于A, 记作A≼B. 如果B不是优势于A, 则记作A⋠B.

  (2) 设A, B是集合, 若A≼B 且 AB, 则称 B 真优势于A, 记作 A≺B. 如果 B 不是真优势于A, 则记作A⊀B.

  定理8.8 设 A, B, C是任意的集合, 则

  (1) A≼A

  (2) 若A≼B且B≼A, 则A≈B

  (3) 若A≼B且B≼C, 则A≼C

  定义8.10 利用空集和后继（紧跟在n后面的自然数）可以把所有的自然数定义为集合：

  0=空集，n⁺=n∪{n}

  设a为集合, 称a∪{a}为a的后继, 记作a⁺, 即 a⁺=a∪{a}.

  定义6.2 设A为任意集合，如果存在自然数n，使得A  {0, 1, 2,…, n−l}，则称A为有限集，否则称A为无限集。

  定义8.11

  (1) 一个集合是有穷的当且仅当它与某个自然数等势；

  (2) 如果一个集合不是有穷的, 就称作无穷集.

  利用自然数的性质可以证明：任何有穷集只与惟一的自然数等势.

  定义8.12

  (1) 对于有穷集合A, 称与A等势的那个惟一的自然数为A的基数, 记作cardA (也可以记作|A|) cardA = n A ≈ n

  (2) 自然数集合N的基数记作À₀, 即cardN =₀

  (3) 实数集R的基数记作À, 即cardR =

  定义8.13 设A, B为集合, 则

  (1) cardA=cardB A≈B

  (2) cardA≤cardB A≼B

  (3) cardAB  cardA≤cardB∧cardA≠cardB

  定义8.14 设A为集合, 若cardA≤₀, 则称A为可数集或可列集.

生日后少"，小了