[tlaplus] Reasoning with functions, except and cardinality

[JosEdu Solsona <josedusolsona@xxxxxxxxx>]

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 tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
To post to this group, send email to tlaplus@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.