3．2．第二种证明这个证明是基于无关选项独立性和帕累托最优原则的性质来证明√6mw不可能性定理【3】。证明从假定一个无穷备选方案集X和在这些备选方案上有严格的偏好序的n个主体开始。我们从备选方案集X里取任意两个不同的各选项a和b。第一步，对于每一个主体i∈(1，…，n)备选项a是排序最高的，备选项b是排序最低的。帕累托最优原则UN要求备选项a是严格在群偏好序的顶部。现在想象备选项b是上升的，一步一步或一列一列，到主体l序列的顶部，而其他各选项的排列仍旧未改变。根据条件帕累托最优原则，备选项a或者仍保持在群序列的项部或者被备选项b替代。如果备选项a仍保持在群体序列的项部，在主体2的排序里上升备选项b直到它到达到顶部，然后在第三，第四，……主体的排序里一样上升备选项b直到它到达项部。根据帕累托最优原则条件当我们上升备选项b到达每一个主体排序时，在最后，群体关系将排列b在a之上。现在我们关注主体m这个地方，备选项b上升到主体m的序列顶部之上之后，b第一次群偏好优于a。表格3．2．1和
      3．2．2表现分别是备选项b上升到主体m的序列顶部之上之前和之后的状态。表3．2．2R1…阶1Rm Rm+1…Ibb…bba…aa a a。 ‘群体序列Rba第二步，我们把下面的变化引入表格3．2．1和3．2．2。我们把备选项a移到i<m的主体i的序列的最低位置，移备选项a到i>m的主体i的序列的第二低位置。对于表格3．2．2，我们意识到向下移动a不会改变备选项b和其他任意一备选项之间的任何关系。因此根据无关选项独立性ⅡA条件，在群体序列中备选项b一定保持最高排序。表3．2．1和
      3．2．2移动备选项a后两种新的序列状态表l'和2’之间唯一的不同在于备选项a和b在m上的序列位置。因此，根据无关选项独立性IL～，在新的序列状态表1’里各选项b一定优于除了a之外的其他选项。但如果备选项b是在新的序列状态表1’里群体排序至少和备选项a一样高，又根据无关选项独立性ⅡA条件，b将在表
      3．2．1里群体排序至少和备选项a一样高。但这将与第一步里得到的内容相矛盾。因此，在新的序列状态表1’里，备选项a是群体排序最高的。第三步，我们考虑任意一个不同于备选项a和b的第三个备选项c。在新的序列状态表l’里备选项a在i<m的个体排序最低位置，在i>m的主体排序第二低位置。个体m在排序最高的位置是备选项a。在表格
      3．2．3里我们构造了一个偏好组合使得：在任意主体序列里，备选项a与其他备选项的关系的排序，保持与在新的序列状态表l’里一样。有这样一个偏好组合，每一个主体都有备选项c排列在备选项b之上。但是根据帕累托最优原12西南大学硕士学位论文 第三章A丌(’w不可能性定理的直观证明则UN条件，备选项a仍就是群体排序最高的。表3．2。3R 1…黜n_1RJnRm+l …Rn群体序列R第四步，以下面的方式修改表格3．2-3里的偏好组合，一个改变：对于i>m的主体，给备选项a和b的排序进行对换。这种变化的结果是什么呢?根据无关选项独立性ⅡA条件，所有主体对于a与除了b之外的所有选项的排序都不变。各选项b能成为群体的最高排序吗?回答是否定的，因为由于帕累托最优原则UN条件，备选项c一定群体偏好优于b。因此，备选项a是在群体序列的最高处，备选项c群体排列在b之上。第五步，我们构造一个在主体m的序列里备选项a在b序列之上的独裁偏好组合。例如，如在表格
      3．2．4里一样，在主体m的序列里备选项c在备选项a和b序列之间，而其他主体序列里备选项c都在顶部。无关选项独立性In条件不允许备选项c的排序对各选项a和b之间的群体排序有任何影响。相对于c来说a的排序如在第四步里一样。根据我们在第四步里的推论，由帕累托最优原则UN条件备选项a一定排序在c上，并且c最优一致与b。因此，根据群关系的传递性，备选项a优于b，并且无论什么时间主体m的序a在b上都成立。表3．2．4R 1…Rm一1 Rm RJn+1…Rn群体序列RaCb在上面的证明中如果我们改变被选方案b和c的排序，我们将得到相同性质a． ． ． ．． ．C ab． ．C aba Cb． ．．．．Cba． ．C-lUaa．C．bC． ．baC．．baC． ．baC． ．ba西南大学硕士学位论文 第三犟Arrow不可能性定理的直观证明的结果。我们看到，主体m对备选项a的排序在备选项c之上，这与群体对a和c排序是一致的。并且对于任意一个不同于a的备选项(如b)的排序也与群体排序一致。说明主体m是独裁的。在上面的分析中，a是在第一步被任意选中的。显然，对每一这样的选择都有一个独裁者。我们还可以有不同的选择，对不同的选择就有不同的独裁者吗?答案是否定的。因为群体偏好序只有一个，而不同的独裁都一定有不同的偏好序，二者矛盾。因此，对任一群体偏好序而言，一定有且仅有一个独裁者。这一证明说明mTow社会福利函数在无限制定义域内不可能同时满足帕累托最优原则UN、无关选项独立性ⅡA和非独裁性ND条件。14西南大学硕士学位论文 第四章Arrow不可能性定理的一阶逻辑形式证明第四章衙ow不可能性定理的一阶逻辑形式证明知Tow不可能性定理是社会选择理论的一个重要理论。理论指出，在一定固有条件下，把一个有限个体集的偏好聚合成一个群偏好序是不可能的[6】。可以用一阶逻辑语言形式化这一理论，从而简化A玎0w不可能性定理为一个命题：一个给定的一阶公式集没有一个有穷模型。最终希望这种形式化能为加Tow不可能性定理的完全自动推理证明提供帮助，成为社会选择理论的一个相似理论。至少在一个固定的个体量的情形下，证明这种情况是可能的，作为这一理论自动推理工具的最初尝试【4】。社会选择理论是关于集体决策理论的设计和分析方法的数理经济学的一个分支。趾T0w不可能性定理是这一领域内的一个经典理论。不可能性定理指出，在一定固有条件下，把一个有限主体集的偏好聚合成一个群偏好序是不可能的。近年来，在社会选择理论中有很多著作专注于形式化的研究。人们对数理逻辑、自动推理到社会选择这类应用工具性理论产生广泛的兴趣，主要原因有：首先，一个问题理论论域的形式化能帮助我们对该理论论域的更深理解。比如，在社会选择理论中，形式化能阐明推演一个描述性理论设想的精准性。．其次，一个完全形式化、自动推演证明能确保一个理论的正确性。正如B1肌f1957)指出的那样，mrow的证明包含了一个错误；这是公认的并且在加T0w著作的第二版中得到修证。标准式的证明是否在充分的细节上加以证明?我们当然不想去解释社会选择最重要的理论不是以合理的基础为依据。然而，对于新的校正方式和不够充足的研究理论，自动推理就是一个很有用的工具。最后，社会选择理论自动推理的使用很有可能完全揭示出新的理论。例如，当我们弱化或改变其中一些公理，或者通过使用模型生成元去自动推演反例时，我们就能设想使用自动推演理论去验证不可能定理所承载的理论将变为可能。文献‰gandLin
      (2009)在基于一定的受限范围下使得这种理论得以实现。以前有很多理论著作中讨论过使用模态逻辑和集合论语言形式化知粥，不可能性定理。本章节用经典的一阶逻辑FOL系统去塑造—咖w不可能性定理的模型框架。把兴趣放在FOL而非其他系统上的理由是：以偏好模型为核心的线序是一种自然语言。相对其他系统来说，FOL在自动推演上更具有先进性。我们能够证明，在描述线序语言的一阶逻辑FOL系统里，棚不可能性定理等值于一个特定有穷一阶公理系统，但它却没有有穷模型。西南大学硕士学位论文

      第四章Arrow不可能性定理的一阶逻辑形式证明
      4．1．一个基于归纳论证的新的证明本节将回顾√6帅w不可能性定理和它表达的社会福利函数结构，讨论‰gandLin
      (2009)的理论中给出了—6啪w不可能性定理的一个基于归纳论证的新的证明，即在最基础的情形下使用自动推理工具自动验证，证明如何生成的一个弓l理(1eIrlIIla)和需要排序的一个无限备选方案集的情形。令X为备选方案集，R为备选方案集X上的二元关系，且R是完备，自反和传递的。T限)表示所有偏好序的集合。其中Ri是个体i的偏好关系。令N为有限主体集，n元组(R-，…，＆)表示偏好的组合，T(R)n表示偏好组合的集合，一个在备选方案x和主体集N上的swF社会福利函数为：F：T(R)“_T(R)。一个社会福利函数SWF聚合机制要满足的几个性质【6，10·15】：第一个性质是普遍定义域，F的定义域包括了备选方案集X上所有逻辑上可能的所有偏好主体序列的n元组。另外三个性质：IJN：(衄如im姆)如果每一个主体认为选项a优于b，那么群偏好也将认为选项a优于b，即F满足一致性原则。ⅡA：如果两个被选方案a和b的群排序仅仅依赖于他们每一个个体的相对排序，那么F满足无关选项独立性原则；舳：在F定义域内的所有偏好组合里，对于备选方案集X上的备选项a和b所有偏好对，群里没有一主体使得如果aPib，那么aPb，F则满足非独裁性条件。mrow不可能性定理表达为：定理4．1．1：如果备选方案集x和主体集N是有限和非空的，并且IXl23，那么不存在二个满足条件UN、ⅡA和ND的在备选方案X主体集N上的社会福利函数S岍。A玎('w不可能性定理的几种重要证明【1l’12，18】大都是在给定任意主体集和备选项集的普通论证。一种新的推演证明：即在最基础的情形下使用自动推理自动验证。通过证明两个引理(1emma)去简化定理为3个备选方案和2个主体的基本情形，最后一步通过使用限制使用程序或可满足性的验证程序(s01ver)而去验证证明【6】。第一个引理(1enHna)是在被选方案数量上的归纳步骤“如果存在满足√咖w不可能性定理性质的m+1个备选方案和n个主体的一个社会福利函数S岍，那么也将存在满足—心row不可能性定理性质的m个备选方案和n个主体的一个社会16西南大学硕士学位论文 第四章A玎ow不可能性定理的一阶逻辑形式证明福利函数S、)l，F。”这个引理(1e姗a)的倒置将会把“不可能性”这个性质从最基本的情形带到每一个有穷的被选方案集：“如果对于3个备选方案集和n个主体集的情形下J咖w不可能性定理成立，那么对于m个备选方案集和n个主体集的情形下mT0w不可能性定理成立。”现在证明也包含一个无穷备选方案集情形下的这个引理(1ema)的概论：引理(妇曩)4．1．2：如果对应于备选方案集X和主体集N，并且IXl23，存在一个满足UN，ⅡA和ND性质的社会福利函数S骄，那么对应于一个备选方案Xt且lX-I=3和主体集N上，存在一个满足相同性质的社会福利函数SWF【13】。证明，令Xf_(al’a2，a3)是X上一个包含三个不同备选方案的任意集，X’上的每一个线序P能被扩展为X上的一个线序Pc，定义对应于X’和N的一个社会福利函数SWf’为：xf’(Dy：§xf(豳y这里旦是X’上的一个偏好组合，堡是X上任意一个扩展的一个偏好组合。根据无关选项独立性原则ⅡA这个定义不受扩张选择性影响；根据定义f’将保持一致性原则和无关选项独立性原则。需要证明的是f’是非独裁的。假设相反：f’是独裁的，我们证明f也是独裁的。与假设矛盾。令i(i∈№是函数f’上的独裁者，x和y是X中的两个不同的备选方案，假设xPiy在偏好组合旦上。需要证明x迎)y成立。x和y是X’中普通的两个各选方案，al和a2是XI中不同于x和y的两个不同元素。令个体i改变它的偏好关系使得alPia2，得到一个偏好组合里。令每个主体(包括i)重新排列他们的偏好关系使得】【Pfal和a2Pjy称这个偏好组合里”，这两步是在不影响最初x和y的排序下进行的。因此，根据I队，xf(勤y当且仅当xf俚”)y。根据f的一致性性质有x f巴’)al和a2f巴’)y。由于i是X’上的一个独裁者，那么a1f巴’)a2成立。因此根据传递性得到x f巴’)yf所以x f(P)y成立。这个引理(1emma)的倒置“：如果在3个备选和n个体的情形下A仃0w定理成立，那么在任意一个超大备选方案集X(包括无穷情形)和n个主体下A盯('w不可能性定理也成立。