How to characterize the convex hull/closure operator

Question

Every subset $A$ of a vector space $S$ over the real numbers, or, more generally, some ordered field, is contained within a smallest convex set (called the convex hull of $A$), namely the intersection of all convex sets containing $A$. The convex-hull operator $Conv()$ has the characteristic properties of a hull operator:

extensive $S ⊆ Conv(S)$,

non-decreasing $S ⊆ T$ implies that $Conv(S) ⊆ Conv(T)$, and

idempotent $Conv(Conv(S)) = Conv(S)$.

I was wondering what else properties of the convex hull/closure operator has, so that

we can define a hull/closure operator with such properties to be a convex hull/closure operator, and
we can define the class of all convex subsets for a given ground set, by for example claiming a subset is convex if and only if it equals its convex hull?

Thanks and regards!

$Conv(T)=T$ for any affine subspace $T$, and $Conv(S\setminus T)= S$ unless $S=T$. — Olivier Bégassat, Jan 02 '13 at 18:01
@OlivierBégassat: Thanks! I was wondering if these two additional properties can define a closure operator to be a convex closure operator? References are also appreciated. — Tim, Jan 02 '13 at 18:05
Also, $$Conv(X)=\bigcup_{F\subset X,~F\text{ finite}}Conv(F)$$ — Olivier Bégassat, Jan 02 '13 at 18:19
@OlivierBégassat: Thanks! Did you come up with the three properties yourself? Do you know if they can characterize a convex closure operation? — Tim, Jan 02 '13 at 18:24
What the above equation tells us, is that we only need to caracterise the operation for finite sets. — Olivier Bégassat, Jan 02 '13 at 19:35
@OlivierBégassat: Thanks! (1) "$Conv(S\setminus T)= S$ unless $S=T$", do you require some conditions on $T$ and/or $S$? (2) in your last comment, is the third property (in your second comment) or all the three properties (in your first two comments) needed for a closure operation to be a convex closure operation? — Tim, Jan 03 '13 at 02:18
In general, closure operators have the properties you listed, though they come in two flavors: hulls and kernels, where kernels are intensive rather than extensive. — alancalvitti, Jan 03 '13 at 03:32
Fyi > in geometry 4 closure operators are widely considered: convex, affine, cone, and linear hulls (spans). — alancalvitti, Jan 03 '13 at 03:33
@alancalvitti: Thanks! (1)I wonder how closure operators "come in two flavors: hulls and kernels"? Isn't it just hulls? (2) "kernels are intensive rather than extensive." How are kernels defined? Do you refer to something like a topological interior operator, or the reduction operator which maps a closed subset to a smallest subset having the closed set as its closure? — Tim, Jan 03 '13 at 18:07
@Tim, the terminology is not really standard, but intuitively hulls are extensive and kernels intensive. For example polyhedra can be defined by half-space intersection (kernel), and dually by convex/cone hull. Except that nobody really calls the intersection a kernel. (Also, unrelated to kernels of vector space maps). — alancalvitti, Jan 03 '13 at 18:25

Jay · Accepted Answer · 2013-01-03T20:05:38.837

There is a theorem in van de Vel's Theory of Convex Structures that may be of interest. First define a closure system. Suppose that $X$ is a set and $\mathcal{C}$ is a collection of subsets of $X$. Then $\langle X, \mathcal{C} \rangle$ is a closure system if and only if for all $\mathcal{A} \subseteq \mathcal{C}$ we have $\cap \mathcal{A} \in \mathcal{C}$. Sometimes people require $\varnothing \in \mathcal{C}$. I can't remember if van de Vel does. For $A \subseteq X$ define $$\mathsf{cl}(A) = \cap \{ C \in \mathcal{C} \colon A \subseteq C \} .$$ In any event the convex subsets of a real vector space satisfy these properties.

Theorem Suppose that $\langle X, \mathcal{C} \rangle$ is a closure system. Then the following statements are equivalent:

