# Counterexample: Convex set which is NOT the intersection of half-spaces

half-space: either an open half-space, a closed half-space, or a set $H$ s.t. $$H^{o} \subsetneq H \subsetneq \bar{H} \,,$$ where the relative interior $H^o$ is an open half-space and the relative closure $\bar{H}$ is a closed half-space. In other words it is an either an open half-space or a closed half-space "modulo the relative boundary".

As defined above half-spaces don't have to be convex (see the community wiki below), so the claim for which I am seeking a counterexample is:

Claim: Every convex set is the intersection of half-spaces (as defined above).

Most of the related questions on this website (e.g. 1 2 3), as far as I can tell, only answer this question for the case of closed convex sets. However, for my purposes it does not matter at all whether or not the convex set is closed. Thus, requiring the intersecting half-spaces to be closed is too restrictive.

The accepted answer to another related question comes closest to addressing this question. However, the counterexample is not valid using the definition of half-space given above, since one can use as one of the intersecting half-spaces $$\{ (x,y): y > 1 \text{ or } (y=1 \text{ and }x < 1) \} \,.$$

The reason why I suspect the claim is false is because it seems to me like such a simple/natural characterization of arbitrary convex sets that, if the characterization were true, one would see it in a textbook somewhere.

The answer to this other related question may implicitly give the answer to the question, since it seems to address why the convex set $C$ would still be the intersection of half spaces even when $\operatorname{relbd}(C) \setminus C \not= \emptyset$.

• Are you interested only in the finite-dimensional situation or also in the infinite-dimensional situation? – gerw Aug 30 '18 at 7:06
• Why are you re-defining the established term "half-space"? Why not pick another term? The title of this question makes no sense to people who use the standard definition of "half-space". – Rodrigo de Azevedo Aug 31 '18 at 4:56
• @RodrigodeAzevedo What is the standard definition of the term? Open or closed? There is no standard definition. – Chill2Macht Sep 1 '18 at 22:33
• @gerw Only the finite-dimensional situation. – Chill2Macht Sep 1 '18 at 22:33

Let $C \subset \mathbb R^n$ be convex. It is clear that you can write $$\bar C = \bigcap_{i \in I} H_i$$ for some index set $I$ and some closed half-spaces $H_i$. Now, for every $x \in \mathrm{bd}(C) \setminus C$, there is a closed half-space $\tilde H_x$ with $C \subset \tilde H_x$ and $x \in \mathrm{bd}(\tilde H_x)$. Then, $H_x := \tilde H_x \setminus \{x\}$ is a half-space and we have $$C = \bigcap_{i \in I} H_i \cap \bigcap_{x \in \mathrm{bd}(C)\setminus C} H_x.$$

• Dumb question (since I was the person who introduced the weird definition of half-space in the first place): can we also use open half-spaces $H_x^* := \operatorname{relint}\tilde{H}_x$ in lieu of the $H_x$? It seems like the proof would still work, and that as a result needing to introduce a notion of half-space in between open and closed half-spaces was unnecessary. – Chill2Macht Sep 3 '18 at 23:44
• No, this seems not to be possible. For $C = (0,1) \times (0,1) \cup \{(1/2,1)\}$, we cannot remove the points $(c,1)$ with $c \in (0,1/2)\cup(1/2,1)$ without removing $(1/2,1)$. Maybe it would work if we only use convex half-spaces. – gerw Sep 4 '18 at 6:20
• You're right, that's a good counterexample. The examples I had in mind all had positive curvature. I don't understand the last part "if we only use convex half-spaces" -- aren't open and closed half-spaces both convex? Or do you mean the proof might still work if we restrict arbitrary half-spaces as defined above to those which are convex? I think that might be true because if you take any open half-space and adjoin only a single point of its boundary to it, then the new half-space will still be convex. – Chill2Macht Sep 4 '18 at 15:00
• Yes, I think that you can modify the proof by using only convex half-spaces. – gerw Sep 5 '18 at 5:54

Half-spaces as defined above are not convex in general. For a specific example, consider the half-space in $\mathbb{R}^2$: $$H:= \{ (x,y): (y > 1) \text{ or } (y=1 \text{ and }x \le 1) \text{ or }(y=1 \text{ and }x \ge 2) \} \,.$$

Clearly $H^o \subsetneq H \subsetneq \bar{H}$, with the relative interior $H^o$ the open half-space

$$H^o = \{ (x,y): y > 1 \} \,,$$

and the relative closure $\bar{H}$ the closed half-space

$$\bar{H} = \{ (x,y): y \ge 1 \} \,.$$

Moreover, $(1,1) \in H$ and $(2,1) \in H$, but the only line segment joining these two points is not contained in $H$, and therefore $H$ is not convex.

So although there are many half-spaces satisfying the above definition which are neither open nor closed and are nevertheless still convex, if $\operatorname{relbd}(H)$ isn't path-connected, then $H$ doesn't have to be convex.

Aside: Is path-connectedness of the part of the relative boundary contained within the half-space a necessary and sufficient condition for half-spaces as defined above to be convex?

EDIT 2: This is false already whenever $n \ge 3$. Basically the idea is that paths inside the relative boundary of a half-space coincide with line segments if and only if the dimension of the relative boundary is $\le 1$.

For a more concrete counterexample, consider $S = \{ (x,y,z) \in \mathbb{R}^3 | z \le 0 \} \setminus \{(0,0,0)\}$. The part of the relative boundary contained in $S$ (namely $\{ (x,y,z) \in \mathbb{R}^3 | z = 0 \} \setminus \{ (0,0,0) \}$) is path connected, but $S$ is not convex, since there is no line segment joining $(-1,0,0)$ and $(1,0,0)$.

Aside 2: This should also easily generalize to the claim that:

For any set $C$ such that $$C^o \subsetneq C \subsetneq \bar{C} \,,$$ with both $C^o$ and $\bar{C}$ convex, $C$ is convex if and only if $\operatorname{relbd}(C) \cap C$ is path-connected.

EDIT 2: This is also false. It's even false for half-spaces with dimension $\ge 3$.

At the very least it should be necessary for half-spaces, since because their relative boundaries have zero curvature, any line segment joining points of the relative boundary must be contained entirely within the relative boundary, i.e. the relative boundary must itself be convex and thus also path-connected.

But it is not even necessary (much less sufficient) for general convex sets. For example, for a convex set with positive curvature, line segments joining points on the relative boundary pass through the relative interior, such that neither convexity nor path-connectedness of the relative boundary is necessary.