如何在 agda 中解释 REL

Question

我试图理解 Agda 标准库的某些部分，但我似乎无法弄清楚 REL 的定义。 FWIW 这是 REL 的定义：

-- Binary relations

-- Heterogeneous binary relations

REL : ∀ {a b} → Set a → Set b → (ℓ : Level) → Set (a ⊔ b ⊔ suc ℓ)
REL A B ℓ = A → B → Set ℓ

我在网上找不到任何解释这一点的文档，这就是我在这里问的原因。这如何定义二元关系？

Answer 1

要定义二元关系，我们需要两个集合，所以 REL 至少需要两种类型。 REL的类型：

REL : ∀ {a b} → Set a → Set b → (ℓ : Level) → Set (a ⊔ b ⊔ suc ℓ)

由于宇宙级别的东西，这种类型有点污染。如果你允许自己有点不拘小节，你可以禁用 universe 级别（有关此 here 的更多信息）并将 REL 写为：

REL : Set -> Set -> Set

这是一种需要两种类型作为参数的类型。

在类型论中使用全域是为了避免像集合论的 Russell's Paradox 这样的悖论。

我不是类型理论专家，但是REL类型的解释可以概括为：

Set a和Set b分别是宇宙层次a和b的参数类型。
运算符⊔returns两个参数级别的最大值。

希望对您有所帮助。

Answer 2

@RodrigoRibeiro 的回答解释了 Level 位，但是一旦你摆脱了宇宙层次，类型 Set → Set → Set 与二元关系有什么关系？

假设你有一个二元关系R ⊆ A × B。建模它的命题方法是创建一些索引类型 R : A → B → Set，这样对于任何 a : A, b : B，R a b 都有居民当且仅当 (a, b) ∈ R。因此，如果你想讨论 A 和 B 上的所有关系，你必须讨论所有 A- 和 B- 索引类型，即你必须讨论RelationOverAandB = A → B → Set。

如果您随后想要抽象关系的左基类型和 right-hand 基类型，这意味着 A 和 B 的选择不再固定。所以你必须谈论REL，这样REL A B = A → B → Set。

那么REL的类型是什么？正如我们从 REL A B 示例中看到的，它将选择 A 和 B 作为两个参数；其结果是 type A → B → Set.

总结一下：给定

A : Set
B : Set

我们有

REL A B = A → B → Set

它本身的类型是 Set（记住，我们在这里忽略了宇宙级别）。

因此，

REL : Set → Set → Set ∎

Answer 3

我想看个例子更容易：

import Level
open import Relation.Binary
open import Data.Nat.Base hiding (_≤_)

data _≤_ : REL ℕ ℕ Level.zero where
  z≤n : ∀ {n} -> 0 ≤ n
  s≤s : ∀ {n m} -> n ≤ m -> suc n ≤ suc m

类型签名等同于

data _≤_ : ℕ -> ℕ -> Set where

所以_≤_是两个自然数之间的关系。它包含所有数字对，使得第一个数字小于或等于第二个数字。同样的方式我们可以写

open import Data.List.Base

data _∈_ {α} {A : Set α} : REL A (List A) Level.zero where
  here  : ∀ {x xs} -> x ∈ x ∷ xs
  there : ∀ {x y xs} -> x ∈ xs -> x ∈ y ∷ xs

类型签名等同于

data _∈_ {α} {A : Set α} : A -> List A -> Set where

_∈_ 是 A 类型元素与 A.

类型元素列表之间的关系

REL的全域单态变体本身就是一个二元关系：

MonoREL : REL Set Set (Level.suc Level.zero)
MonoREL A B = A → B → Set

如何在 agda 中解释 REL

how to interpret REL in agda

agda

dependent-type