Archive for the ‘Category Theory’ Category

Properties of Morphisms

Friday, May 17th, 2013

Properties of Morphisms by Jeremy Kun.

From the post:

This post is mainly mathematical. We left it out of our introduction to categories for brevity, but we should lay these definitions down and some examples before continuing on to universal properties and doing more computation. The reader should feel free to skip this post and return to it later when the words “isomorphism,” “monomorphism,” and “epimorphism” come up again. Perhaps the most important part of this post is the description of an isomorphism.

Isomorphisms, Monomorphisms, and Epimorphisms

Perhaps the most important paradigm shift in category theory is the focus on morphisms as the main object of study. In particular, category theory stipulates that the only knowledge one can gain about an object is in how it relates to other objects. Indeed, this is true in nearly all fields of mathematics: in groups we consider all isomorphic groups to be the same. In topology, homeomorphic spaces are not distinguished. The list goes on. The only way to do determine if two objects are “the same” is by finding a morphism with special properties. Barry Mazur gives a more colorful explanation by considering the meaning of the number 5 in his essay, “When is one thing equal to some other thing?” The point is that categories, more than existing to be a “foundation” for all mathematics as a formal system (though people are working to make such a formal system), exist primarily to “capture the essence” of mathematical discourse, as Mazur puts it. A category defines objects and morphisms, but literally all of the structure of a category lies in its morphisms. And so we study them.

If you are looking for something challenging to read over the weekend, Jeremy’s latest post on morphisms should fit the bill.

The question of “equality” is easy enough to answer as lexical equivalence in UTF-8, but what if you need something more?

Being mindful that “lexical equivalence in UTF-8″ is a highly unreliable form of “equality.”

Jeremy is easing us down the road where such discussions can happen with a great deal of rigor.

Posted in Category Theory, Mathematical Reasoning, Mathematics | No Comments »

Categories as Types

Monday, May 6th, 2013

Categories as Types by Jeremy Kun.

From the post:

In this post we’ll get a quick look at two ways to define a category as a type in ML. The first way will be completely trivial: we’ll just write it as a tuple of functions. The second will involve the terribly-named “functor” expression in ML, which allows one to give a bit more structure on data types.

Jeremy gets us closer to application of category theory to programming with an introduction to types.

Posted in Category Theory, Mathematics | No Comments »

Introducing Categories

Friday, April 26th, 2013

Introducing Categories by Jeremy Kun.

From the post:

It is time for us to formally define what a category is, to see a wealth of examples. In our next post we’ll see how the definitions laid out here translate to programming constructs. As we’ve said in our soft motivational post on categories, the point of category theory is to organize mathematical structures across various disciplines into a unified language. As such, most of this post will be devote to laying down the definition of a category and the associated notation. We will be as clear as possible to avoid a notational barrier for newcomers, so if anything is unclear we will clarify it in the comments.

Definition of a Category

Let’s recall some examples of categories we’ve seen on this blog that serve to motivate the abstract definition of a category. We expect the reader to be comfortable with sets, and to absorb or glaze over the other examples as comfort dictates. The reader who is uncomfortable with sets and functions on sets should stop here. Instead, visit our primers on proof techniques, which doubles as a primer on set theory (or our terser primer on set theory from a two years ago).

The go-to example of a category is that of sets: sets together with functions between sets form a category. We will state exactly what this means momentarily, but first some examples of categories of “sets with structure” and “structure-preserving maps.”

Not easy but not as difficult as some introductions to category theory.

Jeremy promises that the very next post jumps into code to show the “definition of a category as a type in ML.”

Plus some pro’s and con’s on proceeding this way.

Posted in Category Theory, Mathematics | No Comments »

Categories, What’s the Point?

Wednesday, April 17th, 2013

Categories, What’s the Point? by Jeremy Kun.

From the post:

