proposition: Lemma half_lt : forall a b : nat, 0 < b -> b = shift a \/ b = S (shift a) -> a < b.
proof: Proof. intros; case (lt_or_Zero a); intro. case H0; intro. rewrite H2. unfold shift in |- *; apply mult_p_lt_qp; auto with arith. rewrite H2. rewrite plus_n_1. unfold shift in |- *. rewrite mult_comm; apply lt_q_qbr; auto with arith. rewrite H1; auto with arith. Qed.
imports: Arith Peano_dec Constants Mult_compl Wf_nat euclid Le_lt_compl Euclid Compare_dec