3

假设我有一个值x : A,并且我想定义一个仅包含x.

这是我尝试过的:

open import Data.Product
open import Relation.Binary.PropositionalEquality

-- Singleton x is the set that only contains x. Its values are tuples containing
-- a value of type A and a proof that this value is equal to x.
Singleton : ∀ {ℓ} {A : Set ℓ} → (x : A) → Set ℓ
Singleton {A = A} x = Σ[ y ∈ A ] (y ≡ x)

-- injection
singleton : ∀ {ℓ} {A : Set ℓ} → (x : A) → Singleton x
singleton x = x , refl

-- projection
fromSingleton : ∀ {ℓ} {A : Set ℓ} {x : A} → Singleton x → A
fromSingleton s = proj₁ s

有更好的方法吗?


为什么我想要这个的一个例子:如果你在某个集合 A 上有一个幺半群,那么你可以形成一个以 A 作为唯一对象的类别。要在 Agda 中表达这一点,您需要一种方法来编写“仅包含 A 的集合”。

4

3 回答 3

4

我认为这是一个非常好的方法。通常,当你想创建一个类型的“子集”时,它看起来像:

postulate
  A : Set
  P : A → Set

record Subset : Set where
  field
    value : A
    prop  : P value

但是,这可能不是一个子集,因为它实际上可以包含比原始类型更多的元素。那是因为prop可能有更多不同的价值。例如:

open import Data.Nat

data ℕ-prop : ℕ → Set where
  c1 : ∀ n → ℕ-prop n
  c2 : ∀ n → ℕ-prop n

record ℕ-Subset : Set where
  field
    value : ℕ
    prop  : ℕ-prop value

突然之间,子集的元素数量是原始类型的两倍。这个例子有点做作,我同意,但想象一下你在集合上有一个子集关系(来自集合论的集合)。这样的事情实际上是相当可能的:

sub₁ : {1, 2} ⊆ {1, 2, 3, 4}
sub₁ = drop 3 (drop 4 same)

sub₂ : {1, 2} ⊆ {1, 2, 3, 4}
sub₂ = drop 4 (drop 3 same)

解决这个问题的常用方法是使用不相关的参数:

record Subset : Set where
  field
    value : A
    .prop : P value

这意味着如果两个类型Subset的值具有相同的value,则该prop字段与相等性无关。事实上:

record Subset : Set where
  constructor sub
  field
    value : A
    .prop : P value

prop-irr : ∀ {a b} {p : P a} {q : P b} →
  a ≡ b → sub a p ≡ sub b q
prop-irr refl = refl

但是,这更像是一个指导方针,因为您的代表不受此问题的影响。这是因为在 Agda 中模式匹配的实现隐含了公理 K

K : ∀ {a p} {A : Set a} (x : A) (P : x ≡ x → Set p) (h : x ≡ x) →
  P refl → P h
K x P refl p = p

好吧,这并不能告诉你太多。幸运的是,还有另一个等价于公理 K 的性质:

uip : ∀ {a} {A : Set a} {x y : A} (p q : x ≡ y) → p ≡ q
uip refl refl = refl

这告诉我们只有一种方式可以使两个元素相等,即refluip表示身份证明的唯一性)。

这意味着当您使用命题相等来制作子集时,您将得到一个真正的子集。


让我们明确一点:

isSingleton : ∀ {ℓ} → Set ℓ → Set _
isSingleton A = Σ[ x ∈ A ] (∀ y → x ≡ y)

isSingleton A表示仅包含一个元素的事实A,直到命题相等。事实上,Singleton x是一个单例:

Singleton-isSingleton : ∀ {ℓ} {A : Set ℓ} (x : A) →
  isSingleton (Singleton x)
Singleton-isSingleton x = (x , refl) , λ {(.x , refl) → refl}

有趣的是,这在没有公理 K 的情况下也可以工作。如果你把{-# OPTIONS --without-K #-}pragma 放在文件的顶部,它仍然可以编译。

于 2014-01-25T23:01:21.013 回答
1

您可以定义没有投影的记录:

record Singleton {α} {A : Set α} (x : A) : Set α where

fromSingleton : ∀ {α} {A : Set α} {x : A} -> Singleton x -> A
fromSingleton {x = x} _ = x

singleton : ∀ {α} {A : Set α} -> (x : A) -> Singleton x
singleton _ = _

或者同样地

record Singleton {α} {A : Set α} (x : A) : Set α where

  fromSingleton = x
open Singleton public

singleton : ∀ {α} {A : Set α} -> (x : A) -> Singleton x
singleton _ = _

现在你可以像这样使用它:

open import Relation.Binary.PropositionalEquality
open import Data.Nat

f : Singleton 5 -> ℕ
f x = fromSingleton x

test : f (singleton 5) ≡ 5
test = refl

test' : f _ ≡ 5
test' = refl

这被拒绝了:

fail : f (singleton 4) ≡ 4
fail = ?

错误:

4 != 5 of type ℕ
when checking that the expression singleton 4 has type Singleton 5
于 2014-11-09T19:31:10.087 回答
1
于 2017-11-01T00:54:17.330 回答