PhD navigation: PhD Overview Table of Contents, relating the PhD and the online material Detailed description of the files in this directory Download area

Detailed Descriptions: Variance Queue UML

Detailed Desciption for directory Fibration

This page gives detailed information for all files in the directory Fibration.

Click here to jump downwards to the description.
General theory development
nat.pvs Lemma about even and odd numbers
fixedpoints.pvs Correctness of prelude fixed point construction
base.pvs bicartesian closed structure
fibrations.pvs fibrations of predicates and relations
fibprops.pvs properties of predicates and relations
pol_aczel.pvs equivalence of the Aczel/Mendler and Hermida/Jacobs bisimulation for polynomial functors
aczel.pvs equivalence of the Aczel/Mendler and Hermida/Jacobs bisimulation for extended polynomial functors
invariant.pvs relation of invariants and bisimulations
image_morph.pvs The image of a morphism is an invariant
per.pvs partial equivalence relations
per_extended.pvs lattics of partial bisimulation equivalences
cart.pvs Cardinalities of PVS Types
def.pvs Example specification with a binary method for which there exists a final model
rellist.pvs Investigation of the list functor
finitely.pvs Bases and finitely based coalgebras
Functors
t.pvs T(Y,X) = (X => Y) => X
g.pvs G(Y,X) = (X => A) => A
union.pvs K(Y,X) = Y => A
K2.pvs K2(Y,X) = (A => Y) => X.
K3.pvs K3(Y,X) = (A => Y) => bool.
f.pvs F(Y,X) = (Y => X).
rellist.pvs The list functor: finite lists over its argument
lift.pvs Utility lemmas for Lift[A] = A + 1
sequences.pvs The final coalgebra of sequences
power.pvs The covariant powerset functor.
Counterexamples
exp.pvs Fibredness of higher order polynomial functors
intersection.pvs Intersection of bisimulations and invariants
relcomp.pvs Composition of bisimulations
union.pvs Union of bisimulations
inv-union.pvs Union of invariants
graph.pvs the graph of a morphism is not a bisimulation
kernel.pvs the kernel of a morphism is not a bisimulation
inv-char.pvs bisimulation delta* P
aczel_counter.pvs Aczel/Mendler and Hermida/Jacobs bisimulation
aczel_counter2.pvs Aczel/Mendler and Hermida/Jacobs bisimulation, Version II
aczel_counter3.pvs Aczel/Mendler and Hermida/Jacobs bisimulation Version III
mendler_counter.pvs Invariance and subcoalgebra are different notions
perlift_counter.pvs lattics of partial bisimulation equivalences
automatic typechek
typecheck.el control file for PVS
all.pvs Import everything

General theory

nat.pvs: Even and odd numbers

This file contains some simple results about even and odd numbers, this is needed in perlift_counter.pvs.

fixedpoints.pvs: Correctness of prelude fixed point constructions

This file proves that the fixed points from the PVS prelude are correct. In addition it shows that fixed point construction is monotonic for parametrised operators.

base.pvs: Bicartesian closed structure

This file defines the bicartesian closed structure of the base categorie, that is products, coproducts and exponents of sets and functions. Additionally it defines pullbacks and indexed collections.

fibrations.pvs: The fibrations of predicates and relations

This file defines the structure in the fibres and in the total categorie of predicates and relations. It proves the Beck-Chevallier and Frobenius conditions for PVS.

For the embedding of fibrations into the logic of PVS I follow very closely Ulrich Hensels PhD thesis (which is no longer online). The only difference is that, for definitions, I prefer to use the abstract categorical characterizations, whereas Uli uses their concrete PVS incarnations. This way it is possible to see abstract fibrational notion becoming alive. Of course at the expense of using rewrite lemmas to transfer the abstract notation into concreate proof obligations.

fibprops.pvs: Properties of the fibrations of predicates and relations

This file proves many properties of predicates and fibrations. In particular

pol_aczel.pvs: Equivalence of the Aczel/Mendler and Hermida/Jacobs bisimulation for polynomial functors

