Hello,
concerning the first item, expanding the definition of Cardinality is certainly not a good idea. I suggest first proving
/\ IsFiniteSet({x \in S : f[x]})
/\ 2 \notin {x \in S : f[x]}
/\ {x \in S : g[x]} = {x \in S : f[x]} \cup {2}
then applying lemma FS_AddElement to infer that
Cardinality({x \in S : g[x]}) = Cardinality({x \in S : f[x]}) + 1
The first conjunct above follows from
IsFiniteSet({1,2,3})
(proved using FS_EmptySet and FS_AddElement) using lemma FS_Subset. The second conjunct is trivial, and the third conjunct should be proved automatically:
LEMMA
ASSUME NEW S, NEW e \in S, NEW f \in [S -> BOOLEAN]
PROVE { x \in S : [f EXCEPT ![e] = TRUE][x] } = { x \in S : f[x] } \cup {e}
OBVIOUS
Unfortunately, little automation is currently provided for reasoning about Cardinality and these steps are more cumbersome than you would expect them to be.
–––
Concerning the second item, inferring
visit'[k] = TRUE from visit' = [visit EXCEPT ![k] = TRUE]
probably requires making explicit the fact that
k \in DOMAIN visit
For example, you can have
f = [x \in {} |-> FALSE]
g = [f EXCEPT ![1] = TRUE]
without having g[1] = TRUE. In fact, in this example, g = f.
Hope this helps,
Stephan
Hello,
Im having trouble with a safety proof of a spec where a function of [S -> BOOLEAN] is updated. There are two things that bother me, they are related in some way, but i will show them separately.
1. This is relating to Cardinality and EXCEPT. Consider the following:
------------------------------
-------------------
S == {1,2,3}
f == [x \in S |-> FALSE]
g == [f EXCEPT ![2]=TRUE]
THEOREM Ex1 ==
Cardinality({x \in S : g[x]}) = Cardinality({x \in S : f[x]}) + 1
PROOF BY DEF S, f, g, Cardinality
--------------------------------------------------
It didn't convince any backend.
I can get over it declaring an axiom like:
--------------------------------------------------
AXIOM UpdateFunctionCardinality ==
\A S, f, e: (/\ IsFiniteSet(S)
/\ f \in [S -> BOOLEAN]
/\ e \in S /\ f[e]=FALSE
=> Cardinality({x \in S : [f EXCEPT ![e]=TRUE][x]=TRUE}) = Cardinality({x \in S : f[x]=TRUE}) + 1 )
S == {1,2,3}
f == [x \in S |-> FALSE]
g == [f EXCEPT ![2]=TRUE]
LEMMA Ex2 ==
/\ IsFiniteSet(S)
=> Cardinality({x \in S : g[x]=TRUE}) = Cardinality({x \in S : f[x]=TRUE})+1
PROOF BY XC, FS_EmptySet, FS_AddElement, Isa DEF S,f
--------------------------------------------------
(Note that it still requires FS_EmptySet, FS_AddElement, Isa)
It looks like a hack to declare an axiom just for that (and worse, not knowing why is needed). Can this be proved in some other way?.
2. The following is a fragment of specification for the Prisioners problem
(if it isn't enough to be clear i can show more):
...
<1>2. (\E x \in NonLeaders: P(x)) => Inv'
<2> SUFFICES ASSUME NEW k \in NonLeaders, P(k)
PROVE Inv'
...
<6>a. visit' = [visit EXCEPT ![k] = TRUE] BY visit[k]=FALSE, light=FALSE DEF P -- GREEN
<6>b. k \notin {x \in NonLeaders : visit[x]=TRUE} BY visit[k]=FALSE -- GREEN
<6>c. visit'[k] = TRUE BY <6>a -- RED
<6>d. k \in {x \in NonLeaders : visit'[x]=TRUE} BY <6>a -- RED
Step <6>a is GREEN, it says there is an "updated" function visit' at the end of step, with a different boolean value for k. I expect lines <6>c. and <6>d. to be true also but the prover fails. It looks pretty clear to me, so i am missing something or my approach is really naive and that's why i get stuck everywhere?.
I think it would be helpful to get some advice when handling functions with EXCEPT and Cardinality, this is by far what causes major troubles to me, as the above examples suggest.
Regards,
JE
--
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 tla...@googlegroups.com.
To post to this group, send email to tla...@xxxxxxxxxxxxxxxx.
Visit this group at https://groups.google.com/group/tlaplus.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/60418f76-0e9a-468e-b3a3-1538a3811913%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.