Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorKarol Szumiło
   • CommentTimeOct 1st 2015
   • PermaLink
   Author: Karol Szumiło
   Format: MarkdownItexInspired by the recent discussion about objects that are too simple to be simple, I started wondering: should the empty set be considered convex? As a topologist, I feel that the most important property of convex sets is that they are contractible. This makes me want to exclude the empty set. But perhaps there is a reason why convex sets should be merely $(-1)$-truncated and not necessarily $(-2)$-truncated. Any thoughts?

   Inspired by the recent discussion about objects that are too simple to be simple, I started wondering: should the empty set be considered convex? As a topologist, I feel that the most important property of convex sets is that they are contractible. This makes me want to exclude the empty set. But perhaps there is a reason why convex sets should be merely $(-1)$-truncated and not necessarily $(-2)$-truncated. Any thoughts?

2. • CommentRowNumber2.
   • CommentAuthorOscar_Cunningham
   • CommentTimeOct 1st 2015
   • PermaLink
   Author: Oscar_Cunningham
   Format: MarkdownItexAnother oddity is that if the empty set is convex then it should also be affine, which would be odd because it would be an affine space not modelled on a vector space. On the other hand, I can't think of a nice way of defining "convex set" that *automatically* excludes the empty set.

   Another oddity is that if the empty set is convex then it should also be affine, which would be odd because it would be an affine space not modelled on a vector space.

   On the other hand, I can’t think of a nice way of defining “convex set” that automatically excludes the empty set.

3. • CommentRowNumber3.
   • CommentAuthorKarol Szumiło
   • CommentTimeOct 1st 2015
   • PermaLink
   Author: Karol Szumiło
   Format: MarkdownItexNow I'm thinking that there is no reasonable candidate for the convex hull of the empty set, other than the empty set itself. So unless we are willing to say that the empty set has no convex hull, we should make it convex after all.

   Now I’m thinking that there is no reasonable candidate for the convex hull of the empty set, other than the empty set itself. So unless we are willing to say that the empty set has no convex hull, we should make it convex after all.

4. • CommentRowNumber4.
   • CommentAuthorTodd_Trimble
   • CommentTimeOct 1st 2015
   • (edited Oct 1st 2015)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexMy point of view is that convex sets are models of an algebraic theory whose operations are generated from affine combinations $(x, y) \mapsto t x + (1-t)y$ with $0 \leq t \leq 1$. Since this algebraic theory has no constants in the signature, the empty set is surely a model. You just have to be careful to specify 'inhabited' if you want contractibility.

   My point of view is that convex sets are models of an algebraic theory whose operations are generated from affine combinations $(x, y) \mapsto t x + (1-t)y$ with $0 \leq t \leq 1$. Since this algebraic theory has no constants in the signature, the empty set is surely a model. You just have to be careful to specify ’inhabited’ if you want contractibility.

5. • CommentRowNumber5.
   • CommentAuthorTodd_Trimble
   • CommentTimeOct 1st 2015
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexIncidentally, the nLab takes a position on [[affine space]] that they are by definition inhabited ([[torsors]] over vector spaces), and therefore that they do not form an equational variety, although it is conceded that some authors do favor the equational variety definition.

   Incidentally, the nLab takes a position on affine space that they are by definition inhabited (torsors over vector spaces), and therefore that they do not form an equational variety, although it is conceded that some authors do favor the equational variety definition.

6. • CommentRowNumber6.
   • CommentAuthorMike Shulman
   • CommentTimeOct 1st 2015
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexI find the question of whether the empty set is an affine space to be extremely vexing. I am attracted to the idea of affine spaces as an equational variety, and of course I dislike adding "inhabited" as an axiom on general grounds. But unlike many other cases of this sort, it seems as thought most of the interesting theorems about affine spaces *do* require them to be inhabited and don't have any natural generalization to include the "trivial" case. I'm not as sure about convex sets.

   I find the question of whether the empty set is an affine space to be extremely vexing. I am attracted to the idea of affine spaces as an equational variety, and of course I dislike adding “inhabited” as an axiom on general grounds. But unlike many other cases of this sort, it seems as thought most of the interesting theorems about affine spaces do require them to be inhabited and don’t have any natural generalization to include the “trivial” case.

   I’m not as sure about convex sets.

7. • CommentRowNumber7.
   • CommentAuthorColin Tan
   • CommentTimeOct 2nd 2015
   • PermaLink
   Author: Colin Tan
   Format: TextDo we want a right adjoint to the functor that forgets the affine space leaving the underlying set?

   Do we want a right adjoint to the functor that forgets the affine space leaving the underlying set?
8. • CommentRowNumber8.
   • CommentAuthorTodd_Trimble
   • CommentTimeOct 2nd 2015
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexYou 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".

   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”.

9. • CommentRowNumber9.
   • CommentAuthorColin Tan
   • CommentTimeOct 2nd 2015
   • PermaLink
   Author: Colin Tan
   Format: TextLet S be an inhabited subset of an affine space X. Let j: S -> X denote the inclusion. Then j induces an affine map to X from the standard simplex with a vertex for each element of S. This induced map, call it j', has image the convex hull of S. 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?

   Let S be an inhabited subset of an affine space X. Let j: S -> X denote the inclusion. Then j induces an affine map to X from the standard simplex with a vertex for each element of S. This induced map, call it j', has image the convex hull of S.
   
   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?
