# Conditions for augmenting a collection of sets so that the new sets are small but the hull is large?

This is the second of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions.

The first question is here.

The third question is here.

Suppose that $\mathfrak{P} = \langle P, \leq, \bot \rangle$ is a partially ordered set. Let $\mathbf{B}$ be the collection of all nonempty bounded subsets of $P$. That is to say, if $B \in \mathbf{B}$ then there exists a $p \in P$ satisfying $b \leq p$ for all $b \in B$. Let $\mathsf{con} \colon \mathbf{B} \rightarrow P$ satisfy the following conditions:

1. Increasing Condition. For all $B \in \mathbf{B}$ the element $\mathsf{con}(B)$ is an upper bound for $B$.
2. Order Condition. For all $B_{0}, B_{1} \in \mathbf{B}$; if for all $b_{0} \in B_{0}$ there exists a $b_{1} \in B_{1}$ with $b_{0} \leq b_{1}$ then $\mathsf{con}(B_{0}) \leq \mathsf{con}(B)$.
3. Idempotence Condition. For all $B \in \mathbf{B}$ we have $\mathsf{con}(\mathsf{con}(B)) = \mathsf{con}(B)$. Define $\mathbf{C} = \{ \mathsf{con}(B) \colon B \in \mathbf{B} \}$. Elements of $\mathbf{C}$ will be said to be convex. A convex structure will be denoted by $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$.

Suppose that $q\in P$ and the nonempty set $A \subseteq P \smallsetminus \{ \bot \}$ has $q$ as an upper bound. Are there necessary and sufficient conditions so that for all nonempty $E \subseteq A$ if $q \nleq \mathsf{con}(E)$ then there exists an $E^{*} \subseteq A$ satisfying (i) $E \subseteq E^{*}$, (ii) for all $e \in E$ and all $e^{*} \in E^{*} \smallsetminus E$ we have $e \nleq e^{*}$, and (iii) $q \leq \mathsf{con}(E^{*})$?

1. Definitions. In this collection of definitions we will suppose that $\mathfrak{P} = \langle P, \leq, \bot \rangle$ is a partially ordered set. Recall that $\bot$ is the least element of $P$.

Suppose that $A_{0}, A_{1} \subseteq P$ are not empty. Abusing notation, we will write $A_{0} \leq A_{1}$ if and only if $a_{0} \leq a_{1}$ for all $a_{0} \in A_{0}$ and all $a_{1} \in A_{1}$. We will write $A_{0} \leq_{w} A_{1}$ if and only if for all $a_{0} \in A_{0}$ there exists an $a_{1} \in A_{1}$with $a_{0} \leq a_{1}$.

Suppose that $\mathsf{con} \colon \mathbf{B} \rightarrow P$ satisfies the following conditions:

Increasing Condition. For $B \in \mathbf{B}$ we have $B \leq \mathsf{con}(B)$.

Order Condition. For $B_{0}, B_{1} \in \mathbf{B}$; if $B_{0} \leq_{w} B_{1}$ then we have $\mathsf{con}(B_{0})\leq \mathsf{con}(B_{1})$.

Idempotence Condition. For $B \in \mathbf{B}$ we have $\mathsf{con} \{ \mathsf{con}(B) \} = \mathsf{con}(B)$. Then we will say that $\mathsf{con}$ is a convex hull operator for $\mathfrak{P}$. We will also say that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. Define $$\mathbf{C} = \{ \mathsf{con}(B) \colon B \in \mathbf{B} \} \text{.}$$ The elements of $\mathbf{C}$ will be called convex elements. Since $\bot \leq_{w} B$ for any bounded $B$, the order condition implies that $\mathsf{con}(\{ \bot \} )$ is the smallest convex element. We will denote this element by $\bot_{\mathsf{con}}$. It may be the case that $\bot < \bot_{\mathsf{con}}$.

2. Theorem. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. Then $\mathbf{C}$ is the underlying set for a complete lower semilattice whose order is induced by $\leq$.

Proof. Suppose that $C \subseteq \mathbf{C}$ is not empty. Define $$B = \{ b \in P \colon b \leq C \} \text{.}$$ The set $B$ is bounded. The order and idempotence conditions implies that for all $c \in C$ we have $$\mathsf{con}(B) \leq \mathsf{con}(\{ c \} ) = c \text{.}$$ Thus $\mathsf{con}(B)$ is a lower bound in $\mathbf{C}$ for $C$. Now suppose that $a \in \mathbf{C}$ is a lower bound for $C$. Since $a \in P$ we see that $a \in B$. The idempotence and order conditions imply that $a = \mathsf{con}(\{ a \}) \leq \mathsf{con} B$. But then $\mathsf{con}(B)$ is the greatest lower bound, in $\mathbf{C}$, for $C$.

3. Corollary. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. For all nonempty $C \subseteq \mathbf{C}$ and all $p \in P$; if $p = \wedge C$ then $p$ is convex.