Perhaps primarily due to the prominence of monads in the Haskell programming language, programmers are often curious about category theory. Proponents of Haskell and other functional languages can put category-theoretic concepts on a pedestal or in a mexican restaurant, and their benefits can seem as mysterious as they are magical. For instance, the most common use of a monad in Haskell is to simulate the mutation of immutable data. Others include suspending and backtracking computations, and even untying tangled rope.

Category theory is often mocked (or praised) as the be-all and end-all of mathematical abstraction, and as such (and for other reasons I’ve explored on this blog) many have found it difficult to digest and impossible to master. However, in truth category theory arose from a need for organizing mathematical ideas based on their shared structure. In this post, I want to give a brief overview of what purpose category theory serves within mathematics, and emphasize what direction we’ll be going with it on this blog.

We should also note (writing this after the fact), that this article is meant to be a motivation to our future series on category theory. It is very difficult to explain what category theory is without going into very specific details, but we can explain by analogy what category theory achieves for us. That is the goal of this post.

I rather like the line:

However, in truth category theory arose from a need for organizing mathematical ideas based on their shared structure.

Which is one of the reasons why I keep trying to master category theory, for the ability to organize subject identifications based on their shared structures.

Not necessary for all subject identity cases but if topic maps extend into subjects like math, physics, etc., then it may be quite useful.

Posted in Category Theory, Mathematics | No Comments »

SQL, NoSQL =? CoSQL? Category Theory to the Rescue

Wednesday, January 30th, 2013

A co-Relational Model of Data for Large Shared Data Banks by Erik Meijer and Gavin Bierman.

I missed this when it appeared in March of 2011.

From the conclusion:

The nascent noSQL market is extremely fragmented, with many competing vendors and technologies. Programming, deploying, and managing noSQL solutions requires specialized and low-level knowledge that does not easily carry over from one vendor’s product to another.

A necessary condition for the network effect to take off in the noSQL database market is the availability of a common abstract mathematical data model and an associated query language for noSQL that removes product differentiation at the logical level and instead shifts competition to the physical and operational level. The availability of such a common mathematical underpinning of all major noSQL databases can provide enough critical mass to convince businesses, developers, educational institutions, etc. to invest in noSQL.

In this article we developed a mathematical data model for the most common form of noSQL—namely, key-value stores as the mathematical dual of SQL’s foreign-/primary-key stores. Because of this deep and beautiful connection, we propose changing the name of noSQL to coSQL. Moreover, we show that monads and monad comprehensions (i.e., LINQ) provide a common query mechanism for both SQL and coSQL and that many of the strengths and weaknesses of SQL and coSQL naturally follow from the mathematics.

The ACM Digital Library reports only 3 citations, which is unfortunate for such an interesting proposal.

I have heard about key/value pairs somewhere else. I will have to think about that and get back to you. (Hint for the uninitiated, try the Topic Maps Reference Model (TMRM). A new draft of the TMRM is due to appear in a week or so.)

Posted in Category Theory, Database, NoSQL, SQL, TMRM | No Comments »

ALGEBRA, Chapter 0

Wednesday, November 21st, 2012

ALGEBRA, Chapter 0 by Paolo Aluffi. (PDF)

From the introduction:

This text presents an introduction to algebra suitable for upper-level undergraduate or beginning graduate courses. While there is a very extensive offering of textbooks at this level, in my experience teaching this material I have invariably felt the need for a self-contained text that would start ‘from zero’ (in the sense of not assuming that the reader has had substantial previous exposure to the subject), but impart from the very beginning a rather modern, categorically-minded viewpoint, and aim at reaching a good level of depth. Many textbooks in algebra satisfy brilliantly some, but not all of these requirements. This book is my attempt at providing a working alternative.

There is a widespread perception that categories should be avoided at first blush, that the abstract language of categories should not be introduced until a student has toiled for a few semesters through example-driven illustrations of the nature of a subject like algebra. According to this viewpoint, categories are only tangentially relevant to the main topics covered in a beginning course, so they can simply be mentioned occasionally for the general edification of a reader, who will in time learn about them (by osmosis?). Paraphrasing a reviewer of a draft of the present text, ‘Discussions of categories at this level are the reason why God created appendices’.

