Tuesday, November 13, 2012

Conceptual Quicksand:
Vagueness, Topology, and Mereology
An Experiment in Bio-Biblio-Geographic Writing

An introduction to my forthcoming book, Cartography in the Age of Computer Simulation: lectures on the conceptual and topological foundations of GIS

It is obvious that an imagined world, however different it may be from the real one, must have something—a form in common with it.
--Ludwig Wittgestein,
Tractatus Logico-philosophicus

It all begins for me in a bookstore. I can still remember the day that I became interested in the underlying topology of space. I was in graduate school, a physics student, so it was not geographic space that first held my interest, but rather, space in the abstract and purely mathematical sense. A new book called 300 Years of Gravitation had just come out celebrating the publication of Newton's Principia Mathematica. I picked up the book while in the Princeton University Bookstore, and when I opened it, all that I can remember seeing is a series of illustrations that showed something called Everett Branching Space-time. I had never seen diagrams like this before.

The branching of space-time into different possible worlds made such an impression on me that I can still, more than 25 years distant, draw them from memory.  As it turns out they were part of a radical re-thinking of the mathematics of space-time by Hugh Everett, called the relative-state formulation, which is based on what has become known as the many-worlds interpretation and lots of topology.

Although I never looked into the Everett diagrams any further, topology came to be my main subject of study and over the next three years I devoured the classic works on the subject. In particular, Felix Hausdorff’s Set Theory and Nicolas Bourbaki’s General Topology became my close friends, as I started spending more time in mathematics than in physics departments. Topology, especially in its algebraic form, would later become quite important to me in my geographic work and can be formally defined as the study of qualitative properties of certain objects, called topological spaces that are invariant under a certain kinds of transformations.  I have written about the intersection of some of the classic theorems like the Brouwer Fixed Point and the Borsuk-Ulam Theorem and geographical problems. (see my paper How to Map a Sandwich: Surfaces, Topological Existence Theorems and the Changing Nature of Modern Thematic Cartography, 1966-1972)

Most of these have to do with applications in which the properties that we are interested in are invariant under a certain kind of equivalences, called homeomorphisms. To put it quite simply, for geographic purposes, topology is the study of the continuity and connectivity of continuous fields, networks and discrete objects.

Years later the same sort of questions brought up by the Everett diagrams and of the many-worlds interpretation came back into my thinking through a seminar with David Lewis, which concentrated on his theory of modal realism. Modal realism also deals with questions surrounding the plurality of worlds, although from a much more logical and less mathematical perspective. Of all the professors that I have had the pleasure of learning from it was Lewis who had the most profound effect on me. Lewis was a mathematical and philosophical renegade, and although firmly part of academia, was always putting forth new ideas that pushed the limits.

Today I still re-read his four books, On the Plurality of Worlds, Counterfactuals, Convention, Parts of Classes and his essays almost yearly, as the depth of their insights is boundless. I always think of cartography, at least in its modern computer incarnation, as a theory of possible worlds; a place where counter-factual simulations can be carried out. My own sense is that the actual maps that exist are but a tiny subset of the theoretical maps that could exist. These real maps are products of a very small number of trajectories through cartographic space, each with its own unique place in this mathematical construction. Every real map is surrounded by a tiny cluster of real or unreal neighbors who are its ancestors and descendants. Sorting out the real from the unreal is the purpose of geographic analysis.

Even though it is not directly applicable to geography and cartography my interactions with the mathematician Saul Kripke would be decisive for what I would spend many years engaged in reading. Kripke, while at Princeton, gave a series of seminars on Gödel’s Theorems which have become infamous for not only their density but also for their stunning originality. Saul Kripke is one of those creative geniuses who only come along once in a person’s lifetime. He became a professor at MIT while still an undergraduate at Harvard. His published writings are few and difficult to understand, and his lectures are even more so. Most of what he has written circulates around the mathematical logic community in manuscript.

