不可能性定理与通用代数工具箱

在所有情况下，X都必须被视为一个多排序关系，所有组件（参数）都有不同的类型。demponence约束用X+的“+”编码。或者，小工具重新格式化中的支持性条件转换为允许在小工具中使用任意一元关系。当我们允许后者时，这个小工具就是Xf小工具。定理9。对于每个D和m，都有一个多排序关系的固定集P=P（D，m），X Dmis是一个关于IIA+幂等性（支持性）+非独裁的不可能域，当且仅当我们可以用一个gadget来表示P的每个成员，该gadget的联合体只有（适当的多排序）X+-（Xf）-子句。此外，辅助变量的个数由某个显式函数φ（m，|D |）上界（m中的单指数）。更详细的定理在定理17中重述，并在第6节中得到证明。我们的描述允许我们以两种不同的方式在有限时间内计算X是否是不可能域（无论是在弱域还是在支持域中）：要么通过检查聚合器（最多一定数量的参数）（定理8），要么通过检查小工具（最多一定大小）（定理9）。我们的小工具特征化的一个主要应用是，我们可以通过仅仅展示几个小工具（而不是试图排除一大组聚合器）来证明域X的不可能性。在某些情况下，我们可以利用对称性，根据特定问题定制小工具。我们可以通过小工具排除大多数聚合器，而直接处理其他聚合器。使用小工具，我们可以显示由{（u，…，um）定义的成对区分关系∈ Dm | uk6=u`（1≤ k<`≤ m） 当| D |>m时，}是不可能域≥ 2当| D |=m时≥ 3关于IIA+幂等性+非独裁条件。

在[DH10b]中，这仅在IIA+支持性+非独裁条件下得到证明，而[FF11]仅在| D |=m>2时证明上述情况。一些作者认为我们讨论的可能性概念过于宽宏大量。研究了几个进一步的限制，例如[Kal02]。例如，Dokow和Holzman质疑定理5中出现的{0，1}m的线性子空间是否真的应该被视为可能性域[DH10a]。第12节我们提出了一个新的聚合器类，它加强了非独裁的概念。我们的新定义直接来自代数理论，并具有许多可取的性质。虽然Dokow和Holzman完全解决了二元计算的问题，但宇宙代数给出了他们定理的一种更明确的形式：定理10。让X {0，1}mnon退化。那么X是一个关于IIA+幂等+非独裁的不可能域，当且仅当X被完全阻塞并且它不是一个有效子空间。如果X没有完全被阻止，那么对于所有1≤ J≤ m以下情况之一：1。存在一个f，使得fjis是半格运算u∨ v还是u∧ v、 二,。有一个f，使得FJI是多数操作（u∨ v）∧ （五）∨ w）∧ （w）∨ u） ，3。有一个f，使得fjis是Mal’tsev操作u- v+w模式2,4。代数理论一个关键的观察结果是，如果我们转向多排序关系、小工具、多态性等，而不是更常见的单排序关系，代数理论可以在赋值聚合上下文中工作。多重排序关系不同于通常的关系，因为我们考虑的关系的每个组成部分都有一种类型。每种类型b都有一个指定的范围集Db。在不丧失一般性的情况下，我们可以假设允许类型的集合是[t]={1，…，t}，其中t是一个固定的正整数。对应的是D，Dt。

让XQmj=1Dτj，其中τj∈ [t] 一个人≤ J≤ m、 我们用（X，τ）来表示X，其中τ=（τ，…，τm），以表明它是多重排序的，以及其成分的类型。（在我们的赋值聚合设置中，t=m，Dj=prjX，X的类型将是（X，（1，…，m））。）定义6（小工具，多分类）。我们定义了一个类型集[t]，{Db}b∈[t] 。如果存在多排序的小工具表达式R（x，…，xk）= Yyk:R（z1,1，…，z1，k）∧ . . . ∧ Rp（zp，1，…，zp，kp），其中每个Ri要么来自Γ，要么来自多排序等式关系（x=y，（b，b））（因此对于某些b，类型（x）=类型（y）=b）∈ [t] 。变量z1,1，zp，集合{x，…，xk}中的kpare∪ {y，…，yk}。在CSP的代数理论中，投票函数被称为多态性。根据它们的代数性质，对它们进行了广泛的研究和分类。在更常见的单排序情况下，我们被迫用相同的函数汇总每个问题。在多排序的情况下，不同的类型被独立地聚合：我们有和类型一样多的聚合器函数。（即使对于两种类型的SA 6=b，我们有Da=Db，聚合器Fa和FB可能会有所不同。）这些正是我们在评估聚合设置中需要的多态性。定义7（多排序多态性）。固定t，{Db}b∈[t] 。设（X，τ）为多排序关系，其中τ=（τ，…，τm）∈ [t] 修理≥ 1.A系列fb:Dnb→ Db（1）≤ B≤ t） 如果元组（fτ，…，fτm）是关系X的IIA聚合器，即它需要Xninto X，则函数的集合称为（X，τ）的多排序多态性。

