Closure Spaces:  A Brief Overview

The concept of uniquely generated closure spaces has begun to be studied as a common thread emerging in computer applications, in graphs, and in discrete geometries. Briefly, a closure operator CL is said to be uniquely generated if for any closed set there a unique minimal subset for which this is the closure. Such a closure operator acting on a set, or universe, of elements, U is said to be a closure space (U, CL).

The importance of uniquely generated closure spaces lies in the fact that in discrete systems they play a role that is in many respects analogous to the vector spaces of classical mathematics.

The basis set of a vector space can be generalized as a matroid and the vector space is a closure (or spanning) operator on this basis set which satisfies the Steinitz-MacLane exchange axioms. Every uniquely generated closure operator can be shown to satisfy the anti-exchange axioms, and therefore be the closure of an antimatroid. Consequently a closure space is to an antimatroid, what a vector space is to a matroid.

But there the analogy stops. The properties of closure spaces are very different.

Closure operators are fairly common, although they frequently have other names, for example ``convexity''. The convex hull of a discrete set is an uniquely generated closure. A theory of convex geometries is developed in [EJ85]. Convexity in graphs has been examined in [P71], [FJ86]. The ``lower ideals'', or ``down sets'' of a partially ordered set are closed. In concurrent computing, the concept of a ``transaction'' is a simple closure operator. Algorithmic closure, in particular that of greedy algorithms is found in [KLS91] which introduces the term ``greedoid'', a special kind of antimatroid.

In the case of networks, or undirected graphs, a definition of ``neighborhood closure'' has proven to be quite useful. It is neither ``matroid'' nor ``antimatroid''. (See our major heading on ``Social, and other, Networks'' for more details''.

Most closure operators are unary; they have a single argument, usually a set. ``Galois closure'', which usually defined closure relations between a set of objects and their properties, is binary. (See our major heading on ``Concept Graphs and Logical Inference''.)

The subsets of a closure space can be partially ordered to create a lattice with many interesting properties [P96]. An unusual property comes from the observation that for any set Z in U, { X | X.CL = Z.CL } must be a power of 2. Thus any uniquely generated closure operator CL partitions the subsets of U into a disjoint collection of subsets, each containing a single closed set and each consisting of 2^k subsets. Hence every closure space on n points has a characteristic signature of the form < a_n, ... a_1, a_0 > where a_k counts the number of closure subsets of size 2^k. The a_k are called a partition of 2^n. Since every such partition gives rise to at least one closure space, the number of such partitions gives a lower bound for the number of closure spaces on n elements [P95a].

More recent work has included the definition of distance in antimatroids [P97], which turns out to be non-local; transformations of antimatroid closure spaces [P98a], which includes a definition of continuity in discrete spaces; and uniform closure spaces [P98b].

Related Papers