This theory formalizes the inductive predicate, the base cases and the induction steps. To proof the equivalence of the two definitions, it is enough to show that T(R) is isomorphic to Rel(T)(R). This can be done. Here I proof the slightly stronger result, namely that < T(pi_1), T(pi_2) > restricts to the needed isomorphism. I use this in file aczel.pvs.

aczel.pvs: Equivalence of the Aczel/Mendler and Hermida/Jacobs bisimulation for extended polynomial functors

The whole proof is a big induction on the structure of extended polynomial functors. The inductive predicates are in InductionProperties. The final result follows form these predicates, see the last theory AczelEq. There are two possibilities to get the induction going. The difference lays mainly in the induction step for the exponent.
  1. Prove for polynomial functors that <Tpi_1, Tpi_2> restricts to an isomorphism (see file pol_aczel.pvs). Do then two inductions with aczel_property and image_property and use the isomorphism in the induction step of the exponent. (Theory AczelExtendedFun)
  2. Do only one mutual induction and do a more complicated induction step for the exponent (Theory AczelExtendedAAFun).

invariant.pvs: Invariants and Bisimulations

This file shows, that the first projections of a bisimulation is an invariant. Further, the intersection of an invariant P with a bisimulation R is a bisimulation again. Both results hold only for extended polynomial functors. This file contains also counterexample for the functor T from file t.pvs

image_morph.pvs: The image of a morphism

This file shows, that for extended polynomial functors, the image of a morphism is an invariant. In the PVS source, this is proved by two inductions on the structure of the functor. The PhD contains a much simpler proof. But the proof by induction gives the inspiration for an example of a morphism for the higher order functor T whose image is not an invariant.

per.pvs: Partial equivalence relations

The results of this file are not in the PhD. This file defines partial partially reflexive relations and partial equivalence relations and proves a lot of properties about them. The lemmas in this file are towards the result that partial bisimulation equivalences form a complete lattics, see also per_extended.pvs and perlift_counter.pvs.

per_extended.pvs: Partial bisimulation equivalence for extended cartesian functors

The results of this file are not in the PhD. This file proves the inducation steps for the proof that partial bisimulation equivalences form a complete lattics for extended cartesian functors (a proper subclass of extended polynomial functors).

cart.pvs: Cardinalities of PVS Types

Formalizes the two predicates "cardinality less than" and "cardinality strictly less then" and contains lemmas about the powerset construction and the function space. This is used in file g.pvs.

def.pvs: A specification with a binary method

The material of this file is not in the PhD. The file defines a coalgebraic signature with a binary method. A specification restricts the class of valid models. The specification is such that the binary method cannot be defined as definitional extension of the other methods. Still there exists a final model of the specification. As an aside, the file shows also that the category of models has coproducts and that bisimulations are closed under union.

rellist.pvs: Investigation of the list functor.

This file formalises the functor list that generates the finite lists over its argument. The file defines predicate and relation lifting for lists and contains one theory for all induction proofs that are formalised in other theories. For instance the theory AczelList contains the induction step for lists for the proof of the Equivalence of the Aczel/Mendler and Hermida/Jacobs bisimulation for extended polynomial functors, see also this entry.

finitely.pvs: Bases and finitely based coalgebras

The material of this file is not in the PhD, for a description see my paper Greatest Bisimulations for Binary Methods. This file formalises the notions of a base, equality with respect to a base, and finitely based coalgebras. It proves that for finitely based coalgebras a greatest bisimulation equivalence does exist.

Functors

t.pvs: The functor T(Y,X) = (X => Y) => X and its liftings.

This functor is used in many counterexamples.

g.pvs: The doubble exponent functor

The material of this file is not discussed in the PhD. Here I define the functor G(X) = (X => A) => A and investicate its coalgebras. It is interesting because of the following mixture of properties: Note, that Charity allows you to define coalgebras for this functor.

K2.pvs: The functor K2(Y,X) = (A => Y) => X and its liftings.

