阿罗不可能性定理的证明

首先引入一些必要的记号和定义。令有穷集 $N=\{1,\ldots,n\}$ 为 $n$ 个投票者构成的集合，令 $X$ 为所有备选项构成的集合，每个投票者 $i$ 对 $X$ 的排序记作 $\succeq_i$，所有投票者对 $X$ 的一组排序 $(\succeq_1,\ldots,\succeq_n)$ 记作 $\vec{\succeq}$，称为一个排序组合。一个投票规则 $V$ 的作用就是，输入一个排序组合 $\vec{\succeq}$，则返回一个社会排序 $V(\vec{\succeq})$。

阿罗意义上的投票规则要求，每个投票者的排序 $\succeq_i$ 和最后得到的社会排序 $\succeq_V$ 都是弱序，即要满足下面两个性质：

1. 传递性：对任意 $x,y,z\in X$，若 $x\succeq y$ 且 $y\succeq z$，则 $x\succeq z$；
2. 完全性：对任意 $x,y\in X$，要么 $x\succeq y$，要么 $y\succeq x$（由完全性知，弱序也满足自反性，即对任意 $x\in X$，$x\succeq x$）。

我们称满足这些条件的投票规则为阿罗投票规则（阿罗称之为社会福利函数）。

任给弱序 $\succeq$，我们用 $\succ$ 表示其中的严格排序，即 $x\succ y$ 当且仅当 $x\succeq y$ 且并非 $y\succeq x$。我们用 $x\succeq_{V}y$ 表示，在社会排序 $V(\vec{\succeq})$ 中 $x$ 至少和 $y$ 一样好。类似的，$x\succ_V y$ 表示，在社会排序 $V(\vec{\succeq})$ 中 $x$ 严格好于 $y$。

一个阿罗投票规则 $V$ 是独裁的，意指存在某个独裁者 $i\in N$，使得对任意排序组合 $\vec{\succeq}$，对任意 $x,y\in X$，只要 $x\succ_i y$，则 $x\succ_V y$，即社会排序 $\succeq_V$ 中的严格排序完全等同于独裁者 $i$ 的严格排序。现在严格表述阿罗不可能性定理如下：

定理（阿罗不可能性定理）：若 $X$ 中的备选项超过两个，则不存在非独裁的阿罗投票规则 $V$ 能同时满足下面两个条件：
帕累托条件（即一致同意性）：对任意排序组合 $\vec{\succeq}$，对任意备选项 $x,y\in X$，若 $N$ 中投票者一致认为 $x$ 严格好于 $y$，则在社会排序 $\succeq_V$ 中也有 $x$ 严格好于 $y$；
独立性条件：对任意排序组合 $\vec{\succeq},\vec{\succeq'}$，对任意备选项 $x,y\in X$，若排序组合 $\vec{\succeq}$ 与 $\vec{\succeq'}$ 关于 $x,y$ 的个体排序相同，则 $\succeq_V$ 和 $\succeq'_V$ 关于 $x,y$ 的社会排序也相同。

换言之，在备选项超过两个的情况下，同时满足帕累托条件和独立性条件的阿罗投票规则一定是独裁的。为了证明这个定理，我们先引入两个重要概念。

定义 1（决定性联盟）：给定投票规则 $V$，称非空集 $G\subseteq N$ 在 $V$ 下关于 $(x,y)$ 是决定的，若对任意排序组合 $\vec{\succeq}$，只要 $G$ 中的投票者一致认为 $x$ 严格好于 $y$，则社会排序 $\vec{\succeq}$ 中也有 $x$ 严格好于 $y$；称 $G$ 是 $V$ 的决定性联盟，若 $G$ 在 $V$ 下关于所有 $(x,y)$ 都是决定的。

易见，若单点集 $\{i\}$ 是 $V$ 的决定性联盟，则 $i$ 是 $V$ 的独裁者。下面的证明本质上源自 1998 年诺贝尔经济学奖得主 Amartya Sen，他将阿罗的原始证明整理得更清晰了（阿罗的原始证明难以看出独立性条件在证明中的使用）。证明思路如下：

1. 根据定义，若 $V$ 满足帕累托条件，则 $N$ 是 $V$ 的决定性联盟。
2. 先证明关于决定性联盟的收缩引理：若非单点集 $G$ 是 $V$ 的决定性联盟，则 $G$ 的某个真子集 $G'$ 也是 $V$ 的决定性联盟。
3. 由于 $N$ 是有穷的，根据 1、2 归纳可得，存在由一个人构成的决定性联盟，即独裁者。

该证明包含了帕累托条件的明确使用，而独立性条件的使用则暗藏在收缩引理的证明中。为了证明收缩引理，需要引入另一个概念：弱决定性联盟。

定义 2（弱决定性联盟）：给定投票规则 $V$，称非空集 $G\subseteq N$ 在 $V$ 下关于 $(x,y)$ 是弱决定的，若对任意排序组合 $\vec{\succeq}$，只要 $G$ 中的成员一致认为 $x$ 严格好于 $y$，且 $G$ 外的成员（若有的话）一致认为 $y$ 严格好于 $x$，则社会排序 $\succeq_V$ 中也有 $x$ 严格好于 $y$。

