proposition: Lemma is_sorted_smaller x y ys : (((x <=? y)%Z && is_sorted (y :: ys)) ---> is_sorted (x :: ys)).
proof: Proof. destruct ys as [ |z zs]. - simpl. smt. - change (is_sorted (y :: z :: zs)) with ((y <=? z)%Z && (is_sorted (z::zs))). change (is_sorted (x :: z :: zs)) with ((x <=? z)%Z && (is_sorted (z::zs))). assert (H:forall b, (x <=? y)%Z && ((y <=? z) && b) ---> (x <=? z) && b) by smt. apply H. Qed.
imports: SMTCoq.SMTCoq ZArith List Bool