3
$\begingroup$

The Kuratowski closure-complement problem asks what is the largest number of distinct sets obtainable by repeatedly applying the set operations of closure ($-$) and complement ($c$) to a given starting subset of a topological space. By using the identities

  1. $K^{--}=K^{-}$
  2. $K^{cc}=K$
  3. $K^{-c-c-c-}=K^{-c-}$

one can find that an upper bound of this number is given by 14. Furthermore, it is also possible to exhibit a subset of $\mathbb{R}$ which attains this bound.

On the other hand, the dual cone of a subset $K$ of $\mathbb{R}^n$ is the set defined by $$K^* := \left \{y\in \mathbb{R}^{n}: \langle y , x \rangle \geq 0 \quad \forall x\in K \right \} $$ and it is known that if $K$ is a convex cone, then $K^{**} = K^{-}$, i.e. the closure operation can be generated by the dual cone operation which takes a set to its dual cone.

This motivates the following question, which is a variant of Kuratowski closure-complement problem:

Does the number of distinct sets obtainable by repeatedly applying the set operations of dual cone and complement to a given starting convex cone in $\mathbb{R}^n$ has an upper bound?

$\endgroup$
3
  • 1
    $\begingroup$ V. P. Soltan's 1982 paper Problems of Kuratowski Type (in Russian, MR669747) doesn't consider the dual cone, but he does end by replacing closure with convex hull and stating some results without proof. See my English translation here $\endgroup$ May 28 '14 at 19:54
  • $\begingroup$ Thanks a lot @mathematrucker $\endgroup$
    – shamisen
    May 28 '14 at 22:11
  • $\begingroup$ Dear @epimorphic, thanks very much for your useful comments. I updated the question to reflect that the relation $K^{**} = K^{-}$ is valid if $K$ is a convex cone (I confess that I missed it at first). Moreover, I also agree that the other relations of the generators should be further explained. $\endgroup$
    – shamisen
    Jun 4 '14 at 14:51
3
$\begingroup$

The sharp bound is 14 for $n \geq 2$. That's the same as that for the Kuratowski problem, but the match appears to be a coincidence. For $n = 1$, the sharp bound is 4.

We'll focus on the $n \geq 2$ case. Denote $X = \mathbb R^n$. First, some preliminaries:

  • A cone is said to be a ray iff it has the form $\mathbb R_{>0} x = \{ ax : a>0 \}$ or $\mathbb R_{\geq 0} x = \{ ax : a \geq 0 \}$ for some $x \in X$. Rays of the first form are called blunt, while those of the second form are called pointed.

  • An open half-space is a set of the form $\{y \in X : \langle x, y \rangle > 0\}$ for some $x \in X$. More generally, we say that a convex cone $H$ is a half-space iff $O \subseteq H \subseteq O^-$ for some open half-space $O$. Note that $H^- = O^-$ is of the form $\{ y \in X : \langle x, y \rangle \geq 0\}$, and that $H^\circ = O$ ($\circ$ is the interior operation).

  • We show that the vector $x$ in the definition of a half-space is unique up to multiplication by a positive scalar for a given half-space $H$. Let $x_H \in H^\circ$ be a unit vector such that $H^\circ = \{y \in X : \langle x_H, y \rangle > 0\}$. Next, let $z \in X \setminus \mathbb{R}x_H$. Then $z^\bot := z - \langle x_H, z \rangle x_H$ is perpendicular to $x_H$, so $-z^\bot + \epsilon x_H \in H^\circ$ for all $\epsilon > 0$. Now $$ \langle z, -z^\bot + \epsilon x_H \rangle = -\langle z, z \rangle + \langle x_H, z \rangle^2 + \epsilon \langle x_H, z\rangle. $$ Since $x_H$ and $z$ are not collinear, the Cauchy–Schwarz inequality tells us that $\langle x_H, z \rangle^2 < \langle x_H, x_H \rangle \langle z, z\rangle = \langle z, z \rangle$. Thus for sufficiently small $\epsilon$, we have $\langle z, -z^\bot + \epsilon x_H \rangle < 0$. Therefore $H^\circ \neq \{ y \in X : \langle z, y \rangle > 0\}$.

  • The above definitions and discussions imply that the dual of a ray is a closed half-space, and that the dual of a half-space is a pointed ray. In particular, for any half-space $H \subset X$, we have $H^* = \mathbb R_{\geq 0} x_H$ and $(\mathbb R_{>0}x_H)^* = (\mathbb R_{\geq 0}x_H)^* = H^-$.

So we distinguish two cases for your question.

Case 1. The starting cone $K$ is either a half-space, a ray, or one of $\varnothing$, $\{0\}$, and $X$.

If $K$ is a half-space, set $H = K$. Or if $K$ is a ray, let $x$ be the unit vector determining $K$. Then $x = x_H$ for some half-space $H$. The sets that can be generated are shown in the following diagram, in which $A \to B$ means $A^* = B$, and $A \dashrightarrow B$ means $A^c = B$.

