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,
X ≤ Y := X is included in Y,
X ≥ Y := X is a superset of Y.

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

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

1. H_wave(Ø) = Ø.
2. X ≤ H_wave(X).
3. X ≤ Y → H_wave(X) ≤ H_wave(Y).

Lemma. For any sets X, Y ≤ S, r ≥ 0, the following properties hold:

1. B_r(X U Y) = B_r(X) U B_r(Y).
2. B_r(X ∩ Y) ≤ B_r(X) ∩ B_r(Y).
3. CB_rCB_rCB_rCB_rX = CB_rCB_rX.

Proof. 1 and 2 are trivial. As for 3, an element x belongs to CB_rCB_rX iff B_rx ≤ B_rX, hence B_rCB_rCB_rX ≤ B_rX → CB_rCB_rCB_rX ≥ CB_rX → B_rCB_rCB_rCB_rX≤ B_rCB_rX → CB_rCB_rCB_rCB_rX ≤ CB_rCB_rX (the converse inclusion is trivial).

For H_wave to qualify as a closure operator it must be idempotent, i.e. H_wave(H_wave(X)) = H_wave(X), so that we can define convex sets as those in the range of H_wave. 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 H_wave(X) = {0,1}, H_wave(H_wave(X)) = {0,1,2}. So, we must impose some restrictions on S to guarantee the idempotence of H_wave.

Definition. S is regular if B_rX ≤ B_rY → B_sX ≤ B_sY for all X, Y in S and r ≤ s.

Lemma. If S is regular, CB_rCB_rCB_sCB_sX ≤ CB_max{r,s}CB_max{r,s}X for all X in S.

Proof. Let t = max{r,s}. x belongs to CB_sCB_sX iff B_sx ≤ B_sX, which by the regularity of S implies that B_tx ≤ B_tX, hence CB_sCB_sX ≤ CB_tCB_tX and CB_rCB_rCB_sCB_sX ≤ CB_rCB_rCB_tCB_tX. By an equivalent argument, CB_rCB_rCB_tCB_tX ≤ CB_tCB_tCB_tCB_tX, and this latter set is CB_tCB_tX.

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

Proof. Using the lemmas stated above and de Morgan's Laws, we have H_wave(H_wave(X)) =
= U_r≥0CB_rCB_rU_s≥0CB_sCB_sX =
= U_r≥0CB_rCU_s≥0B_rCB_sCB_sX =
= U_r≥0CB_r∩_s≥0CB_rCB_sCB_sX ≤
≤ U_r≥0C∩_s≥0B_rCB_rCB_sCB_sX =
= U_r≥0U_s≥0CB_rCB_rCB_sCB_sX ≤
≤ U_r,s≥0CB_max{r,s}CB_max{r,s}X = H_wave(X).
The converse inclusion is given by property 2 of H_wave.

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

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) H_wave(X) is convex for any arbitrary X in S.