David Spivak

Visiting Assistant Professor
University of Oregon
Department of Mathematics

Office: 317 Fenton Hall
Email: dspivak

Winter 2010 -- Informatics Seminar

Meeting time: Tuesday and Thursday at 4pm
Meeting place: 103 Peterson Hall.

What is the mathematics of information?

David Hilbert 1928: "the fundamental idea [of Spivak's Informatics Seminar] is none other than to describe the activity of our understanding, to make a protocol of the rules according to which our thinking actually proceeds."

Purpose of this seminar:

The world is too complex to understand, but aspects of it can be understood. Some things which are understood can be expressed in words, not only for the purpose of mumbling to ourselves but for communicating to others. Let's call anything of this form, anything that can be understood and communicated in words to others, "information."

What is information? What aspects of the world can be fully communicated? It seems that mathematics comes close to being "pure information." Of course, people often define a set to be "a collection" (which is nothing more than a synonym for "a set") -- this is circular. Thus we realize that even sets, the most basic objects of mathematical thought, are not fully defined in mathematics, so math is not really "pure"; it relies on agreement. But perhaps that's fair. Regardless, math certainly comes as close as anything else to being pure information.

Thus, whatever we define information to be, mathematics should be "at home" there. This suggests perhaps that we use mathematics to define information; otherwise, math will always be a foreigner within our definition. Defining information in terms of mathematics may be seen as circular in that math is seen both as a basic kind of information and as a language in which to define information. The implications of this circularity require philosophical analysis, but we may begin to consider information in mathematical terms before having to take on that analysis.

The goal of this seminar is to define a reasonable notion of "information," using mathematics as a foundation and language for the definition. In particular, I will discuss my research in this direction. I began this research with the belief that the most appropriate vantage point from which to view information is category theory. My studies have led me more specifically to topos theory.

While I don't yet have a finished definition, I do have a prototype: an ontology log (or olog) is a topos sketch. In other words, it's a graph together with a set of diagrams that are said to commute, a set of diagrams which are said to be limits, and an object which represents those limits which enforce monomorphism. The topos sketch may also be enriched in the monoidal category of sets of strings. Less formally, an olog is a system of boxes and arrows, each labeled by english text, with some amount of the additional structure guaranteed by the axioms of a topos.

We each have our own olog (which is the situation as we see it, and the language we use to describe it). The name "olog" is short for "ontology log", where ontology is a subject studied both in computer science and philosophy referring to "the way things are." The word olog is supposed to be both reminiscent of "blog" and of the suffix "-ology", meaning the study of something. Ologs are created by studying the way things are and logging it.

The relation of ologs to blogs (weblogs) is that if everyone "ologs" the situation as they see it, and we attempt to connect our ologs together into one big human olog (in the appropriate topos-theoretic way), then we'll have a better understanding of each other's viewpoint on the world. Information will flow between humans more readily and accurately. I imagine a "Facebook" type system where users olog their ideas and lives, and connect them with their friends. Doing so would force us to understand each other. Moreover, computers would be able to "understand" us quite well.

Your job in this course is to understand these ideas, to improve upon them, and to challenge them.

Suggested reading:

1. Lawvere and Schanuel. Conceptual Mathematics: a first introduction to categories. An excellent book. Amazon.com link

2. Lawvere. Taking categories seriously A great 25 page article, including how to think of dynamical systems from a categorical perspective.

3. A short paper on topoi. It is good, but I think that there is at least one medium-sized error; ask me about it some time.

4. Stanford Encyclopedia entry on Information. I personally found sections 2.2 and 3.2.2 particularly relevant.

5. For topoi: Moerdijk and Mac Lane. Sheaves in geometry and Logic: a first introduction to topos theory. Amazon.com link

6. Andreas Blass, Topoi and Computation.

7. Doring and Isham, `What is a thing?': Topos Theory in the Foundations of Physics. Well-written and understandable (at least the first few sections are). This brings home the point that toposes are appropriate for modeling the "real world."

8. Bell, The Development of Categorical Logic. In particular, this discusses the lambda calculus, as well as proving the theorem "every topos is linguistic."

An appropriate amount of work for this class:


See me.

Ideas to consider:

1. Global truth versus local truth. Can something be true only locally? For example, should a pencil be considered "for all time and space, a pencil" or just "for the last 5 days, a pencil".

2. Context. Related to (1), information is always contextual. In other words, we are always looking at information from the viewpoint of a certain audience (e.g. just myself). Given a sensible "change-of-audience" morphism, should we get a change-of-information functor, that takes information from one perspective to information from another? Please consider slice-toposes and change-of-base functors in a topos and see how well they stack up to this idea.

3. Measurements. Suppose we say something has weight 5 lbs. What does that mean? It means that when we put it on a good scale, the scale returns the number 5. (What does it mean that the scale is good?) Does weight, as a function from physical objects to numbers, exist as a stand-alone concept, or should it be considered only as a function from pairs (physical object, scale) to numbers?

4. Objects are like sets? The objects in our ologs are labeled as though they are sets (as one interprets a box labeled "a person" as the set of all persons). Are they? Toposes are categories in which the objects feel like sets, but do not have to be such. Perhaps we should think of objects as moduli spaces instead. See "moduli space" email.

5. Parts of speech. Objects in an olog should be labeled with noun phrases. Morphisms should be labeled with verb phrases. Adjectives are used in noun phrases to suggest subobject-hood. As such, they should suggest a name for the characteristic morphism corresponding to that subobject. Adverbs correspond to subobjects of exponential objects.

6. Two types of info? The Stanford Encyclopedia article made a distinction between information that is instructional (e.g. a computer program) and information that is factual (e.g. like a database). Is that distinction important? How do ologs handle these two types of information?

Creative Commons License
This work by David I. Spivak is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.