One can reach at most 14 nodes from any given starting point. A blunt ray is an example of a starting cone where all 14 nodes represent distinct sets.

Case 2. $K$ is none of the above.

Since $K \neq X$, the supporting hyperplane theorem tells us that $K$ lies in some half-space $H$. Moreover, we have that $K^\circ = K^{-\circ}$ (Corollary 1.2.12 here; also mentioned in another question), so $K^- \not\supseteq H^\circ$ (otherwise $K$ would be a half-space). It follows that $K^{c*} = K^{-c*} = \{0\}$.

What's more, $K^* \neq X$ is also not a half-space (otherwise $K^- = K^{**}$ would be a ray, hence $K$ would also be a ray). The same argument as above shows that $K^{*c*} = \{0\}$.

So we have a considerably simpler diagram, with only 10 nodes:

enter image description here

We are done.

I'll briefly mention the situation for other dimensions:

  • In $\mathbb R$, there are only 7 convex cones. The collections $\{\mathbb R_{<0}, \mathbb R_{\leq 0}, \mathbb R_{\geq 0}, \mathbb R_{>0}\}$ and $\{\varnothing, \{0\}, \{0\}^c, \mathbb R\}$ are each closed under the two operations and together contain the convex cones.

  • The situation where $X$ is an infinite-dimensional real Hilbert space is reasonably similar to that of $X = \mathbb R^n$, $n \geq 2$. Case 1 would be exactly the same. However, Case 2 would not: The supporting hyperplane theorem as stated for $\mathbb R^n$ no longer holds. Perhaps a weakened version of the supporting hyperplane theorem, that either $K$ is contained in a half-space or is dense, might still be true. We also have instances where $K$ is not a half-space but $K^-$ is (consider the algebraic linear span of an orthonormal basis, intersected with a half-space), but that just means that we would have a third case where we combine parts of the two diagrams, which isn't a big deal.

$\endgroup$
1
  • $\begingroup$ Wow, thanks a lot for the excellent answer! $\endgroup$
    – shamisen
    Sep 29 '14 at 1:10
2
$\begingroup$

Edit: My answer is irrelevant because the OP stated a fact incorrectly and edited the question. Also, assuming the set to begin with is convex and $\delta^2=a$, I cannot think of a relation between $\delta$ and $b$ so the monoid so generated isn't necessarily finite. Please un-accept my answer.

The answer is YES, the number of sets is finite.

In case of the classical Kuratowski problem, the number of sets, 14 is the cardinality of the monoid (say $M$) generated by two elements, say $a, b$ subject to the relations $a^2 = a, b^2 = e, abababa = aba$. Here, $a$ (resp. $b$) denotes the operation of closure (resp. complement).

In the case of the operations being dual cone and complement, the monoid $N$ is generated by $\delta, a, b$ with $\delta^2=a$ and other relations as before. (Here, $\delta$ is the operation of taking the dual cone.) Now there is an injection $M \hookrightarrow N$ of monoids and the index of $M$ in $N$ is 2.

Of course, one needs to construct an example (if possible) that the 28 sets are actually distinct, but surely there is an upper bound.

$\endgroup$
4
  • 1
    $\begingroup$ It is possible to give a relation analogous to (3) that guarantees that the word $\delta b \delta b \delta b \delta b \ldots$ isn't infinite? $\endgroup$
    – shamisen
    May 28 '14 at 14:37
  • 1
    $\begingroup$ Perhaps I'm missing some other line of reasoning, but I don't see why, given the relations on generators that you've listed, the index of $M$ in $N$ is 2. It seems to me like $M, \delta M, b \delta M, \delta b \delta M,\dotsc$ could all potentially be distinct cosets. If there are other relations that aren't consequences of those already listed, I think they should be explicated. $\endgroup$
    – epimorphic
    May 31 '14 at 5:40
  • 1
    $\begingroup$ Also, I believe the relation $\delta^2=a$ you used is false. The equation $K^{**}=K^-$ is valid if $K$ is a convex cone, but not for general $K \subset \mathbb R^n$ (a fact that the asker should have clarified). The problem with $\delta^2 = a$ arises from the fact that the complement of a convex cone is generally not a convex cone. $\endgroup$
    – epimorphic
    May 31 '14 at 21:56
  • 1
    $\begingroup$ Counterexample that shows $\delta^2 \neq a$: Denote by $C$ the open upper-right quadrant of $\mathbb R^2$ (note that $C$ is a convex cone). Then the complement $bC$ is the closure of the union of the other three quadrants. We then have $\delta(bC) = \{0\} \implies \delta^2(bC) = \mathbb R^2$, which is not equal to $a(bC) = bC$. $\endgroup$
    – epimorphic
    May 31 '14 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.