为什么基于构造微积分的语言如此多地使用 Setoids?
Why do Calculus of Construction based languages use Setoids so much?
人们发现 Setoid 被广泛用于 Agda、Coq 等语言中……确实,Lean 等语言认为它们可以帮助避免“Setoid 地狱”。首先使用 Setoids 的原因是什么?
转向基于 HoTT 的外延类型理论(例如立方体 Agda)是否减少了对 Setoids 的需求?
理想情况下,人们当然希望能够将任意等价关系视为莱布尼茨等式 (eq
),从而能够在任意上下文中进行重写。即通过等价关系定义一个类型的商
我不是该主题的专家,但我一直在想同样的问题有一段时间了,我认为对 setoids 的依赖源于这样一个事实,即商在类型论中仍然是一个鲜为人知的概念。
- 当我们不 have/want 商类型时,我们就会陷入困境。
- 我们可以公理化商类型,我相信(我可能弄错了)这就是精益所做的。
- 我们可以开发一种可以自然地表达商的类型理论,这就是 HoTT/Cubical TT 对更高归纳类型所做的。
此外,商类型(或我对它们的幼稚想象)迫使我们以一种可能不太理想的方式将程序和证明打包在一起:两个商类型之间的函数是一个普通函数以及一个证明它尊重潜在的等价关系。虽然技术上可以做到这一点,但这种编程和证明的交错可以说是不可取的,因为它使程序不可读:人们经常试图将程序和证明保存在两个完全独立的世界中(这样就要求 setoids,使类型与其等价关系分开) ,或者更改一些表示,使程序和证明成为同一个实体(因此我们甚至可能不需要首先明确地推理等价性)。
正如 Li-yao Xia 的回答所述,当我们没有或不想使用商时,使用 setoids。
在 HoTT 书中和精益商数中(基本上)公理化。 Lean 和 HoTT 书之间的一个区别是后者有更多更高的归纳类型,而 Lean 只有商和(常规)归纳类型。如果我们只关注商数(在 HoTT 书中设置商数),它在精益和 Book HoTT 中的效果是一样的。在这种情况下,您只需假设给定一个类型 A
和 A
上的等价 R
,您有一个商 Q
,以及一个函数 [-] : A → Q
属性 ∀ x y : A, R x y → [x] = [y]
。它具有以下消除原则:要为某种类型 X
(或 HoTT 中的 hSet X
)构造一个函数 g : Q → X
,我们需要一个函数 f : A → X
以便我们可以证明∀ x y : A, R x y → f x = f y
。这与计算规则一起出现,该规则声明 ∀ x : A, g [x] ≡ f x
(这是 Lean 和 Book HoTT 中的定义等式)。
这个商的主要缺点是它破坏了正则性。规范性指出,(比方说)自然数中的每个封闭项(即没有自由变量的项)都归一化为零或某个自然数的后继项。这个商打破正则性的原因是我们可以将 =
的消元原理应用于商中的新等式,并且这样的项不会减少。在精益中,这无关紧要,因为在所有我们关心的情况下,我们仍然可以证明相等,即使它可能不是定义上的相等。
三次型理论有一种奇特的方法来处理商,同时保持正则性。在 CTT 中,相等性的工作方式不同,这意味着可以在保持规范性的同时引入更高的归纳类型。 CTT 的潜在缺点是类型理论要复杂得多,并且您必须接受 HoTT(尤其是放弃证明无关性)。
[Lia-yao Xia 和 Floris van Doorn 的回答都很好,所以我会尝试用更多信息来补充他们。]
另一种观点认为,商虽然在经典数学中经常使用,但也许毕竟不是那么大。不取商但坚持 Groupoids 是 exactly 非交换几何 从哪里开始!它告诉我们,有些商的表现非常糟糕,而我们最不想做的事情(在那些情况下!)就是实际商。但是如果你使用 'right' 工具来处理它,它本身并没有那么糟糕,甚至还不错。
它可以说也深深植根于所有范畴论中,在范畴论中,人们不会商出等价的对象。在范畴论中取 'skeletons' 被认为是品味低下。严格和许多其他事情也是如此,所有这些都归结为试图压扁最好保持原样的东西,因为它们根本不会造成伤害。我们只是习惯于希望 'uniqueness' 反映在我们的陈述中——这是我们应该克服的。
Setoid 地狱的出现不是因为必须证明某些一致性(您需要证明它们以表明您具有适当的等价性,并且每当您在原始表示而不是商版本上定义函数时再次证明)。当您在定义不可能“出错”的函数时被迫一次又一次地证明这些一致性时,就会出现这种情况。所以Setoid地狱实际上是由于未能提供适当的抽象机制造成的。
换句话说,如果您正在做足够多的简单数学,其中商的行为很好,那么应该有一些自动化可以让您顺利地处理它。目前,在类型理论中,正在进行的研究正在研究它到底是什么样子。 Floris 的回答很好地概括了一个陷阱是什么:在某些时候,你放弃了 computations 将表现良好的想法,并且从那时起,被迫通过证明来做所有事情。
人们发现 Setoid 被广泛用于 Agda、Coq 等语言中……确实,Lean 等语言认为它们可以帮助避免“Setoid 地狱”。首先使用 Setoids 的原因是什么? 转向基于 HoTT 的外延类型理论(例如立方体 Agda)是否减少了对 Setoids 的需求?
理想情况下,人们当然希望能够将任意等价关系视为莱布尼茨等式 (eq
),从而能够在任意上下文中进行重写。即通过等价关系定义一个类型的商
我不是该主题的专家,但我一直在想同样的问题有一段时间了,我认为对 setoids 的依赖源于这样一个事实,即商在类型论中仍然是一个鲜为人知的概念。
- 当我们不 have/want 商类型时,我们就会陷入困境。
- 我们可以公理化商类型,我相信(我可能弄错了)这就是精益所做的。
- 我们可以开发一种可以自然地表达商的类型理论,这就是 HoTT/Cubical TT 对更高归纳类型所做的。
此外,商类型(或我对它们的幼稚想象)迫使我们以一种可能不太理想的方式将程序和证明打包在一起:两个商类型之间的函数是一个普通函数以及一个证明它尊重潜在的等价关系。虽然技术上可以做到这一点,但这种编程和证明的交错可以说是不可取的,因为它使程序不可读:人们经常试图将程序和证明保存在两个完全独立的世界中(这样就要求 setoids,使类型与其等价关系分开) ,或者更改一些表示,使程序和证明成为同一个实体(因此我们甚至可能不需要首先明确地推理等价性)。
正如 Li-yao Xia 的回答所述,当我们没有或不想使用商时,使用 setoids。
在 HoTT 书中和精益商数中(基本上)公理化。 Lean 和 HoTT 书之间的一个区别是后者有更多更高的归纳类型,而 Lean 只有商和(常规)归纳类型。如果我们只关注商数(在 HoTT 书中设置商数),它在精益和 Book HoTT 中的效果是一样的。在这种情况下,您只需假设给定一个类型 A
和 A
上的等价 R
,您有一个商 Q
,以及一个函数 [-] : A → Q
属性 ∀ x y : A, R x y → [x] = [y]
。它具有以下消除原则:要为某种类型 X
(或 HoTT 中的 hSet X
)构造一个函数 g : Q → X
,我们需要一个函数 f : A → X
以便我们可以证明∀ x y : A, R x y → f x = f y
。这与计算规则一起出现,该规则声明 ∀ x : A, g [x] ≡ f x
(这是 Lean 和 Book HoTT 中的定义等式)。
这个商的主要缺点是它破坏了正则性。规范性指出,(比方说)自然数中的每个封闭项(即没有自由变量的项)都归一化为零或某个自然数的后继项。这个商打破正则性的原因是我们可以将 =
的消元原理应用于商中的新等式,并且这样的项不会减少。在精益中,这无关紧要,因为在所有我们关心的情况下,我们仍然可以证明相等,即使它可能不是定义上的相等。
三次型理论有一种奇特的方法来处理商,同时保持正则性。在 CTT 中,相等性的工作方式不同,这意味着可以在保持规范性的同时引入更高的归纳类型。 CTT 的潜在缺点是类型理论要复杂得多,并且您必须接受 HoTT(尤其是放弃证明无关性)。
[Lia-yao Xia 和 Floris van Doorn 的回答都很好,所以我会尝试用更多信息来补充他们。]
另一种观点认为,商虽然在经典数学中经常使用,但也许毕竟不是那么大。不取商但坚持 Groupoids 是 exactly 非交换几何 从哪里开始!它告诉我们,有些商的表现非常糟糕,而我们最不想做的事情(在那些情况下!)就是实际商。但是如果你使用 'right' 工具来处理它,它本身并没有那么糟糕,甚至还不错。
它可以说也深深植根于所有范畴论中,在范畴论中,人们不会商出等价的对象。在范畴论中取 'skeletons' 被认为是品味低下。严格和许多其他事情也是如此,所有这些都归结为试图压扁最好保持原样的东西,因为它们根本不会造成伤害。我们只是习惯于希望 'uniqueness' 反映在我们的陈述中——这是我们应该克服的。
Setoid 地狱的出现不是因为必须证明某些一致性(您需要证明它们以表明您具有适当的等价性,并且每当您在原始表示而不是商版本上定义函数时再次证明)。当您在定义不可能“出错”的函数时被迫一次又一次地证明这些一致性时,就会出现这种情况。所以Setoid地狱实际上是由于未能提供适当的抽象机制造成的。
换句话说,如果您正在做足够多的简单数学,其中商的行为很好,那么应该有一些自动化可以让您顺利地处理它。目前,在类型理论中,正在进行的研究正在研究它到底是什么样子。 Floris 的回答很好地概括了一个陷阱是什么:在某些时候,你放弃了 computations 将表现良好的想法,并且从那时起,被迫通过证明来做所有事情。