显然，若 $G$ 在 $V$ 下关于 $(x,y)$ 的决定的，则 $G$ 也在 $V$ 下关于 $(x,y)$ 也是弱决定的。反之是否成立呢？如果 $V$ 满足帕累托条件和独立性条件，则反过来不仅成立，而且我们还有如下更强的结论：

引理 1（扩展引理）：设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。若 $G$ 在 $V$ 下关于 $(a,b)$ 是弱决定的，则 $G$ 是 $V$ 的决定性联盟（即 $G$ 在 $V$ 下关于任意 $(x,y)$ 都是决定的）。

这个结论有些令人意外，其证明需要使用独立性条件。

证明：设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。设 $G$ 在 $V$ 关于 $(a,b)$ 是弱决定的，任给 $(x,y)$，我们证明 $G$ 在 $V$ 下关于 $(x,y)$ 是决定的。不妨设 $x,y$ 与 $a,b$ 均不相同（相同的情况类似可证）。任给排序组合 $\vec{\succeq}$，使得 $G$ 中所有成员一致认为 $x$ 严格好于 $y$，只需证 $x\succ_V y$。考虑如下的排序组合 $\vec{\succeq'}$，其中

• $G$ 中的投票者认为：$x\succ' a\succ' b\succ' y$
• $G$ 之外的投票者认为：$x\succ' a$，$b\succ' y$，$b\succ' a$，且对 $x,y$ 的排序与 $\vec{\succeq}$ 保持一致

易见，$G$ 中成员一致认为 $a$ 严格好于 $b$，且 $G$ 外的成员一致认为 $b$ 严格好于 $a$，由于 $G$ 在 $V$ 下关于 $(a,b)$ 是弱决定的，故 $a\succ'_{V}b$。由于在 $\vec{\succeq'}$ 中所有人都认为 $x$ 严格好于 $a$，$b$ 严格好于 $y$，据帕累托条件有，$x\succ'_{V}a$，$b\succ'_V y$，据社会排序的传递性可得，$x\succ'_V y$。注意到 $\vec{\succeq}$ 与 $\vec{\succeq}$ 关于 $x,y$ 的个体排序是一样的，由独立性条件有，$x\succ_V y$，证毕。

有了扩展引理，现在我们可以证明下面的收缩引理了。

引理 2（收缩引理）：设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。若非单点集 $G$ 是 $V$ 的决定性联盟，则 $G$ 的某个真子集 $G'$ 也是 $V$ 的决定性联盟。

证明：由于 $G$ 是非单点集，故可将 $G$ 划分成两个不相交的非空子集 $G_{1}$ 和 $G_{2}$。考虑满足如下条件的排序组合 $\vec{\succeq}$（由于备选项超过两个，故可以做到）：

• $G_{1}$ 中的投票者认为：$x\succ y\succ z$；
• $G_{2}$ 中的投票者认为：$y\succ z\succ x$；
• $G$ 之外的投票者（如果有的话）认为：$z\succ x\succ y$。

注意到 $G$ 中所有投票者都认为 $y$ 严格好于 $z$，由 $G$ 是 $V$ 的决定性联盟可得，$y\succ_V z$。现在分别考虑两种情况（由于 $\succeq_V$ 是完全的，故有且仅有两种情况）：