It will be clear from a cursory glance at the table of contents that I think otherwise. In this text, categories are introduced around p. 20, after a scant reminder of the basic language of naive set theory, for the main purpose of providing a context for universal properties. These are in turn evoked constantly as basic definitions are introduced. The word ‘universal’ appears at least 100 times in the first three chapters.

If you are interested in a category theory based introduction to algebra, this may be the text for you. Suitable (according to the author) for use in a classroom or for self-study.

The ability to reason carefully, about what we imagine is known, should not be underestimated.

I first saw this in a tweet from Algebra Fact.

Posted in Algebra, Category Theory, Mathematics | No Comments »

Polarity in Type Theory

Saturday, August 25th, 2012

Polarity in Type Theory by Robert Harper.

From the post:

There has recently arisen some misguided claims about a supposed opposition between functional and object-oriented programming. The claims amount to a belated recognition of a fundamental structure in type theory first elucidated by Jean-Marc Andreoli, and developed in depth by Jean-Yves Girard in the context of logic, and by Paul Blain-Levy and Noam Zeilberger in the context of programming languages. In keeping with the general principle of computational trinitarianism, the concept of polarization has meaning in proof theory, category theory, and type theory, a sure sign of its fundamental importance.

Polarization is not an issue of language design, it is an issue of type structure. The main idea is that types may be classified as being positive or negative, with the positive being characterized by their structure and the negative being characterized by their behavior. In a sufficiently rich type system one may consider, and make effective use of, both positive and negative types. There is nothing remarkable or revolutionary about this, and, truly, there is nothing really new about it, other than the terminology. But through the efforts of the above-mentioned researchers, and others, we have learned quite a lot about the importance of polarization in logic, languages, and semantics. I find it particularly remarkable that Andreoli’s work on proof search turned out to also be of deep significance for programming languages. This connection was developed and extended by Zeilberger, on whose dissertation I am basing this post.

The simplest and most direct way to illustrate the ideas is to consider the product type, which corresponds to conjunction in logic. There are two possible ways that one can formulate the rules for the product type that from the point of view of inhabitation are completely equivalent, but from the point of view of computation are quite distinct. Let us first state them as rules of logic, then equip these rules with proof terms so that we may study their operational behavior. For the time being I will refer to these as Method 1 and Method 2, but after we examine them more carefully, we will find more descriptive names for them.

Best read in the morning with a fresh cup of coffee (or whenever you do your best work).

Can’t talk about equivalence without types. (Well, not interchangeably.)

Posted in Category Theory, Types | No Comments »

Category Theory

Thursday, August 2nd, 2012

Category Theory by Steve Awodey.

While writing up my earlier post on category theory I encountered this Summer, 2011 course page:

Description:

Category theory, a branch of abstract algebra, has found many applications in mathematics, logic, and computer science. Like such fields as elementary logic and set theory, category theory provides a basic conceptual apparatus and a collection of formal methods useful for addressing certain kinds of commonly occurring formal and informal problems, particularly those involving structural and functional considerations. This course is intended to acquaint students with these methods, and also to encourage them to reflect on the interrelations between category theory and the other basic formal disciplines.

There is an extensive set of course notes and homework problem sets.

Posted in Category Theory | No Comments »

Does category theory make you a better programmer?

Thursday, August 2nd, 2012

Does category theory make you a better programmer? by Debasish Ghosh.

From the post:

How much of category theory knowledge should a working programmer have ? I guess this depends on what kind of language the programmer uses in his daily life. Given the proliferation of functional languages today, specifically typed functional languages (Haskell, Scala etc.) that embeds the typed lambda calculus in some form or the other, the question looks relevant to me. And apparently to a few others as well. In one of his courses on Category Theory, Graham Hutton mentioned the following points when talking about the usefulness of the theory :

  • Building bridges—exploring relationships between various mathematical objects, e.g., Products and Function
  • Unifying ideas – abstracting from unnecessary details to give general definitions and results, e.g., Functors
  • High level language – focusing on how things behave rather than what their implementation details are e.g. specification vs implementation
  • Type safety – using types to ensure that things are combined only in sensible ways e.g. (f: A -> B g: B -> C) => (g o f: A -> C)
  • Equational proofs—performing proofs in a purely equational style of reasoning