Kripke’s seminar concentrated on how in 1931, the young Kurt Gödel single handedly changed the face of mathematics through his proof that its basic foundations could not be derived from the axioms of logic alone. Gödel’s theorems are simple in their conclusions but the insights that Gödel needed to have in order to prove them are the stuff of any mathematician’s dreams. Gödel’s first incompleteness theorem continues to fascinate me and I try to keep up on anything written about it, as it has deep implications for the foundations of computation and the development of algorithms. The idea that it is wrong to think that the perfectly natural notion that we can completely axiomatize simple arithmetic, still seems strange and otherworldly in my mind.

In studying Gödel’s work Kripke found several alternate proofs, and his lectures and unpublished manuscript, ‘Non-Standard Models and Gödel's Theorem: A Model-Theoretic Proof of Gödel's Theorem,’ have circulated widely in manuscript form. So widely in fact, that the philosopher of science Hilary Putnam felt it necessary to publish a summary of the article in 2000. Putnam showed that while today we know purely algebraic techniques that could be used to show the same thing, Kripke actually used techniques to establish incompleteness that could have, in principle, been understood by nineteenth-century mathematicians. This kind of thing, at least to me, is truly beautiful stuff. It is this kind of retrograde analysis that makes looking back at the history of geographic analysis so rewarding.

To get back geography, it was Lewis, who first introduced me to the subject of mereology that is such a large part of my book on the foundations of GIS. Lewis, in Parts of Classes, sets out to provide a mereological foundation for the richer and more abstract field of classes found in set theory. Mereology in Lewis’ sense is simply a formal and mathematical theory that tries to discern general principles regarding the relationships of parts and wholes that provide the starting point for most of pure mathematics. When first approaching these ideas this level of abstraction may seem to have little relationship to cartography, but in fact it is critically important to the foundations of modern GIS and mapmaking, as these activities take place within an algorithmic and mereotopological formal framework.

In a Geographic Information System we are worried about keeping track of different kinds of objects and fields that inhabit our lived space and that have different dimensional and topological structure. So for example we have zero-dimensional points for cities, one-dimensional lines for roads and other networks,  two-dimensional polygons for regions and territories, three-dimensional spaces for the earth itself, and four-dimensional space-time structures when we add in temporality. As we build in other thematic forms of data we add continuous fields into the mix. (for more on topology of GIS see the ERSI White Paper, GIS Topology )

To keep track of all this in a computer is quite different from the drawing of lines of traditional cartography. We need to know deep mathematical things about the world’s spatial structure, like the overlap of roads with regions, the temporal extent of events and how boundaries are spatially related to the regions they bound. It might have been Nick Chrisman in his insightful article from 1978 called, ‘Concepts of Space as a Guide to Cartographic Data Structures,’ who first pointed out the deep conceptual connections between the mathematical structure of space and the data structures of computer mapping. Today cartography is at its base mereological and is much different from its former printed incarnation. These foundations have both profound mathematical and philosophical import that is just beginning to be sorted out by people like me who are interested in such problems.

Another one of the biggest influences on my thinking about geographical mereology is Achilles Varzi, professor of philosophy at Columbia University. Varzi’s two books, Holes and other Superficialities and Parts and Places: the structures of spatial representation treat in great detail the various formal and mathematical systems of mereology and topology.

In his books and papers Varzi gives the various formalizations and discusses logical structure of each of these systems and their philosophical import. One of the deepest conclusions of mereology is that there can be, just like in geometry, a large group of different axiom systems, which are all consistent with each other.  The important thing proposed by Varzi, in examining these various systems, is that none of them is alone strong enough axiomatically and logically to contain a full theory of spatial objects. It is here that topology comes into play and provides the link to a full formal theory of GIS, something he calls mereotopology. (for more on this see Casati and Varzi, Ontological Tools for Geographic Representation)

Varzi, in a long discussion we once had about the mathematics books that had been most important to us, once told me that if he was stranded on a desert island the title he would want to have with him would be Lattice Theory by Garrett Birkoff. I agreed, if we added The Elementary Concepts of Topology by Paul Alexandroff.

