I have been working on an algorithm (Dafny cannot prove function-method equivalence, with High-Order-Polymorphic Recursive vs Linear Iterative) to count the number of subsequences of a sequence that hold a property P. For instance, how many subsequences hold that 'the number of positives on its left part are more that on its right part'.
But this was just to offer some context.
The important function is this CountAux function below. Given a proposition P (like, x is positive), a sequ sequence of sequences, an index i to move through the sequences, and an upper bound j:
function CountAux<T>(P: T -> bool, sequ: seq<T>, i: int, j:int): int
requires 0 <= i <= j <= |sequ|
decreases j - i //necessary to prove termination
ensures CountAux(P,sequ,i,j)>=0;
{
if i == j then 0
else (if P(sequ[i]) then 1 else 0) + CountAux(P, sequ, i+1,j)
}
To finish with it, now, it turns out I need a couple of lemmas (which I strongly believe they are true). But I have no idea how to do prove, could anyone help or provide the proofs? Do not seem difficult, but I am not used to prove in Dafny (sure they can be done using structural induction).
These are the lemmas I would like to prove:
lemma countLemma1<T>(P: T -> bool, sequ: seq<T>,i:int,j:int,k:int)
requires 0<=i<=k<=j<=|sequ|
ensures CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j)
//i.e. [i,k) [k,j)
{
if sequ == [] {
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
else{
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
}
lemma countLemma2<T>(P: T -> bool, sequ: seq<T>,i:int,j:int,k:int,l:int)
requires 0<=i<=j<=|sequ| && 0<=k<=l<=j-i
ensures CountAux(P,sequ[i..j],k,l)==CountAux(P,sequ,i+k,i+l)
//that is, counting the subsequence is the same as counting the original sequence with certain displacements
{
if sequ == [] {
assert CountAux(P,sequ[i..j],k,l)==CountAux(P,sequ,i+k,i+l);
}
else{
assert CountAux(P,sequ[i..j],k,l)==CountAux(P,sequ,i+k,i+l);
}
}
EDIT:
I have been trying but it seems I am misunderstanding structural induction. I identified three basic cases. Out of them, I see that if i==0, then the induction should hold (it fails), and therefore if i>0 I try to reach the i==0 using induction:
lemma countID<T>(P: T -> bool, sequ: seq<T>,i:int,j:int,k:int)//[i,k) [k,j)
requires 0<=i<=k<=j<=|sequ|
ensures CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j)
{
if sequ == [] || (j==0) || (k==0) {
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
else {
if (i==0) {
countID(P,sequ[1..],i,j-1,k-1);
assert CountAux(P,sequ[1..],i,j-1)
==CountAux(P,sequ[1..],i,k-1)+CountAux(P,sequ[1..],k-1,j-1);
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
else{
//countID(P,sequ[i..],0,j-i,k-i);
//assert CountAux(P,sequ[i..],0,j-i)
// ==CountAux(P,sequ[i..],0,k-i)+CountAux(P,sequ[i..],k-i,j-i);
countID(P,sequ[1..],i-1,j-1,k-1);
assert CountAux(P,sequ[1..],i-1,j-1)
==CountAux(P,sequ[1..],i-1,k-1)+CountAux(P,sequ[1..],k-1,j-1);
}
//assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
}
You can prove your lemma in recursive manner. You can refer https://www.rise4fun.com/Dafny/tutorialcontent/Lemmas#h25 for detailed explanation. It also has an example which happens to be very similar to your problem.
lemma countLemma1<T>(P: T -> bool, sequ: seq<T>,i:int,j:int,k:int)
requires 0<=i<=k<=j<=|sequ|
ensures CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j)
decreases j - i
//i.e. [i,k) [k,j)
{
if i == j {
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
else{
if i == k {
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
else {
countLemma1(P, sequ, i+1, j, k);
assert CountAux(P,sequ,i,j)==CountAux(P,sequ,i,k)+CountAux(P,sequ,k,j);
}
}
}
lemma countLemma2<T>(P: T -> bool, sequ: seq<T>,i:int,j:int,k:int,l:int)
requires 0<=i<=j<=|sequ| && 0<=k<=l<=j-i
ensures CountAux(P,sequ[i..j],k,l)==CountAux(P,sequ,i+k,i+l)
decreases j - i
//that is, counting the subsequence is the same as counting the original sequence with certain displacements
{
if i == j {
assert CountAux(P,sequ[i..j],k,l) == CountAux(P,sequ,i+k,i+l);
}
else{
if k == l {
assert CountAux(P,sequ[i..j],k,l) == CountAux(P,sequ,i+k,i+l);
}
else {
countLemma1(P, sequ[i..j], k, l, l-1);
assert CountAux(P,sequ[i..j],k,l) == CountAux(P,sequ[i..j],k,l-1) + CountAux(P,sequ[i..j],l-1,l);
countLemma1(P, sequ, i+k, i+l, i+l-1);
assert CountAux(P,sequ,i+k,i+l) == CountAux(P,sequ,i+k,i+l-1) + CountAux(P,sequ,i+l-1,i+l);
countLemma2(P, sequ, i, j-1, k ,l-1);
assert CountAux(P,sequ[i..(j-1)],k,l-1) == CountAux(P,sequ,i+k,i+l-1);
lastIndexDoesntMatter(P, sequ, i,j,k,l);
assert CountAux(P,sequ[i..j],k,l-1) == CountAux(P,sequ[i..(j-1)],k,l-1); // this part is what requires two additional lemmas
assert CountAux(P,sequ[i..j],l-1,l) == CountAux(P,sequ,i+l-1,i+l);
assert CountAux(P,sequ[i..j],k,l) == CountAux(P,sequ,i+k,i+l);
}
}
}
lemma lastIndexDoesntMatter<T>(P: T -> bool, sequ: seq<T>,i:int,j:int,k:int,l:int)
requires i != j
requires k != l
requires 0<=i<=j<=|sequ| && 0<=k<=l<=j-i
ensures CountAux(P,sequ[i..j],k,l-1) == CountAux(P,sequ[i..(j-1)],k,l-1)
{
assert l-1 < j;
if j == i + 1 {
}
else {
unusedLastIndex(P, sequ[i..j], k, l-1);
assert sequ[i..(j-1)] == sequ[i..j][0..(|sequ[i..j]|-1)];
assert CountAux(P,sequ[i..j],k,l-1) == CountAux(P,sequ[i..(j-1)],k,l-1);
}
}
lemma unusedLastIndex<T>(P: T -> bool, sequ: seq<T>, i: int, j:int)
requires 1 < |sequ|
requires 0 <= i <= j < |sequ|
ensures CountAux(P,sequ,i,j) == CountAux(P,sequ[0..(|sequ|-1)],i,j)
decreases j-i
{
if i == j{
}
else {
unusedLastIndex(P, sequ, i+1, j);
}
}