Thanks Stephan.
THEOREM ax1 == ASSUME
NEW x \in Int PROVE IsFiniteSet({x})
THEOREM ax2 == ASSUME
NEW x \in Int, NEW y \in Int
PROVE IsFiniteSet({y-x})
THEOREM ax3 == ASSUME
NEW S1, NEW S2,
/\ IsFiniteSet(S1)
/\ IsFiniteSet(S2)
PROVE /\ IsFiniteSet(S1 \ S2)
/\ IsFiniteSet(S1 \cup S2)
THEOREM Spec => []PartialCorrectness
<1>1. Init => SInv
BY InputOK DEF Init, SInv, TypeOK, PartialCorrectness
<1>2. SInv /\ [Next]_vars => SInv'
<2> SUFFICES ASSUME SInv /\ [Next]_vars
PROVE SInv'
OBVIOUS
<2>1. TypeOK'
<3>1. CASE Lbl_1
<4>1. (S \subseteq Nat \{0})'
BY <3>1 DEF SInv, TypeOK, Next, vars, Lbl_1
<4>2. (S # {})'
BY <3>1 DEF SetGCD, SInv, TypeOK, Next, vars, Lbl_1, SetMax, Divides
<4>3. IsFiniteSet(S)'
BY <3>1, ax1, ax2, ax3
DEF SInv, TypeOK, Next, vars, Lbl_1
<4>4. QED
BY <4>1, <4>2, <4>3
DEF TypeOK
<3>2. CASE pc = "Done" /\
UNCHANGED vars
BY <3>2 DEF PartialCorrectness, SInv, TypeOK, vars
<3>3. CASE UNCHANGED vars
BY <3>3 DEF Init, SetGCD, PartialCorrectness, SInv, TypeOK, Next, vars
<3>4. QED
BY <3>1, <3>2, <3>3
DEF Next
<2>2. (SetGCD(S) = SetGCD(T))'
BY InputOK DEF Init, SInv, TypeOK, Next, vars
<2>3. PartialCorrectness'
BY InputOK DEF Init, SInv, TypeOK, Next, vars
<2>4. QED
BY <2>1, <2>2, <2>3 DEF SInv
<1>3. SInv => PartialCorrectness
BY DEF SInv, PartialCorrectness
<1>4. QED
BY <1>1, <1>2, <1>3, PTL
DEF Spec
On Friday, June 24, 2016 at 11:15:34 AM UTC-7, Stephan Merz wrote:
I haven't tried writing a formal proof of that algorithm, and it is not entirely clear to me where you are stuck.
The (type) invariant contains the conjunct
and you need to prove that this predicate is preserved by action Lbl_1. You'll need to use the standard module FiniteSetTheorems contained in the TLAPS distribution. (If you haven't done so yet, you should add the corresponding directory
to the Toolbox search path.) In particular, the lemmas FS_AddElement and FS_RemoveElement will be useful.