Project topics and materials
Get Complete Project Material File(s) Now! »
Links between limits and their special cases
All four of them are crucial in category theory, and in the study of limits and colimits, because they are the basic bricks with which we build limits and colimits. Let C be any category. The following propositions are equivalent:
1. C has finite products and equalisers.
2. C has pullbacks and a terminal object.
3. C has finite limits.
Of course, the dual theorem is also true: Let C be any category. The following propositions are equivalent:
1. C has finite coproducts and coequalisers.
2. C has pushouts and an initial object.
3. C has finite colimits.
The proof of this theorem is a long, long run, and most lemmas it requires will not be used afterwards. Here, we give the proof of only one of them, because it will be used to build limits and colimits in Sets in the next section and use that expression in Chapter 4.
If C has small products and equalisers, then C has small limits. This lemma is about small products/limits, but the same lemma with small replaced by finite also holds and may be used as a lemma to Theorem 2.4.38. However we need this lemma for small limits. Proof. (The proof written here is a resolution of [25, Exercise 3, Section 2.13, Chapter 9]) We will start the proof with one special case of index category. We then give a hint for a second special case. Those two proofs are given just as an exemplification of the general case that we detail right after.
Background on boxes and wiring diagrams
We will now apply the categorical framework to build discrete systems. Our approach is different from the one in [32]. The dynamical systems presented here are defined as a generalisation of automata whose input and output spaces are predetermined. We will define a category of lists, a category of boxes, and diverse operations on them.
In this section, C will be any category with finite products (typically Sets). Most of the following notions were already defined in [19]; we only recall them without proving their properties. We also give examples in order to help for comprehension.
The category of typed finite sets
Before defining proper boxes, we need to define the notion of input and output ports. These will eventually be the sides of our boxes. Definition 3.2.1 (Category of C -typed finite sets [19]) The category TFSC of C -typed finite sets is defined as follows:Objects: An object is any pair (P, ) such that P is a finite set and P ObC is a function Morphisms: A morphism from (P, ) to (P, ) is a function P P such that = X Identities: The identity morphism on (P, ) is the identity function of the set P Composition: The composition of morphisms is the usual composition of functions An object in TFSC is called a C -typed finite set; a morphism in TFSC is called a C -typed function. We can rewrite a C -typed finite set (P, ) as the finite sequence ` (p0), . . . , (pn−1)e where P = {p0, . . . , pn−1}. A C -typed finite set is simply a list of objects in C , indexed by a finite set P. If C = Sets, a Sets-typed finite set is a list of sets. A C -typed function (P, ) (P, ) can be then seen as a means to obtain the former list ` (p0), . . . , (pn−1)e from the latter list ` (p0), . . . , (pn−1)e, by reordering, duplicating or even ignoring its elements. As = X , the list ` (p0), . . . , (pn−1)e can be rewritten ` ( (p0)) , . . . , ( (pn−1))e. Beware of the inversion: goes from (P, ) to (P, ) and we see it as a transformation of the list (P, ) into the list (P, ).
Monoidal structure of the category of boxes
The category WC has a monoidal structure for the parallel composition of boxes, that corresponds to the intuitive idea of parallelising boxes. Definition 3.2.16 (Parallel composition of boxes [19]).
Let X = (Xin,Xout) and Y = (Y in, Y out) be two C -boxes. The parallel composition, or sum, of X and Y , denoted X t Y , is the box XtY = (Xin + Y in,Xout + Y out), where + is the sum of C -typed finite sets (cf. Definition 3.2.3). The parallel composition of two C -boxes summarises to the concatenation of both input ports, and both output ports.
An internal equivalence relation on dynamical systems
The relation defined above does not give any information on the links between two discrete systems that are equivalent as stream transducers. In this subsection, we define another equivalence relation that provides an internal point of view. We then prove that the two equivalence relations are the same.
A priori, the simulation relation does not relate the output of the two discrete systems F and G (though this does follow; see Lemma 3.3.19); it only declares a correspondence between both their state sets and update and readout functions. Both discrete systems can work in parallel; their state sets need not be the same, nor even of the same cardinality, but they somehow coordinate via the map . The function draws the parallel between the internal machinery of F and that of G. For the rest of the chapter, we will be more interested in the simulation relation F Ø G than any particular simulation function witnessing it: any one will do. Remark 3.3.15. Definition 3.3.14 refers to the existence of morphisms between two automata as described in the automata theory litterature [34]. The existence of such morphisms suffices for our purposes. We are a bit more restrictive here, as the outputs need to be the same in both automata, while in the usual definition of morphisms, automata can have different output alphabets, as long as there is a function to convert one output into the other.
Table of contents :
Acknowledgement
Abstract
Résumé long
I Introduction and a warm welcome to category theory
1 Introduction
1.1 Context
1.2 Dynamical systems
1.3 Multiplicity and clusters
1.4 Contributions
2 A mere crash course on category theory
2.1 Introduction
2.2 Basic notions
2.3 Monoidal categories
2.4 Your only colimit is yourself
2.4.1 Basics
2.4.2 Initial object, terminal object
2.4.3 Products and coproducts
2.4.4 Equalisers and coequalisers
2.4.5 Pullbacks and pushouts
2.4.6 Links between limits and their special cases
2.4.7 Explicit computation in Sets
II Dynamical systems
3 Dynamical systems
3.1 Introduction
3.2 Background on boxes and wiring diagrams
3.2.1 The category of typed finite sets
3.2.2 Dependent products
3.2.3 The category of boxes and wiring diagrams
3.2.4 Monoidal structure of the category of boxes
3.2.5 Dependent product of boxes
3.3 Discrete systems and their equivalences
3.3.1 Definition and basic properties
3.3.2 An external equivalence relation on dynamical systems
3.3.3 An internal equivalence relation on dynamical systems
3.4 Main results
3.4.1 Algebras and closures
3.4.2 Memoryless systems
3.4.3 Finite-state systems
3.5 Conclusion
III Clusters and multiplicity
4 Mais dis-moi Jamy, c’est quoi un cluster ?
4.1 Introduction
4.2 Detour by connected components
4.3 Grothendieck’s legacy
4.3.1 Introduction to ind-categories
4.3.2 Explicit computation
4.3.3 A natural isomorphism
4.4 Descriptive definitions of clusters
4.5 Pro-categories and ind-categories
4.5.1 Pro-categories as dual to ind-categories
4.5.2 A natural isomorphism
4.6 Clusters as functors, clusters as functions
4.6.1 Clusters as functors
4.6.2 Discussion about the cardinality of clusters
4.7 Conclusion
5 Construction of clusters
5.1 Introduction
5.2 Generating clusters from the full protocluster
5.3 When is there no cluster at all?
5.3.1 A quest of compatibility
5.3.2 A first attempt – Very Weak CCCT
5.3.3 Second attempt – Weak CCCT
5.3.4 Third attempt – Transfinite recursion in a transfinite algorithm
5.3.5 More properties and an example
5.4 The special case of preorders
5.5 Conclusion
6 Das Multiplizitätsprinzip in Quasiordnungen
6.1 Introduction
6.2 Background
6.3 A characterisation of preorders with Multiplicity
6.4 Other examples of multiplicity
6.4.1 Example of MP by (sMP-2)
6.4.2 Preorder on the ordinals
6.4.3 Can a total order verify strict MP?
6.4.4 Non-standard models of Peano
6.5 Conclusion
7 Multiplicity in tests
7.1 Introduction
7.2 Multiplicity Principle
7.3 Statistical detection of a signal in noise
7.3.1 Problem statement
7.3.2 Decision with level > [0, 1] and oracles
7.3.3 Observations
7.4 Selectivity, landscapes of tests and preordering
7.5 The Neyman-Pearson (NP) solution
7.6 The RDT solution
7.6.1 An elementary RDT problem
7.6.2 Application to detection
7.7 Multiplicity Principle
7.8 MP in a slightly different preorder
7.9 Conclusions and Perspectives
IV Conclusion
8 Conclusion
8.1 Summary
8.2 Contributions
8.3 Perspectives