For all $A \subseteq X$ we have $\mathsf{cl}(A) = \cup \{ \mathsf{cl}(F) \colon F \text{ is a finite subset of } A \} $.
For all $\mathcal{D}$ which are collections of subsets of $X$ that are directed by inclusion (see below for a definition of directed by inclusion) we have $\mathsf{cl}(\cup \mathcal{D}) = \cup \{ \mathsf{cl}(D) \colon D \in \mathcal{D} \} $.
For all $\mathcal{T}$ which are collections of subsets of $X$ that are totally ordered by inclusion (see below for a definition of totally ordered by inclusion) we have $\mathsf{cl}(\cup \mathcal{T}) = \cup \{ \mathsf{cl}(T) \colon T \in \mathcal{T} \} $.

A collection $\mathcal{D}$ of subsets is directed by inclusion if and only if for all $D_{0}, D_{1} \in \mathcal{D}$ there is a $D \in \mathcal{D}$ with $D_{0}, D_{1} \subseteq D$.

A collection of subsets is totally ordered by inclusion if and only if for all $T_{0}, T_{1} \in \mathcal{T}$ we have $T_{0} \subseteq T_{1}$ or $T_{1} \subseteq T_{0}$.

Edit

This is in response to Tim's comment.

Suppose that $X$ is a set and $\mathcal{F}$ is the collection of finite subsets of $X$. Suppose also that $f \colon \mathcal{F} \rightarrow \mathcal{P}(X)$ where $\mathcal{P}(X)$ is the collection of all subsets of $X$. For each $n \in \mathbb{N}$ define \begin{align} g_{n} \colon \mathcal{P}(X) &\rightarrow \mathcal{P}(X) \\ \text{for all $A \subseteq X$ by the assignment} \\ g_{0} \colon A &\mapsto A \\ g_{n} \colon A & \mapsto g_{n-1}(A) \cup (\cup \{ f(F) \colon F \subseteq g_{n-1}(A) \text{ is finite} \} ) \end{align}

Then $A \mapsto \cup \{ g_{n}(A) \colon n \in \mathbb{N} \} $ is a convex hull operator. The function $f$ generalizes the notion of the points between $x, y \in \mathbb{R}^{k}$. If you think of this construction in this manner then the $g_{n}$ functions just accumulate line segments.

+1. Thanks! (1) In the theorem just for a closure system and its closure operator, and there is no convexity structure and convexity closure operator involved? What references is the theorem from? (2) When can a closure operator be a convexity closure operator (in abstract sense)? I guess we will need some properties from a convexity closure operator (in concrete sense, for a vector space over an ordered field)? — Tim, Jan 03 '13 at 02:06
The result is, more or less, theorem 1.3 in van de Vel's book. Click on this versionof the book The result is on page 5. — Jay, Jan 03 '13 at 19:35
In thm 1.3, he says that a closure operator is a convex closure operator iff it is domain finite. Is a closure operator being domain finite equivalent to $ \operatorname{cl}(X) = \bigcup\left{\operatorname{cl}(Y) : Y\subseteq X \text{ and } Y \text{ finite} \right}$, i.e. finitary property in Wikipedia? So can we say that a closure operator is a convex closure operator iff it has the finitary property? — Tim, Jan 07 '13 at 17:40
(2) Wikipedia says "The convex hull in n-dimensional Euclidean space is another example of a finitary closure operator. It satisfies the anti-exchange property: If x is not contained in the union of A and {y}, but in its closure, then y is not contained in the closure of the union of A and {x}. Finitary closure operators with this property give rise to antimatroids." This is a concrete convexity structure, but for an abstract convexity, does its closure satisfy the anti-exchange property? (...) — Tim, Jan 07 '13 at 17:43
(...) Is a closure operator a convex closure operator iff it has both finatary and anti-exchange properties? — Tim, Jan 07 '13 at 17:45
A convex closure operator need not satisfy the anti-exchange property. Suppose that $X$ is a real vector space. For all $A \subseteq X$ let $\mathsf{con}(A)$ be the smallest affine subspace that contains $A$. An affine subspace is a translate of a (usual) subspace. In this case $\mathsf{con}(A) = Y + x$ where $Y$ is a subspace of $X$ and $x \in X$. — Jay, Jan 08 '13 at 16:26

How to characterize the convex hull/closure operator

1 Answers1