更一般地说，集合fb:Dnb→ Db（1）≤ B≤ t） 如果{fb}b，则函数集合是关于一组多排序关系（每个关系都在同一固定类型集合上）的多排序多态性∈[t] 是Γ中每个关系的多排序多态性。笔记上面概括了单排序多态性的概念，当t=1和D=D时，也可以选择t=m，Dj=Prj（X），并键入Xas（X，（1，…，m））。定义8（MPol）。Fix[t]和{Db}b∈[t] 。多排序关系集合Γ的所有多排序多态性集合用MPol（Γ）表示。定义9（MInv）。Fix[t]和{Db}b∈[t] 。由多排序聚合器函数的集合F保持的所有多排序关系的集合用MInv（F）表示。定义10（h·i）。Fix[t]和{Db}b∈[t] 。对于一组多排序关系，我们定义：hΓi={（R，τ）|（R，τ）多排序gadget-简化为}现在我们可以陈述我们的多排序盖革定理：定理11。Fix[t]和{Db}b∈[t] ，并设Γ，Γ为（可能为有限）多排序关系集，设F，Fbe为（可能为有限）多排序聚合器集。然后1。MInv（MPol（Γ））=hΓi2。Γ  Γ==> MPol（Γ） MPol（Γ）3。F F==> MInv（F） MInv（F）证明。让我们首先回顾一下单排序盖革定理：定理12（D.盖革[Geiger[68]）。固定D，并让Γ，Γ成为函数集上的关系集，让F，Fbe（可能是有限的）函数集，这样每个函数都来自于一些D次方toD（即D的聚合函数）。然后1。Inv（Pol（Γ））=hΓi2。Pol（Inv（F））=[F]3。Γ  Γ==> 波尔（Γ） Pol（Γ）4。F F==> 投资部（F） Inv（F）为了将我们的多排序版本翻译成上述单排序版本，我们首先定义=D˙∪D˙∪ · · ·˙∪Dt，其中Db是类型b的范围。如果最初的Db不是不相交的，我们会使它们不相交，而不会失去通用性。

非空的多排序关系X Dτ×···×Dτmca现在可以解释为单排序关系XD 马克。我们注意到，将它们视为集合，X和XD是完全相同的。XD中的索引D只是提醒我们，我们将XD视为D中的单个排序关系，而将X视为（X，τ）。由于Dbs是不相交的，因此从任何此类XD6= 我们可以恢复每个坐标的类型（XD的单个元素的组件已经提供了这个信息）。如果Γ是固定类型集[t]上的一组多排序关系，那么让ΓDbe是X∈ Γ.为了b∈ [t] 我们介绍了一元关系tbd（在单排序世界中）：Tb（u）←→ U∈ 换句话说，Tb（u）表示“在多排序的世界中，u有b型。”对于关系集合{T，…，Tt}，我们引入符号Θ。定义11。允许 D上的任何一组关系，使得Θ . 那么对于任何多态性f:Dn→ D of 还有b∈ [t] 我们可以定义fb:Dnb→ Dbas fb（x）=Dnb上的f（x）。笔记我们知道DNB上的f从DBS中获取值，因为它是Tb的聚合器∈ .我们现在有：引理13。设Γ是固定类型集[t]上的任意多排序关系集，其符号如前所述。那么以下是等价的：1。（f，…，ft）是Γ的多排序多态性；2.序列f，如定义11所述，FTA是由以下因素的某些多态性引起的： = ΓD∪ Θ.我们不能证明这个简单的引理。回到定理11的证明，唯一的挑战是证明1。从2号开始。三,。这是显而易见的。根据已知的复合引理（多态复合，gadgets）可知，minv（MPol（Γ）） 我必须向另一个方向展示安全壳。定理12给出了inv（Pol（ΓD∪ Θ））=hΓD∪ Θid在这里，h·id中的下标表示该小工具一代是在单一排序的世界中获取的。

我们的证明方案是将hΓi与hΓD联系起来∪ ΘiDand MInv（MPol（Γ））至Inv（Pol（ΓD）∪ Θ)).我们可以从ΓD生成哪些非空关系∪ Θ，即hΓD的元素是什么∪ Θi？这组发电机的Agadget的形式为（x，…，xk）= Yyk:R（z1,1，…，z1，k）∧ . . . ∧ Rp（zp，1，…，zp，kp）（1），其中每个Ri要么来自Γ，要么来自Θ或=关系。定义12。我们说（1）中的（x-或y-）变量z的类型为b，如果当赋值的共轭项（不含存在量词）保持时，z的值为Db。换句话说，在连词中加上tb（z）并不能消除连词中任何令人满意的赋值。从aΓD开始∪ Θgadget（回忆一下，这是一个单独排序的gadget）只有D个变量，任何变量都没有先验类型限制（除了整个D）。然而，如果变量z与关系SD有关，其中S是来自Γ的关系，则S为该变量提供了类型b：如果z为6，则SDnever不成立∈ Db，所以我们不妨将z限制为Db。现在假设有一个变量zsuch，它在（1）的右边包含一个关系z=zz和一个已经受限的z。那么zmust也来自Db。当然，这样的方程链也会对链末端的变量强制执行类型。最后，任何关系Tb（z）都会在z上强制执行类型b。总之，我们可以将类型b分配给变量z if1。Tb（z）出现在小工具中；2.z出现在类型为b的ΓD约束中；3.有一系列等式关系，从任何限制为b型的变量开始（1.或2.）这导致了z。我们注意到，一个变量不能有两种不同（即相互矛盾）的类型。类型中的任何矛盾都会使R不可维护（即空关系）。

