在实变函数中，Levi定理，又名Levi单调收敛定理，是说非负可测函数的求极限和积分运算可以交换顺序。具体表述如下：
设和 都是可测集D上的非负可测函数，而且对几乎所有的，单调增加收敛于，则
在周性伟编著的《实变函数》一书中，上述定理的证明思想如下：由于非负可测函数的Lebesgue积分是由单调增加的非负简单函数列的积分的极限来定义的，所以对每一个，都用一列单增非负简单函数列来逼近，设为。然后，按下图所示的方式构造一个新的函数列 ：

即令

这样得到具有两个重要的性质：
(1)单调增加
(2)
在第(2)条性质中，我们先令 ，再令便可得到的极限即为，又根据第(1)条性质，的积分可以用的积分的极限来定义。
这个证明颇具启发性，它的关键在于非负简单函数列的构造。其实，的构造方法并不是唯一的，只要构造出的函数列满足上述两条性质便可。在这里，我们采用如下图所示的构造方式（是否似曾相识？还记得上篇博客中“至多可数个可数集的并是可数集”的证明方法吗？）：

证明：,设的积分由单调增加的非负简单函数列定义。现令


…

则为非负简单函数，且满足
(1)单调增加
(2)
由(2)，得
(3)

在(2),(3)中，令(则 )，得到
(4)
(5)
在(4),(5)中，令，得


则

参考资料：周性伟，《实变函数》，科学出版社

[English Version of This Post]

如果集合A和集合B之间存在一个一一映射(双射)，则称A和B等价。如果A和正整数集N等价，我们称A是可数的。换句话说，A可数的充要条件是A中的全体元素可以排列成a₁,a₂,…,a_n,..的形状。
根据这个定义，我们很容易得出整数集是可数的。因为我们可以构造如下正整数集到整数集的一一映射：

一个更有意思的命题是：
可数个可数集的并是可数集。
它的证明使用了经典的“对角线”法，这种方法被各种实变函数或集合论的书广泛采用。
证明：假设{A_m}是一列可数集，其中A_m={a_m1,a_m2,…}，把它们按如下顺序排列

可以按如图箭头所指的方向数U{A_m}中的元素，即把U{A_m}中元素排列成a₁₁,a₂₁,a₁₂,a₃₁,…}，于是U{A_m}是可数的，命题得证。
上述证明虽然已经说明U{A_m}可数，却没有给出它与正整数之间的一一映射关系。能否写出这个映射呢？
仔细观察发现，每个“对角线”上元素a_mn的下标之和m+n是一个常数。于是我们可以得到，按上图所示的排列方法，a_mn所处的位置为：

其中m+n≥3，a₁₁=1
这样我们就得到了U{A_m}到正整数集的一个一一映射：

这个命题的一个应用就是：有理数集是可数的。因为有理数可以被看作一个二元有序对(p,q)。但当我们用类似的方法排列有理数时，却发现了上述映射的一个致命错误：

(图片来自维基百科，它采用了“蛇状”的盘旋数法)
注意到图中红色的有理数，它们的分子和分母有公约数，这些数都已经被数过了。也就是说，我们上面构造的映射中忽略了a_mn中会有重复元素的情况。
我试图把重复的情况考虑进去，构建从正有理数到正整数的一一映射，但发现这时问题变得异常复杂，最终没能写出一个通式来。
那么，到底能不能找到这样的一个映射关系呢？ Read the rest of this entry »

当两个连续函数都趋于无穷时，我们常用洛必达法则来比较它们趋向无穷的快慢。函数的阶越高，它趋向无穷的速度就越快。在定义在正整数域上的函数中，n!趋向于正无穷的速度非常快，所以在算法设计中如果出现这样的时间复杂度就太糟糕了。logn趋向无穷的速度则非常慢。
今天你将看到一个增长速度比n!快的多的函数和一个比logn慢的多的函数，它们都源于一个函数–’Ackerman Function’。
并非一切的递归函数都有通项公式，Ackerman函数就是这么一个例子。它是一个双递归函数，有两个自变量(独立)。定义如下： 
 
Read the rest of this entry »

今天上习题课的时候老师讲了一道非常有意思的题目：
设F1，F2为R²上两个互不相交的非空闭集，求R²上的连续函数f(x) ，使得

大家可以先想像一下这个函数的三维图形，形象一下说就像是山峰中的两块平地，它们的高度差为１。这个问题的难点就是要求f(x)是一个连续函数。在看解答之前，希望大家能够自己想一想。 Read the rest of this entry »