WITNESS BY

[Jaco van de Pol]

Hi,

My "WITNESS x \in y" generates a proof obligation, so it would be nice to

write WITNESS x\in y BY <proof>, but as far as I understand this is not

possible. Is there a reason? Is there a general work around?

Thanks for your thoughts,
Jaco van de Pol

[Andrew Helwer]

You are correct you cannot write WITNESS x \in y BY <proof>. The proof constructs that can be followed by a nested proof are:

• THEOREM, PROPOSITION, LEMMA, & COROLLARY (at the very top level of the proof)
• SUFFICES
• CASE
• PICK

SUFFICES is probably the closest to your desired usage. I am drawing this from reading the TLA+ tree-sitter grammar here. See which ones have the optional($._proof) rule at the end.

Andrew

[Stephan Merz]

Hi Jaco,

the directive "WITNESS e" quite clearly does not require proof, and by analogy (and in order to simplify the grammar) it was decided that "WITNESS e \in S" would not take a proof either but that the fact "e \in S" should follow obviously from the context. What you can do is write something like the following where the first step inserts the required fact in the context.

<1>. e \in S

  BY ...

<1>. WITNESS e \in S

Personally, I tend to use WITNESS rarely but usually write something like

<1>x. e \in S

  BY ...

<1>y. P(e)

  BY ...

<1>z. \E x \in S : P(x)

  BY <1>x, <1>y

Regards,

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 view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/57a329dc-6578-4235-ad56-a579e35c2234n%40googlegroups.com.

[Andrew Helwer]

To expand on Stephan's reply, the SUFFICES keyword is actually optional in SUFFICES steps. So just writing an expression without any keyword prepended is writing a SUFFICES step.

Andrew

[Stephan Merz]

Hi Andrew,

you are right that the SUFFICES keyword is optional in the grammar. However, its presence changes the meaning of the step. Consider the following example of a step claiming that some predicate P is provable.

<1>x. P

  <2>1. SUFFICES Q

    BY ... \* proof establishing ASSUME Q PROVE P

  <2>. QED

    BY ...   \* proof establishing Q

Step <2>1 reduces the proof of P to that of Q, i.e. its proof requires inferring P provided Q is provable. The current goal is now no longer P, but Q, and the QED step must prove that Q holds.

On the other hand, consider the following:

<1>x. P
  <2>1. Q
    BY ... \* proof establishing Q
  <2>. QED
    BY ...   \* proof establishing P (possibly using Q)

Here, step <2>1 just asserts Q as a fact, and the BY clause must allow it to be proved. The current goal is still P, and therefore the QED step must establish P. It may use the fact Q by invoking <2>1 in the BY clause for the QED step. So, while both proofs are syntactically legal, their logical meaning is different.

At the end of the day, the same arguments must be provided in both proofs, but in a different order, and one or the other may feel more natural in a given context. In proof assistant jargon, the first approach is called "backward chaining", and the second one is called "forward chaining". The latter is the default in TLAPS.

Also, this discussion is actually unrelated to the original question about WITNESS: that keyword is intended for instantiating existential quantification, and it doesn't make sense to write SUFFICES WITNESS e.

Regards,

Stephan

To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/5ae6ca5e-e749-4373-afce-13ceea4655a1n%40googlegroups.com.

[Andrew Helwer]

Thanks, Stephan! Very interesting. Semantics are different from syntax, of course. Always nice to peek into the other side.

Andrew