proposition: Fact list_has_dup_map_inv X Y (f : X -> Y) l : (forall x y, In x l -> In y l -> f x = f y -> x = y) -> list_has_dup (map f l) -> list_has_dup l.
proof: Proof. intros H; do 2 rewrite list_has_dup_eq_duplicates. intros (y & m1 & m2 & m3 & E). apply map_app_inv in E; destruct E as (l1 & l10 & H1 & H2 & H3); symmetry in H3. apply map_cons_inv in H3; destruct H3 as (x1 & l11 & H3 & H4 & H5). apply map_app_inv in H5; destruct H5 as (l2 & l12 & H5 & H6 & H7); symmetry in H7. apply map_cons_inv in H7; destruct H7 as (x2 & l3 & H7 & H8 & H9); subst. apply H in H8; subst. + exists x1, l1, l2, l3; auto. + apply in_or_app; right; right; simpl. apply in_or_app; simpl; auto. + apply in_or_app; simpl; auto. Qed.
imports: Arith Lia List Permutation Relations Undecidability.Shared.Libs.DLW.Utils(utils_tac utils_list)