nLab
convex space

Contents

Idea

A convex space (also called barycentric algebra and other terms, invented independently many times) is a set equipped with a notion of taking weighted averages, or convex-linear combinations, of its elements. Do not confuse this with an (abstract) convex set , which a special kind of convex space, also defined below.

A convex space is a set XX equipped with a family of maps c p:X×XXc_p : X \times X \to X satisfying some natural axioms (described below). All commutative monoids are convex spaces, with the map c p(x,y)=x+p(yx)c_p(x,y) = x + p(y-x).

Convex spaces may be important in the foundations of probability theory. The category of convex spaces is semicartesian monoidal but not cartesian monoidal.

The monad assigning to any set the free convex space on that set is a finitary commutative monad. We can thus follow Durov in thinking of it as a generalized ring. This allows us to think of convex spaces as ‘modules’ of a generalized ring, very much as vector spaces are modules of a field. This is also true of the relatives of convex spaces: affine spaces and conical spaces. For example, all affine spaces are convex spaces as defined below.

Of particular importance are convex spaces parametrized by the interval P=[0,1]P = [0,1] or the Boolean algebra P={0,1}P = \{0,1\}. These two algebras are dual, in a certain sense described by Jacobs (2009). This duality is functorial, and therefore is present for convex spaces for general PP. This leads to the notion of a dual convex space?.

Definition