Mereotopology is composed of two parts and for logicians and mathematicians studying spatial structure at this level of abstraction these two parts are really two ways at looking at spatial entities. One of them considers part/whole distinctions, which is the job of mereology. Modern mereology is very much connected with various forms of ontology that philosophers have studied since Plato and Aristotle, and that were a bit of an obsession for medieval philosophers like Abelard and Aquinas. The problems of parts and wholes and their relationship to the identity of objects would not receive formal treatment however, until after Edmund Husserl published his Logical Investigations around 1900.

Classical mereology takes as its foundation the fact that any theory of spatial representation, geographic or otherwise, must consider the structure of the entities that inhabit the space. For geographers this is a critical point as one could doubt the usefulness of representing space either logically or mathematically independent of the entities that are in it.

The second part is that of connection and continuity. How are the various types of entities connected to the space they inhabit and to each other? This is the territory of topology, which studies the mathematics of connection. We can begin asking mathematical and ontological questions like, “What is the difference between the cup and the glass spread all over the floor after we drop it?” These kinds of questions are important to geographers, as they give us insight into how events are connected physically, and how they retain or loose their material identity over time. One must remember that all of this conceptual thinking must be formalized into algebraic structures within some computational framework.

Geographical space is much different than any abstract notion of bare space, which is infinitely extended and is an infinitely divisible continuum.  This conception of space has proved enormously fruitful in providing a framework for the physical sciences. Geographical space on the other hand is different and is divided into regions and populated with many kinds of objects. Regions themselves can be treated as abstract objects and their existence is entirely dependent on the existence of other more concrete objects.  As soon as space is partitioned like this the mathematical continuum loses its purity but acquires a degree of richness that is represented by sets of relations where space itself is composed of discrete and identifiable objects. It is these complex conceptual connections that mereotopology sets out to explore.

Formal mereotopological treatments, which really form the basic ontology of today’s GIS, have their roots in some of the debates surrounding the axiomatic foundations of geometry that took place at the turn of the last century. In the midst of all the problems stemming from the discovery and applications of non-Euclidean geometry, logicians like Alfred Tarski and Stanislaw Lesniewski, wrote classic papers on the mereology of objects. One of Lesniewski’s in particular, “Foundations of the General Theory of Sets,” from 1916, started me thinking about some of the problems of integrating time in geographic analysis as a continuum rather than a series of discrete values. A kinematics of cartography is the way I like to look at it.

Many researchers are now looking into these kinds of representations and have started to think in terms of “geographic flows” and the kind of dynamical systems that would be required to picture these in a GIS. In mathematical terms this can be thought of as the difference between Eulerian and Lagrangian approaches. Eulerian models look at the evolution of a system, or a piece of geographic space, through time as series of discrete snapshots. Lagrangian models, on the other hand, follow some part of the system being modeled, continuously.

On the geographic but still analytical side, perhaps the most important person for me, and for many others, who have over the years become interested in the foundations of GIS, was William Warntz. During the 1970s Warntz ran the Harvard Laboratory for Computer Graphics and Spatial Analysis, and with an extremely creative group of mathematicians and programmers, took the first steps towards creating modern GIS. Warntz, and other members of the lab, produced a series of important but now largely forgotten papers called, The Harvard Papers in Theoretical Geography.

The papers themselves, which are really short books of about 75 pages, treated geographical and cartographic problems with a mathematical sophistication that was new. The papers utilized theorems from algebraic topology, from abstract algebra and other areas of pure mathematics to try to solve real world problems. Reading them, even today is not for the timid, as they are extremely dense and require much more mathematics than most geographers ever see. But they are thought provoking, their creativity is stunning, and these papers were the first things I ever read that made me want to become a geographer. I have read through the entire run many times.