因此，R相当于一个“类型化部分”和一个“非类型化部分”的直接乘积：R=Rtyped×（w1,1=·s=w1，s）×·wl，1=·wl，sl）|{z}非类型化部分wi，js是变量，非类型化（或类型化）部分可能不存在。第一点-3.也给thatRtypedis一个语法上可识别的R部分，它是通过从右边删除一些变量和术语而产生的。尽管Rtypedis是一个ΓD-gadget（回想一下，Γ是一个由类型化关系集Γ构造的非类型化关系集），但由于其语法，我们也可以将其解读为（类型化的）Γgadget，此外还有完全相同的语义（这意味着Rtypedas a set与我们将公式解读为Γ-gadget时完全相同）。因此，Rtyped[被视为一种多排序关系]∈ hΓi.接下来我们宣称∈ MInv（MPol（Γ））-→ 研发部∈ 投资部（波兰）∪ Θ)).左侧显示R由所有多排序多态性（f，…，ft）保持∈ MPol（Γ））。我们有f∈ 波尔（ΓD）∪ Θ）当且仅当其成分序列（如定义11所示）（f，…，ft）∈ MPol（Γ）。所以RDI由所有f∈ 波尔（ΓD）∪ Θ），证明我们的主张。通过单排序盖革定理（应用于ΓD∪Θ）我们从第三次世界大战开始∈ 投资部（波兰）∪Θ）），我们也有那条路∈ 赫德∪ Θi.在前面的两段中，我们已经看到，那么Rd的形式必须是Rtyped×（α1,1=···=α1，s）×·····×（αl，1=··=αl，sl）。但由于RDA的所有组件都是类型化的，所以只有类型化的部分（RD=Rtyped=R作为集合）。所以R∈ hΓi.5小工具描述不可能盖革的Galois连接（及其多排序版本）发出这样一个信息：我们可以从一组关系（或从单个关系）创建的小工具越多，这组关系的聚合器就越小。不可能域X没有任何非平凡的聚合器，因此X被期望生成所有关系。对于科塞来说，更让我们兴奋的是相反的情况。

