[Math] How to characterize the convex hull/closure operator

convex-analysis

From Wikipedia

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!

Best Answer

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:

  1. For all $A \subseteq X$ we have $\mathsf{cl}(A) = \cup \{ \mathsf{cl}(F) \colon F \text{ is a finite subset of } A \} $.
  2. 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} \} $.
  3. 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.

Related Question