Proving inductive predicates in TLAPS

[Leander Jehl]

I have a specification with constant Blocks and a function prev \in [Blocks -> Blocks] that defines a tree.
I would like to define an ancestor relation on that tree and prove statements like reflexivity and transitivity.

If I try to prove NatInductiveDefConclusion, it triggers a bug in TLAPS.

I would be grateful for any tips on how to define the ancestor relation, or how to avoid the bug.

Here is my current definition of the ancestor relation:

Extend(A) == A \cup { <<b,c>> \in Blocks \X Blocks: <<b,prev[c]>> \in A }
A0 == { <<b,c>> \in Blocks \X Blocks: b=c }

ancestors[i \in Nat] == IF i=0 THEN A0
                                        ELSE Extend(ancestors[i-1])

Ancestor(b,c) == /\ height[b] <= height[c]
                               /\ height[c] - height[b] \in Nat
                               /\ <<b,c>> \in ancestors[height[c] - height[b]]
My complete tree specification can be found here:
https://github.com/leandernikolaus/hotstuff-ivy/blob/master/Tree.tla

Thanks,

Leander

[Stephan Merz]

Hello,

TLAPS unfortunately doesn't handle quantification over tuples [1]. You have to rewrite your definitions as follows for the proof of the lemma to work:

Extend(A) == A \cup { bc \in Blocks \X Blocks: <<bc[1],prev[bc[2]]>> \in A }
A0 == { bc \in Blocks \X Blocks: bc[1]=bc[2] }

I didn't look at the rest of the module, please feel free to come back if you run into more trouble.

Stephan

[1] https://tla.msr-inria.inria.fr/tlaps/content/Documentation/Unsupported_features.html

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/8bbc83f3-9900-4230-baa5-c3f5af7d0514n%40googlegroups.com.

[Leander Jehl]

Hi Stephan,

thanks a lot for the help.

I was able to prove all my properties.

I'm including a link to my proofs in case anyone else is interested: https://github.com/leandernikolaus/hotstuff-ivy/blob/tla/tla-spec/Tree.tla

Leander