如果我们可以把所有关系写成由X和一些简单关系组成的小工具，那么X一定是一个不可能域。然而，还有一些工作要做：1。我们需要理解幂等性（支持性）条件的作用。2.我们想找到一个最小的（出于算法原因，但也为了方便）小工具集，它已经暗示了X的不可能性。5.1幂等性和支持性条件幂等性和支持性条件对应于向我们的关系基集中添加额外的关系，我们从中构建证明X不可能性的小工具。我们的基集是原始的{X}。对于幂等条件，我们添加所有赋值关系；对于支持条件，我们添加所有一元关系（定义如下）。定义13（一元关系，Xf）。多重排序的一元关系是（x）∈ A、 （A）），其中∈ [t] isa类型和A 爸爸。对于多排序关系X，我们将X定义为包含X的关系集，以及类型集[t]、{Db}b的所有一元关系∈[t] 定义了X。定义14（分配关系，X+）。多排序赋值关系是（x=v，（a））形式的一元关系，其中v∈ Da（即| A |=1）。X+是一组关系，包括X和类型集[t]，{Db}b的所有赋值关系∈[t] 定义了X。引理14。一个多排序函数g=（g，…，gt），其中ga:Dna→ Da是幂等的（意思是每个GAI都是幂等的）当且仅当它聚合了所有类型的所有赋值关系。它是支持的，当且仅当它聚合了所有类型的所有一元关系时。我们省略了这个已知陈述的简单证明。5.2原始问题的翻译在用小工具描述它之前，我们用一小段时间来讨论代数语言中“不可能”的确切概念。引理15。

以下投票理论和代数条件是等价的：代数投票理论 Dmis是一个关系X Dmis a Domainf=（f，…，fm），其中fj:Dnj→ 流行音乐播音员Herdj=定义的prjX（将D限定为DJ很重要）。IIA聚合器函数f:Xn→ 十、 1.≤ K≤ n：所有的fjare投影在他们的坐标上。下面的投票理论和代数问题是等价的：代数投票理论判定X是否具有决定X是否具有幂等（支持）幂等（支持）非独裁非独裁多排序多态性。IIA聚合器。如果上述问题的答案是“否”，那么X是一个不可能域。5.3根据引理14、15和我们的多排序盖革定理（定理11），不难证明：引理16。域X 就IIA+幂等性（支持性）+非独裁而言，当且仅当所有多排序关系都可以生成为多排序X+（Xf）-小工具时，Dmis是不可能的。这里t=m，Dj=prjX表示1≤ J≤ 而X的类型是（X，（1，…，m））。然而，所有（多排序）关系的集合非常大！幸运的是，我们可以选择一个生成所有关系的有限子集（实际上，以许多不同的方式），只考虑这些就足够了。定义15（非二进制或关系）。我们定义了多重排序关系Ru，vk，`只有当x=u和y=v同时保持时，它才是不成立的（x有k型，v有`）。信息公式：Ru，vk，`（x，y）=（x=u）∧ y=v，（k，`）。定义16（多重排序并非所有相等的关系）。只有当Da=Db=Dc={0,1}时，才能定义A、b、c型上的多排序NAE关系。在这种情况下，a，b，c（x，y，z）=（|{x，y，z}|>1，（a，b，c））。我们现在准备陈述我们的小工具对不可能域X的描述：定理17。

让X 不退化。设t=m，τ=（1，…，m），j型beDj=prjX的范围。那么X是关于IIA+幂等性+非独裁性的不可能域，当且仅当每1有（X，τ）+-表示Ru，vk的gadget≤ k、 `≤ MU∈ prkX，v∈ pr`X.此外，对于某些1，如果| Dj |=2≤ J≤ m、 我们还需要添加多排序的NAE gadgeton类型（j，j，j）。类似的陈述，当我们用“支持性”替换“幂等性”时，需要用（X，τ）f.6替换（X，τ）+。首先，我们给出定理17的证明。我们展示了非平凡的方向，也就是说，如果我们能创造出定理17所要求的所有小工具，剩下的唯一多态性就是独裁。备注2。即使是hΓi中的一个小玩意也可能产生严重后果。例如，如果我们可以在两种不同类型的a和b（使用通用字母表）之间构造相等小工具（x=y，（a，b）），任何多排序多态性（f，…，ft）∈ MPol（Γ）必须具有相同的a和B成分。我们将在本节末尾证明这一点。我们证明定理17的方法是开始创建小工具，并将它们用作“子程序”，以创建更多的小工具。下面的引理表示，对于任何固定的1≤ k、 “<t来自Ru，vk`∈ hΓi引理18中，hΓi one可以构造类型为（k，`）的所有多排序二元关系。让我≤ k、 `≤ t和（S，（k，`）是包含在prkX×pr`X中的任何多排序关系∧（u，v）6∈SRu，vk，`。我们省略了直接的证据。注意，没有什么能阻止我们在引理中设置k=`的，在这种情况下，我们得到了所有的二元关系（R） Dk）。hΓi中这些关系的存在说明了Γ的（多排序）多态性是什么？他们说了很多。