Reasoning with functions, except and cardinality

[JosEdu Solsona]

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

[Stephan Merz]

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

--
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 post to this group, send email to tla...@googlegroups.com.
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.

[JosEdu Solsona]

Hello Stephan,

After trying many things it looks like i was missing the finite property of subsets. Also the tip about k \in DOMAIN f was crucial to finish the proof.

.

Thanks for the help,

JE

To unsubscribe from this group and stop receiving emails from it, send an email to tla...@googlegroups.com.