1. $x\succ_{V}z$。任给排序组合 $\vec{\succeq'}$，使得 $G_{1}$ 中的成员在 $\vec{\succeq'}$ 中一致认为 $x$ 严格好于 $z$，且 $G_1$ 外的成员一致认为 $z$ 严格好于 $x$，此时 $\vec{\succeq'}$ 和 $\vec{\succeq}$ 关于 $x,z$ 的个体排序相同，故由独立性条件可得，$x\succ'_{V}z$，这意味着 $G_{1}$ 在 $V$ 下关于 $(x,z)$ 是弱决定的，再据扩展引理有，$G_{1}$ 是 $V$ 的决定性联盟。
2. $z\succeq_{V}x$。此时，据 $\succeq_{V}$ 的传递性有 $y\succ_{V}x$。同理于情况 1 可证，$G_{2}$ 是 $V$ 的决定性联盟。

综合 1、2，故总有 $G$ 的真子集是决定性联盟，证毕！

侠之大者：阿马蒂亚·森与自由悖论

“如果你因失去太阳而流泪，那么你也将失去群星”，这句国人耳熟能详的名人名言出自印度诗人泰戈尔的《飞鸟集》。泰戈尔不仅以诗著名，他还因不满僵化的英国殖民教育，创办了自己的学校。这位第一个获得诺贝尔文学奖的亚洲人大概不会料到，他的学校会走出亚洲第一个（也是迄今唯一的）诺贝尔经济学奖得主，而这位幸运儿的大名正是泰戈尔亲自拟定的，他的名字叫阿马蒂亚·森（Amartya Sen）。

少年英雄

与作为倒闭银行家的儿子阿罗不同，森出生于书香门第，父亲和外公都是大学教授。从小混迹于茵茵校园，除了投身学术，森想不出还有第二条路可以走。他在泰戈尔创办的学校里读完小学和中学，自由驰骋于梵文、数学和物理之间。9 岁时他目睹了 1943 年的孟加拉大饥荒，三百万人丧生的惨剧给他幼小的心灵以巨大震撼，17 岁中学毕业的他就选定了经济学作为自己的主攻方向，开始严肃思考贫困、公正、社会福利等他的国家以及整个人类都面临的重大问题。20 岁时他以最优异的成绩在印度获得经济学学士学位，3 年后他又以最优异的成绩获得英国剑桥大学的学士学位，在他刚成为剑桥大学的博士生时，年仅 23 岁的他就被任命为印度 Jadavpur 大学经济学系首任系主任。

才华横溢的森获得剑桥大学的优秀奖学金，这笔钱允许他在 4 年里做任何他想做的研究。森做了一个大胆决定：研习哲学。事后证明，这是一个相当明智的决定，为他日后在经济学、政治学、伦理学等领域向人类贡献前所未有的深刻洞见奠定了坚实的基础。没有这 4 年的内力修为，森仍然会是一名出色的剑客，但决不会成为一代武林宗师。

由于剑桥大学不怎么待见社会选择理论，森直到博士毕业回到印度，才有机会开展这方面的研究。他对世界最重要的贡献之一——自由悖论（又称帕累托自由不可能性定理）是在印度本土做出的。

自由悖论

“自由，自由，多少罪名假汝名以行”，罗曼·罗兰的这句名言至今仍振聋发聩。森是如何界定自由这个一望而知又难以琢磨的概念的呢？森认为，尽管自由并不是你想干什么就能干什么，但至少在某些私人领域，这个条件是可以得到满足的。例如，相比躺着睡，我更喜欢趴着睡，我这个口味虽然重了点，但不碍别人什么事。如果有两个社会状态 x 和 y，除了在 x 中我趴着睡而在 y 中我躺着睡以外，其他都一样，那么社会应该偏好或选择 x 而不是 y。每个人都有这样一些让社会遵从自己口味的私人领域（或社会状态），这一点看上去毫无争议。

然而，森发现，这个条件与另一个毫无争议的条件——帕累托条件（即一致同意性条件）竟然不能被同时满足。帕累托条件要求，如果每个人都认为 x 比 y 好，那么社会也要认为 x 比 y 好。帕累托条件通常被认为是效率的体现，在自由主义者看来，自由是效率的保障。计划经济之所以不如市场经济在配置资源上更有效率，就是因为后者比前者拥有更多自由。然而森的定理表明，自由不但不是效率的保障，甚至会妨碍效率。这真是见了鬼了！

实际上，森证明了一个更强的结论。首先，他重新定义了社会整合机制。他没有像阿罗一样，要求社会整合机制在输入一组线序后，也返回一个线序，而是只要求返回一个非空集合。即社会整合机制根据个体偏好，选出最好的（可以是多个）备选项，森称这样的社会整合机制为“社会选择函数”。其次，在社会选择函数的框架下，森重新表述了自由性条件和帕累托条件，使得这两个条件都变得更弱了。

自由性条件：至少有两个个体是自由的。某个个体是自由的，意指对该个体而言，存在一对社会状态（或备选项）x, y，使得该个体能根据自己关于 x, y 的偏好，决定哪个备选项不能入选社会选择的结果集：若个体认为 x > y，则 y 不能入选；反之，则 x 不能入选。

帕累托条件：若每个人都认为 x > y，则 y 不能入选社会选择的结果集。

帕累托自由不可能性定理（Sen 1970）：没有社会选择函数能同时满足自由性条件和帕累托条件。

这个结果尽管看上去令人惊讶，但证明却异常简单。假设存在满足这两个条件的社会选择函数，根据自由性条件，存在个体 A 和 B，A 关于某一对备选项 a, a' 有否决权，B 关于某一对备选项 b, b' 有否决权，不妨设 b, b' 与 a, a' 均不相同（相同的情况类似可证）。考虑如下一组排序：

A：b' > a > a' > b > 其他选项
B：a' > b > b' > a > 其他选项
其他个体：与 A 排序一样（或与 B 排序一样）

根据自由性条件，对任意社会选择函数，a' 和 b' 都不能入选。另一方面，由于所有人都认为 a' > b 且 b' > a，故据帕累托条件，a 和 b 也不能入选。最后，由于每个人都认为 a > 其他选项，故据帕累托条件，所有其他选项也不能入选，这与社会选择函数必须返回非空集矛盾，证毕！

名噪江湖

凭借自由悖论一举成名的森几乎在英美所有顶尖大学都担任过教授或访问教授（其中包括哈佛大学、剑桥大学、牛津大学、斯坦福大学、伦敦经济学院、耶鲁大学、加州大学伯克利分校、麻省理工大学、康乃尔大学等），拥有超过 90 所大学的名誉学位，并曾出任英国剑桥大学三一学院院长、美国经济学会会长和国际经济学会会长（至少在经济学领域，这近似于武林盟主了）。

值得一提的是，尽管大部分时间在英美等国工作和生活，森至今仍保持印度国籍（也是其唯一国籍，即使印度承认双重国籍），而他的印度身份还曾给他带来过不少麻烦。

一次，时任剑桥大学三一学院院长的森从国外旅行回到英国，伦敦机场的官员仔细审核了森的护照，发现住址一栏写的是“剑桥三一学院院长公寓”，这位官员怎么也想不到，赫赫有名的三一学院的院长是眼前这位印度佬，于是问森是不是院长的亲密朋友（否则怎么能与院长共处一室呢），森思考了一下“自己是不是自己的朋友”这个哲学问题，踌躇片刻后给出了肯定的回答，官员见森迟疑半晌，更加怀疑森是非法移民，于是盘问起森迟疑的原因。当然，这戏剧性的一幕最终妥善收场。

森不但坚持做一名印度公民，而且每年都要回国参与印度的公共事务。由于他对贫困、饥荒、不平等、剥夺等问题的研究，他被人们尊称为“经济学的良心”，这是比诺贝尔奖得主更来之不易的称谓。正如行走江湖，见面被人称呼一声“大侠”不难，而被唤作“侠之大者”的，恐怕就没有几个了。

2006 年《时代》杂志评选他为 60 年来的亚洲英雄。
2010 年《时代》杂志评选他为世界最有影响的百人之一。
2012 年他获得美国政府颁发的国家人文科学奖章，成为获得该奖的首位非美国公民。

1970 年，森曾在哈佛大学与阿罗和罗尔斯共同开设“社会公正”课程，42 年后的今天，已年届 80 的他，仍然以每学期两门课程的工作量，奋战在哈佛大学的教学第一线。

从“哥德尔不完备性定理”到“阿罗不可能性定理”

哥尼斯堡，这个德国小镇以拥有 7 座令人晕头转向的小桥而著名（直到瑞士人欧拉发明图论治好了晕头症）。一个被当地人用来对时的超级宅男诞生于此，他的名字叫康德。若干年后，康德仙逝，康德的母校迎来了一位新同学，他的名字叫希尔伯特。勤奋好学的希尔伯特迅速成长为数学界的带头大哥。在风起云涌的 1920 年代，这位带头大哥为江湖侠士们编织了一个值得赴汤蹈火、万死不辞的伟大梦想：构造一个完美的（一致且完备的）形式证明系统，用以证明任何数学命题的真假。（这令人想起他的德国前辈莱布尼茨）。直到 1930 年退休时，希尔伯特仍然对此心怀壮志，他掷地有声的放言：我们必须知道，我们必将知道（Wir müssen wissen, wir werden wissen）。不到 1 年，横空出世的奥地利剑客哥德尔（Gödel）就无情的粉碎了希尔伯特的美梦。他以无可辩驳的数学严密性证明了，在任何一致的可以表达初等算术的形式系统中，总有一些真的数学命题是不可证明的；换言之，一致性和（足够的）完备性不可能同时达到，完美的的形式系统不存在。这就像当各路人马怀揣藏宝图四处寻找那个传闻中的巨大宝藏时，有个初涉江湖的无名少侠跳出来说，藏宝图是假的，宝藏根本不存在。

20 年后，一度为找工作发愁的美国人阿罗（Kenneth Arrow）撕碎了人们心中的另一张藏宝图。从柏拉图开始，人们就一直向往着一种理想社会，在这个理想社会中，贤人当政，好人当道。然而，好坏这样的价值判断因人而异，如果没有一种机制能调和众人的口味，将其整合成整个社会的统一价值，那么贤人政治就只能是痴人说梦。一种完美的整合个人偏好的投票制度，一直是各路人马竞相探寻的宝藏。

阿罗也是寻宝大军中的一员。在美国经济大萧条时代，阿罗的最高理想是当一名中学数学老师，这个很快破灭的理想成就了日后 6 个诺贝尔奖得主（除阿罗外，他的 5 个学生也陆续获得诺奖）。1940 年大学毕业后，走头无路的阿罗选择了读研，边读书边打零工，并曾一度想放弃学术，到保险公司谋个赚钱的精算师职位了却余生。苍天有眼，阿罗最终放弃了这个糟糕的念头。本科毕业 11 年后，阿罗终于拿到博士学位，其姗姗来迟的博士论文让整个学界为之震惊。

在写博士论文期间，阿罗重新发现了 18 世纪法国数学家、政治学家孔多塞（Marquis de Condorcet）发现的投票悖论：少数服从多数原则可能导致投票结果出现循环，而循环排序被认为是不可接受的。这个投票悖论经常以水果大战的面目出现。我更喜欢用西游记里的人物举例。假设如来、观音和唐僧对孙悟空、猪八戒、沙和尚 3 个人进行人事考核，考核意见如下：

如来：沙和尚 > 猪八戒 > 孙悟空

观音：孙悟空 > 沙和尚 > 猪八戒

唐僧：猪八戒 > 孙悟空 > 沙和尚

由于多数人（如来、唐僧）认为猪八戒比孙悟空好，故根据少数服从多数原则，最终考核结果为：猪八戒 > 孙悟空；同样的，多数人（观音、唐僧）认为孙悟空比沙和尚好，故最终考核结果为：孙悟空 > 沙和尚；另一方面，多数人（如来，观音）又认为沙和尚比猪八戒好，于是最终结果出现“猪八戒 > 孙悟空 > 沙和尚 > 猪八戒”这样的循环。

这个悖论一直困扰着阿罗，他没有将其看作发现阿罗不可能性定理的契机，而是认为它“十分讨厌”，无缘无故招来麻烦。不久，阿罗发现，如果人们的偏好能够在一条直线上分布，例如在政治立场中，每个人的偏好要么趋左，要么居中，要么偏右，一个偏右的人不会同时趋左，同样，一个居中偏左的人也不会同时偏右，在这种情况下，像“剪刀-石头-布”这样的投票循环就不可能出现。阿罗认为这是一个值得发表的全新发现。他兴致勃勃在一次午餐向客人介绍了自己的发现。之后他随手拿起一本《政治经济学杂志》，令他大失所望的是，其中一篇文章讲的正好就是自己的发现。一计不成，又生一计，1948 年秋天，阿罗终于发现了令世人震惊的“阿罗不可能性定理”。

阿罗认为，一个完美的投票制度至少要同时满足下面 3 个条件：

条件 1（一致同意性）：如果所有人一致认为貂婵比西施好看，那么投票选出的美人榜中，貂婵也要排在西施前面。

条件 2（独立无关性）：投票制度在比较貂婵和西施谁更美时，只需要知道每个人对貂婵和西施的看法（谁更美）即可，不需要知道投票者对其他无关人等（比如说杨玉环或李宇春）的看法，即使这些人也是榜单中的候选项。

条件 3（非独裁性）：投票制度选出的结果不能由一个人说了算。

这 3 个条件看起来都相当自然，尽管离完美标准似乎还有相当的距离。然而，石破天惊的是，阿罗用初中生都能看懂的证明表明，即使只满足这 3 个条件也不可能办到。与之等价的结论是：任何同时满足条件 1 和条件 2 的投票制度只能是独裁制。这个结果实在太悲观，以至于阿罗根据建议在博士论文中改用了一个不那么悲观的名字：一般可能性定理（general possibility theorem）。令阿罗哭笑不得的是，在麦卡锡主义恰好大行其道的年代，这个藏头露尾的可能性定理仍然让他背上了“共产主义分子”的恶名。

需要立刻提醒的是，就像哥德尔不完备性定理被广为误解一样，阿罗不可能性定理也有严格的应用范围，不可无限推广。首先，该定理有两个隐含的前提：1、投票人数是有穷的；2、候选项至少有 3 项，这两个前提中的任何一个不满足，阿罗不可能性定理即不再成立。例如，如果候选项只有 2 项，则少数服从多数原则就能够同时满足上述 3 个条件（这也是为什么该原则被广泛使用，为什么很多国家都是两党制而不是多党制）；其次，阿罗考虑的投票制度只限于对线性排序进行整合的制度，阿罗称之为社会福利函数（social welfare function）。该函数的输入是一组线序，输出是一个线序，因而不包括像记分制这样的投票制度。所谓完美的投票制度不可能，只是说完美的社会福利函数不可能。

阿罗并非没有考虑到记分制这样的投票制度，只是他固执的认为，个体偏好具有主观性，不可公度。记分制的前提是可以统一度量不同个体的偏好，而阿罗认为，对不同个体的偏好进行运算，就像 10 个苹果 + 20 个香蕉一样没有意义。虽然我和你都对貂婵打了满分 5 分，可是这能说明我俩喜欢貂婵的程度一样吗？很可能不一样，我可能超级粉貂婵，如果满分是 100 分的话，我可能会打 100 分，而你可能只会打 95 分。另外，每个人的区分能力不一样，对我来说，99 分和 98 分是不同的，而对你来说，98 分和 95 分没有分别。这好比我手里拿着游标卡尺，而你手里只有米尺，而最后却要统一按照其中一种尺子的精度将我俩度量的值汇总，这在一个严格的数学家看来形同儿戏（实际上，一个物理学家已经不允许这样做了）。相反，采用排序制尽管在实际上忽略了很多信息（如偏好程度），但在数学上却经得起严格推敲。这就是阿罗拒绝考虑记分制的理由。

阿罗将其不可能性定理扩展成了 100 多页的博士论文，但单就定理证明而言，一页 A4 纸的篇幅足以胜任。这个深刻定理导致了其后一系列不可能性定理的发现，从此江湖上出现了一个叫“社会选择理论”（social choice theory）的新门派。在 1972 年的诺贝尔华山论剑中，开山掌门阿罗获得了经济学武学分支的最高奖赏。

SOMP 计划

SOMP 是 Study on Mobile Phone 的缩写，这是个一个3-5年的长期计划。

目标：建成一个手机上的综合学习平台，并针对逻辑学专业提供足够的学习内容。
定位：以大学生为主，以后可扩展至中小学生。
依托系统：以 Android 为主，以后可向 iphone 等其他平台移植。

功能描述：
1、课程学习
按课程名称提供课程的阅读资料，包括教材、经典文献、讲义、课件等，所有内容应适合手机阅读，方便查阅，并有批注功能。

2、课程回顾
按课程名称提供该课程的复习卡片，功能上与 Anki 类似。

3、指点迷津
提供各种学习和研究指南，包括英文写作、开题报告和毕业论文撰写、如何选题、如何查找文献等。

4、教学互动
具有 twitter 模式的提问功能，任何人都可以在第一时间给提问者解惑。

5、他山之石
提供相关课程的网络公开课视频或其他资料的链接，方便学生观看和学习网络公开课。

6、搜索引擎
提供一个搜索引擎，学生可以方便的搜索不清楚的概念和命题，或搜索想学习的课程。

7、边玩边学
设计一些可以在玩乐中学习知识的游戏。

8、自我测试
从试题库中随机生成一套试卷（主要是判断题和选择题），测试自己掌握知识的程度。

9、学术屏保
提供相关课程的学者照片、简介或逸闻趣事作为动态屏保，或者更 geek 一点，用定理和命题作屏保。

10、同步更新
具有云端功能，从而提供与网络和电脑的同步，也方便老师不断更新学习内容。

其实这些功能在软件上应该都不难实现，关键还是要有内容（特别是7），这需要每一个老师的参与。可以考虑让学生助教也参与到这个计划中来。

请大家想想还需要什么其他功能，欢迎留言。

面向大学学习的手机学习软件

随着智能手机的普及，在手机上使用软件以提高工作效率的软件越来越多，其中包括一些教育方面的软件。不过现有的教育软件大多是面向中小学的。是不是可以把大学的一些课程也做成手机软件的形式，从而让学生能随时随地的学习和复习课堂上的内容呢？特别的，可以通过网络建立学生与老师之间的更即时的互动，从而提高教学效果。换言之，把网络课堂变成手机课堂，把微博这种形式引入到教学系统，我认为这是个不错的主意。

面向计算机科学的非经典逻辑

目前的非经典逻辑教材多基于哲学逻辑传统，是从自然语言或哲学问题出发将各种非经典逻辑串起来的（例如Priest的那本）。今天看Gabbay的What is a logical system发现，很多非经典逻辑其实是从计算机领域产生的。应该另外有一条线，即以计算机领域的主要问题将非经典逻辑串起来。这样的教材不说更有价值，至少对原来的教材是一个有益的补充。

逻辑学何去何从？

为了给研究生上《非经典逻辑》，第一堂课准备讲什么是逻辑。于是想起 van Benthem 的一篇早就下载了但一直没看的文章：Where is logic going, and should it? 读 van Benthem 的文章既轻松又费力。轻松的是他的文字通常没那么严肃，笔调轻快，技术细节能省则省，不时还来点小幽默（譬如这篇文章他以列宁的《怎么办》开篇就显得很滑稽）。费力的是他文采太好，经常用一些对我来说不常见的单词，害得我动不动就要点星级译王（Linux下最好的字典）。看完后发现他的一些想法竟然和我的不谋而合（也许反过来说更嫌虚一点）。他指出了逻辑学将来下面几个方向值得探索：

1、图形逻辑与信息逻辑

信息有各种承载形式，除了语言文字外还有图形（van Benthem 一连用了三个和图形有关的词：diagram, picture, image，再加上他提到的 graph，这些词大概可以分别对应汉语里的图表、图片、图像、图形）。关于语言信息的推理和关于图形信息的推理之间有何关系？二者如何统一起来？目前为止基于语言的标准逻辑能够处理其他形式的信息推理吗？更一般的，信息这个概念究竟指什么？对信息概念的理解如何推动逻辑的发展？特别的，逻辑关于信息的定性刻画如何与信息论中关于信息的定量刻画统一起来？

我认为语言信息与图形信息的最大区别在于，前者是线性的，而后者是非线性的。语言信息的处理是串行的（或者说主要是串行的），而图形信息的处理则是并行的（或者说主要是并行的）。如果这一点是成立的，那么关于图形信息的逻辑推理（姑且称之为图形逻辑）会与关于语言信息的逻辑推理会有很大的不同。图形逻辑或许对图像和模式识别这一重要技术有所帮助。我想到的是图形逻辑这个方向，而 van Benthem 则野心更大，虽然他也拿图形说事，但最终他关心的是一个统一的信息逻辑。

我想到图形逻辑源于一篇科幻小说。这篇小说的作者是一个华裔奇才，中文名字叫蒋峯楠（Ted Chiang），学计算机出身的。他只写过八篇中短篇科幻小说，却几乎篇篇得奖。拿过三次科幻界至高奖雨果奖，以及星云奖、斯特金奖、坎贝尔奖等所有科幻大奖。在他的《你一生的故事》中，他想象了一种外星人用的文字，这种文字有点类似于汉字，不是字母的线性排列，但它比汉字更特别，它表达思想不是用若干字组成一句话，而是将所有思想都统一在一个字里，这个字或许更准确的说是一幅图。这幅图不能再拆分出更小的意义单位了。画这幅图也不是像我们通常作图那样有个起点和终点，而是同时进行的，因为这些外星人有七只手，他们写字的时候是同时在不同地方起笔的。这是启发我想到图形信息和文字信息区别的关键。由此我想到应该有一种刻画图形信息推理的逻辑。我认为任何语言学家和逻辑学家都应该看一下这篇小说，一定会有所启迪。

关于信息逻辑目前最好的参考文献是Handbook of the Philosophy of Information，是大牛Gabbay主编的Hanbook of the Philosophy of Science丛书中的第8卷。

2、动态、多主体与交互

这是以 van Benthem 为首的荷兰逻辑学家最近10年来一直在做的事。但一个一般的交互逻辑（logic of interaction）究竟是什么仍然没有解决。我认为到目前为止，博弈论仍然是刻画交互最有效的工具。交互逻辑离不开与博弈论的交叉。但到底是用逻辑去刻画博弈，还是用博弈来刻画逻辑，这两个方向哪个更有前途呢？现在的趋势似乎是前者占主流。Hitikka学派的Sandu则更倾向于后者。据说 van Benthem 关于逻辑与博弈的书马上要出版了，值得期待。

3、时间尺度与概率

这一部分没看明白，不知 van Benthem 究竟想表达什么。似乎是说大尺度的规律涉及到经验、进化、概率之类。逻辑与概率的交叉是个老问题了。逻辑（至少标准的逻辑）是基于规则的，而概率是基于统计的，而规则和统计似乎是两条平行不交叉的道路。早期的人工智能研究多是基于规则的，现在似乎转向基于大规模数据和统计为主。就以最常见的中文输入法来说，最智能的输入法通常所依赖的词库也是最大的。现在智能性奇高的所谓云输入法就是通过网上的海量数据弥补本地数据的不足而达到其神奇效果的（我曾用它输入过初中学过的一篇文言文，几乎不需要改动一个字）。两年前我曾尝试把统计的东西纳入逻辑模型用来刻画自然语言语义，但那个尝试实在太粗浅了。无论如何，如果真有基于统计的逻辑这样的东西出现，那它的革命性不会比图形逻辑甚至一个统一的信息逻辑更小。

逻辑学的宏伟蓝图

现代逻辑是在为数学乃至所有自然科学奠定基础这一宏伟目标下诞生和发展的。如今这一目标早已被证明无法实现，逻辑学一下子从一个耀眼明星变成了一个不受待见的客串演员。虽然几乎每一个重要学科都少不了它出场，但却总是当不了主角。面对这一现状，van Benthem 用上面这些他展望的前景为我们勾勒了一幅宏伟蓝图。尽管这幅蓝图还有些模糊不清，但只要怀有这分雄心壮志，矢志不移的坚持下去，即使一个跑龙套的演员也会成为国际巨星。那时候，我们可以像说出那句著名的台词“我是一个演员”一样而掷地有声的说一句：我是一个逻辑学家！

但随之而来的问题是，上面这些方向所涉及的内容似乎也是认知科学和计算机科学研究的对象，逻辑学在其中究竟扮演什么角色呢？van Benthem 给出下面这个图（他在文中并没有直接画出这个图）：


对这个图的解释 van Benthem 有点语焉不详，但多少有点启发性。认知科学属于自然科学，是直接描述和刻画现实世界（包括人）的；计算机科学则属于技术科学，其目的不是解释世界而是改造世界；逻辑学则可以和哲学、数学归为一类，提供理论基础和思维工具。van Benthem 认为这个分类可以代替逻辑学究竟是规范性的科学还是实证性的科学这样的陈词滥调。

这篇文章还提到，美国时代周刊曾在2000年评选100位20世纪最具影响力的人物，其中对人类思想影响最大的20位巨人中，哥德尔、图灵、维特根斯坦这些或多或少的逻辑学家赫然在列。这对于从事逻辑学研究的人来说或许是一件值得欣慰的事情。正如学校可以拿著名校友为自己脸上贴金，我们也可以拿这些杰出前辈和同行来哄哄自己或者后来之辈。

如何选题？（译稿）

下面是我2003年12月译自网上的一篇文章，现在看来这篇文章仍然有一定价值。原文的链接现在已经失效了，但为了表明出处仍然给出原来的链接：http://writecenter.cgu.edu/students/disstopic.html

翻译得比较生硬，请读者们包涵。

选择一个题目

很多学生在做学位论文的过程中都会碰到选题这个主要障碍。以下是如何选题的准备（proactive）方法：

1、形成一个在整个本科或研究生阶段都让你感兴趣的题目

对一些人而言这是显然的。一些研究生入学时清楚地知道自己想要与谁一起工作，想要写关于哪方面的文章。对另一些而言，研究生阶段是探索过程的一部分。很多研究生直到通过考试后才清楚自己学位论文的确切题目。下面的方法会帮助你发现自己的兴趣模式。列出你在本科和研究生期间所有学过课程的清单。列出你最喜欢的课本和作者的清单。列出你最喜欢阅读或思考的项目清单。有什么模式会出现？什么题目或问题一直是你感兴趣的？想办法把一些看上去不同类的题目关联起来。最重要的，思考在你的研究领域中什么地方是你想进去参加交流的。很少有学位论文能够实际改变一个领域的研究范式。因此你要做的是想办法加入这个领域的交流并对其有所贡献。你必须决定你究竟想和谁、想围绕哪些问题加入学术交流。

2、思考三个你想研究的首要问题（issues）并将其变成问句（questions）

有时我们知道我们想写的大题目，但需要帮助以找到一个角度或确定我们试图评价的研究问题。为此可以实施头脑风暴和自由写作（free-writing）练习。就一个问题花10到15分钟写出你能写出的所有内容。包括所有你能想到的问题和评论。不要担心语法或词语的选择。你所做的目的是尽量产生想法（ideas）。就一个或多个题目连续做几天这种练习。然后，回头看看你创造出了什么。是不是有些想法看上去像有前途的题目？和同行、老师或写作顾问讨论这些想法。有任何想法能够变成切实可行的研究问题以用来开题吗？类似的，你可以思考你的三个首要问题并其中两个或所有三个问题之间的交叉关联。通常这是学位论文写作者追求的一条卓有成效的途径。

3、看其他学者是怎么说的，这需要更多的调研和预研

预研在研究生阶段可能对所有课题都是至关重要的。显然你必须知道关于一个题目其他学者都说了些什么。然后你才能开始确定那个题目是否足够令你兴奋从而在几年内都能抓住你的注意。然后，决定从哪儿开始加入交流。我的一个同行发现她不得不缩小她的题目，因为她选择了两个19世纪的女作家作为写作对象，但发现她完全被其中一个吸引住了，从而放弃了另一个。因此，预备阅读能够唤醒你自己的热情和兴趣。如同他们在工作世界中所说：“做你喜爱的工作，那么你绝不会在你的一生中只工作一天。”看看课程笔记，老师们可能已经指出了潜在的研究题目或者就一个领域中尚未回答的问题作过评论。类似的，学者们经常就那些在专著中尚未予以充分研究的领域进行评论。他们从手头的研究转向批评，指出某些特定的研究应该完成。这通常意味着关于一个给定想法的研究的时机已经成熟。和老师或导师们讨论可能的题目。许多老师乐意就整个学位论文或一个给定题目的角度提供思想上的帮助。在你研究生阶段的早期就和老师们交谈，这样他们就知道你的兴趣所在。当你确定最终选题时，尽你所能和尽量多的学者们讨论，这样你就能得到帮助用来形成你的研究问题。注意论文征稿。会议组织要求论文提交者报告的主题（issue）通常能帮你了解这个领域的发展趋势。因此查阅这些信息，以为你潜在的题目或正在思考的题目的角度服务。类似的，申请奖学金资助。确信你仍然关注着你感兴趣的东西，但奖学金资助能使你的研究领域有感兴趣的读者群。最后，熟悉你的领域中那些可以获得的专门文集。你的老师可能会指导你去看以前的某个学者曾经涉及但未能尽力彻底调查的资料。

4、重复其他人的研究

有时一些老的、经典的研究可以在一个新的背景下或运用更现代的方法进行重新研究。但是注意不要进入那些已经被长期解决的问题中去。

注意事项：
在寻求能激发你的学术热情的学位论文题目时，将下列注意事项牢记在心：
1、选择一个能让你充满热情的题目，但同时注意其在就业市场上的生存能力。从你的导师那里获得关于潜在题目的反馈。你的题目可能不会像使你一样也使别人感兴趣。这会导致麻烦，因为如果你想进入学术交流，你需要能与之一起交流的人。很可能你在毕业时也想得到一份工作。思考期刊或学术出版社是否刊登或出版与你的题目类似的作品，在学术会议上同样的题目是否正引起人们的关注。不要为考虑你的课题能否马上出书而烦恼，但确实要注意学术动态，注意哪些领域是急需的，哪些关键问题正在形成。

2、研究并发现为什么你的题目以前未被研究
因为没有可获得的材料或无法得到潜在的采访对象，可能你选择的题目没有被研究过。尽管这个问题可能不会阻止一个有决心的学者从学术奥秘的最底层开始做起，但现实地说，如果有名的学者已经尝试过一个既定的题目并且未获成功，那么在开始你的杰作之前你可能还要再等几年。

3、选择一个可行的题目
诚实地对待你的课题的范围。如果你没有10年时间奉献给一个给定的课题，那么确保你选择的题目会花更少的时间。

一点评论：
从该文可以看出，对选题最重要的有四组关键词：一、兴趣（interest, passion, exciting）；二、问题（issue, question, problem）；三、角度（angle, approach）；四、交流（talk, conversation, discuss）。兴趣为研究提供持久的动力，问题决定研究的内容和深度，角度决定研究的创新性，交流使研究更完善。另，由于中英文的差异，像issue/question/topic，study/research/explore这样的近义词在中文中缺乏相应的区分，为了强调其区别，在翻译过程中做了一些处理。