Applying axioms about Sequents

2019-08-27 22:52发布

问题:

Consider the following minimal development based on the Isabelle Sequents library:

theory Test
  imports Pure Sequents.Sequents
begin

syntax "_Trueprop"    :: "two_seqe" ("((_)/ ⊢ (_))" [6,6] 5)
consts Trueprop :: two_seqi
parse_translation ‹[  (@{syntax_const "_Trueprop"}, K (two_seq_tr @{const_syntax Trueprop}))  ]›
print_translation ‹[  (@{const_syntax Trueprop}, K (two_seq_tr' @{syntax_const "_Trueprop"}))  ]›

axiomatization where
  identity : "$A, P, $B ⊢ $C, P, $D" and
  xch : "$A, $B, $C, $D, $E ⊢ $F  ⟹  $A, $D, $C, $B, $E ⊢ $F"

lemma xch0 : "$A, $B, $D, $E ⊢ $F  ⟹  $A, $D, $B, $E ⊢ $F"
  apply (rule xch ; assumption)  done

lemma xch1 : "$A, $B, P, $D, $E ⊢ $F  ⟹  $A, $D, P, $B, $E ⊢ $F"
  apply (rule xch ; assumption)  done

lemma xch2 : "$A, $B, P1, P2, $D, $E ⊢ $F  ⟹  $A, $D, P1, P2, $B, $E ⊢ $F"
  apply (rule xch ; assumption)  done

The attempted proofs of the lemmas fail. However, they succeed if I remove the identity axiom! So my first question is, why does the presence of the identity axiom affect these proofs that don't use it?

My main question is how to make these proofs work when I do have the identity axiom. My guess is that I need to explicitly specialize the variables, such as by applying xch[of A B _ D E F]. This seems like the right specialization (it works in the absence of identity), but it gives a very strange error

Failed to meet type constraint:
Term   A :: 'a => seq'
Type   seq' => seq'

Do I need to write something explicit in place of the _? If so, what? I can't figure out how to explicitly write "the empty sequence" or "the sequence containing only P" or "the sequence containing only P1, P2" — the magic-ness of the $A notation is defeating me.

Edit: Andreas's answer to my first question solves my actual problem completely, so I am renaming this question and accepting that answer. But I would still like to know the answer to my second question, so I'm re-asking it separately here.

回答1:

The error message for the explicit instantiation of the variables already indicates that something with the types is wrong. The problem is that axiomatization calls the type inference on all axioms at the same time. Since the identity axiom uses the same variable name A as the xch axiom, type inference assigns them the same type. If the identity axiom is not there, type inference computes a more general type, which makes the proofs work. Consequently, there are two ways to avoid this problem:

  1. Use different variable names in all axioms mentioned in an axiomatization block. This does the trick, but it usually reduces readability and it is easy to overlook something.

  2. Avoid free variables in the axioms by explicitly quantifying them using Pure's meta quantifier.

In your example, approach 2 would look like this:

axiomatization where
  identity : "⋀A P B C D. $A, P, $B ⊢ $C, P, $D" and 
  xch : "⋀A B C D E F. $A, $B, $C, $D, $E ⊢ $F  ⟹  $A, $D, $C, $B, $E ⊢ $F"


标签: isabelle