Proof. Suppose that $C \subseteq \mathbf{C}$ is not empty and $p \in P$ is the greatest lower bound for $C$ in $P$. Using the notation from theorem 1 we see that $p \in B$. But then $p \leq \mathsf{con}( \{ p \} ) \leq \mathsf{con}( B ) \leq p$.

4. Proposition. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure, we have $q \in P$, the set $\mathcal{A}$ is a nonempty collection of nonempty subsets of ${\downarrow} q$, and the function $f \colon \mathcal{A} \rightarrow P$ satisfies: for all $A \in \mathcal{A}$ we have $A \leq f(A) \leq \mathsf{con}(A)$. Then $$\mathsf{con}(\cup \mathcal{A}) = \mathsf{con}(\{ f(A) \colon A \in \mathcal{A} \} ) = \mathsf{con}(\{ \mathsf{con}(A) \colon A \in \mathcal{A} \} ) \text{.}$$

Proof. Using the order condition we have \begin{align} \cup \mathcal{A} &\leq_{w} \{ f(A) \colon A \in \mathcal{A} \} \leq_{w} \{ \mathsf{con}(A) \colon A \in \mathcal{A} \} \text{.} \\ \mathsf{con}(\cup \mathcal{A}) &\leq \mathsf{con}(\{ f(A) \colon A \in \mathcal{A} \}) \leq \mathsf{con}(\{ \mathsf{con}(A) \colon A \in \mathcal{A} \}) \text{.} \end{align} For each $A \in \mathcal{A}$ we have $A \leq_{w} \cup \mathcal{A}$; hence $\mathsf{con}(A) \leq \mathsf{con}(\cup \mathcal{A})$. This means $\{ \mathsf{con}(A) \colon A \in \mathcal{A} \} \leq_{w} \{ \mathsf{con}(\cup \mathcal{A}) \}$. The order and idempotent conditions imply $$\mathsf{con}(\{ \mathsf{con}(A) \colon A \in \mathcal{A} \} ) \leq \mathsf{con}(\cup \mathcal{A}) \text{.}$$

5. Definitions. Throughout this collection of definitions we will suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure.

For all $E \in \mathbf{B}$ and all $p \in P$ satisfying $E \cup \{ p \} \in \mathbf{B}$ we will say that $p$ augments $E$ if and only if $e \nleq p$ for all $e \in E$ and $\mathsf{con}(E) < \mathsf{con}(E \cup \{ p \} )$.

Suppose that $q \in P$ and the set $A \subseteq {\downarrow} q$ is not empty. We will say that $A$ satisfies the augmentation property if and only if for all nonempty $E \subseteq A$ if $q \nleq \mathsf{con}(E)$ then there exists a $p \in A$ that augments $E$. For all nonempty $E_{0}, E_{1} \subseteq A$ we will write $$E_{0} \preceq E_{1}$$ if and only if $E_{0} \subseteq E_{1}$ and, for all $e_{1} \in E_{1} \smallsetminus E_{0}$, the element $e_{1}$ augments $E_{0}$.

6. Lemma. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. Suppose also that $A_{0}, A_{1} \in \mathsf{B}$ and $p \in P$ satisfy: 1. We have $A_{0} \subseteq A_{1}$. 2. The set $A_{1}o \cup \{ p \}$ is bounded. 3. We have $\mathsf{con}(A_{1}) < \mathsf{con}(A_{1} \cup \{ p \} )$. Then $\mathsf{con}(A_{0}) < \mathsf{con}(A_{0} \cup \{ p \} )$.

Proof. The order condition implies $\mathsf{con}(A_{0}) \leq \mathsf{con}(A_{0} \cup \{ p \} )$. For the purpose of deriving a contradiction suppose that $\mathsf{con}(A_{0}) = \mathsf{con}(A_{0} \cup \{ p \} )$. Since $$A_{1} \cup \{ p \} = A_{1} \cup (A_{0} \cup \{ p \} )$$ proposition 4 and the properties of a convex hull operator imply \begin{align} \mathsf{con}(A_{1} \cup \{ p \} ) &= \mathsf{con}(A_{1} \cup (A_{0} \cup \{ p \} )) \\ &= \mathsf{con}(\{ \mathsf{con}(A_{1}), \mathsf{con}(A_{0} \cup \{ p \} ) \} ) \\ &= \mathsf{con}(\{ \mathsf{con}(A_{1}), \mathsf{con}(A_{0}) \} ) \\ &= \mathsf{con}( \{ \mathsf{con}(A_{1}) \} ) \\ &= \mathsf{con}(A_{1}) \text{.} \end{align} This is the desired contradiction.

7. Lemma. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. The relation $\preceq$ is a partial order on $\mathbf{B}$.

