CODEWITHSUNDEEP
coq
laiba naz
laiba naz

Reputation: 57

Natural number list in coq

I have a list of natural numbers, elements in the list are in descending order. I want to write lemma about the list ,that first element h is greater than all the elements of list . Let list is [h;h1;t] . 0 h1? Please guide me , how to write h is greater than all the elements in the tail of list.

Upvotes: 1

Views: 910

Answers (3)

larsr
larsr

Reputation: 5811

You need to define what you mean by descending and use that in your proof. @Yves has perhaps the neatest way of doing it. Here is another definition that is just writing down a simple inductive definition. A list is descending if the tail is descending and the first element is larger or equal to the second element.

One nice thing with inductive definitions is that you can do induction on them, which gives you a lot of information in each proof case, with very little work.

Require Import List.

Inductive descending : list nat -> Prop :=
  desc_nil : descending nil
| desc_1 n : descending (cons n nil)
| desc_hd n m l :
    m <= n ->
    descending (cons m l) ->
    descending (cons n (cons m l)).

Lemma head_gt l d:
  descending l -> forall m, In m l -> m <= hd d l.
Proof.
  induction 1; intros k H'.
  now exfalso; apply in_nil in H'.
  now replace k with n; [ | inversion H'].
  now inversion H';
    [ subst; apply le_n
    | eapply PeanoNat.Nat.le_trans; auto].
Qed.

Upvotes: 1

Yves
Yves

Reputation: 4236

To express that a given list of natural numbers is in descending order, you can use existing functions in the List module of Coq.

Require Import List Lia.

Definition desc (l : list nat) : Prop :=
  forall i j, i <= j -> nth j l 0 <= nth i l 0.

What did I do? I just expressed that the value at rank i must be larger than the value at rank j for any j larger than i. This is clever in a subtle way. The expression nth j l 0 actually represents the value at rank i in l if i is smaller than the length of the list or 0 otherwise. It happens that 0 is smaller than any other natural number, so this definition does work. If instead, you had asked for a list of numbers in strictly descending order, then I would have had to write a more precise definition, involving only ranks that are smaller than the list length (you can use the function length for this). I let you do this as an exercise.

When you write a logical predicate like desc here, it is important to test this definition, to make sure you have really captured the notion you had in mind. To test my own definition, I wrote the following code:

Definition sample1 := 1 :: 2 :: 3 :: nil.

Definition sample2 := map (fun x => 10 - x) sample1.

Lemma s2_desc : desc sample2.
Proof.
intros [ | [ | [ | [ | ]]]] [ | [ | [ | [ | ]]]];
  intros ilej; simpl; lia.
Qed.

Lemma s1_n_desc : ~desc sample1.
Proof.
intros abs; generalize (abs 0 1 (le_S _ _ (le_n _))).
  compute; lia.
Qed.

The proof of s2_desc is a proof by brute force, it actually tries all pairs of ranks smaller than 4, and checks that in all these cases the comparisons between natural numbers (ranks or values in the list) do give logically provable formulas.

The proof of s1_n_desc is used to check that my definition of desc really rejects a list that obviously does not satisfy the criterion. It is a good thing I wrote this proof, because it helped me discover a bug in my code of desc that was not caught by the previous proof: I had written nth 0 l i instead of nth i l 0!

Last, but not least, my solution starts with Require Import List Lia. This means that we use two existing modules of Coq. The first one provides frequently used functions about lists, the second one provides an automatic tool to perform easy proofs about comparison between numbers (natural numbers or integers, actually).

As a next step, one could also write a boolean function that computes the value true exactly when its input is in descending order and develop proofs of tests to verify that both functions behave accordingly.

Upvotes: 1

Kamyar Mirzavaziri
Kamyar Mirzavaziri

Reputation: 858

You need to say

For any natural number, and any list like h::t, if the list is descending and if the number is in the tail, then it's smaller than the head.

So in Coq language you may write

Lemma head_is_max : forall n h t, desc (h::t) -> In n t -> h >= n.

if desc is a Boolean predicate you may write

Lemma head_is_max : forall n h t, desc (h::t) = true -> In n t -> h >= n.

Performing an induction on t would work for the proof.

In a more sophisticated way, you may use a predicate on list which asserts that all elements of a list have a specific property, you may define it as

Fixpoint All {T : Type} (P : T -> Prop) (l : list T) : Prop :=
  match l with
    | [] => True
    | h :: t => P h /\ All P t
  end.

So All P l means P x holds for all xs in l. Now we can write the mentioned lemma as

Lemma head_is_max : forall h t, desc (h::t) -> All (fun n => h >= n) t.

Upvotes: 1

Related Questions