Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

function lemma in "ensures" doesn't work in 1.9.8 (worked in 1.9.7) #25

Closed
xinhaoyuan opened this issue Sep 2, 2016 · 3 comments
Closed
Labels
has-workaround: yes There is a known workaround incompleteness Things that Dafny should be able to prove, but can't part: verifier Translation from Dafny to Boogie (translator)

Comments

@xinhaoyuan
Copy link

xinhaoyuan commented Sep 2, 2016

The third lemma doesn't verify:

lemma lemma_Subset_Cardinalities<I>(a : set<I>, b : set<I>)
    ensures a <= b ==> |a| <= |b| && |b - a| == |b| - |a|
{
    if (a <= b) {
        if x :| x in a {
            assert x in b;
            lemma_Subset_Cardinalities(a - {x}, b - {x});
        }
        else {
            assert a == {};
            assert |b - a| == |b| == |b| - |a|;
        }
    }
}

predicate pred_lemma_Subset_Cardinalities<I>(a : set<I>, b : set<I>) 
    ensures a <= b ==> |a| <= |b| && |b - a| == |b| - |a|
    ensures pred_lemma_Subset_Cardinalities(a, b) 
{
    lemma_Subset_Cardinalities(a, b);
    true
}

lemma lemma_Subset_Cardinalities_Universal<I>()
    ensures forall a : set<I>, b : set<I> :: a <= b ==> pred_lemma_Subset_Cardinalities(a, b) && |a| <= |b| && |b - a| == |b| - |a|
{
}

while function lemma in body is still working in 1.9.8:

lemma lemma_Subset_Cardinalities_Universal<I>()
    ensures forall a : set<I>, b : set<I> :: a <= b ==> |a| <= |b| && |b - a| == |b| - |a|
{
    if a : set<I>, b : set<I> :| a <= b && !(|a| <= |b| && |b - a| == |b| - |a|) {
        assert pred_lemma_Subset_Cardinalities(a, b);
    }
}
@seanmcl
Copy link
Collaborator

seanmcl commented Jul 1, 2019

Still a problem at master.

@acioc acioc added kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label and removed weakness labels Jun 22, 2020
@acioc acioc added this to the Dafny 3.0 milestone Jul 8, 2020
@acioc
Copy link
Collaborator

acioc commented Jul 8, 2020

Investigating this issue will be done for Dafny 3.0

@davidcok davidcok modified the milestones: Dafny 3.0, Dafny 3.1 Dec 23, 2020
camrein added a commit that referenced this issue Apr 8, 2021
@atomb atomb removed this from the Dafny 3.1 milestone Apr 21, 2022
@cpitclaudel cpitclaudel added part: verifier Translation from Dafny to Boogie (translator) incompleteness Things that Dafny should be able to prove, but can't has-workaround: yes There is a known workaround and removed kind: bug Crashes, unsoundness, incorrect output, etc. If possible, add a `part:` label labels May 11, 2022
@cpitclaudel
Copy link
Member

This bug was fixed in Dafny 3.1, and remains fixed in 3.6 🎉
I will add it to the test suite to make sure that it remains so.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
has-workaround: yes There is a known workaround incompleteness Things that Dafny should be able to prove, but can't part: verifier Translation from Dafny to Boogie (translator)
Projects
None yet
Development

No branches or pull requests

6 participants