高等代数中的证明：最长减子数列和增子数列长度的界限

2023-11-22 理论教育版权反馈

【摘要】：，umn+1中，或者存在一个长度大于m的减子数列，或者存在一个长度大于n的增子数列.证明：分别用l-i，l-i表示从ui开始的最长的减子数列和最长的增子数列的长度.假设命题的结论是错误的，即每个减子数列的长度不超过m，并且每个增子数列的长度不超过n.定义一

定义1.8 设X，Y是非空集合，所谓映射f是集合X，Y以及X和Y的元素之间的一个对应法则f，依照这个法则，X中的每一个元素x都对应于Y中唯一确定的一个元素y.映射通常记作f：X→Y.X称为映射f的定义域，Y称为映射f的值域.

在这个对应关系中，若x∈X对应于y∈Y，记作y=f（x）或f：xy，y叫作x的像，x叫作y的原像.集合{f（x）|x∈X}称为映射f的像，记作f（X）或Imf.若y∈Y，集合{x|f（x）=y}称为y的原像，记作f^-1（y）.

定义1.9 如果Imf=Y，则称f为满射；如果x₁≠x₂，则f（x₁）≠f（x₂），称f为单射.如果f既是满射，又是单射，则称为双射.

定理1.4 若f是X到Y的映射，

（1）f是单射当且仅当对任意的x₁，x₂∈X，如果f（x₁）=f（x₂），则x₁=x₂；

（2）f是满射当且仅当对任意的y∈Y，存在x∈X，使得y=f（x）.

此定理的证明是相当简单的，故从略.

若X，Y都是数集，从X到Y的映射称为函数.设X，Y，Z都是非空集合，映射f：X→Y，g：Y→Z，定义一个新映射记作gf，

gf：X→Z，xg（f（x））

称为映射g与f的复合映射.若f都是非空集合X到自身上的映射，那么复合映射f记作fⁿ.

定理1.5 设A，B，C，D是非空集合，f：A→B，g：B→C，h：C→D，那么，有等式

h（gf）=（hg）f

成立.也就是说，映射的复合运算满足结合律.

证明：显然映射h（gf）与（hg）f都是从A到D的映射.

设A中元素x_A在f之下的像是x_B，x_B在g之下的像是x_C，x_C在h之下的像是x_D，即

f（x_A）=x_B，g（x_B）=x_C，h（x_C）=x_D.

那么根据复合映射的定义，gf将把x_A对应到x_C，hg将把x_B对应到x_D，即

gf（x_A）=x_C，hg（x_B）=x_D.

因此我们有

h（gf）（x_A）=h（x_C）=x_D，

以及

（hg）f（x_A）=（hg）（x_B）=x_D.

由此可见，h（gf）=（hg）f.证毕.

若X，Y是非空集合，映射f：X→Y，g：Y→X，则gf和fg都有定义.但是gf和fg是不同的映射.

设X是一个非空集合，所谓恒等映射，通常记作i_X或简记作i（也可记作e，1），定义为i_X：X→X，xx或i_X（x）=x，i（x）=x.

设f是非空集合X到自身上的双射，定义一个对应关系g：X→X，yx，这里，y=f（x）.容易验证g是一个映射，也是双射，并且fg=gf=i_X.映射g称为映射f的逆映射，记作f^-1.函数的逆映射（如果存在）叫作反函数.

例1.10f，g，h是实数集合R上的映射，也就是函数，定义如下：

f（x）=2x+1，g（x）=e^x，h（x）=x²+1.

由于h（1）=h（-1）=2，因此h不是单射.又由于h（x）≥1≠0，因此零不可能有原像，h不是满射.

显然，g（x）>0，因此g不是满射.对实数x₁，x₂，如果g（x₁）=g（x₂），即e^x1=e^x2，那么有e^x1-x2=1，因此有x₁-x₂=0，即x₁=x₂.这表明g是单射.

对任意的实数y，显然有，因此f是满射.另一方面，对于两个实数x₁，x₂，若f（x₁）=f（x₂），即2x₁+1=2x₂+1，因此x₁=x₂.这表明f是单射.映射f既满且单，因此是一个双射.容易计算出f的反函数是.

