proposition: Lemma NoDup_Add a l l' : Add a l l' -> (NoDup l' <-> NoDup l /\ ~In a l).
proof: Proof. induction 1 as [l|x l l' AD IH]. - split; [ inversion_clear 1; now split | now constructor ]. - split. + inversion_clear 1. rewrite IH in *. rewrite (Add_in AD) in *. simpl in *; split; try constructor; intuition. + intros (N,IN). inversion_clear N. constructor. * rewrite (Add_in AD); simpl in *; intuition. * apply IH. split; trivial. simpl in *; intuition. Qed.
imports: PeanoNat