I'm trying to use a CoQ/SSReflect proof using nat
to prove a very similar statement in rat
. The current proof status, within an Open Scope ring_scope
, is
(price bs i - price bs' i <= tnth bs i * ('ctr_ (sOi i) - 'ctr_ (sOi i')))%N
→ (price bs i)%:~R - (price bs' i)%:~R <=
(value_per_click i)%:~R * (('ctr_ (sOi i))%:~R - ('ctr_ (sOi i'))%:~R)
and, using Set Printing All
, it shows as
forall
_ : is_true
(leq (subn (price bs i) (price bs' i))
(muln (@nat_of_ord p (@tnth n bid bs i))
(subn (@nat_of_ord q (@tnth k ctr cs (sOi i)))
(@nat_of_ord q (@tnth k ctr cs (sOi i')))))),
is_true
(@Order.le ring_display (Num.NumDomain.porderType rat_numDomainType)
(@GRing.add rat_ZmodType
(@intmul (GRing.Ring.zmodType rat_Ring) (GRing.one rat_Ring) (Posz (price bs i)))
(@GRing.opp rat_ZmodType
(@intmul (GRing.Ring.zmodType rat_Ring) (GRing.one rat_Ring) (Posz (price bs' i)))))
(@GRing.mul rat_Ring
(@intmul (GRing.Ring.zmodType rat_Ring) (GRing.one rat_Ring)
(Posz (value_per_click i)))
(@GRing.add (GRing.Ring.zmodType rat_Ring)
(@intmul (GRing.Ring.zmodType rat_Ring) (GRing.one rat_Ring)
(Posz (@nat_of_ord q (@tnth k ctr cs (sOi i)))))
(@GRing.opp (GRing.Ring.zmodType rat_Ring)
(@intmul (GRing.Ring.zmodType rat_Ring) (GRing.one rat_Ring)
(Posz (@nat_of_ord q (@tnth k ctr cs (sOi i')))))))))
I have been trying to use various rewrite
such as ler_nat
, PoszM
, intrM
, but with not much success. Could anyone provide me with some hints on how to proceed?
PS: I'm not able to provide a minimal working example, given I'm not exactly mastering what I'm doing here ;)
As you might have noticed, going from nat
to rat
there are two embeddings: first from nat
to int
, then from int
to rat
. The latter is a ring morphism, you can thus use generic morphism theorems such as rmorphM
and rmorphB
, in your case you could start with rewrite -!rmorphB -rmorphM ler_int.
The former embedding (Posz : nat -> int
) however is not a ring morphism, you could still use PoszM
indeed (Posz
is multiplicative), but the major problem would be that Posz (m - n) != Posz m - Posz n
in general (and the silent insertion of the coercion complicates matter here). So it would appear that you would need to postulate both (price bs' i <= price bs i)%N
and 'ctr_ (sOi i') <= 'ctr_ (sOi i)
. However thanks to leq_subLR
you can avoid the first hypothesis.
Here is a mock-up of your problem and a solution (it would have been nice to have the full context if you could not minimize). Assuming I reverse engineered the right types for price _ _
(thereafter abbreviated with p
and p'
), 'ctr _ _
(thereafter abbreviated with c
and c'
) and value_per_click _
(abbrev v
):
Lemma test (p p' v c c' : nat) : (c' <= c)%N -> (p - p' <= v * (c - c'))%N ->
p%:~R - p'%:~R <= v%:~R * (c%:~R - c'%:~R) :> rat.
Proof.
rewrite leq_subLR => le_c'c le_pp'_vMcc'. (* Removing the first subn. *)
rewrite -!rmorphB -rmorphM ler_int. (* Changing rat goal into int goal. *)
by rewrite ler_subl_addl subzn. (* Changing int goal into nat goal. *)
(* The rest of the proof was actually carried out using conversion. *)
Qed.