Re: 26: Ah, of course; my dumb mistake!

]]>Looking at the thread that Todd linked to, I noticed that all the theorems mentioned that fail when the empty set is taken to be convex are theorems that make use of the Minkowski sum. The Minkowski sum could be defined as follows: given subsets $A$ and $B$ of a vector space, define $A+B$ to be the support of the convolution of their indicator functions. I’m thinking that when we take the support we are drawing a hard line between zero and not-quite-zero, and this is what leads to the bad interaction between the Minkowski sum and the empty set.

]]>Right. I felt that there was something suspicious about the first definition but I couldn’t put my finger on it. The fact that it only makes sense for subsets of vector spaces and not affine spaces is a clear sign that it is probably not a natural definition. This is also related to the previous discussion – in an affine space the only candidate for the convex hull of the empty set is the empty set itself. In a vector space we could pretend that $\{ 0 \}$ is a candidate (at least it seems more natural than other singletons at the first glance). However, this is rather thin, for example it would mean that the convex hull operator no longer preserves inclusions which is also a bad sign.

]]>I think that that example does show that definition (1) doesn’t generalise to a definition of affine space, whereas definition (2) does. So maybe that’s a suggestion that (2) is more natural.

]]>SridharRamesh, all $\lambda_i$s are supposed to be non-negative.

]]>Doesn’t the first definition also rule out, for example, the interval $A = [-1, 1]$ as a convex set, considering $n = 2$ (note: $n$ is overloaded in the description above; I am referring here to the number of weights in our linear combinations, not to the dimension of the ambient space $\mathbb{R}^n$ with $n = 1$) with $\lambda_1 = 1$ and $\lambda_2 = -1$?

If I understand correctly, in this case, $\sum_{i} \left( \lambda_i A \right)$ would be the space $\{a_1 - a_2 \mid a_1, a_2 \in A\} = [-2, 2]$, while $\left( \sum_i \lambda_i \right)A$ would be $0A = \{0\}$.

]]>I’d say the empty sum is defined and equal to zero. See the thread on linear combinations.

]]>Oscar, I don’t understand. I think my question is this: when $n=0$, is the sum $\sum_{i=1}^n \lambda_i$ defined? If this sum is defined, then what does it equal to?

]]>Colin, I think in the first definition we are thinking of the ambient space as being linear. After all the sum makes no sense when $\Sigma \lambda_i\neq 1$ unless we are in a linear space.

We could phrase the first definition like this: a combination of elements of $A$ with positive coefficients must lie inside the image of $A$ after scaling towards or away from the origin by a factor of the sum of those coefficients.

]]>The empty sum of sets is the set of all empty sums of elements of these sets. The empty sum of elements is $0$, so it is an element of the empty sum of sets.

]]>In the first definition, we have an empty sum $\sum_i (\lambda_i A)$. Why should an empty sum be equal to $\{ 0 \}$ and not $\emptyset$? After all, the ambient ${\mathbb{R}}^n$ is viewed as an affine space and not a linear space.

]]>Thanks Todd. After the discussion here, I was basically ready to concede that there doesn’t seem to be any good reason to exclude the empty set from being convex. However, people in the old thread were mostly arguing against the empty set.

To make things even more confusing, Tom actually gave a definition of convex sets similar to the Oscar’s definitions of connected spaces and prime numbers. In fact, he gave two different ones, one excluding the empty set, the other including it.

Here are two possible definitions of convex set. Let $A \subseteq \mathbb{R}^n$.

- $A$ is convex if for all $n \geq 0$, for all $n(\lambda_1, \ldots, \lambda_n) \in [0, \infty)^n$, $\sum_i (\lambda_i A) = (\sum_i \lambda_i) A$
- Same, but only quantifying over $(\lambda_1, \ldots, \lambda_n) \in [0, \infty)^n$ such that $\sum_i \lambda_i = 1$.
These do not give quite the same result. In both definitions, the inclusion $\supseteq$ of the equation is trivial; it’s $\subseteq$ that’s in question. In both definitions, the case $n = 1$ is trivially true, and the case $n = 2$ implies all the cases $n \geq 2$. Moreover, the case $n = 2$ of the first definition is equivalent to the case $n = 2$ of the second: they both say that $A$ is convex or empty. So the only possible difference is the case $n = 0$. There, the first definition says $\{0\} = 0 A$, i.e. $A \neq \emptyset$. But the second definition is vacuously true, since there are no $0$-tuples $\lambda$ satisfying $\sum_i \lambda_i = 1$.

So the first definition excludes $\emptyset$ as a convex set, and the second definition includes it.

So the question is: do we have any reasons to prefer one of these definitions over the other?

]]>Karol: Tom Leinster pointed out to me that there was an extended discussion about whether convex sets are nonempty at the Café, starting right about here.

]]>Karol: re the first question, I believe the answer is ’yes’.

Re your response to #15: fair enough! Thanks.

]]>Todd, is every convex set in the sense of the definition you gave in #4 isomorphic to a convex subset of an affine space?

About #15, it seems to me that acyclic spaces are just $0$-truncated spaces and the monad you are talking about is $0$-truncation. If so, I don’t see how this is related to the original problem which in my mind is about $(-1)$-truncation vs. $(-2)$-truncation.

]]>This reminds me too that acyclicity (property that the discrete space of connected components is a deformation retract) is often a reasonable substitute for contractibility. There is a monad on topological spaces or on simplicial sets which takes a space to the sum of cones over connected components, whose algebras are acyclic structures. This category of algebras has some very nice properties. And the empty space is surely acyclic.

]]>And analogously empty convex spaces arise as the solution spaces of insoluble linear programming problems.

]]>A very good point, Colin.

]]>That’s one equivalent way of expressing the question, yes. (Note, though, that there is no such thing as a “smallest (inhabited) convex subset” of an affine space — any one-point set is *minimal* inhabited convex, but since different one-point sets are incomparable there is no smallest one.)

Hence, the subset S is convex in X iff the image of the j' equals S. The question is, image in which category?

Now, in order that convex sets are contractible, we may stipulate that affine spaces and convex sets are inhabited, while plain vallina sets can be empty. Consider the situation when S is the empty subset of an affine space X. The standard simplex with a vertex for each element of S would be standard (-1)-simplex, which really has no vertices, and is the initial set. Hence, the map j' to X the unique one. But if we take the image of j' is the smallest *convex* subobject of X, then this would be a single point, which is contractible.

So the key question in this debate is really whether we would like the forgetful functor from the category of affine spaces to the category of sets to have a left adjoint. Yes? ]]>

You mean left adjoint? The underlying-set functor $U: Aff \to Set$ doesn’t have a right adjoint, because it doesn’t preserve colimits (coproducts in particular).

Part of the discussion above is whether we want to define $Aff$ so that $U: Aff \to Set$ becomes monadic. If so, then the left adjoint would take the empty set to the “empty affine space”.

]]>