Как доказать утверждения вида 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
?