This functor is used in a counterexample about partial equivalence relations in perlift_counter.pvs.

K3.pvs: The functor K3(Y,X) = (A => Y) => bool and its liftings.

This functor is used in a counterexample that partial bisimulation equivalences do not form a complete lattics for extended polynomial functors in perlift_counter.pvs.

f.pvs: The functor F(Y,X) = Y => X and its liftings.

This functor is used in the counterexample about the union of invariants in inv-union.pvs.

lift.pvs: Utility function for Lift[A] = A + 1.

This file defines the functor Lift as PVS data type and proves some utility lemmas about it. These lemmas are used in the file sequences.pvs.

sequences.pvs: The functor for possibly infinite sequences.

This file formalises the final coalgebra or possibly infinite sequences. In addition it proves a few general results about sequences, for instance fibredness and cofibredness.

power.pvs: The covariant powerset functor.

The material in this file is not in the PhD. The file contains a very rudimentary investigation of the covariant powerset functor: I only proof fibredness and cofibredness of the predicate lifting here.

Counterexamples

exp.pvs: Predicate lifting for Higher order polynomial functors is not fibred

This file contains an example for a situation, in which the exponent (of predicates) is not cofibred. The idea is then developed to an example, where the predicate lifting for T is not fibred.

intersection.pvs: Intersection of bisimulations and invariants for higher order polynomial functors

This file contains two T-bisimulations and two T-invariants, whoose intersection is not a bisimulation.

relcomp.pvs: Composition of bisimulations

For higher order functors composition of relations does not commute with relation lifting. Here are two conterexamples. Then there is an example, where the composition of two bisimulation is not a bisimulation again.

union.pvs: Union of bisimulations

Define the functor K(Y,X) = Y => A. For this functor,

inv-union.pvs: Union of invariants

This example shows a coalgebra for the functor F from f.pvs to demonstrate that in general invariants are not closed under union and the greatest bisimulation (contained in some predicate) does not exist.

graph.pvs: Graphs of morphisms

For higher order polynomial functors the graph of a morphism need not be a bisimulations. This file shows an example.

kernel.pvs: The Kernel of a morphism

For higher order polynomial functors the kernel of a morphism need not be a bisimulations. This file shows an example.

inv-char.pvs: bisimulation delta* P

For higher order polynomial functors the relation delta * P is not necessarily a bisimulation for an invariant P. Where delta * P = { (x,y) | x = y and P(x)}.

aczel_counter.pvs: Counterexample for the equivalence of Aczel/Mendler and Hermida/Jacobs bisimulation for higher order functors

This file contains two examples, an Aczel/Mendler bisimulation which does not satisfy the requirements of a Hermida/Jacobs bisimulation and vice versa. The examples work with the functor T from file t.pvs.

aczel_counter2.pvs: Counterexample Version II

The same as aczel_counter.pvs, but use functor H(Y,X) = A x ((X => Y) => X), which has no trivial final coalgebra (as T does).

aczel_counter3.pvs: Counterexample Version III

The same as aczel_counter.pvs, but in the version which is in the PhD.

mendler_counter.pvs: Invariance vs. Subcoalgebras

The file contains two examples, clarifying the relation of invariance and subcoalgebras. The first example shows a subcoalgebra, whose state space is not an invariant. The second example shows an invariant for which no subcoalgebra exists. The examples work with the functor T from file t.pvs. Note, that for extended polynomial functors invariants and subcoalgebras coincide.

perlift_counter.pvs: Lattics of partial bisimulation equivalences

This file a coalgebra for the functor K3 from K3.pvs for which there is an infinite chain of bisimulations such that every upper bound of this chain is not a bisimulation.

Automatic type check

all.pvs: Import everything

Use this theory to run all proofs via prove-importchain.

typecheck.el: typecheck everything

To typecheck everything start PVS in this directory and type
M-x load-file typecheck.el

Home Science Overview All Publications Talks PhD CCSL Robin

last modified on 20 Sep 2011 by Hendrik