The work done at the Harvard Lab was controversial and revolutionary and it also changed the face of cartography for ever. Warntz’s words about the changing face of discipline, to me at least, still ring true, even though geographers in most academic departments today might not fully agree.

We now look upon maps not only as stores for spatially ordered information, but also as a means for the graphical solution of certain spatial problems for which the mathematics proves to be intractable, and to produce the necessary spatial transformations for hypothesis testing....The modern geographer conceives of spatial structures and spatial processes as applying not only to such things as landforms....but also to social, economic, and cultural phenomena portraying not only conventional densities but other things such as field quantity potentials, probabilities, refractions etc. Always these conceptual patterns may be regarded as overlying the surface of the real earth and the geometrical and topological characteristics of these patterns, as transformed mathematically or graphically, thus describe aspects of the geography of the real world,
and

We recognize yet another role for maps. In the solution of certain problems for which the mathematics, however elegantly stated, is intractable, graphical solutions are possible. This is especially true with regard to "existence theorems". There are many cases in which the graphical solution to a spatial problem turns out to be a map in the full geographical sense of the term, "map." Thus a map is a solution to the problem.

These days my interests have become even more theoretical and I mostly find myself reading and writing about the two poles of geographic information called the object and field approaches. These two approaches to the questions of what geographic objects are and how can they be portrayed in an algorithmic way are now at the forefront of geographic research.

These distinctions are important because the one element that has been missing from GIS analysis is that of time. GIS, in the past, has typically treated time in discrete units, asking questions like what is the temperature or population at some moment in time and then graphically displaying them on a map. For some simple problems this works quite well and is a common form of thematic mapping.  But when one is dealing with rapidly changing fields (in the fullest mathematical sense) and huge data sets that can be modeled with complex non-linear differential equations these discrete units tell us very little. We want to visualize spatial evolution of whatever we are studying in all its temporal richness. We really want to model, predict and visually represent real world events. This kind of modeling does away with all the traditional forms of cartography and makes GIS a true computational tool.

Adding temporality to geographic information systems poses real serious problems both from a philosophical and technical perspective. From the philosophical point of view there are questions of identity. How do we represent geographic objects that change over time? How much change can take place before these objects are no longer the same? Do spatial objects have temporal parts? How do we keep track of these parts? Strangely enough, these are some of the very problems that Plato talks about in his dialogues like the Theaetetus and the Meno and that philosophers like David Wiggins in his groundbreaking Sameness and Substance Renewed, have been theorizing about for many years.

The Theseus Ship paradox, which Plato writes about in the Meno, is a problem that brings up the question of whether an object which has had all its component parts replaced remains fundamentally the same object. In geography this is important because we are constantly seeing the objects of our study change and evolve. This kind of change takes place in the material, conceptual and bio-geographical sense continuously in the real world, and is the source of many of the philosophical and analytical conundrums that confront the foundations of GIS.

The other much related question that interests me and that is quite difficult to explain to someone not versed in the theoretical underpinnings at this level of abstraction, is geographic vagueness. Vagueness enters into geographical analysis when we ask questions like, “Are the world’s forests disappearing?” or “Is desertification increasing?”

Vagueness is ubiquitous in spatial and geographical concepts and tends to persist even where steps are taken to give precise definitions. To answer questions like this we need formal and topological definitions of what a forest and a desert is. When one begins to think about questions of this type, other deeper questions appear. What do we mean by a forest’s boundary? How does it grow or shrink? How many trees make up a forest?  Must a forest or desert be self-contained, or can it consist of several disjoint parts?  These questions may seem trivial, but in fact they are quite difficult. The definitions we come up with must be subject to quantification in order for us to build algorithms that allow a GIS to actually give us real world answers.

These are exciting and theoretically complicated problems which are also formally very difficult to program. How we answer them in the future will determine the strength of our newly evolving spatial models and the role that geographical analysis will play in policy decisions regarding things like global warming, resource allocation and urban planning. They are also the very questions whose theoretical core I hope to deal with in this book.