Palle aperte non troppo sovrapposte
Palle aperte non troppo sovrapposte
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$.
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.
Re: Palle aperte non troppo sovrapposte
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?
Torna tutto?
Re: Palle aperte non troppo sovrapposte
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$..
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.
Re: Palle aperte non troppo sovrapposte
Sai che non mi è molto chiaro questo passaggio? Potresti motivare meglio?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$.
Re: Palle aperte non troppo sovrapposte
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.
Re: Palle aperte non troppo sovrapposte
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?
Qualcuno ha qualche idea?
Re: Palle aperte non troppo sovrapposte
è 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ì?
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ì?
Re: Palle aperte non troppo sovrapposte
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?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ì?
Grazie ma_go!
The only goal of science is the honor of the human spirit.
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Re: Palle aperte non troppo sovrapposte
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
Re: Palle aperte non troppo sovrapposte
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 ).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 $?
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.
Re: Palle aperte non troppo sovrapposte
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)$..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 $?
The only goal of science is the honor of the human spirit.