Palle aperte non troppo sovrapposte

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Palle aperte non troppo sovrapposte

Messaggio da jordan » 17 nov 2012, 20:25

Direttamente da math.stackexchange.com , ho appena postato una risposta, ma nessuno conferma se è giusta o meno..

Sia fissato uno spazio compatto $X$ con metrica $d$, e sia fissato un reale positivo $r$. Mostrare che esistono un sottoinsieme $S \subset X$ tali che
\[ \begin{cases} d(p,q)>r/2, \text{ per ogni }p,q \in S \text{ tali che }p\neq q \\ \\ X \subseteq \bigcup_{p\in S}{B(p,r)}\end{cases} \]

Qui $B(x_0,r)$ indica la palla aperta di centro $x_0$ e raggio $r$.
The only goal of science is the honor of the human spirit.

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Palle aperte non troppo sovrapposte

Messaggio da ndp15 » 19 nov 2012, 22:48

Non ho tempo per scriverla per bene quindi sarò breve: per compattezza esiste un ricoprimento finito formato da bolle di raggio $ r/2 $. Ordiniamo i centri. Prendiamo il primo e consideriamo tutte le bolle che hanno centro che dista al più $ r/2 $ da tale centro. Cancelliamo tali bolle e sostituiamo a quella originaria una bolla centrata nello stesso punto e di raggio $ r $. Ora (se necessario) ripetiamo l'operazione a partire dalla seconda bolla che non è ancora stata cancellata e così via. Il procedimento ha termine perché le bolle sono finite. Per costruzione i centri delle nuove bolle distano più di $ r/2 $ tra loro e otteniamo ancora un ricoprimento (banale uso della disuguaglianza triangolare).
Torna tutto?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Palle aperte non troppo sovrapposte

Messaggio da jordan » 19 nov 2012, 23:37

Era anche la soluzione originale di chi ha proposto il problema, a prima vista non pensavo fosse corretta, perchè mi ero perso per strada il fatto che se $p^\star \in B(p,r/2)$ allora $B(p^\star,r/2) \subset B(p,r)$.. sì, torna tutto.

Chi controlla la mia?

Since we assume the contraint $d(p,q)>r/2$ then $S$ is finite, i.e. there exists a integer $n\ge 1$ such that $|S|=n$ and $S:=\{p_1,p_2,\ldots,p_n\}$. It's well known that the propositions:

i) $X$ is totally limited

ii) $X$ is compact

iii) $X$ is sequentially compact

are equivalent (the easiest way to prove it is that (i) implies (ii) implies (iii) implies (i)).

So, there exists a finite collection of open balls $B(x_1,3r/4),B(x_2,3r/4),\ldots,B(x_{k_1},3r/4)$ that covers the whole compact metric space $(X,d)$. We can also assume without loss of generality that $B(x_i,3r/4) \cap X \neq \emptyset$ for all $1\le i\le k_1$.

Define $x_1:=\alpha_1$, and also $X_1:=X\setminus B(x_1,3r/4)$: if $x_1$ is empty then we ended (see below), otherwise $X_1\neq \emptyset$ is a metric space too, bounded, and closed, hence compact too. Then there exist a finite collection of open balls $B(y_1,3r/4),B(y_2,3r/4),\ldots,B(y_{k_2},3r/4)$ that covers $X_1$. Define $y_1:=\alpha_2$.

Repeat this algorithm infinitely many times, we have two cases:

1) If the sequence $\alpha_1,\alpha_2,\ldots$ is finite, then just define $p_i:=\alpha_i$ for all $i$ and we are done, indeed $d(p_i,p_j)\ge 3r/4 > r/2$ for all $1\le i < j \le n$.

2) If the sequence $\alpha_1,\alpha_2,\ldots$ is not finite, then the infinite collection of open balls $B(\alpha_1,3r/4),B(\alpha_2,3r/4),\ldots$ is a cover of $X$. Since $X$ is compact there exists a finite set of pairwise disjoint positive integers $T:=\{t_1,t_2,\ldots,t_n\}$ such that $B(\alpha_{t_1},3r/4),B(\alpha_{t_2},3r/4),\ldots,B(\alpha_{t_n},3r/4)$ is a cover too. Just set $\alpha_{t_i}=p_i$ for all $1\le i\le n$ and we really made our subcover of open balls that "do not overlap too much". []

Ps. Se la mia fosse giusta, implicherebbe che a $r/2$ si potrebbe sostituire un qualunque $r/\varepsilon$, con $\varepsilon>1$..
The only goal of science is the honor of the human spirit.

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Palle aperte non troppo sovrapposte

Messaggio da ndp15 » 20 nov 2012, 09:19

