# Computational Category Theory by D. E. Rydeheard

By D. E. Rydeheard

CONTENTS
========

1 Introduction
1.1 The contents
1.2 Accompanying texts
1.2.1 Textbooks on class theory
1.2.2 ML references and availability
1.2.3 a range of textbooks on sensible programming
1.3 Acknowledgements
2 practical Programming in ML
2.1 Expressions, values and environments
2.2 Functions
2.2.1 Recursive definitions
2.2.2 better order functions
2.3 Types
2.3.1 Primitive types
2.3.2 Compound types
2.3.3 sort abbreviation
2.4 kind polymorphism
2.5 Patterns
2.6 Defining types
2.7 summary types
2.8 Exceptions
2.9 different facilities
2.10 Exercises
3 different types and Functors
3.1 Categories
3.1.1 Diagram chasing
3.1.2 Subcategories, isomorphisms, monics and epis
3.2 Examples
3.2.1 units and finite sets
3.2.2 Graphs
3.2.3 Finite categories
3.2.4 kinfolk and partial orders
3.2.5 Partial orders as categories
3.2.6 Deductive systems
3.2.7 common algebra: phrases, algebras and equations
3.2.8 units with constitution and structure-preserving arrows
3.3 different types computationally
3.4 different types as values
3.4.1 the class of finite sets
3.4.2 phrases and time period substitutions: the class T_tau^Fin
3.4.3 A finite category
3.5 Functors
3.5.1 Functors computationally
3.5.2 Examples
3.6 Duality
3.7 An assessment*
3.8 Conclusion
3.9 Exercises
4 Limits and Colimits
4.1 Definition through universality
4.2 Finite colimits
4.2.1 preliminary objects
4.2.2 Binary coproducts
4.2.3 Coequalizers and pushouts
4.3 Computing colimits
4.4 Graphs, diagrams and colimits
4.5 A normal building of colimits
4.6 Colimits within the classification of finite sets
4.7 A calculation of pushouts
4.8 Duality and limits
4.9 Limits within the type of finite sets
4.10 An software: operations on relations
4.11 Exercises
5 developing Categories
5.1 Comma categories
5.1.1 Representing comma categories
5.2 Colimits in comma categories
5.3 Calculating colimits of graphs
5.4 Functor categories
5.4.1 ordinary transformations
5.4.2 Functor categories
5.5 Colimits in functor categories
5.6 Duality and limits
5.7 summary colimits and limits*
5.7.1 summary diagrams and colimits
5.7.2 classification constructions
5.7.3 listed colimit structures
5.7.4 Discussion
5.8 Exercises
6.3 Examples
6.3.1 flooring and ceiling capabilities: changing genuine numbers to integers
6.3.2 elements of a graph
6.3.3 unfastened algebras
6.3.4 Graph theory
6.3.5 Limits and colimits
6.3.7 Examples from algebra and topology
6.5 loose algebras
6.5.1 developing unfastened algebras
6.5.2 A program
6.5.3 An instance: transitive closure
6.5.4 different structures of unfastened algebras
6.6 Exercises
7 Toposes
7.1 Cartesian closed categories
7.1.1 An instance: the class of finite sets
7.2 Toposes
7.2.1 An instance: the topos of finite sets
7.2.2 Computing in a topos
7.2.3 common sense in a topos
7.2.4 An instance: a three-valued logic
7.3 Conclusion
7.4 Exercises
8 A specific Unification Algorithm
8.1 The unification of terms
8.2 Unification as a coequalizer
8.3 On developing coequalizers
8.4 A specific program
9 developing Theories
9.1 Preliminaries
9.2 developing theories
9.3 Theories and institutions
9.4 Colimits of theories
9.5 Environments
9.6 Semantic operations
9.7 enforcing a specific semantics
10 Formal platforms for classification Theory
10.1 Formal points of classification theory
10.2 classification thought in OBJ
10.3 class concept in a sort theory
10.4 specific information types
A ML Keywords
B Index of ML Functions
C different ML Functions
D solutions to Programming workouts 231

Best logic books

Lectures on Algebraic Model Theory

In recent times, version concept has had notable luck in fixing very important difficulties in addition to in laying off new mild on our realizing of them. the 3 lectures accrued the following current fresh advancements in 3 such parts: Anand Pillay on differential fields, Patrick Speissegger on o-minimality and Matthias Clasen and Matthew Valeriote on tame congruence conception.

Foundations of Computing

Presents an creation to the speculation of computing technology. masking the most components of complexity thought, automata and formal languages in a coherent approach, the textual content additionally covers the theoretical elements of extra utilized parts. The author's strategy is to stimulate scholars' figuring out of the relevance of concept to big program components - for instance, photo processing, communique networks and cryptography are all mentioned.

Compressed Data Structures for Strings: On Searching and Extracting Strings from Compressed Textual Data

Information compression is essential to regulate big datasets, indexing is key to question them. although, their ambitions look as counterposed: the previous goals at minimizing information redundancies, while the latter augments the dataset with auxiliary details to hurry up the question answer. during this monograph we introduce strategies that conquer this dichotomy.

A Boole Anthology: Recent and Classical Studies in the Logic of George Boole

Sleek mathematical common sense wouldn't exist with out the analytical instruments first constructed by means of George Boole within the Mathematical research of good judgment and The legislation of notion. The impact of the Boolean tuition at the improvement of good judgment, regularly regarded yet lengthy underestimated, has lately turn into a tremendous learn subject.

Extra resources for Computational Category Theory

Sample text

Other features of ML are a type-safe reference and assignment facility and a collection of input/output primitives based on streams. 10 Exercises The exercises in this chapter are designed to be done interactively on an ML system. They may, however, be done as pen-and-paper exercises. They follow roughly the order of presentation in the chapter, with some more substantial exercises at the end. Answers to the exercises are given in Appendix D. Exercise 1. Values and environments What values or environments are given by the following ML expressions?

6), sum and maplist (Exercise 5) all have the same general form. This may be explained by the fact that lists form a free monoid. The monoid structure is that of concatenating lists with the empty list as the identity. There is a function h : A → list(A) which returns the singleton list on an element. 10 EXERCISES 33 Given the monoid (B, ∗, e), the map f → f # can be constructed and the construction can be expressed as a program in ML. Representing the target monoid as a pair of a binary function and a constant, write this program.

1 Categories Category theory is founded upon the abstraction of the arrow, f :a→b Here a and b are called objects and f is an arrow whose source is object a and target is object b. Such directional structures occur widely in set theory, algebra, topology and logic. For example, a and b may be sets and f a total function from a to b or, indeed, f may be a partial function from set a to set b; or a and b may be algebras of the same type and f a homomorphism between them; or a and b may be topological spaces and f a continuous map; or, again, a and b may be propositions and f a proof of a b.