1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1 |
(*<*)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
2 |
theory Paper
|
2568
8193bbaa07fe
merged Nominal-General directory into Nominal; renamed Abs.thy to Nominal2_Abs.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
3 |
imports "../Nominal/Nominal2_Base"
|
8193bbaa07fe
merged Nominal-General directory into Nominal; renamed Abs.thy to Nominal2_Abs.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
4 |
"../Nominal/Atoms"
|
2747
|
5 |
"~~/src/HOL/Library/LaTeXsugar"
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
6 |
begin
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
7 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
8 |
notation (latex output)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
9 |
sort_of ("sort _" [1000] 100) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
10 |
Abs_perm ("_") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
11 |
Rep_perm ("_") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
12 |
swap ("'(_ _')" [1000, 1000] 1000) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
13 |
fresh ("_ # _" [51, 51] 50) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
14 |
Cons ("_::_" [78,77] 73) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
15 |
supp ("supp _" [78] 73) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
16 |
uminus ("-_" [78] 73) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
17 |
atom ("|_|") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
18 |
If ("if _ then _ else _" 10) and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
19 |
Rep_name ("\<lfloor>_\<rfloor>") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
20 |
Abs_name ("\<lceil>_\<rceil>") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
21 |
Rep_var ("\<lfloor>_\<rfloor>") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
22 |
Abs_var ("\<lceil>_\<rceil>") and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
23 |
sort_of_ty ("sort'_ty _")
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
24 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
25 |
(* BH: uncomment if you really prefer the dot notation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
26 |
syntax (latex output)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
27 |
"_Collect" :: "pttrn => bool => 'a set" ("(1{_ . _})")
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
28 |
*)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
29 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
30 |
(* sort is used in Lists for sorting *)
|
2005
|
31 |
hide_const sort
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
32 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
33 |
abbreviation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
34 |
"sort \<equiv> sort_of"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
35 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
36 |
abbreviation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
37 |
"sort_ty \<equiv> sort_of_ty"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
38 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
39 |
(*>*)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
40 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
41 |
section {* Introduction *}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
42 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
43 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
44 |
Nominal Isabelle is a definitional extension of the Isabelle/HOL theorem
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
45 |
prover providing a proving infrastructure for convenient reasoning about
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
46 |
programming languages. It has been used to formalise an equivalence checking
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
47 |
algorithm for LF \cite{UrbanCheneyBerghofer08},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
48 |
Typed Scheme~\cite{TobinHochstadtFelleisen08}, several calculi for concurrency
|
1780
|
49 |
\cite{BengtsonParrow07} and a strong normalisation result for
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
50 |
cut-elimination in classical logic \cite{UrbanZhu08}. It has also been used
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
51 |
by Pollack for formalisations in the locally-nameless approach to binding
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
52 |
\cite{SatoPollack10}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
53 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
54 |
At its core Nominal Isabelle is based on the nominal logic work of Pitts et
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
55 |
al \cite{GabbayPitts02,Pitts03}. The most basic notion in this work is a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
56 |
sort-respecting permutation operation defined over a countably infinite
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
57 |
collection of sorted atoms. The atoms are used for representing variables
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
58 |
that might be bound. Multiple sorts are necessary for being
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
59 |
able to represent different kinds of variables. For example, in the language
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
60 |
Mini-ML there are bound term variables and bound type variables; each kind
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
61 |
needs to be represented by a different sort of atoms.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
62 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
63 |
Unfortunately, the type system of Isabelle/HOL is not a good fit for the way
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
64 |
atoms and sorts are used in the original formulation of the nominal logic work.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
65 |
Therefore it was decided in earlier versions of Nominal Isabelle to use a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
66 |
separate type for each sort of atoms and let the type system enforce the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
67 |
sort-respecting property of permutations. Inspired by the work on nominal
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
68 |
unification \cite{UrbanPittsGabbay04}, it seemed best at the time to also
|
1776
|
69 |
implement permutations concretely as lists of pairs of atoms. Thus Nominal
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
70 |
Isabelle used the two-place permutation operation with the generic type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
71 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
72 |
@{text [display,indent=10] "_ \<bullet> _ :: (\<alpha> \<times> \<alpha>) list \<Rightarrow> \<beta> \<Rightarrow> \<beta>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
73 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
74 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
75 |
where @{text "\<alpha>"} stands for the type of atoms and @{text "\<beta>"} for the type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
76 |
of the objects on which the permutation acts. For atoms of type @{text "\<alpha>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
77 |
the permutation operation is defined over the length of lists as follows
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
78 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
79 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
80 |
\begin{tabular}{@ {}r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
81 |
@{text "[] \<bullet> c"} & @{text "="} & @{text c}\\
|
1776
|
82 |
\end{tabular}\hspace{12mm}
|
|
83 |
\begin{tabular}{@ {}r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
84 |
@{text "(a b)::\<pi> \<bullet> c"} & @{text "="} &
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
85 |
$\begin{cases} @{text a} & \textrm{if}~@{text "\<pi> \<bullet> c = b"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
86 |
@{text b} & \textrm{if}~@{text "\<pi> \<bullet> c = a"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
87 |
@{text "\<pi> \<bullet> c"} & \textrm{otherwise}\end{cases}$
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
88 |
\end{tabular}\hfill\numbered{atomperm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
89 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
90 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
91 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
92 |
where we write @{text "(a b)"} for a swapping of atoms @{text "a"} and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
93 |
@{text "b"}. For atoms of different type, the permutation operation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
94 |
is defined as @{text "\<pi> \<bullet> c \<equiv> c"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
95 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
96 |
With the list representation of permutations it is impossible to state an
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
97 |
``ill-sorted'' permutation, since the type system excludes lists containing
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
98 |
atoms of different type. Another advantage of the list representation is that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
99 |
the basic operations on permutations are already defined in the list library:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
100 |
composition of two permutations (written @{text "_ @ _"}) is just list append,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
101 |
and inversion of a permutation (written @{text "_\<^sup>-\<^sup>1"}) is just
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
102 |
list reversal. A disadvantage is that permutations do not have unique
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
103 |
representations as lists; we had to explicitly identify permutations according
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
104 |
to the relation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
105 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
106 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
107 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
108 |
@{text "\<pi>\<^isub>1 \<sim> \<pi>\<^isub>2 \<equiv> \<forall>a. \<pi>\<^isub>1 \<bullet> a = \<pi>\<^isub>2 \<bullet> a"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
109 |
\end{tabular}\hfill\numbered{permequ}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
110 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
111 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
112 |
When lifting the permutation operation to other types, for example sets,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
113 |
functions and so on, we needed to ensure that every definition is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
114 |
well-behaved in the sense that it satisfies the following three
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
115 |
\emph{permutation properties}:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
116 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
117 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
118 |
\begin{tabular}{@ {}r@ {\hspace{4mm}}p{10cm}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
119 |
i) & @{text "[] \<bullet> x = x"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
120 |
ii) & @{text "(\<pi>\<^isub>1 @ \<pi>\<^isub>2) \<bullet> x = \<pi>\<^isub>1 \<bullet> (\<pi>\<^isub>2 \<bullet> x)"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
121 |
iii) & if @{text "\<pi>\<^isub>1 \<sim> \<pi>\<^isub>2"} then @{text "\<pi>\<^isub>1 \<bullet> x = \<pi>\<^isub>2 \<bullet> x"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
122 |
\end{tabular}\hfill\numbered{permprops}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
123 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
124 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
125 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
126 |
From these properties we were able to derive most facts about permutations, and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
127 |
the type classes of Isabelle/HOL allowed us to reason abstractly about these
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
128 |
three properties, and then let the type system automatically enforce these
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
129 |
properties for each type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
130 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
131 |
The major problem with Isabelle/HOL's type classes, however, is that they
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
132 |
support operations with only a single type parameter and the permutation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
133 |
operations @{text "_ \<bullet> _"} used above in the permutation properties
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
134 |
contain two! To work around this obstacle, Nominal Isabelle
|
1776
|
135 |
required the user to
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
136 |
declare up-front the collection of \emph{all} atom types, say @{text
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
137 |
"\<alpha>\<^isub>1,\<dots>,\<alpha>\<^isub>n"}. From this collection it used custom ML-code to
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
138 |
generate @{text n} type classes corresponding to the permutation properties,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
139 |
whereby in these type classes the permutation operation is restricted to
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
140 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
141 |
@{text [display,indent=10] "_ \<bullet> _ :: (\<alpha>\<^isub>i \<times> \<alpha>\<^isub>i) list \<Rightarrow> \<beta> \<Rightarrow> \<beta>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
142 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
143 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
144 |
This operation has only a single type parameter @{text "\<beta>"} (the @{text "\<alpha>\<^isub>i"} are the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
145 |
atom types given by the user).
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
146 |
|
1776
|
147 |
While the representation of permutations-as-lists solved the
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
148 |
``sort-respecting'' requirement and the declaration of all atom types
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
149 |
up-front solved the problem with Isabelle/HOL's type classes, this setup
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
150 |
caused several problems for formalising the nominal logic work: First,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
151 |
Nominal Isabelle had to generate @{text "n\<^sup>2"} definitions for the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
152 |
permutation operation over @{text "n"} types of atoms. Second, whenever we
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
153 |
need to generalise induction hypotheses by quantifying over permutations, we
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
154 |
have to build cumbersome quantifications like
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
155 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
156 |
@{text [display,indent=10] "\<forall>\<pi>\<^isub>1 \<dots> \<forall>\<pi>\<^isub>n. \<dots>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
157 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
158 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
159 |
where the @{text "\<pi>\<^isub>i"} are of type @{text "(\<alpha>\<^isub>i \<times> \<alpha>\<^isub>i) list"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
160 |
The reason is that the permutation operation behaves differently for
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
161 |
every @{text "\<alpha>\<^isub>i"}. Third, although the notion of support
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
162 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
163 |
@{text [display,indent=10] "supp _ :: \<beta> \<Rightarrow> \<alpha> set"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
164 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
165 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
166 |
which we will define later, has a generic type @{text "\<alpha> set"}, it cannot be
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
167 |
used to express the support of an object over \emph{all} atoms. The reason
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
168 |
is again that support can behave differently for each @{text
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
169 |
"\<alpha>\<^isub>i"}. This problem is annoying, because if we need to know in
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
170 |
a statement that an object, say @{text "x"}, is finitely supported we end up
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
171 |
with having to state premises of the form
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
172 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
173 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
174 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
175 |
@{text "finite ((supp x) :: \<alpha>\<^isub>1 set) , \<dots>, finite ((supp x) :: \<alpha>\<^isub>n set)"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
176 |
\end{tabular}\hfill\numbered{fssequence}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
177 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
178 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
179 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
180 |
Sometimes we can avoid such premises completely, if @{text x} is a member of a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
181 |
\emph{finitely supported type}. However, keeping track of finitely supported
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
182 |
types requires another @{text n} type classes, and for technical reasons not
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
183 |
all types can be shown to be finitely supported.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
184 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
185 |
The real pain of having a separate type for each atom sort arises, however,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
186 |
from another permutation property
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
187 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
188 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
189 |
\begin{tabular}{@ {}r@ {\hspace{4mm}}p{10cm}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
190 |
iv) & @{text "\<pi>\<^isub>1 \<bullet> (\<pi>\<^isub>2 \<bullet> x) = (\<pi>\<^isub>1 \<bullet> \<pi>\<^isub>2) \<bullet> (\<pi>\<^isub>1 \<bullet> x)"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
191 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
192 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
193 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
194 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
195 |
where permutation @{text "\<pi>\<^isub>1"} has type @{text "(\<alpha> \<times> \<alpha>) list"},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
196 |
@{text "\<pi>\<^isub>2"} type @{text "(\<alpha>' \<times> \<alpha>') list"} and @{text x} type @{text
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
197 |
"\<beta>"}. This property is needed in order to derive facts about how
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
198 |
permutations of different types interact, which is not covered by the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
199 |
permutation properties @{text "i"}-@{text "iii"} shown in
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
200 |
\eqref{permprops}. The problem is that this property involves three type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
201 |
parameters. In order to use again Isabelle/HOL's type class mechanism with
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
202 |
only permitting a single type parameter, we have to instantiate the atom
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
203 |
types. Consequently we end up with an additional @{text "n\<^sup>2"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
204 |
slightly different type classes for this permutation property.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
205 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
206 |
While the problems and pain can be almost completely hidden from the user in
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
207 |
the existing implementation of Nominal Isabelle, the work is \emph{not}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
208 |
pretty. It requires a large amount of custom ML-code and also forces the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
209 |
user to declare up-front all atom-types that are ever going to be used in a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
210 |
formalisation. In this paper we set out to solve the problems with multiple
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
211 |
type parameters in the permutation operation, and in this way can dispense
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
212 |
with the large amounts of custom ML-code for generating multiple variants
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
213 |
for some basic definitions. The result is that we can implement a pleasingly
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
214 |
simple formalisation of the nominal logic work.\smallskip
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
215 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
216 |
\noindent
|
1798
d8bd4923b3aa
edit 'contributions' section so we do not just quote directly from the reviewer
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
217 |
{\bf Contributions of the paper:} Using a single atom type to represent
|
d8bd4923b3aa
edit 'contributions' section so we do not just quote directly from the reviewer
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
218 |
atoms of different sorts and representing permutations as functions are not
|
d8bd4923b3aa
edit 'contributions' section so we do not just quote directly from the reviewer
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
219 |
new ideas. The main contribution of this paper is to show an example of how
|
d8bd4923b3aa
edit 'contributions' section so we do not just quote directly from the reviewer
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
220 |
to make better theorem proving tools by choosing the right level of
|
d8bd4923b3aa
edit 'contributions' section so we do not just quote directly from the reviewer
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
221 |
abstraction for the underlying theory---our design choices take advantage of
|
d8bd4923b3aa
edit 'contributions' section so we do not just quote directly from the reviewer
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
222 |
Isabelle's type system, type classes, and reasoning infrastructure.
|
1790
|
223 |
The novel
|
|
224 |
technical contribution is a mechanism for dealing with
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
225 |
``Church-style'' lambda-terms \cite{Church40} and HOL-based languages
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
226 |
\cite{PittsHOL4} where variables and variable binding depend on type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
227 |
annotations.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
228 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
229 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
230 |
section {* Sorted Atoms and Sort-Respecting Permutations *}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
231 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
232 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
233 |
In the nominal logic work of Pitts, binders and bound variables are
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
234 |
represented by \emph{atoms}. As stated above, we need to have different
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
235 |
\emph{sorts} of atoms to be able to bind different kinds of variables. A
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
236 |
basic requirement is that there must be a countably infinite number of atoms
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
237 |
of each sort. Unlike in our earlier work, where we identified each sort with
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
238 |
a separate type, we implement here atoms to be
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
239 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
240 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
241 |
datatype atom\<iota> = Atom\<iota> string nat
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
242 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
243 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
244 |
\noindent
|
1780
|
245 |
whereby the string argument specifies the sort of the atom.\footnote{A similar
|
|
246 |
design choice was made by Gunter et al \cite{GunterOsbornPopescu09}
|
|
247 |
for their variables.} (The use type
|
|
248 |
\emph{string} is merely for convenience; any countably infinite type would work
|
|
249 |
as well.)
|
1776
|
250 |
We have an auxiliary function @{text sort} that is defined as @{thm
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
251 |
sort_of.simps[no_vars]}, and we clearly have for every finite set @{text X} of
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
252 |
atoms and every sort @{text s} the property:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
253 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
254 |
\begin{proposition}\label{choosefresh}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
255 |
@{text "If finite X then there exists an atom a such that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
256 |
sort a = s and a \<notin> X"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
257 |
\end{proposition}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
258 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
259 |
For implementing sort-respecting permutations, we use functions of type @{typ
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
260 |
"atom => atom"} that @{text "i)"} are bijective; @{text "ii)"} are the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
261 |
identity on all atoms, except a finite number of them; and @{text "iii)"} map
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
262 |
each atom to one of the same sort. These properties can be conveniently stated
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
263 |
for a function @{text \<pi>} as follows:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
264 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
265 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
1779
|
266 |
i)~~~@{term "bij \<pi>"}\hspace{5mm}
|
|
267 |
ii)~~~@{term "finite {a. \<pi> a \<noteq> a}"}\hspace{5mm}
|
|
268 |
iii)~~~@{term "\<forall>a. sort (\<pi> a) = sort a"}\hfill\numbered{permtype}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
269 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
270 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
271 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
272 |
Like all HOL-based theorem provers, Isabelle/HOL allows us to
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
273 |
introduce a new type @{typ perm} that includes just those functions
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
274 |
satisfying all three properties. For example the identity function,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
275 |
written @{term id}, is included in @{typ perm}. Also function composition,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
276 |
written \mbox{@{text "_ \<circ> _"}}, and function inversion, given by Isabelle/HOL's
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
277 |
inverse operator and written \mbox{@{text "inv _"}}, preserve the properties
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
278 |
@{text "i"}-@{text "iii"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
279 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
280 |
However, a moment of thought is needed about how to construct non-trivial
|
1776
|
281 |
permutations. In the nominal logic work it turned out to be most convenient
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
282 |
to work with swappings, written @{text "(a b)"}. In our setting the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
283 |
type of swappings must be
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
284 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
285 |
@{text [display,indent=10] "(_ _) :: atom \<Rightarrow> atom \<Rightarrow> perm"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
286 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
287 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
288 |
but since permutations are required to respect sorts, we must carefully
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
289 |
consider what happens if a user states a swapping of atoms with different
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
290 |
sorts. In earlier versions of Nominal Isabelle, we avoided this problem by
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
291 |
using different types for different sorts; the type system prevented users
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
292 |
from stating ill-sorted swappings. Here, however, definitions such
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
293 |
as\footnote{To increase legibility, we omit here and in what follows the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
294 |
@{term Rep_perm} and @{term "Abs_perm"} wrappers that are needed in our
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
295 |
implementation since we defined permutation not to be the full function space,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
296 |
but only those functions of type @{typ perm} satisfying properties @{text
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
297 |
i}-@{text "iii"}.}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
298 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
299 |
@{text [display,indent=10] "(a b) \<equiv> \<lambda>c. if a = c then b else (if b = c then a else c)"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
300 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
301 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
302 |
do not work in general, because the type system does not prevent @{text a}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
303 |
and @{text b} from having different sorts---in which case the function would
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
304 |
violate property @{text iii}. We could make the definition of swappings
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
305 |
partial by adding the precondition @{term "sort a = sort b"},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
306 |
which would mean that in case @{text a} and @{text b} have different sorts,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
307 |
the value of @{text "(a b)"} is unspecified. However, this looked like a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
308 |
cumbersome solution, since sort-related side conditions would be required
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
309 |
everywhere, even to unfold the definition. It turned out to be more
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
310 |
convenient to actually allow the user to state ``ill-sorted'' swappings but
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
311 |
limit their ``damage'' by defaulting to the identity permutation in the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
312 |
ill-sorted case:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
313 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
314 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
315 |
\begin{tabular}{@ {}rl}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
316 |
@{text "(a b) \<equiv>"} & @{text "if (sort a = sort b)"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
317 |
& \hspace{3mm}@{text "then \<lambda>c. if a = c then b else (if b = c then a else c)"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
318 |
& \hspace{3mm}@{text "else id"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
319 |
\end{tabular}\hfill\numbered{swapdef}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
320 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
321 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
322 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
323 |
This function is bijective, the identity on all atoms except
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
324 |
@{text a} and @{text b}, and sort respecting. Therefore it is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
325 |
a function in @{typ perm}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
326 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
327 |
One advantage of using functions instead of lists as a representation for
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
328 |
permutations is that for example the swappings
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
329 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
330 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
331 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
332 |
@{thm swap_commute[no_vars]}\hspace{10mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
333 |
@{text "(a a) = id"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
334 |
\end{tabular}\hfill\numbered{swapeqs}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
335 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
336 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
337 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
338 |
are \emph{equal}. We do not have to use the equivalence relation shown
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
339 |
in~\eqref{permequ} to identify them, as we would if they had been represented
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
340 |
as lists of pairs. Another advantage of the function representation is that
|
1781
|
341 |
they form a (non-commutative) group, provided we define
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
342 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
343 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
344 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
345 |
@{thm zero_perm_def[no_vars, THEN eq_reflection]} \hspace{4mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
346 |
@{thm plus_perm_def[where p="\<pi>\<^isub>1" and q="\<pi>\<^isub>2", THEN eq_reflection]} \hspace{4mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
347 |
@{thm uminus_perm_def[where p="\<pi>", THEN eq_reflection]} \hspace{4mm}
|
2736
|
348 |
@{thm minus_perm_def[where ?p1.0="\<pi>\<^isub>1" and ?p2.0="\<pi>\<^isub>2"]}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
349 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
350 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
351 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
352 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
353 |
and verify the simple properties
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
354 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
355 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
356 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
357 |
@{thm add_assoc[where a="\<pi>\<^isub>1" and b="\<pi>\<^isub>2" and c="\<pi>\<^isub>3"]} \hspace{3mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
358 |
@{thm monoid_add_class.add_0_left[where a="\<pi>::perm"]} \hspace{3mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
359 |
@{thm monoid_add_class.add_0_right[where a="\<pi>::perm"]} \hspace{3mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
360 |
@{thm group_add_class.left_minus[where a="\<pi>::perm"]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
361 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
362 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
363 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
364 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
365 |
Again this is in contrast to the list-of-pairs representation which does not
|
1781
|
366 |
form a group. The technical importance of this fact is that we can rely on
|
|
367 |
Isabelle/HOL's existing simplification infrastructure for groups, which will
|
|
368 |
come in handy when we have to do calculations with permutations.
|
|
369 |
Note that Isabelle/HOL defies standard conventions of mathematical notation
|
|
370 |
by using additive syntax even for non-commutative groups. Obviously,
|
|
371 |
composition of permutations is not commutative in general---@{text
|
|
372 |
"\<pi>\<^sub>1 + \<pi>\<^sub>2 \<noteq> \<pi>\<^sub>2 + \<pi>\<^sub>1"}. But since the point of this paper is to implement the
|
|
373 |
nominal theory as smoothly as possible in Isabelle/HOL, we tolerate
|
|
374 |
the non-standard notation in order to reuse the existing libraries.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
375 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
376 |
By formalising permutations abstractly as functions, and using a single type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
377 |
for all atoms, we can now restate the \emph{permutation properties} from
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
378 |
\eqref{permprops} as just the two equations
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
379 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
380 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
381 |
\begin{tabular}{@ {}r@ {\hspace{4mm}}p{10cm}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
382 |
i) & @{thm permute_zero[no_vars]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
383 |
ii) & @{thm permute_plus[where p="\<pi>\<^isub>1" and q="\<pi>\<^isub>2",no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
384 |
\end{tabular}\hfill\numbered{newpermprops}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
385 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
386 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
387 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
388 |
in which the permutation operations are of type @{text "perm \<Rightarrow> \<beta> \<Rightarrow> \<beta>"} and so
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
389 |
have only a single type parameter. Consequently, these properties are
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
390 |
compatible with the one-parameter restriction of Isabelle/HOL's type classes.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
391 |
There is no need to introduce a separate type class instantiated for each
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
392 |
sort, like in the old approach.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
393 |
|
1779
|
394 |
The next notion allows us to establish generic lemmas involving the
|
|
395 |
permutation operation.
|
|
396 |
|
|
397 |
\begin{definition}
|
|
398 |
A type @{text "\<beta>"} is a \emph{permutation type} if the permutation
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
399 |
properties in \eqref{newpermprops} are satisfied for every @{text "x"} of type
|
1779
|
400 |
@{text "\<beta>"}.
|
|
401 |
\end{definition}
|
|
402 |
|
|
403 |
\noindent
|
|
404 |
First, it follows from the laws governing
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
405 |
groups that a permutation and its inverse cancel each other. That is, for any
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
406 |
@{text "x"} of a permutation type:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
407 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
408 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
409 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
410 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
411 |
@{thm permute_minus_cancel(1)[where p="\<pi>", no_vars]}\hspace{10mm}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
412 |
@{thm permute_minus_cancel(2)[where p="\<pi>", no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
413 |
\end{tabular}\hfill\numbered{cancel}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
414 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
415 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
416 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
417 |
Consequently, in a permutation type the permutation operation @{text "\<pi> \<bullet> _"} is bijective,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
418 |
which in turn implies the property
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
419 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
420 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
421 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
422 |
@{thm (lhs) permute_eq_iff[where p="\<pi>", no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
423 |
$\;$if and only if$\;$
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
424 |
@{thm (rhs) permute_eq_iff[where p="\<pi>", no_vars]}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
425 |
\end{tabular}\hfill\numbered{permuteequ}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
426 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
427 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
428 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
429 |
In order to lift the permutation operation to other types, we can define for:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
430 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
431 |
\begin{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
432 |
\begin{tabular}{@ {}c@ {\hspace{-1mm}}c@ {}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
433 |
\begin{tabular}{@ {}r@ {\hspace{2mm}}l@ {}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
434 |
atoms: & @{thm permute_atom_def[where p="\<pi>",no_vars, THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
435 |
functions: & @{text "\<pi> \<bullet> f \<equiv> \<lambda>x. \<pi> \<bullet> (f ((-\<pi>) \<bullet> x))"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
436 |
permutations: & @{thm permute_perm_def[where p="\<pi>" and q="\<pi>'", THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
437 |
sets: & @{thm permute_set_eq[where p="\<pi>", no_vars, THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
438 |
booleans: & @{thm permute_bool_def[where p="\<pi>", no_vars, THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
439 |
\end{tabular} &
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
440 |
\begin{tabular}{@ {}r@ {\hspace{2mm}}l@ {}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
441 |
lists: & @{thm permute_list.simps(1)[where p="\<pi>", no_vars, THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
442 |
& @{thm permute_list.simps(2)[where p="\<pi>", no_vars, THEN eq_reflection]}\\[2mm]
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
443 |
products: & @{thm permute_prod.simps[where p="\<pi>", no_vars, THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
444 |
nats: & @{thm permute_nat_def[where p="\<pi>", no_vars, THEN eq_reflection]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
445 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
446 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
447 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
448 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
449 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
450 |
and then establish:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
451 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
452 |
\begin{theorem}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
453 |
If @{text \<beta>}, @{text "\<beta>\<^isub>1"} and @{text "\<beta>\<^isub>2"} are permutation types,
|
1776
|
454 |
then so are @{text "atom"}, @{text "\<beta>\<^isub>1 \<Rightarrow> \<beta>\<^isub>2"},
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
455 |
@{text perm}, @{term "\<beta> set"}, @{term "\<beta> list"}, @{term "\<beta>\<^isub>1 \<times> \<beta>\<^isub>2"},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
456 |
@{text bool} and @{text "nat"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
457 |
\end{theorem}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
458 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
459 |
\begin{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
460 |
All statements are by unfolding the definitions of the permutation operations and simple
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
461 |
calculations involving addition and minus. With permutations for example we
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
462 |
have
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
463 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
464 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
465 |
\begin{tabular}[b]{@ {}rcl}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
466 |
@{text "0 \<bullet> \<pi>'"} & @{text "\<equiv>"} & @{text "0 + \<pi>' - 0 = \<pi>'"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
467 |
@{text "(\<pi>\<^isub>1 + \<pi>\<^isub>2) \<bullet> \<pi>'"} & @{text "\<equiv>"} & @{text "(\<pi>\<^isub>1 + \<pi>\<^isub>2) + \<pi>' - (\<pi>\<^isub>1 + \<pi>\<^isub>2)"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
468 |
& @{text "="} & @{text "(\<pi>\<^isub>1 + \<pi>\<^isub>2) + \<pi>' - \<pi>\<^isub>2 - \<pi>\<^isub>1"}\\
|
1776
|
469 |
& @{text "="} & @{text "\<pi>\<^isub>1 + (\<pi>\<^isub>2 + \<pi>' - \<pi>\<^isub>2) - \<pi>\<^isub>1"} @{text "\<equiv>"} @{text "\<pi>\<^isub>1 \<bullet> \<pi>\<^isub>2 \<bullet> \<pi>'"}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
470 |
\end{tabular}\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
471 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
472 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
473 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
474 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
475 |
The main point is that the above reasoning blends smoothly with the reasoning
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
476 |
infrastructure of Isabelle/HOL; no custom ML-code is necessary and a single
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
477 |
type class suffices. We can also show once and for all that the following
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
478 |
property---which caused so many headaches in our earlier setup---holds for any
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
479 |
permutation type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
480 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
481 |
\begin{lemma}\label{permutecompose}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
482 |
Given @{term x} is of permutation type, then
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
483 |
@{text "\<pi>\<^isub>1 \<bullet> (\<pi>\<^isub>2 \<bullet> x) = (\<pi>\<^isub>1 \<bullet> \<pi>\<^isub>2) \<bullet> (\<pi>\<^isub>1 \<bullet> x)"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
484 |
\end{lemma}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
485 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
486 |
\begin{proof} The proof is as follows:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
487 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
488 |
\begin{tabular}[b]{@ {}rcl@ {\hspace{8mm}}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
489 |
@{text "\<pi>\<^isub>1 \<bullet> \<pi>\<^isub>2 \<bullet> x"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
490 |
& @{text "="} & @{text "\<pi>\<^isub>1 \<bullet> \<pi>\<^isub>2 \<bullet> (-\<pi>\<^isub>1) \<bullet> \<pi>\<^isub>1 \<bullet> x"} & by \eqref{cancel}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
491 |
& @{text "="} & @{text "(\<pi>\<^isub>1 + \<pi>\<^isub>2 - \<pi>\<^isub>1) \<bullet> \<pi>\<^isub>1 \<bullet> x"} & by {\rm(\ref{newpermprops}.@{text "ii"})}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
492 |
& @{text "\<equiv>"} & @{text "(\<pi>\<^isub>1 \<bullet> \<pi>\<^isub>2) \<bullet> (\<pi>\<^isub>1 \<bullet> x)"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
493 |
\end{tabular}\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
494 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
495 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
496 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
497 |
%* }
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
498 |
%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
499 |
%section { * Equivariance * }
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
500 |
%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
501 |
%text { *
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
502 |
|
1799
6471e252f14e
rewrite paragraph introducing equivariance, add citation to Pitts03
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
503 |
An \emph{equivariant} function or predicate is one that is invariant under
|
6471e252f14e
rewrite paragraph introducing equivariance, add citation to Pitts03
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
504 |
the swapping of atoms. Having a notion of equivariance with nice logical
|
6471e252f14e
rewrite paragraph introducing equivariance, add citation to Pitts03
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
505 |
properties is a major advantage of bijective permutations over traditional
|
6471e252f14e
rewrite paragraph introducing equivariance, add citation to Pitts03
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
506 |
renaming substitutions \cite[\S2]{Pitts03}. Equivariance can be defined
|
6471e252f14e
rewrite paragraph introducing equivariance, add citation to Pitts03
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
507 |
uniformly for all permutation types, and it is satisfied by most HOL
|
6471e252f14e
rewrite paragraph introducing equivariance, add citation to Pitts03
Brian Huffman <brianh@cs.pdx.edu>
diff
changeset
|
508 |
functions and constants.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
509 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
510 |
\begin{definition}\label{equivariance}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
511 |
A function @{text f} is \emph{equivariant} if @{term "\<forall>\<pi>. \<pi> \<bullet> f = f"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
512 |
\end{definition}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
513 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
514 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
515 |
There are a number of equivalent formulations for the equivariance property.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
516 |
For example, assuming @{text f} is of type @{text "\<alpha> \<Rightarrow> \<beta>"}, then equivariance
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
517 |
can also be stated as
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
518 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
519 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
520 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
521 |
@{text "\<forall>\<pi> x. \<pi> \<bullet> (f x) = f (\<pi> \<bullet> x)"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
522 |
\end{tabular}\hfill\numbered{altequivariance}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
523 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
524 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
525 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
526 |
To see that this formulation implies the definition, we just unfold the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
527 |
definition of the permutation operation for functions and simplify with the equation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
528 |
and the cancellation property shown in \eqref{cancel}. To see the other direction, we use
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
529 |
the fact
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
530 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
531 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
532 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
533 |
@{text "\<pi> \<bullet> (f x) = (\<pi> \<bullet> f) (\<pi> \<bullet> x)"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
534 |
\end{tabular}\hfill\numbered{permutefunapp}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
535 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
536 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
537 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
538 |
which follows again directly
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
539 |
from the definition of the permutation operation for functions and the cancellation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
540 |
property. Similarly for functions with more than one argument.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
541 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
542 |
Both formulations of equivariance have their advantages and disadvantages:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
543 |
\eqref{altequivariance} is often easier to establish. For example we
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
544 |
can easily show that equality is equivariant
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
545 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
546 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
547 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
548 |
@{thm eq_eqvt[where p="\<pi>", no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
549 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
550 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
551 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
552 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
553 |
using the permutation operation on booleans and property \eqref{permuteequ}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
554 |
Lemma~\ref{permutecompose} establishes that the permutation operation is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
555 |
equivariant. It is also easy to see that the boolean operators, like
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
556 |
@{text "\<and>"}, @{text "\<or>"} and @{text "\<longrightarrow>"} are all equivariant. Furthermore
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
557 |
a simple calculation will show that our swapping functions are equivariant, that is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
558 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
559 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
560 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
561 |
@{thm swap_eqvt[where p="\<pi>", no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
562 |
\end{tabular}\hfill\numbered{swapeqvt}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
563 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
564 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
565 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
566 |
for all @{text a}, @{text b} and @{text \<pi>}. These equivariance properties
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
567 |
are tremendously helpful later on when we have to push permutations inside
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
568 |
terms.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
569 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
570 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
571 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
572 |
section {* Support and Freshness *}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
573 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
574 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
575 |
The most original aspect of the nominal logic work of Pitts et al is a general
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
576 |
definition for ``the set of free variables of an object @{text "x"}''. This
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
577 |
definition is general in the sense that it applies not only to lambda-terms,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
578 |
but also to lists, products, sets and even functions. The definition depends
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
579 |
only on the permutation operation and on the notion of equality defined for
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
580 |
the type of @{text x}, namely:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
581 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
582 |
@{thm [display,indent=10] supp_def[no_vars, THEN eq_reflection]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
583 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
584 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
585 |
(Note that due to the definition of swapping in \eqref{swapdef}, we do not
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
586 |
need to explicitly restrict @{text a} and @{text b} to have the same sort.)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
587 |
There is also the derived notion for when an atom @{text a} is \emph{fresh}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
588 |
for an @{text x}, defined as
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
589 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
590 |
@{thm [display,indent=10] fresh_def[no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
591 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
592 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
593 |
A striking consequence of these definitions is that we can prove
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
594 |
without knowing anything about the structure of @{term x} that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
595 |
swapping two fresh atoms, say @{text a} and @{text b}, leave
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
596 |
@{text x} unchanged. For the proof we use the following lemma
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
597 |
about swappings applied to an @{text x}:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
598 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
599 |
\begin{lemma}\label{swaptriple}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
600 |
Assuming @{text x} is of permutation type, and @{text a}, @{text b} and @{text c}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
601 |
have the same sort, then @{thm (prem 3) swap_rel_trans[no_vars]} and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
602 |
@{thm (prem 4) swap_rel_trans[no_vars]} imply @{thm (concl) swap_rel_trans[no_vars]}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
603 |
\end{lemma}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
604 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
605 |
\begin{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
606 |
The cases where @{text "a = c"} and @{text "b = c"} are immediate.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
607 |
For the remaining case it is, given our assumptions, easy to calculate
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
608 |
that the permutations
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
609 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
610 |
@{thm [display,indent=10] (concl) swap_triple[no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
611 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
612 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
613 |
are equal. The lemma is then by application of the second permutation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
614 |
property shown in \eqref{newpermprops}.\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
615 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
616 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
617 |
\begin{theorem}\label{swapfreshfresh}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
618 |
Let @{text x} be of permutation type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
619 |
@{thm [mode=IfThen] swap_fresh_fresh[no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
620 |
\end{theorem}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
621 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
622 |
\begin{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
623 |
If @{text a} and @{text b} have different sort, then the swapping is the identity.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
624 |
If they have the same sort, we know by definition of support that both
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
625 |
@{term "finite {c. (a \<rightleftharpoons> c) \<bullet> x \<noteq> x}"} and @{term "finite {c. (b \<rightleftharpoons> c) \<bullet> x \<noteq> x}"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
626 |
hold. So the union of these sets is finite too, and we know by Proposition~\ref{choosefresh}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
627 |
that there is an atom @{term c}, with the same sort as @{term a} and @{term b},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
628 |
that satisfies \mbox{@{term "(a \<rightleftharpoons> c) \<bullet> x = x"}} and @{term "(b \<rightleftharpoons> c) \<bullet> x = x"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
629 |
Now the theorem follows from Lemma~\ref{swaptriple}.\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
630 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
631 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
632 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
633 |
Two important properties that need to be established for later calculations is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
634 |
that @{text "supp"} and freshness are equivariant. For this we first show that:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
635 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
636 |
\begin{lemma}\label{half}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
637 |
If @{term x} is a permutation type, then @{thm (lhs) fresh_permute_iff[where p="\<pi>",no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
638 |
if and only if @{thm (rhs) fresh_permute_iff[where p="\<pi>",no_vars]}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
639 |
\end{lemma}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
640 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
641 |
\begin{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
642 |
\begin{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
643 |
\begin{tabular}[t]{c@ {\hspace{2mm}}l@ {\hspace{5mm}}l}
|
1776
|
644 |
& \multicolumn{2}{@ {}l}{@{thm (lhs) fresh_permute_iff[where p="\<pi>",no_vars]} @{text "\<equiv>"}
|
|
645 |
@{term "finite {b. (\<pi> \<bullet> a \<rightleftharpoons> b) \<bullet> \<pi> \<bullet> x \<noteq> \<pi> \<bullet> x}"}}\\
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
646 |
@{text "\<Leftrightarrow>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
647 |
& @{term "finite {b. (\<pi> \<bullet> a \<rightleftharpoons> \<pi> \<bullet> b) \<bullet> \<pi> \<bullet> x \<noteq> \<pi> \<bullet> x}"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
648 |
& since @{text "\<pi> \<bullet> _"} is bijective\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
649 |
@{text "\<Leftrightarrow>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
650 |
& @{term "finite {b. \<pi> \<bullet> (a \<rightleftharpoons> b) \<bullet> x \<noteq> \<pi> \<bullet> x}"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
651 |
& by \eqref{permutecompose} and \eqref{swapeqvt}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
652 |
@{text "\<Leftrightarrow>"}
|
1776
|
653 |
& @{term "finite {b. (a \<rightleftharpoons> b) \<bullet> x \<noteq> x}"} @{text "\<equiv>"}
|
|
654 |
@{thm (rhs) fresh_permute_iff[where p="\<pi>",no_vars]}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
655 |
& by \eqref{permuteequ}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
656 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
657 |
\end{isabelle}\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
658 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
659 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
660 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
661 |
Together with the definition of the permutation operation on booleans,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
662 |
we can immediately infer equivariance of freshness:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
663 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
664 |
@{thm [display,indent=10] fresh_eqvt[where p="\<pi>",no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
665 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
666 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
667 |
Now equivariance of @{text "supp"}, namely
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
668 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
669 |
@{thm [display,indent=10] supp_eqvt[where p="\<pi>",no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
670 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
671 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
672 |
is by noting that @{thm supp_conv_fresh[no_vars]} and that freshness and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
673 |
the logical connectives are equivariant.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
674 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
675 |
While the abstract properties of support and freshness, particularly
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
676 |
Theorem~\ref{swapfreshfresh}, are useful for developing Nominal Isabelle,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
677 |
one often has to calculate the support of some concrete object. This is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
678 |
straightforward for example for booleans, nats, products and lists:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
679 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
680 |
\begin{center}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
681 |
\begin{tabular}{@ {}c@ {\hspace{2mm}}c@ {}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
682 |
\begin{tabular}{@ {}r@ {\hspace{2mm}}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
683 |
@{text "booleans"}: & @{term "supp b = {}"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
684 |
@{text "nats"}: & @{term "supp n = {}"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
685 |
@{text "products"}: & @{thm supp_Pair[no_vars]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
686 |
\end{tabular} &
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
687 |
\begin{tabular}{r@ {\hspace{2mm}}l@ {}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
688 |
@{text "lists:"} & @{thm supp_Nil[no_vars]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
689 |
& @{thm supp_Cons[no_vars]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
690 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
691 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
692 |
\end{center}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
693 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
694 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
695 |
But establishing the support of atoms and permutations in our setup here is a bit
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
696 |
trickier. To do so we will use the following notion about a \emph{supporting set}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
697 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
698 |
\begin{definition}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
699 |
A set @{text S} \emph{supports} @{text x} if for all atoms @{text a} and @{text b}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
700 |
not in @{text S} we have @{term "(a \<rightleftharpoons> b) \<bullet> x = x"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
701 |
\end{definition}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
702 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
703 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
704 |
The main motivation for this notion is that we can characterise @{text "supp x"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
705 |
as the smallest finite set that supports @{text "x"}. For this we prove:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
706 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
707 |
\begin{lemma}\label{supports} Let @{text x} be of permutation type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
708 |
\begin{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
709 |
\begin{tabular}{r@ {\hspace{4mm}}p{10cm}}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
710 |
i) & @{thm[mode=IfThen] supp_is_subset[no_vars]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
711 |
ii) & @{thm[mode=IfThen] supp_supports[no_vars]}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
712 |
iii) & @{thm (concl) supp_is_least_supports[no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
713 |
provided @{thm (prem 1) supp_is_least_supports[no_vars]},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
714 |
@{thm (prem 2) supp_is_least_supports[no_vars]}
|
1776
|
715 |
and @{text "S"} is the least such set, that means formally,
|
|
716 |
for all @{text "S'"}, if @{term "finite S'"} and
|
|
717 |
@{term "S' supports x"} then @{text "S \<subseteq> S'"}.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
718 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
719 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
720 |
\end{lemma}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
721 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
722 |
\begin{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
723 |
For @{text "i)"} we derive a contradiction by assuming there is an atom @{text a}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
724 |
with @{term "a \<in> supp x"} and @{text "a \<notin> S"}. Using the second fact, the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
725 |
assumption that @{term "S supports x"} gives us that @{text S} is a superset of
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
726 |
@{term "{b. (a \<rightleftharpoons> b) \<bullet> x \<noteq> x}"}, which is finite by the assumption of @{text S}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
727 |
being finite. But this means @{term "a \<notin> supp x"}, contradicting our assumption.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
728 |
Property @{text "ii)"} is by a direct application of
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
729 |
Theorem~\ref{swapfreshfresh}. For the last property, part @{text "i)"} proves
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
730 |
one ``half'' of the claimed equation. The other ``half'' is by property
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
731 |
@{text "ii)"} and the fact that @{term "supp x"} is finite by @{text "i)"}.\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
732 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
733 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
734 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
735 |
These are all relatively straightforward proofs adapted from the existing
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
736 |
nominal logic work. However for establishing the support of atoms and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
737 |
permutations we found the following ``optimised'' variant of @{text "iii)"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
738 |
more useful:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
739 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
740 |
\begin{lemma}\label{optimised} Let @{text x} be of permutation type.
|
1776
|
741 |
We have that @{thm (concl) finite_supp_unique[no_vars]}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
742 |
provided @{thm (prem 1) finite_supp_unique[no_vars]},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
743 |
@{thm (prem 2) finite_supp_unique[no_vars]}, and for
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
744 |
all @{text "a \<in> S"} and all @{text "b \<notin> S"}, with @{text a}
|
1787
|
745 |
and @{text b} having the same sort, \mbox{@{term "(a \<rightleftharpoons> b) \<bullet> x \<noteq> x"}}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
746 |
\end{lemma}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
747 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
748 |
\begin{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
749 |
By Lemma \ref{supports}@{text ".iii)"} we have to show that for every finite
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
750 |
set @{text S'} that supports @{text x}, \mbox{@{text "S \<subseteq> S'"}} holds. We will
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
751 |
assume that there is an atom @{text "a"} that is element of @{text S}, but
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
752 |
not @{text "S'"} and derive a contradiction. Since both @{text S} and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
753 |
@{text S'} are finite, we can by Proposition \ref{choosefresh} obtain an atom
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
754 |
@{text b}, which has the same sort as @{text "a"} and for which we know
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
755 |
@{text "b \<notin> S"} and @{text "b \<notin> S'"}. Since we assumed @{text "a \<notin> S'"} and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
756 |
we have that @{text "S' supports x"}, we have on one hand @{term "(a \<rightleftharpoons> b) \<bullet> x
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
757 |
= x"}. On the other hand, the fact @{text "a \<in> S"} and @{text "b \<notin> S"} imply
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
758 |
@{term "(a \<rightleftharpoons> b) \<bullet> x \<noteq> x"} using the assumed implication. This gives us the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
759 |
contradiction.\hfill\qed
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
760 |
\end{proof}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
761 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
762 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
763 |
Using this lemma we only have to show the following three proof-obligations
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
764 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
765 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
766 |
\begin{tabular}{@ {}r@ {\hspace{4mm}}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
767 |
i) & @{term "{c} supports c"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
768 |
ii) & @{term "finite {c}"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
769 |
iii) & @{text "\<forall>a \<in> {c} b \<notin> {c}. sort a = sort b \<longrightarrow> (a b) \<bullet> c \<noteq> c"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
770 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
771 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
772 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
773 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
774 |
in order to establish that @{thm supp_atom[where a="c", no_vars]} holds. In
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
775 |
Isabelle/HOL these proof-obligations can be discharged by easy
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
776 |
simplifications. Similar proof-obligations arise for the support of
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
777 |
permutations, which is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
778 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
779 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
780 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
781 |
@{thm supp_perm[where p="\<pi>", no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
782 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
783 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
784 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
785 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
786 |
The only proof-obligation that is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
787 |
interesting is the one where we have to show that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
788 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
789 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
790 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
791 |
@{text "If \<pi> \<bullet> a \<noteq> a, \<pi> \<bullet> b = b and sort a = sort b, then (a b) \<bullet> \<pi> \<noteq> \<pi>"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
792 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
793 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
794 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
795 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
796 |
For this we observe that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
797 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
798 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
799 |
\begin{tabular}{@ {}rcl}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
800 |
@{thm (lhs) perm_swap_eq[where p="\<pi>", no_vars]} &
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
801 |
if and only if &
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
802 |
@{thm (rhs) perm_swap_eq[where p="\<pi>", no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
803 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
804 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
805 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
806 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
807 |
holds by a simple calculation using the group properties of permutations.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
808 |
The proof-obligation can then be discharged by analysing the inequality
|
1776
|
809 |
between the permutations @{term "(\<pi> \<bullet> a \<rightleftharpoons> b)"} and @{term "(a \<rightleftharpoons> b)"}.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
810 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
811 |
The main point about support is that whenever an object @{text x} has finite
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
812 |
support, then Proposition~\ref{choosefresh} allows us to choose for @{text x} a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
813 |
fresh atom with arbitrary sort. This is an important operation in Nominal
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
814 |
Isabelle in situations where, for example, a bound variable needs to be
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
815 |
renamed. To allow such a choice, we only have to assume \emph{one} premise
|
1780
|
816 |
of the form @{text "finite (supp x)"}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
817 |
for each @{text x}. Compare that with the sequence of premises in our earlier
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
818 |
version of Nominal Isabelle (see~\eqref{fssequence}). For more convenience we
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
819 |
can define a type class for types where every element has finite support, and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
820 |
prove that the types @{term "atom"}, @{term "perm"}, lists, products and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
821 |
booleans are instances of this type class. Then \emph{no} premise is needed,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
822 |
as the type system of Isabelle/HOL can figure out automatically when an object
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
823 |
is finitely supported.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
824 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
825 |
Unfortunately, this does not work for sets or Isabelle/HOL's function type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
826 |
There are functions and sets definable in Isabelle/HOL for which the finite
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
827 |
support property does not hold. A simple example of a function with
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
828 |
infinite support is the function that returns the natural number of an atom
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
829 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
830 |
@{text [display, indent=10] "nat_of (Atom s i) \<equiv> i"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
831 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
832 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
833 |
This function's support is the set of \emph{all} atoms. To establish this we show @{term "\<not> a \<sharp> nat_of"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
834 |
This is equivalent to assuming the set @{term "{b. (a \<rightleftharpoons> b) \<bullet> nat_of \<noteq> nat_of}"} is finite
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
835 |
and deriving a contradiction. From the assumption we also know that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
836 |
@{term "{a} \<union> {b. (a \<rightleftharpoons> b) \<bullet> nat_of \<noteq> nat_of}"} is finite. Then we can use
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
837 |
Proposition~\ref{choosefresh} to choose an atom @{text c} such that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
838 |
@{term "c \<noteq> a"}, @{term "sort_of c = sort_of a"} and @{term "(a \<rightleftharpoons> c) \<bullet> nat_of = nat_of"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
839 |
Now we can reason as follows:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
840 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
841 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
842 |
\begin{tabular}[b]{@ {}rcl@ {\hspace{5mm}}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
843 |
@{text "nat_of a"} & @{text "="} & @{text "(a \<rightleftharpoons> c) \<bullet> (nat_of a)"} & by def.~of permutations on nats\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
844 |
& @{text "="} & @{term "((a \<rightleftharpoons> c) \<bullet> nat_of) ((a \<rightleftharpoons> c) \<bullet> a)"} & by \eqref{permutefunapp}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
845 |
& @{text "="} & @{term "nat_of c"} & by assumptions on @{text c}\\
|
1776
|
846 |
\end{tabular}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
847 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
848 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
849 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
850 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
851 |
But this means we have that @{term "nat_of a = nat_of c"} and @{term "sort_of a = sort_of c"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
852 |
This implies that atoms @{term a} and @{term c} must be equal, which clashes with our
|
1776
|
853 |
assumption @{term "c \<noteq> a"} about how we chose @{text c}.
|
|
854 |
Cheney \cite{Cheney06} gives similar examples for constructions that have infinite support.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
855 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
856 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
857 |
section {* Concrete Atom Types *}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
858 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
859 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
860 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
861 |
So far, we have presented a system that uses only a single multi-sorted atom
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
862 |
type. This design gives us the flexibility to define operations and prove
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
863 |
theorems that are generic with respect to atom sorts. For example, as
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
864 |
illustrated above the @{term supp} function returns a set that includes the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
865 |
free atoms of \emph{all} sorts together; the flexibility offered by the new
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
866 |
atom type makes this possible.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
867 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
868 |
However, the single multi-sorted atom type does not make an ideal interface
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
869 |
for end-users of Nominal Isabelle. If sorts are not distinguished by
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
870 |
Isabelle's type system, users must reason about atom sorts manually. That
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
871 |
means subgoals involving sorts must be discharged explicitly within proof
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
872 |
scripts, instead of being inferred by Isabelle/HOL's type checker. In other
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
873 |
cases, lemmas might require additional side conditions about sorts to be true.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
874 |
For example, swapping @{text a} and @{text b} in the pair \mbox{@{term "(a,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
875 |
b)"}} will only produce the expected result if we state the lemma in
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
876 |
Isabelle/HOL as:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
877 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
878 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
879 |
lemma
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
880 |
fixes a b :: "atom"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
881 |
assumes asm: "sort a = sort b"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
882 |
shows "(a \<rightleftharpoons> b) \<bullet> (a, b) = (b, a)"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
883 |
using asm by simp
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
884 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
885 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
886 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
887 |
Fortunately, it is possible to regain most of the type-checking automation
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
888 |
that is lost by moving to a single atom type. We accomplish this by defining
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
889 |
\emph{subtypes} of the generic atom type that only include atoms of a single
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
890 |
specific sort. We call such subtypes \emph{concrete atom types}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
891 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
892 |
The following Isabelle/HOL command defines a concrete atom type called
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
893 |
\emph{name}, which consists of atoms whose sort equals the string @{term
|
1790
|
894 |
"''name''"}.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
895 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
896 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
1790
|
897 |
\isacommand{typedef}\ \ @{typ name} = @{term "{a. sort\<iota> a = ''name''}"}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
898 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
899 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
900 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
901 |
This command automatically generates injective functions that map from the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
902 |
concrete atom type into the generic atom type and back, called
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
903 |
representation and abstraction functions, respectively. We will write these
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
904 |
functions as follows:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
905 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
906 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
907 |
\begin{tabular}{@ {}l@ {\hspace{10mm}}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
908 |
@{text "\<lfloor>_\<rfloor> :: name \<Rightarrow> atom"} &
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
909 |
@{text "\<lceil>_\<rceil> :: atom \<Rightarrow> name"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
910 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
911 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
912 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
913 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
914 |
With the definition @{thm permute_name_def [where p="\<pi>", THEN
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
915 |
eq_reflection, no_vars]}, it is straightforward to verify that the type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
916 |
@{typ name} is a permutation type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
917 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
918 |
In order to reason uniformly about arbitrary concrete atom types, we define a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
919 |
type class that characterises type @{typ name} and other similarly-defined
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
920 |
types. The definition of the concrete atom type class is as follows: First,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
921 |
every concrete atom type must be a permutation type. In addition, the class
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
922 |
defines an overloaded function that maps from the concrete type into the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
923 |
generic atom type, which we will write @{text "|_|"}. For each class
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
924 |
instance, this function must be injective and equivariant, and its outputs
|
1780
|
925 |
must all have the same sort, that is
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
926 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
927 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
1776
|
928 |
i) \hspace{1mm}if @{thm (lhs) atom_eq_iff [no_vars]} then @{thm (rhs) atom_eq_iff [no_vars]}\hspace{4mm}
|
|
929 |
ii) \hspace{1mm}@{thm atom_eqvt[where p="\<pi>", no_vars]}\hspace{4mm}
|
|
930 |
iii) \hspace{1mm}@{thm sort_of_atom_eq [no_vars]}
|
|
931 |
\hfill\numbered{atomprops}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
932 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
933 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
934 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
935 |
With the definition @{thm atom_name_def [THEN eq_reflection, no_vars]} we can
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
936 |
show that @{typ name} satisfies all the above requirements of a concrete atom
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
937 |
type.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
938 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
939 |
The whole point of defining the concrete atom type class was to let users
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
940 |
avoid explicit reasoning about sorts. This benefit is realised by defining a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
941 |
special swapping operation of type @{text "\<alpha> \<Rightarrow> \<alpha>
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
942 |
\<Rightarrow> perm"}, where @{text "\<alpha>"} is a concrete atom type:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
943 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
944 |
@{thm [display,indent=10] flip_def [THEN eq_reflection, no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
945 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
946 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
947 |
As a consequence of its type, the @{text "\<leftrightarrow>"}-swapping
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
948 |
operation works just like the generic swapping operation, but it does not
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
949 |
require any sort-checking side conditions---the sort-correctness is ensured by
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
950 |
the types! For @{text "\<leftrightarrow>"} we can establish the following
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
951 |
simplification rule:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
952 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
953 |
@{thm [display,indent=10] permute_flip_at[no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
954 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
955 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
956 |
If we now want to swap the \emph{concrete} atoms @{text a} and @{text b}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
957 |
in the pair @{term "(a, b)"} we can establish the lemma as follows:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
958 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
959 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
960 |
lemma
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
961 |
fixes a b :: "name"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
962 |
shows "(a \<leftrightarrow> b) \<bullet> (a, b) = (b, a)"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
963 |
by simp
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
964 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
965 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
966 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
967 |
There is no need to state an explicit premise involving sorts.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
968 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
969 |
We can automate the process of creating concrete atom types, so that users
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
970 |
can define a new one simply by issuing the command
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
971 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
972 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
973 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
974 |
\isacommand{atom\_decl}~~@{text "name"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
975 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
976 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
977 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
978 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
979 |
This command can be implemented using less than 100 lines of custom ML-code.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
980 |
In comparison, the old version of Nominal Isabelle included more than 1000
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
981 |
lines of ML-code for creating concrete atom types, and for defining various
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
982 |
type classes and instantiating generic lemmas for them. In addition to
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
983 |
simplifying the ML-code, the setup here also offers user-visible improvements:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
984 |
Now concrete atoms can be declared at any point of a formalisation, and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
985 |
theories that separately declare different atom types can be merged
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
986 |
together---it is no longer required to collect all atom declarations in one
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
987 |
place.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
988 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
989 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
990 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
991 |
section {* Multi-Sorted Concrete Atoms *}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
992 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
993 |
(*<*)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
994 |
datatype ty = TVar string | Fun ty ty ("_ \<rightarrow> _")
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
995 |
(*>*)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
996 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
997 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
998 |
The formalisation presented so far allows us to streamline proofs and reduce
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
999 |
the amount of custom ML-code in the existing implementation of Nominal
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1000 |
Isabelle. In this section we describe a mechanism that extends the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1001 |
capabilities of Nominal Isabelle. This mechanism is about variables with
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1002 |
additional information, for example typing constraints.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1003 |
While we leave a detailed treatment of binders and binding of variables for a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1004 |
later paper, we will have a look here at how such variables can be
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1005 |
represented by concrete atoms.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1006 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1007 |
In the previous section we considered concrete atoms that can be used in
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1008 |
simple binders like \emph{@{text "\<lambda>x. x"}}. Such concrete atoms do
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1009 |
not carry any information beyond their identities---comparing for equality
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1010 |
is really the only way to analyse ordinary concrete atoms.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1011 |
However, in ``Church-style'' lambda-terms \cite{Church40} and in the terms
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1012 |
underlying HOL-systems \cite{PittsHOL4} binders and bound variables have a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1013 |
more complicated structure. For example in the ``Church-style'' lambda-term
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1014 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1015 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1016 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1017 |
@{text "\<lambda>x\<^isub>\<alpha>. x\<^isub>\<alpha> x\<^isub>\<beta>"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1018 |
\end{tabular}\hfill\numbered{church}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1019 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1020 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1021 |
\noindent
|
1779
|
1022 |
both variables and binders include typing information indicated by @{text \<alpha>}
|
|
1023 |
and @{text \<beta>}. In this setting, we treat @{text "x\<^isub>\<alpha>"} and @{text
|
|
1024 |
"x\<^isub>\<beta>"} as distinct variables (assuming @{term "\<alpha>\<noteq>\<beta>"}) so that the
|
|
1025 |
variable @{text "x\<^isub>\<alpha>"} is bound by the lambda-abstraction, but not
|
|
1026 |
@{text "x\<^isub>\<beta>"}.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1027 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1028 |
To illustrate how we can deal with this phenomenon, let us represent object
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1029 |
types like @{text \<alpha>} and @{text \<beta>} by the datatype
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1030 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1031 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1032 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1033 |
\isacommand{datatype}~~@{text "ty = TVar string | ty \<rightarrow> ty"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1034 |
\end{tabular}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1035 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1036 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1037 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1038 |
If we attempt to encode a variable naively as a pair of a @{text name} and a @{text ty}, we have the
|
1779
|
1039 |
problem that a swapping, say @{term "(x \<leftrightarrow> y)"}, applied to the pair @{text "((x, \<alpha>), (x, \<beta>))"}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1040 |
will always permute \emph{both} occurrences of @{text x}, even if the types
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1041 |
@{text "\<alpha>"} and @{text "\<beta>"} are different. This is unwanted, because it will
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1042 |
eventually mean that both occurrences of @{text x} will become bound by a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1043 |
corresponding binder.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1044 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1045 |
Another attempt might be to define variables as an instance of the concrete
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1046 |
atom type class, where a @{text ty} is somehow encoded within each variable.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1047 |
Remember we defined atoms as the datatype:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1048 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1049 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1050 |
datatype atom\<iota>\<iota> = Atom\<iota>\<iota> string nat
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1051 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1052 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1053 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1054 |
Considering our method of defining concrete atom types, the usage of a string
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1055 |
for the sort of atoms seems a natural choice. However, none of the results so
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1056 |
far depend on this choice and we are free to change it.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1057 |
One possibility is to encode types or any other information by making the sort
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1058 |
argument parametric as follows:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1059 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1060 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1061 |
datatype 'a \<iota>atom\<iota>\<iota>\<iota> = \<iota>Atom\<iota>\<iota> 'a nat
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1062 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1063 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1064 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1065 |
The problem with this possibility is that we are then back in the old
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1066 |
situation where our permutation operation is parametric in two types and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1067 |
this would require to work around Isabelle/HOL's restriction on type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1068 |
classes. Fortunately, encoding the types in a separate parameter is not
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1069 |
necessary for what we want to achieve, as we only have to know when two
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1070 |
types are equal or not. The solution is to use a different sort for each
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1071 |
object type. Then we can use the fact that permutations respect \emph{sorts} to
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1072 |
ensure that permutations also respect \emph{object types}. In order to do
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1073 |
this, we must define an injective function @{text "sort_ty"} mapping from
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1074 |
object types to sorts. For defining functions like @{text "sort_ty"}, it is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1075 |
more convenient to use a tree datatype for sorts. Therefore we define
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1076 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1077 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1078 |
datatype sort = Sort string "(sort list)"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1079 |
datatype atom\<iota>\<iota>\<iota>\<iota> = Atom\<iota>\<iota>\<iota>\<iota> sort nat
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1080 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1081 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1082 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1083 |
With this definition,
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1084 |
the sorts we considered so far can be encoded just as \mbox{@{text "Sort s []"}}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1085 |
The point, however, is that we can now define the function @{text sort_ty} simply as
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1086 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1087 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1088 |
\begin{tabular}{@ {}l}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1089 |
@{text "sort_ty (TVar s) = Sort ''TVar'' [Sort s []]"}\\
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1090 |
@{text "sort_ty (\<tau>\<^isub>1 \<rightarrow> \<tau>\<^isub>2) = Sort ''Fun'' [sort_ty \<tau>\<^isub>1, sort_ty \<tau>\<^isub>2]"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1091 |
\end{tabular}\hfill\numbered{sortty}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1092 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1093 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1094 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1095 |
which can easily be shown to be injective.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1096 |
|
1776
|
1097 |
Having settled on what the sorts should be for ``Church-like'' atoms, we have to
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1098 |
give a subtype definition for concrete atoms. Previously we identified a subtype consisting
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1099 |
of atoms of only one specified sort. This must be generalised to all sorts the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1100 |
function @{text "sort_ty"} might produce, i.e.~the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1101 |
range of @{text "sort_ty"}. Therefore we define
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1102 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1103 |
\begin{isabelle}\ \ \ \ \ \ \ \ \ \ %%%
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1104 |
\isacommand{typedef}\ \ @{text var} = @{term "{a. sort a : range sort_ty}"}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1105 |
\end{isabelle}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1106 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1107 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1108 |
This command gives us again injective representation and abstraction
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1109 |
functions. We will write them also as \mbox{@{text "\<lfloor>_\<rfloor> :: var \<Rightarrow> atom"}} and
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1110 |
@{text "\<lceil>_\<rceil> :: atom \<Rightarrow> var"}, respectively.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1111 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1112 |
We can define the permutation operation for @{text var} as @{thm
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1113 |
permute_var_def[where p="\<pi>", THEN eq_reflection, no_vars]} and the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1114 |
injective function to type @{typ atom} as @{thm atom_var_def[THEN
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1115 |
eq_reflection, no_vars]}. Finally, we can define a constructor function that
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1116 |
makes a @{text var} from a variable name and an object type:
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1117 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1118 |
@{thm [display,indent=10] Var_def[where t="\<alpha>", THEN eq_reflection, no_vars]}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1119 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1120 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1121 |
With these definitions we can verify all the properties for concrete atom
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1122 |
types except Property \ref{atomprops}@{text ".iii)"}, which requires every
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1123 |
atom to have the same sort. This last property is clearly not true for type
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1124 |
@{text "var"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1125 |
This fact is slightly unfortunate since this
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1126 |
property allowed us to use the type-checker in order to shield the user from
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1127 |
all sort-constraints. But this failure is expected here, because we cannot
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1128 |
burden the type-system of Isabelle/HOL with the task of deciding when two
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1129 |
object types are equal. This means we sometimes need to explicitly state sort
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1130 |
constraints or explicitly discharge them, but as we will see in the lemma
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1131 |
below this seems a natural price to pay in these circumstances.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1132 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1133 |
To sum up this section, the encoding of type-information into atoms allows us
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1134 |
to form the swapping @{term "(Var x \<alpha> \<leftrightarrow> Var y \<alpha>)"} and to prove the following
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1135 |
lemma
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1136 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1137 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1138 |
lemma
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1139 |
assumes asm: "\<alpha> \<noteq> \<beta>"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1140 |
shows "(Var x \<alpha> \<leftrightarrow> Var y \<alpha>) \<bullet> (Var x \<alpha>, Var x \<beta>) = (Var y \<alpha>, Var x \<beta>)"
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1141 |
using asm by simp
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1142 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1143 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1144 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1145 |
As we expect, the atom @{term "Var x \<beta>"} is left unchanged by the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1146 |
swapping. With this we can faithfully represent bindings in languages
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1147 |
involving ``Church-style'' terms and bindings as shown in \eqref{church}. We
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1148 |
expect that the creation of such atoms can be easily automated so that the
|
1779
|
1149 |
user just needs to specify \isacommand{atom\_decl}~~@{text "var (ty)"}
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1150 |
where the argument, or arguments, are datatypes for which we can automatically
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1151 |
define an injective function like @{text "sort_ty"} (see \eqref{sortty}).
|
1788
|
1152 |
Our hope is that with this approach Benzmueller and Paulson can make
|
|
1153 |
headway with formalising their results
|
|
1154 |
about simple type theory \cite{PaulsonBenzmueller}.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1155 |
Because of its limitations, they did not attempt this with the old version
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1156 |
of Nominal Isabelle. We also hope we can make progress with formalisations of
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1157 |
HOL-based languages.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1158 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1159 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1160 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1161 |
section {* Conclusion *}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1162 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1163 |
text {*
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1164 |
This proof pearl describes a new formalisation of the nominal logic work by
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1165 |
Pitts et al. With the definitions we presented here, the formal reasoning blends
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1166 |
smoothly with the infrastructure of the Isabelle/HOL theorem prover.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1167 |
Therefore the formalisation will be the underlying theory for a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1168 |
new version of Nominal Isabelle.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1169 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1170 |
The main difference of this paper with respect to existing work on Nominal
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1171 |
Isabelle is the representation of atoms and permutations. First, we used a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1172 |
single type for sorted atoms. This design choice means for a term @{term t},
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1173 |
say, that its support is completely characterised by @{term "supp t"}, even
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1174 |
if the term contains different kinds of atoms. Also, whenever we have to
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1175 |
generalise an induction so that a property @{text P} is not just established
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1176 |
for all @{text t}, but for all @{text t} \emph{and} under all permutations
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1177 |
@{text \<pi>}, then we only have to state @{term "\<forall>\<pi>. P (\<pi> \<bullet> t)"}. The reason is
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1178 |
that permutations can now consist of multiple swapping each of which can
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1179 |
swap different kinds of atoms. This simplifies considerably the reasoning
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1180 |
involved in building Nominal Isabelle.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1181 |
|
1776
|
1182 |
Second, we represented permutations as functions so that the associated
|
|
1183 |
permutation operation has only a single type parameter. This is very convenient
|
|
1184 |
because the abstract reasoning about permutations fits cleanly
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1185 |
with Isabelle/HOL's type classes. No custom ML-code is required to work
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1186 |
around rough edges. Moreover, by establishing that our permutations-as-functions
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1187 |
representation satisfy the group properties, we were able to use extensively
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1188 |
Isabelle/HOL's reasoning infrastructure for groups. This often reduced proofs
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1189 |
to simple calculations over @{text "+"}, @{text "-"} and @{text "0"}.
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1190 |
An interesting point is that we defined the swapping operation so that a
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1191 |
swapping of two atoms with different sorts is \emph{not} excluded, like
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1192 |
in our older work on Nominal Isabelle, but there is no ``effect'' of such
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1193 |
a swapping (it is defined as the identity). This is a crucial insight
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1194 |
in order to make the approach based on a single type of sorted atoms to work.
|
1779
|
1195 |
But of course it is analogous to the well-known trick of defining division by
|
|
1196 |
zero to return zero.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1197 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1198 |
We noticed only one disadvantage of the permutations-as-functions: Over
|
1788
|
1199 |
lists we can easily perform inductions. For permutations made up from
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1200 |
functions, we have to manually derive an appropriate induction principle. We
|
1779
|
1201 |
can establish such a principle, but we have no real experience yet whether ours
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1202 |
is the most useful principle: such an induction principle was not needed in
|
1779
|
1203 |
any of the reasoning we ported from the old Nominal Isabelle, except
|
|
1204 |
when showing that if @{term "\<forall>a \<in> supp x. a \<sharp> p"} implies @{term "p \<bullet> x = x"}.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1205 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1206 |
Finally, our implementation of sorted atoms turned out powerful enough to
|
1779
|
1207 |
use it for representing variables that carry on additional information, for
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1208 |
example typing annotations. This information is encoded into the sorts. With
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1209 |
this we can represent conveniently binding in ``Church-style'' lambda-terms
|
1779
|
1210 |
and HOL-based languages. While dealing with such additional information in
|
|
1211 |
dependent type-theories, such as LF or Coq, is straightforward, we are not
|
|
1212 |
aware of any other approach in a non-dependent HOL-setting that can deal
|
|
1213 |
conveniently with such binders.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1214 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1215 |
The formalisation presented here will eventually become part of the Isabelle
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1216 |
distribution, but for the moment it can be downloaded from the
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1217 |
Mercurial repository linked at
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1218 |
\href{http://isabelle.in.tum.de/nominal/download}
|
1779
|
1219 |
{http://isabelle.in.tum.de/nominal/download}.\smallskip
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1220 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1221 |
\noindent
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1222 |
{\bf Acknowledgements:} We are very grateful to Jesper Bengtson, Stefan
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1223 |
Berghofer and Cezary Kaliszyk for their comments on earlier versions
|
1776
|
1224 |
of this paper. We are also grateful to the anonymous referee who helped us to
|
|
1225 |
put the work into the right context.
|
1772
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1226 |
*}
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1227 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1228 |
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1229 |
(*<*)
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1230 |
end
|
48c2eb84d5ce
merged pearl paper with this repository; started litrature subdirectory
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1231 |
(*>*) |