如何证明一个类型与自身的布尔不等式在 Idris 中是无人居住的？

Question

我想知道如何证明 (So (not (y == y))) 是 Uninhabited 的一个实例，但我不确定如何去做。它在 Idris 中是可证明的，还是由于 y 的奇怪 Eq 实现的可能性而无法证明？

Answer 1

Shersh 是对的：你不能。 (==) 的实现不保证是自反的，所以它可能不是真的。

您可以限制 y 的类型，以便证明属性是 (==) 的特定实现，但我怀疑您想使用 decEq和 (=) 而不是 So 和 (==)。很容易证明 Not (y = y) 无人居住。

Answer 2

Eq 接口不需要实现来遵循正常的平等法则。但是，我们可以定义一个扩展的 LawfulEq 接口，它可以：

%default total

is_reflexive : (t -> t -> Bool) -> Type
is_reflexive {t} rel = (x : t) -> rel x x = True

is_symmetric : (t -> t -> Bool) -> Type
is_symmetric {t} rel = (x : t) -> (y : t) -> rel x y = rel y x

is_transitive : (t -> t -> Bool) -> Type
is_transitive {t} rel = (x : t) -> (y : t) -> (z : t) -> rel x y = True -> rel x z = rel y z

interface Eq t => LawfulEq t where
  eq_is_reflexive : is_reflexive {t} (==)
  eq_is_symmetric : is_symmetric {t} (==)
  eq_is_transitive : is_transitive {t} (==)

题中要求的结果可以证明类型Bool:

so_false_is_void : So False -> Void
so_false_is_void Oh impossible

so_not_y_eq_y_is_void : (y : Bool) -> So (not (y == y)) -> Void
so_not_y_eq_y_is_void False = so_false_is_void
so_not_y_eq_y_is_void True = so_false_is_void

以下Weird类型可以证明结果不正确：

data Weird = W

Eq Weird where
  W == W = False

weird_so_not_y_eq_y : (y : Weird) -> So (not (y == y))
weird_so_not_y_eq_y W = Oh

可以证明 Weird (==) 不是自反的，因此 LawfulEq Weird 的实现是不可能的：

weird_eq_not_reflexive : is_reflexive {t=Weird} (==) -> Void
weird_eq_not_reflexive is_reflexive_eq = 
  let w_eq_w_is_true = is_reflexive_eq W in
    trueNotFalse $ trans (sym w_eq_w_is_true) (the (W == W = False) Refl)

如何证明一个类型与自身的布尔不等式在 Idris 中是无人居住的？

How to prove that the boolean inequality of a type with itself is uninhabited in Idris?

dependent-type

idris