A convex space is a set XX equipped with:

  • a (semi)(ring PP, so that for each element pPp \in P, there exists an operation c p:X×XXc_p: X \times X \to X,

such that the following identities always hold:

  • c 0(x,y)=xc_0(x,y) = x,
  • c p(x,x)=xc_p(x,x) = x for all pPp \in P,
  • c p(x,y)=c 1p(y,x)c_p(x,y) = c_{1-p}(y,x) for all pPp \in P,
  • c p(x,c q(y,z))=c pq(c r(x,y),z)c_p(x, c_q(y,z)) = c_{p q}(c_r(x,y),z) for all p,q,rPp,q,r \in P satisfying p(1q)=(1pq)rp(1 - q) = (1 - p q)r.

As a consequence of the first and third axioms, c 1(x,y)=c 0(y,x)=yc_1(x,y) = c_0(y,x) = y.

This defines convex spaces as a variety of algebras, with one binary operation for each pp.

The intended interpretation is that c p(x,y)=x+p(yx)=(1p)x+pyc_p(x,y) = x + p(y-x) = (1-p)x + py. i.e., c p(x,y)c_p(x,y) is the pp-weighted average of xx and yy, where xx gets weight 1p1-p and yy gets weight pp. By thinking of pp as a continuous parameter, this interpretation has the advantage of “starting” at xx, then moving toward yy at “rate” pp.

This interpretation is ‘biased’, in the sense that the centered choice p=0p=0 favors xx. It is also possible to give an ‘unbiased’ definition, which characterizes to convex-linear combinations of many points. This is an nn-ary operation parametrised by a list p:=(p 1,,p n)p := (p_1,\ldots,p_n) satisfying i=1 np i=1\sum_{i = 1}^n p_i = 1. If x:=(x 1,,x n),thenx := (x^1,\ldots, x^n), then c_p(x) := \sum_i p_i x^i$.

A homomorphism of convex spaces may be called a convex-linear map or an affine linear map (since an affine space is a convex space with extra properties, as in the examples below). It should probably not be called a ‘convex map’, which (between affine spaces) is something more general.

Examples

Any real vector space is a convex space, with c p(x,y)=x+p(yx)c_p(x,y) = x + p(y-x). In the unbiased version, any convex-linear combination is a linear combination. Note that a convex-linear map between vector spaces may not be a linear map, since it may not preserve the identity; thus, a vector space is a convex space with extra structure.

More generally, any real affine space is a convex space; since p+(1p)=1p + (1 - p) = 1, the expression for c pc_p in a vector space is valid in an affine space. In the unbiased version, any convex-linear combination is an affine linear combination. Now any convex-linear map between affine spaces is an affine linear map (and conversely); an affine space is a convex space with extra properties.

Still more generally, any convex subset (that is, one containing the entire line segment between two given points) of a real affine space is a convex space (again with extra properties, which are described algebraically below).

The Boolean field {0,1}\{0,1\} is a convex space with c p(x,y)=xy=x+yxyc_p(x,y) = x \vee y = x + y - x y whenever 0<p<10 \lt p \lt 1 (with c 0(x,y)=xc_0(x,y) = x and c 1(x,y)=yc_1(x,y) = y as always); this cannot be realised as a subset of a vector space. This can be generalised to any (possibly unbounded) semilattice. (It would be nice to find an example like this that can be defined constructively; this one relies on excluded middle.)

Abstract convex sets

There is a nice abstract converse to the example of a convex subset of an affine space. A convex space is cancellative if y=zy = z whenever c p(x,y)=c p(x,z)c_p(x,y) = c_p(x,z) for some cc and p0p \ne 0. We may call a cancellative convex space an abstract convex set. The justification for this terminology is this

Theorem (Thm 2 in the paper by Stone)

A convex space is cancellative if and only if it is isomorphic (as a convex space) to a convex subset of some real affine space.

Compare this with the theorem that a monoid is cancellative? if and only if it is isomorphic to a submonoid of some group.

Of course, most of the examples given above are cancellative, being manifestly given as convex subsets of real affine space. However, the last example—a semilattice with c p(x,y)=xyc_p(x,y) = x \vee y whenever 0<p<10 \lt p \lt 1—is non-cancellative.

References

Convex spaces have been rediscovered many times under many different names. References tend to define c pc_p only for 0<p<10 \lt p \lt 1, but it seems obvious that it's best to include the edge cases as well. Classically, it makes no difference, but the definition above is probably better in constructive mathematics.

  • Handbook of Analysis and its Foundations, Section 12.7 (short and to the point).

  • Romanowska, Smith, Orłowska; Abstract barycentric algebras; pdf. This generalises from [0,1][0,1] to an arbitrary LΠL \Pi-algebra (LL for ‘Łukasiewicz’, Π\Pi for ‘product’, so think of [0,1][0,1] as a space of fuzzy truth values).

  • Romanowska & Smith (1985); Modal Theory: An Algebraic Approach to Order, Geometry, and Convexity; Res. Exp. Math. 9; Heldermann-Verlag, Berlin, 1985.

  • Marshall Harvey Stone, Postulates for the barycentric calculus, Ann. Mat. Pura. Appl. (4), 29:25–30, 1949.

  • Tobias Fritz, Convex spaces I: definition and examples. arXiv

  • John Baez, Tobias Fritz, Tom Leinster, Convex spaces and an operadic approach to entropy, nnLab draft

  • Bart Jacobs, Duality for convexity arXiv/0911.3834

  • Shiri Artstein-Avidan, Vitali Milman, The concept of duality in convex analysis, and the characterization of the Legendre transform, Annals of Math. 169, n.2, 661-674 (2009)

  • Joe Flood, Semiconvex geometry, J. Austral. Math. Soc. Ser. A 30 (1980/81), 496-–510.

  • T. Swirszcz, Monadic functors and categories of convex sets , Preprint No. 70, Proc. Inst. Math. Pol. Acad. Sci., Warsaw; Monadic functors and convexity, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 22 (1974), 39–42.

  • Stanley P. Gudder, Convexity and mixtures, SIAM Review 19 (1977), 221–240; A general theory of convexity, Milan Journal of Mathematics, 49 (1979), 89–96.

Many other references, and a discussion of how convex spaces have been repeatedly rediscovered, can be found at the nn-Category Café post Convex Spaces.

Revised on August 8, 2013 10:18:52 by Anonymous Coward (74.66.20.170)