Many of the above points can be related to the experience that we encounter while programming in a functional language today. We use Product and Sum types, we use Functors to abstract our computation, we marry types together to encode domain logic within the structures that we build and many of us use equational reasoning to optimize algorithms and data structures.

But how much do we need to care about how category theory models these structures and how that model maps to the ones that we use in our programming model ?

Read the post for Debasish’s answer for programmers.

For topic map authors, remember category theory began as an effort to find commonalities between abstract mathematical structures.

Commonalities? That sounds a lot like subject sameness doesn’t it?

With category theory you can describe, model, uncover commonalities in mathematical structures and commonalities in other areas as well.

A two for one as it were. Sounds worthwhile to me.

I first saw this at DZone.

Posted in Category Theory, Modeling | No Comments »

Categorial Compositionality:….

Wednesday, September 7th, 2011

Categorial Compositionality: A Category Theory Explanation for the Systematicity of Human Cognition

Abstract:

Classical and Connectionist theories of cognitive architecture seek to explain systematicity (i.e., the property of human cognition whereby cognitive capacity comes in groups of related behaviours) as a consequence of syntactically and functionally compositional representations, respectively. However, both theories depend on ad hoc assumptions to exclude specific instances of these forms of compositionality (e.g. grammars, networks) that do not account for systematicity. By analogy with the Ptolemaic (i.e. geocentric) theory of planetary motion, although either theory can be made to be consistent with the data, both nonetheless fail to fully explain it. Category theory, a branch of mathematics, provides an alternative explanation based on the formal concept of adjunction, which relates a pair of structure-preserving maps, called functors. A functor generalizes the notion of a map between representational states to include a map between state transformations (or processes). In a formal sense, systematicity is a necessary consequence of a higher-order theory of cognitive architecture, in contrast to the first-order theories derived from Classicism or Connectionism. Category theory offers a re-conceptualization for cognitive science, analogous to the one that Copernicus provided for astronomy, where representational states are no longer the center of the cognitive universe—replaced by the relationships between the maps that transform them.

Categorial Compositionality II: Universal Constructions and a General Theory of (Quasi-)Systematicity in Human Cognition

Abstract:

A complete theory of cognitive architecture (i.e., the basic processes and modes of composition that together constitute cognitive behaviour) must explain the systematicity property—why our cognitive capacities are organized into particular groups of capacities, rather than some other, arbitrary collection. The classical account supposes: (1) syntactically compositional representations; and (2) processes that are sensitive to—compatible with—their structure. Classical compositionality, however, does not explain why these two components must be compatible; they are only compatible by the ad hoc assumption (convention) of employing the same mode of (concatenative) compositionality (e.g., prefix/postfix, where a relation symbol is always prepended/appended to the symbols for the related entities). Architectures employing mixed modes do not support systematicity. Recently, we proposed an alternative explanation without ad hoc assumptions, using category theory. Here, we extend our explanation to domains that are quasi-systematic (e.g., aspects of most languages), where the domain includes some but not all possible combinations of constituents. The central category-theoretic construct is an adjunction involving pullbacks, where the primary focus is on the relationship between processes modelled as functors, rather than the representations. A functor is a structure-preserving map (or construction, for our purposes). An adjunction guarantees that the only pairings of functors are the systematic ones. Thus, (quasi-)systematicity is a necessary consequence of a categorial cognitive architecture whose basic processes are functors that participate in adjunctions.

“Copernican revolution” may be a bit strong but these are interesting articles.

I am more sympathetic to the discussion of the short-falls of first-order theories than I am to their replacement with other theories. Although theories can make for entertaining reading.

Posted in Category Theory, Human Cognition | No Comments »

Semantic Integration in the IFF

Sunday, September 4th, 2011