10. • CommentRowNumber10.
    • CommentAuthorColin Tan
    • CommentTimeOct 2nd 2015
    • PermaLink
    Author: Colin Tan
    Format: TextYeah, sorry, should be left adjoint.

    Yeah, sorry, should be left adjoint.
11. • CommentRowNumber11.
    • CommentAuthorMike Shulman
    • CommentTimeOct 2nd 2015
    • PermaLink
    Author: Mike Shulman
    Format: MarkdownItexThat'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.)

    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.)

12. • CommentRowNumber12.
    • CommentAuthorColin Tan
    • CommentTimeOct 4th 2015
    • PermaLink
    Author: Colin Tan
    Format: TextRegarding item 6 of this thread, empty affine spaces arise as the solution space of inhomogeneous linear systems Ax = b.

    Regarding item 6 of this thread, empty affine spaces arise as the solution space of inhomogeneous linear systems Ax = b.
13. • CommentRowNumber13.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 4th 2015
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItexA very good point, Colin.

    A very good point, Colin.

14. • CommentRowNumber14.
    • CommentAuthorOscar_Cunningham
    • CommentTimeOct 4th 2015
    • PermaLink
    Author: Oscar_Cunningham
    Format: MarkdownItexAnd analogously empty convex spaces arise as the solution spaces of insoluble linear programming problems.

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

15. • CommentRowNumber15.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 4th 2015
    • (edited Oct 4th 2015)
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItexThis 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.

    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.

16. • CommentRowNumber16.
    • CommentAuthorKarol Szumiło
    • CommentTimeOct 6th 2015
    • PermaLink
    Author: Karol Szumiło
    Format: MarkdownItexTodd, 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.

    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.

17. • CommentRowNumber17.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 6th 2015
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItexKarol: re the first question, I believe the answer is 'yes'. Re your response to #15: fair enough! Thanks.

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

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

18. • CommentRowNumber18.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 22nd 2015
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItexKarol: 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](https://golem.ph.utexas.edu/category/2011/08/mixed_volume.html#c039338).

    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.

19. • CommentRowNumber19.
    • CommentAuthorKarol Szumiło
    • CommentTimeOct 22nd 2015
    • PermaLink
    Author: Karol Szumiło
    Format: MarkdownItexThanks 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](http://nforum.ncatlab.org/discussion/6774/too-simple-to-be-simple/) 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$. > 1. $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$ > 2. 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?

    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$.

    1. $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$
    2. 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?

20. • CommentRowNumber20.
    • CommentAuthorColin Tan
    • CommentTimeOct 27th 2015
    • PermaLink
    Author: Colin Tan
    Format: MarkdownItexIn 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.

    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.

21. • CommentRowNumber21.
    • CommentAuthorKarol Szumiło
    • CommentTimeOct 27th 2015
    • PermaLink
    Author: Karol Szumiło
    Format: MarkdownItexThe 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.

    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.

22. • CommentRowNumber22.
    • CommentAuthorOscar_Cunningham
    • CommentTimeOct 27th 2015
    • PermaLink
    Author: Oscar_Cunningham
    Format: MarkdownItexColin, 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.

    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.

23. • CommentRowNumber23.
    • CommentAuthorColin Tan
    • CommentTimeOct 27th 2015
    • PermaLink
    Author: Colin Tan
    Format: MarkdownItexOscar, 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?

    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?

24. • CommentRowNumber24.
    • CommentAuthorOscar_Cunningham
    • CommentTimeOct 27th 2015
    • PermaLink
    Author: Oscar_Cunningham
    Format: MarkdownItexI'd say the empty sum is defined and equal to zero. See the [thread](http://nforum.ncatlab.org/discussion/4043/linear-combinations/) on linear combinations.

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

25. • CommentRowNumber25.
    • CommentAuthorSridharRamesh
    • CommentTimeOct 27th 2015
    • (edited Oct 27th 2015)
    • PermaLink
    Author: SridharRamesh
    Format: MarkdownItexDoesn'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\}$.

    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\}$.

26. • CommentRowNumber26.
    • CommentAuthorKarol Szumiło
    • CommentTimeOct 27th 2015
    • PermaLink
    Author: Karol Szumiło
    Format: MarkdownItexSridharRamesh, all $\lambda_i$s are supposed to be non-negative.

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

27. • CommentRowNumber27.
    • CommentAuthorOscar_Cunningham
    • CommentTimeOct 28th 2015
    • PermaLink
    Author: Oscar_Cunningham
    Format: MarkdownItexI 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.

    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.

28. • CommentRowNumber28.
    • CommentAuthorKarol Szumiło
    • CommentTimeOct 28th 2015
    • PermaLink
    Author: Karol Szumiło
    Format: MarkdownItexRight. 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.

    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.

29. • CommentRowNumber29.
    • CommentAuthorOscar_Cunningham
    • CommentTimeOct 28th 2015
    • PermaLink
    Author: Oscar_Cunningham
    Format: MarkdownItexLooking at the [thread](https://golem.ph.utexas.edu/category/2011/08/mixed_volume.html#c039338) 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.

    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.

30. • CommentRowNumber30.
    • CommentAuthorSridharRamesh
    • CommentTimeOct 28th 2015
    • (edited Oct 28th 2015)
    • PermaLink
    Author: SridharRamesh
    Format: MarkdownItexRe: 26: Ah, of course; my dumb mistake!

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