Proof. Select $E \in \mathbf{B}$. Since inclusion is reflexive and $E \smallsetminus E$ is empty the relation $\preceq$ is reflexive. Since inclusion is anti-symmetric so is $\preceq$. Select $E_{0}, E_{1}, E_{2} e\in \mathbf{B}$ and suppose we have both $E_{0} \preceq E_{1}$ and $E_{1} \preceq E_{2}$. If $E_{0} = E_{1}$ or $E_{1}= E_{2}$ then $E_{0} \preceq E_{2}$. For the remainder of this proof we will suppose that neither $E_{1} \smallsetminus E_{0}$ nor $E_{2} \smallsetminus E_{1}$ is empty. Select $e_{2} \in E_{2}$. If $e_{2} \in E_{1}$ then, since $E_{0} \preceq E_{1}$ the element $e_{2}$ augments $E_{0}$. Suppose that $e_{2} \in E_{2} \smallsetminus E_{1}$. Since $E_{0} \subseteq E_{1}$ and $E_{1} \preceq E_{2}$ we have $\mathsf{con}(E_{1}) < \mathsf{con}(E_{1} \cup \{ e_{2} \} )$. Recalling lemma 6 we see that $\mathsf{con}(E_{0}) < \mathsf{con}(E_{0} \cup \{ p \} )$. But then $E_{0} \preceq E_{2}$.

8. Theorem. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. Suppose also that $q \in P$ and $A \subseteq {\downarrow} q$ is not empty. Then $A$ satisfies the augmentation property if and only if for all nonempty $E \subseteq A$ there exists an $E^{*} \subseteq A$ satisfying both $E \preceq E^{*}$ and $q \leq \mathsf{con}(E^{*})$.

Proof. In this paragraph we will suppose that $A$ satisfies the augmentation property. Choose a nonempty $E \subseteq A$. Define $$\mathcal{G} = \{ G \subseteq A \colon E \preceq G \} \text{.}$$ Since $E \in \mathcal{G}$ the set $\mathcal{G}$ is not empty. The relation $\preceq$ partially orders $\mathcal{G}$. Suppose that $\mathcal{T} \subseteq \mathcal{G}$ is not empty and is totally ordered by inclusion. We have $E \subseteq \cup \mathcal{T}$. Select $g \in \cup \mathcal{T}$. For some $G \in \mathcal{T}$ we have $g \in G$. Since $E\preceq G$ the element $g$ augments $E$. But then $\cup \mathcal{T} \in \mathcal{G}$. Applying Zorn's lemma we see that $\mathcal{G}$ has a maximal element $E^{*}$ For the purpose of deriving a contradiction suppose that $q \nleq \mathsf{con}(E^{*})$. Since $A$ satisfies the augmentation property there exists a $p \in A$ that augments $E^{*}$. But then $E^{*} \prec E^{*} \cup \{ p \}$ which contradicts the maximality of $E^{*}$.

In this paragraph we will suppose that for all nonempty $E \subseteq A$ there exists an $E^{*} \subseteq A$ satisfying both $E \preceq E^{*}$ and $q \leq \mathsf{con}(E^{*})$. Select a nonempty $E \subseteq A$. If $q \leq \mathsf{con}(E)$ there is nothing to prove. Suppose that $q \nleq \mathsf{con}(E)$. Choose $E^{*} \subseteq A$ satisfying both $E \preceq E^{*}$ and $q \leq E^{*}$. Now choose $e^{*} \in E^{*} \smallsetminus E$ and note that $e^{*}$ augments $E$.

9. Proposition. Suppose that $\mathfrak{C} = \langle P, \leq, \bot, \mathsf{con} \rangle$ is a convex structure. The relation $\preceq$ is a partial order on $\mathbf{B}$.

Proof. Inclusion is reflexive. In the case that $E_{1} = E_{0}$ the meet and hull conditions are vacuous. But then $\preceq$ is reflexive. Since inclusion is anti-symmetric so is $\preceq$. Select $E_{0}, E_{1}, E_{2} \in \mathbf{B}$ and suppose that $E_{0} \preceq E_{1}$ and $E_{1} \preceq E_{2}$. If $E_{0} = E_{}$ or $E_{1} = E_{2}$ then $E_{0} \preceq E_{2}$. For the remainder of the proof we will suppose that neither $E_{1} \smallsetminus E_{0}$ nor $E_{2} \smallsetminus E_{1}$ is empty. Select $e_{0} \in E_{0}$ and $e_{2} \in E_{2} \smallsetminus E_{0}$. If $e_{2} \in E_{1}$ then, since $E_{0} \preceq E_{1}$, it is not the case that $e_{0} \leq e_{2}$. If $e_{2} \in E_{2} \smallsetminus E_{1}$ then, since $e_{0} \in E_{1}$ and $E_{1} \preceq E_{2}$, it is not the case that $e_{0} \leq e_{2}$.Thus the meet condition holds. Select $e_{2} \in E_{2}$. Lemma 6 implies that $\mathsf{con}(E_{0}) < \mathsf{con}(E_{0} \cup \{ e_{2} \} )$. But then the hull condition holds.