Saturday, February 16, 2008

A non-Euclidean characterization of convexity: properties

The extension of the concept of convexity closure we devised at a prior entry has some of the usual properties of standard convexity. In the following we consider a generic metric space S, and use the following notation:

CX := X \ S,
XY := X is included in Y,
XY := X is a superset of Y.

Also, we drop parentheses in some expressions to make them more readable.

Theorem. Hwave verifies the following properties (proof trivial):

  1. Hwave(Ø) = Ø.
  2. XHwave(X).
  3. XYHwave(X) ≤ Hwave(Y).

Lemma. For any sets X, YS, r ≥ 0, the following properties hold:

  1. Br(X U Y) = Br(X) U Br(Y).
  2. Br(X Y) ≤ Br(X) Br(Y).
  3. CBrCBrCBrCBrX = CBrCBrX.

Proof. 1 and 2 are trivial. As for 3, an element x belongs to CBrCBrX iff Brx BrX, hence BrCBrCBrXBrXCBrCBrCBrXCBrXBrCBrCBrCBrXBrCBrX CBrCBrCBrCBrXCBrCBrX (the converse inclusion is trivial).

For Hwave to qualify as a closure operator it must be idempotent, i.e. Hwave(Hwave(X)) = Hwave(X), so that we can define convex sets as those in the range of Hwave. This property is not verified in general; as a counterexample take S = N \ {3} with dist(n,m) = |m n| and X = {0}, resulting in Hwave(X) = {0,1}, Hwave(Hwave(X)) = {0,1,2}. So, we must impose some restrictions on S to guarantee the idempotence of Hwave.

Definition. S is regular if BrXBrYBsXBsY for all X, Y in S and rs.

Lemma. If S is regular, CBrCBrCBsCBsX CBmax{r,s}CBmax{r,s}X for all X in S.

Proof. Let t = max{r,s}. x belongs to CBsCBsX iff Bsx BsX, which by the regularity of S implies that Btx BtX, hence CBsCBsX CBtCBtX and CBrCBrCBsCBsX CBrCBrCBtCBtX. By an equivalent argument, CBrCBrCBtCBtX CBtCBtCBtCBtX, and this latter set is CBtCBtX.

Theorem. If S is regular, Hwave(Hwave(X)) = Hwave(X) for all X in S.

Proof. Using the lemmas stated above and de Morgan's Laws, we have Hwave(Hwave(X)) =
= Ur≥0CBrCBrUs≥0CBsCBsX =
= Ur≥0CBrCUs≥0BrCBsCBsX =
=
Ur≥0CBrs≥0CBrCBsCBsX
Ur≥0Cs≥0BrCBrCBsCBsX =
=
Ur≥0Us≥0CBrCBrCBsCBsX
Ur,s≥0CBmax{r,s}CBmax{r,s}X = Hwave(X).
The converse inclusion is given by property 2 of Hwave.

We define convexity in the customary manner: X is convex if X = Hwave(X). Remember that this definition of convexity does not exactly coincide with the classical one for S = Rn.

Theorem. The following properties hold (proof trivial):
  1. Ø and S are convex.
  2. The intersection of a familiy of convex sets of S is also convex.
  3. (S is regular) Hwave(X) is convex for any arbitrary X in S.

No comments :

Post a Comment