jordan ha scritto: 2) If the sequence $\alpha_1,\alpha_2,\ldots$ is not finite, then the infinite collection of open balls $B(\alpha_1,3r/4),B(\alpha_2,3r/4),\ldots$ is a cover of $X$.
Sai che non mi è molto chiaro questo passaggio? Potresti motivare meglio?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Palle aperte non troppo sovrapposte

Messaggio da jordan » 20 nov 2012, 14:28

Volevo dire che l'algoritmo sopra definisce sempre (<- questo è infatti il punto in cui ho qualche dubbio, esiste qualche controesempio?) una copertura tale che la sequenza degli $\alpha_i$ è al piu' numerabile..
The only goal of science is the honor of the human spirit.

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Palle aperte non troppo sovrapposte

Messaggio da ndp15 » 20 nov 2012, 17:13

Sì avevo inteso. Avevo pensato anche io alla tua stessa soluzione, solo che ho anche io il dubbio di come mostrare che l'algoritmo va in effetti a determinare sempre un ricoprimento. "Ad occhio" direi che la procedura ha sempre termine e anche in un numero finito di passi, però quando ci ho pensato non ho trovato modo di dimostrarlo (mi è venuta in mente solo una strada non facilmente percorribile..)
Qualcuno ha qualche idea?

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Palle aperte non troppo sovrapposte

Messaggio da ma_go » 20 nov 2012, 19:48

è un fatto piuttosto standard.

lemma. se un sottoinsieme $D$ di uno spazio metrico compatto $(X,d)$ è tale che $d(x,y)\ge 1$ per ogni coppia di punti $x,y\in D$, allora $D$ è finito.

dimostrazione. $D$ è localmente chiuso, quindi chiuso, quindi $U=X\setminus D$ è aperto. la famiglia di aperti $\{B_{1/2}(x)|x\in D\}\cup\{U\}$ è un ricoprimento di $X$, quindi ammette un sottoricoprimento finito. ma non possiamo togliere nessuno dei $B_{1/2}(x)$, quindi $D$ è finito.

in teoria dice che la procedura si deve fermare, se la mia logica non m'inganna. ma non dà nessun upper bound (che dovrebbe esistere, credo...).

comunque le due dimostrazioni mi sembrano funzionare, e mi sembrano molto simili. sono l'unico a pensarla così?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Palle aperte non troppo sovrapposte

Messaggio da jordan » 20 nov 2012, 19:54

ma_go ha scritto:lemma. se un sottoinsieme $D$ di uno spazio metrico compatto $(X,d)$ è tale che $d(x,y)\ge 1$ per ogni coppia di punti $x,y\in D$, allora $D$ è finito.[...]
comunque le due dimostrazioni mi sembrano funzionare, e mi sembrano molto simili. sono l'unico a pensarla così?
Ottimo, era quello che mi mancava per convincermi, in pratica l'algoritmo è sempre finito; si, col senno di poi, sono molto simili, ma la prima dimostrazione non funziona se a $r/2$ si sostuisce $r/\varepsilon$ con $1<\varepsilon<2$, giusto?
Grazie ma_go!
The only goal of science is the honor of the human spirit.

Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Re: Palle aperte non troppo sovrapposte

Messaggio da Nonno Bassotto » 20 nov 2012, 21:48

Ma sono tonto io o la condizione $ d(p, q) > r/2 $ può essere resa più forte e diventare $ d(p, q) \geq r $?
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: Palle aperte non troppo sovrapposte

Messaggio da ndp15 » 21 nov 2012, 00:05

Nonno Bassotto ha scritto:Ma sono tonto io o la condizione $ d(p, q) > r/2 $ può essere resa più forte e diventare $ d(p, q) \geq r $?
No torna anche a me. Di fatto si ripete la dimostrazione di Jordan con le bolle di raggio $ r $ e grazie a quanto ha ricordato ma_go la procedura ha termine in un numero finito di passi (tra l'altro il lemma lo conoscevo anche :? ).
Meglio di così non si può fare perché se si prende un insieme formato da due punti a distanza $ r $ tra loro (nota che tale insieme è ovviamente compatto) e se lo si vuole coprire con bolle di raggio $ r $ è necessario prendere le due bolle centrate nei due punti dell'insieme, che distano proprio $ r $ tra loro.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Palle aperte non troppo sovrapposte

Messaggio da jordan » 21 nov 2012, 01:32

Nonno Bassotto ha scritto:Ma sono tonto io o la condizione $ d(p, q) > r/2 $ può essere resa più forte e diventare $ d(p, q) \geq r $?
Hai ragione, e' l'ultimo punto per vale ancora questo problema.. se al posto di $r/2$ si sostuisse un qualunque $kr$ con $k>1$ allora la tesi sarebbe vera se e solo se fossimo nel caso banale in cui una sola palla copre completamente X, i.e. $X\subseteq B(p,kr)$..
The only goal of science is the honor of the human spirit.

Rispondi