Как доказать утверждения вида x. фи х в F*?

Я только начал изучать F*, изучая урок. Одно из упражнений - доказать, что reverse Функция в списках является инъективной. Поскольку это следует из того факта, что инволюции инъективны, я хотел бы выразить этот факт в виде леммы в F*. Для этого я определяю

let is_involutive f = forall x. (f (f x) == x)
let is_injective f = forall x y. (f x == f y) ==> x == y

Это правильный способ определить понятие f быть инволютивным или инъективным в F*?

Тогда я излагаю лемму

val inv_is_inj: #a:eqtype -> a -> f:(a->a) -> 
    Lemma (requires (is_involutive f)) (ensures(is_injective f))

Неформально доказательство можно записать в виде

 { fix (x:a) (y:a)
   assume (f x == f y)
   then have (f (f x) == f (f y))
   with (is_involutive f) have (x == y)
 } hence (forall (x:a) (y:a). f x == f y ==> x == y)
 then have (is_injective f)

Как мне выразить такое доказательство в F*? В общем, какие языковые конструкции F * можно использовать для доказательства утверждений вида forall (x:a). phi x, где phi является предикатом типа a?

0 ответов

Другие вопросы по тегам