另外，简单计算还有

ff（x）=4x+3，fg（x）=2e^x+1，gf（x）=e^2x+1，

以及

fⁿ（x）=2ⁿ（x+1）-1.

例1.11（Eulerϕ-函数）定义在自然数集合N上的函数称为数论函数.函数ϕ：N→N称为Eulerϕ-函数，如果ϕ（n）等于不超过n的与n互素的自然数的个数.

通过简单的计算可以得到ϕ（1）=1，ϕ（2）=1，ϕ（3）=2，ϕ（4）=2，ϕ（5）=4，ϕ（6）=2，ϕ（7）=6，ϕ（8）=4，ϕ（9）=6，ϕ（10）=4等.

另外，还有ϕ^-1（1）={1，2}，ϕ^-1（2）={3，4，6}，ϕ^-1（3）=等.求出集合Imϕ是一个困难的数学问题.

例1.12 用[x]表示实数x的整数部分，即不超过x的最大整数.函数f：R→Z，x[x]，f称为取整函数.例如，[4]=4，[5.7]=5，[-π]=-4等.

例1.13（3n+1映射）定义数论函数C如下，C：N→N，

这个映射C称为3n+1映射或Collatz映射.(www.chuimin.cn)

容易计算C（1）=2，C（2）=1，C（3）=5，C（4）=2，C（5）=8，…，C（18）=9，C（19）=29等.映射C是满射，但不是单射，这是因为C（3）=C（10）=5，C^-1（5）={3，10}，C^-1（6）={12}.

一个著名的猜想是对任意的自然数n，一定存在自然数k，使得C^k（n）=1，这个猜想称为3n+1猜想.

例1.14 在平面直角坐标系OXY中，由所有的圆心在坐标原点的同心圆组成的集合记作A.这样的圆可以由它们的半径r决定，记为O（r），那么A={O（r）|r>0}.

建立从实数集合R到集合A的映射f：R→A，xO（e^x）.显然，映射f是双射，它的逆映射是f^-1：A→R，O（r）lnr.

例1.15 记A={（x，y）|x²+y²=1}，定义映射f如下：

f：[0，2π）→A，t（cost，sint）.

映射f是双射，其逆映射

这一对应关系也可以写作

（x，y）π（1-sgny）+arccosx·sgny.

例1.16 本例试图在一个单位圆周与直线之间建立一个双射.在平面直角坐标系OXY中，集合

A={（x，y）|x²+y²=1且y≠1}，B={（x，0）|x∈R}.

对单位圆周上的任意一个异于（0，1）的点（x，y），连接（0，1）、（x，y）的直线交直线.建立映射

可以验证f是双射.f的逆映射f^-1是

例1.17（Erdös Szekeres）在一个有mn+1个各不相同的整数的数列u₁，u₂，…，u_mn+1中，或者存在一个长度大于m的减子数列，或者存在一个长度大于n的增子数列.

证明：分别用l^-_i，l^-_i表示从u_i开始的最长的减子数列和最长的增子数列的长度.假设命题的结论是错误的，即每个减子数列的长度不超过m，并且每个增子数列的长度不超过n.

定义一个从集合{u₁，u₂，…，u_mn+1}到笛卡儿积{1，2，…，m}×{1，2，…，n}的映射f如下：

下面我们来证明f是单射.

假定i<j.在这个情形下，u_i>u_j就蕴涵l^-_i>l^-_j.因为我们至少可以加一个元素（即u_i）到从u_i开始的最大长度的减子数列的左边，从而得到一个从u_i开始的更长的减子数列，所以l^-_i>l^-_j.类似地，u_i<u_j就蕴涵l⁺_i>l⁺_j.因为我们至少可以加一个元素（即u_i）到从u_i开始的最大长度的增子数列的左边，从而得到一个从u_i开始的长度更大的增子数列，所以l⁺_i>l⁺_j.因此u_i≠u_j就蕴涵（u^-_i，u⁺_i）≠（u^-_j，u⁺_j）.因为这些有序对中至少有一个位置上的数是不同的.最后这个不等式就意味着f（u_i）≠f（u_j）.这样就证明了f是单射.