Semantic Integration in the IFF by Robert E. Kent

Abstract:

The IEEE P1600.1 Standard Upper Ontology (SUO) project aims to specify an upper ontology that will provide a structure and a set of general concepts upon which domain ontologies could be constructed. The Information Flow Framework (IFF), which is being developed under the auspices of the SUO Working Group, represents the structural aspect of the SUO. The IFF is based on category theory. Semantic integration of object-level ontologies in the IFF is represented with its fusion construction. The IFF maintains ontologies using powerful composition primitives, which includes the fusion construction.

Comments: Presented at the Semantic Integration Workshop of the 2nd International Semantic Web Conference (ISWC2003), Sanibel Island, Florida, October 20, 2003.

IFF = Information Flow Framework. From, Barwise, Jon and Jerry Seligman. Information Flow: The Logic of Distributed Systems. Cambridge Tracts in Theoretical Computer Science 44. Cambridge University Press. 1997.

Historical document at this point but interesting none the less. Describes a category theory view of semantic integration.

Posted in Category Theory, Ontology | No Comments »

Category Theory (eBooks)

Tuesday, June 21st, 2011

Category Theory (eBooks)

A nice collection of pointers to eBooks on category theory for the most part.

Posted in Category Theory | No Comments »

An introduction to Category Theory for Software Engineers

Thursday, June 2nd, 2011

An introduction to Category Theory for Software Engineers

Dr. Steve Easterbrook of University of Toronto introduces category theory and covers these topics:

  • What is Category Theory?
  • Why should we be interested in Category Theory?
  • How much Category Theory is it useful to know?
  • What kinds of things can you do with Category Theory in Software Engineering?
  • Does Category Theory help us to automate things? (for the ASE audience)

One of the more approachable introductions/overviews of category theory that I have seen.

Posted in Category Theory, Software | No Comments »

The Catsters’ Category Theory Videos

Wednesday, March 30th, 2011

The Catsters’ Category Theory Videos

Courtesy of Edsko de Vries:

Eugenia Cheng and Simon Willerton of the University of Sheffield, a.k.a. The Catsters, have an excellent series of lectures on category theory on YouTube. The only thing missing is some overview of the lectures, which I have provided below. A graphical overview is available too.

I don’t recall ever seeing anyone lecture so excitedly about math. The lectures are not only enjoyable but the enthusiasm is strangely infectious.

Posted in Category Theory | No Comments »

Good Math, Bad Math – Category Theory

Monday, March 28th, 2011

Good Math, Bath Math – Category Theory

A series of posts on category theory.

Posted in Category Theory | No Comments »

Category Theory for the Java Programmer

Sunday, March 27th, 2011

Category Theory for the Java Programmer

From the post:

There are several good introductions to category theory, each written for a different audience. However, I have never seen one aimed at someone trained as a programmer rather than as a computer scientist or as a mathematician. There are programming languages that have been designed with category theory in mind, such as Haskell, OCaml, and others; however, they are not typically taught in undergraduate programming courses. Java, on the other hand, is often used as an introductory language; while it was not designed with category theory in mind, there is a lot of category theory that passes over directly.

I’ll start with a sentence that says exactly what the relation is of category theory to Java programming; however, it’s loaded with category theory jargon, so I’ll need to explain each part.

A collection of Java interfaces is the free3 cartesian4 category2 with equalizers5 on the interface6 objects1 and the built-in7 objects.

Interested?

Posted in Category Theory, Java | No Comments »

Computational Category Theory

Wednesday, March 23rd, 2011

Computational Category Theory

Published in 1990 by D.E. Rydeheard and R.M. Burstall, Computational Category Theory uses ML to illustrate the relevance of category theory to CS.

Posted in Category Theory | No Comments »

Introduction to Categories and Categorical Logic

Wednesday, February 16th, 2011

Introduction to Categories and Categorical Logic by Samson Abramsky and Nikos Tzevelekos.

Category theory is important for theoretical CS and I suspect should skilled explanations come along, CS practice as well.

From the preface:

The aim of these notes is to provide a succinct, accessible introduction to some of the basic ideas of category theory and categorical logic. The notes are based on a lecture course given at Oxford over the past few years. They contain numerous exercises, and hopefully will prove useful for self-study by those seeking a first introduction to the subject, with fairly minimal prerequisites. The coverage is by no means comprehensive, but should provide a good basis for further study; a guide to further reading is included.

The main prerequisite is a basic familiarity with the elements of discrete mathematics: sets, relations and functions. An Appendix contains a summary of what we will need, and it may be useful to review this first. In addition, some prior exposure to abstract algebra—vector spaces and linear maps, or groups and group homomorphisms—would be helpful.

Under further reading, F. Lawvere and S. Schanuel, Conceptual Mathematics: A First Introduction to Categories, Cambridge University Press, 1997, is described by the authors as “idiosyncratic.” Perhaps so but I found it to be a useful introduction.

Posted in Category Theory | No Comments »

Applicatives are generalized functors

Monday, January 31st, 2011

Applicatives are generalized functors

A continuation of Heiko Seeberger’s coverage of Scala and category theory.

Highly recommended.

Posted in Category Theory, Scala | No Comments »

Quantum Mechanics of Topic Maps

Wednesday, January 19th, 2011

I ran across Alfred Korzybski’s dictum “…the map is not the territory…” the other day.

I’ve repeated it and have heard others repeat it.

Not to mention it being quoted in any number of books on mapping and mapping technologies.

It’s a natural distinction, between the artifact of a map and the territory it is mapping.

But it is important to note that Korzbski did not say “…a map cannot be a territory….”

Like the wave/particle duality in quantum mechanics, maps can be maps or they can be territories.

Depends upon the purpose with which we are viewing them.

A rather wicked observer effect that changes the formal properties of a map vis-a-vis a territory to being the properties of a territory vis-a-vis a map.

Maps (that is syntaxes/data models) try to avoid that observer effect by proclaiming themselves to be the best possible of all possible maps in the traditional of Dr. Pangloss.

They may be the best map for some situation, but they remain subject to being viewed as a territory, should the occasion arise.

(If that sounds like category theory to you, give yourself a gold star.)

The map-as-territory principle is what enables the viewing of subject representatives in different maps as representatives of the same subjects.

Otherwise, we must await the arrival of the universal mapping strategy.

It is due to arrive on the same train as the universal subject identifier for all subjects, for all situations and time periods.

Posted in Category Theory, Mapping, Maps, Topic Maps | No Comments »

Computable Category Theory

Sunday, November 28th, 2010

Computable Category Theory

From the Preface (in the book):

This book should be helpful to computer scientists wishing to understand the computational significance of theorems in category theory and the constructions carried out in their proofs. Specialists in programming languages should be interested in the use of a functional programming language in this novel domain of application, particularly in the way in which the structure of programs is inherited from that of the mathematics. It should also be of interest to mathematicians familiar with category theory – they may not be aware of the computational significance of the constructions arising in categorical proofs.

In general, we are engaged in a bridge-building exercise between category theory and computer programming. Our efforts are a first attempt at connecting the abstract mathematics with concrete programs, whereas others have applied categorical ideas to the theory of computation.

Website has a pdf of a book by the same title and source code for programs.

This may not be useful for the “meatball” semantics of everyday practice, developing tools for use in the design information systems is another matter.

Questions:

  1. Suggest updated works for each section in “Accompanying Texts.”
  2. Annotated bibliography of works listed in #1.
  3. Instances of use of category theory in library science? Should there be? (3-5 pages, citations)

Posted in Category Theory | No Comments »

Introduction to Category Theory in Scala

Saturday, November 27th, 2010

Introduction to Category Theory in Scala.

Jack Park and I have been bouncing posts about category theory resources off of each other for years.

This one looks like a keeper.

It may be the sort of series that acts as a bridge between an abstraction (category theory) and the real world of programming.

They are related you know.

Posted in Category Theory, Scala | 1 Comment »