CODEWITHSUNDEEP
agda
Yuras
Yuras

Reputation: 13876

Proof that (prev n) <= m starting from n <= m

I have the next definition:

data Nat : Set where
  zero : Nat
  succ : Nat -> Nat

prev : Nat -> Nat
prev zero = zero
prev (succ n) = n

data _<=_ : Nat -> Nat -> Set where
  z<=n : forall {n} -> zero <= n
  s<=s : forall {n m} -> (n<=m : n <= m) -> (succ n) <= (succ m)

It easy to proof the next lemma:

lem-prev : {x y : Nat} -> x <= y -> (prev x) <= (prev y)
lem-prev z<=n = z<=n
lem-prev (s<=s t) = t

But I can't find a way to proof the next lemma:

lem-prev' : {x y : Nat} -> x <= y -> (prev x) <= y

I can change definition of <= to the next:

data _<='_ : Nat -> Nat -> Set where
  z<=n' : forall {n} -> zero <=' n
  s<=s' : forall {n m} -> (n<=m : n <=' m) -> (succ n) <=' m

In that case I can proof lem-prev':

lem-prev' : {x y : Nat} -> x <=' y -> (prev x) <=' y
lem-prev' z<=n' = z<=n'
lem-prev' (s<=s' t) = t

But now I can't proof lem-prev.

Is there a way to proof both lemmas for <= and/or <='? If no, then how should I change the definition to make it possible?

ADD: The solution using hammar's helper lemma:

lem-prev : {x y : Nat} -> x <= y -> (prev x) <= y
lem-prev z<=n = z<=n
lem-prev (s<=s prev-n<=prev-m) = weaken (prev-n<=prev-m)

Upvotes: 4

Views: 221

Answers (2)

hammar
hammar

Reputation: 139840

Try this lemma:

weaken : {x y : Nat} -> x <= y -> x <= succ y
weaken z<=n = z<=n
weaken (s<=s n<=m) = s<=s (weaken n<=m)

Upvotes: 4

Saizan
Saizan

Reputation: 1401

you can find a proof of that lemma in the standard library http://www.cse.chalmers.se/~nad/listings/lib/Data.Nat.Properties.html#10457

Upvotes: 6

Related Questions