Densita` densa (own)
Densita` densa (own)
Definizioni.
1. Densita`. Sia $ $~\mathcal{S} \in \mathbb{Z}^+$ $, e sia inoltre $ $~c(n) = \lvert\{m \in S : m \leq n\}\rvert$ $, ovvero la funzione che conta quanti elementi di questo insieme sono minori o uguali a $ $~n$ $. Diciamo che la densita` di $ $~\mathcal{S}$ $ e` $ $~\alpha$ $ se
$ $~\lim_{n\to\infty} \frac{c(n)}{n} = \alpha.$ $
2. Densita` (lol). Diciamo che un insieme $ $~\mathcal{A}\in\mathbb{Q}^+$ $ e` denso in $ $~\mathbb{Q}+$ $ se
$ $~\forall r\in\mathbb{Q}^+, \varepsilon\in\mathbb{R}^+, \exists x\in\mathcal{A} : \lvert r - x \rvert \leq \varepsilon.$ $
Problema.
Siano $ $~\mathcal{S}$ $ un sottoinsieme di $ $~\mathbb{Z}^+$ $ con densita` $ $~1$ $, e $ $~\mathcal{T} = \left\{\frac{m}{n} : m, n\in\mathcal{S}\right\}$ $.
Dimostrare che $ $~\mathcal{T}$ $ e` denso in $ $~\mathbb{Q}^+$ $.
PS: Non sapevo quale sezione fosse piu` appropriata per questo problema...
Edit: anche se in fondo e` la stessa cosa (giusto?) penso che si possa dimostrare che l'ipotesi di questo problema implichi direttamente che T e` denso in R+. Sbaglio?
1. Densita`. Sia $ $~\mathcal{S} \in \mathbb{Z}^+$ $, e sia inoltre $ $~c(n) = \lvert\{m \in S : m \leq n\}\rvert$ $, ovvero la funzione che conta quanti elementi di questo insieme sono minori o uguali a $ $~n$ $. Diciamo che la densita` di $ $~\mathcal{S}$ $ e` $ $~\alpha$ $ se
$ $~\lim_{n\to\infty} \frac{c(n)}{n} = \alpha.$ $
2. Densita` (lol). Diciamo che un insieme $ $~\mathcal{A}\in\mathbb{Q}^+$ $ e` denso in $ $~\mathbb{Q}+$ $ se
$ $~\forall r\in\mathbb{Q}^+, \varepsilon\in\mathbb{R}^+, \exists x\in\mathcal{A} : \lvert r - x \rvert \leq \varepsilon.$ $
Problema.
Siano $ $~\mathcal{S}$ $ un sottoinsieme di $ $~\mathbb{Z}^+$ $ con densita` $ $~1$ $, e $ $~\mathcal{T} = \left\{\frac{m}{n} : m, n\in\mathcal{S}\right\}$ $.
Dimostrare che $ $~\mathcal{T}$ $ e` denso in $ $~\mathbb{Q}^+$ $.
PS: Non sapevo quale sezione fosse piu` appropriata per questo problema...
Edit: anche se in fondo e` la stessa cosa (giusto?) penso che si possa dimostrare che l'ipotesi di questo problema implichi direttamente che T e` denso in R+. Sbaglio?
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
Provo (o almeno ci provo...) una tesi un pò più forte: T contiene tutti i razionali.
Supponiamo esiste un razionale $ \frac mn $ che non appartiene a T.
Allora S non può contenere nessuna coppia di elementi $ (km,kn) $
Allora il complementare di S, che chiamo FB, contiene almeno uno tra km e kn per ogni k. Un elemento può stare massimo in 2 coppie quindi la densita di FB è almeno
$ \frac 1{2m} $ (dove m>n per comodità) ed è diversa da 0.
S ha quindi densita al massimo$ 1-\frac 1{2m} $ perchè è complementare di FB
sisi sono proprio le sue iniziali!
Assurdo
Tu hai fatto così? Ciao!
Supponiamo esiste un razionale $ \frac mn $ che non appartiene a T.
Allora S non può contenere nessuna coppia di elementi $ (km,kn) $
Allora il complementare di S, che chiamo FB, contiene almeno uno tra km e kn per ogni k. Un elemento può stare massimo in 2 coppie quindi la densita di FB è almeno
$ \frac 1{2m} $ (dove m>n per comodità) ed è diversa da 0.
S ha quindi densita al massimo$ 1-\frac 1{2m} $ perchè è complementare di FB
sisi sono proprio le sue iniziali!
Assurdo
Tu hai fatto così? Ciao!
EATO non è un'idea, è uno stile di vita
Umpfh ma cosi` non vale, il lemma perde il suo significato mistico-trascendentale Stupido insieme, perche` doveva contenere un rappresentante di ogni rapporto in Q!? Bah....
Comunque si`, la soluzione funziona, penso
La mia era molto piu` articolata
Avevo fatto cosi`:
Per assurdo, $ $~\exists r\in\mathbb{Q}^+, \varepsilon\in\mathbb{R}^+ : \forall s, t\in\mathcal{S}, s < (r-\varepsilon) t \vee s > (r+\varepsilon) t$ $, cioe` $ $~\exists a<b\in\mathbb{R}^+ : \forall s, t\in\mathcal{S}, s < a t \vee s > b t$ $. Ma $ $~\forall m\in\mathbb{Z}^+, \exists u\in\mathcal{S} : u>m$ $, altrimenti $ $~\mathcal{S}$ $ sarebbe finito e avrebbe densita` $ $~0$ $, dunque:
$ $~\lim_{n\to\infty} \frac{c(n)}{n} = \lim_{bt\to\infty} \frac{c(bt)}{bt} = \lim_{bt\to\infty}\frac{at}{bt} \leq \lim_{bt\to\infty} \frac{at}{bt} = \frac{a}{b} < 1$ $, assurdo.
Non c'era bisogno di dirlo, l'ho capito appena l'ho letto!
Comunque si`, la soluzione funziona, penso
La mia era molto piu` articolata
Avevo fatto cosi`:
Per assurdo, $ $~\exists r\in\mathbb{Q}^+, \varepsilon\in\mathbb{R}^+ : \forall s, t\in\mathcal{S}, s < (r-\varepsilon) t \vee s > (r+\varepsilon) t$ $, cioe` $ $~\exists a<b\in\mathbb{R}^+ : \forall s, t\in\mathcal{S}, s < a t \vee s > b t$ $. Ma $ $~\forall m\in\mathbb{Z}^+, \exists u\in\mathcal{S} : u>m$ $, altrimenti $ $~\mathcal{S}$ $ sarebbe finito e avrebbe densita` $ $~0$ $, dunque:
$ $~\lim_{n\to\infty} \frac{c(n)}{n} = \lim_{bt\to\infty} \frac{c(bt)}{bt} = \lim_{bt\to\infty}\frac{at}{bt} \leq \lim_{bt\to\infty} \frac{at}{bt} = \frac{a}{b} < 1$ $, assurdo.
Non c'era bisogno di dirlo, l'ho capito appena l'ho letto!
Physics is like sex. Sure, it may give some practical results, but that's not why we do it.
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
Edriv: c=c+2; "tu sarai ricordato come `colui che ha convertito edriv alla fisica' ;)"
[quote="Tibor Gallai"]Alla fine sono macchine di Turing pure loro, solo un po' meno deterministiche di noi.[/quote]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
A questo punto aggiungiamo le naturali estensioni:
Dimostrare che se un insieme $ S \subset \mathbb{N} $ ha una densità positiva, l'insieme S/S è denso in $ \mathbb Q $.
Un altro modo per dire che un S sottoinsieme di N ha abbastanza elementi è questo:
ci chiediamo se esiste un reale $ \alpha $ tale che, per ogni n sufficientemente grande:
$ \frac{c(n)}{n} \ge \alpha $. Un $ \alpha $ esiste sicuramente... lo 0.
Quindi prendiamo il più grande $ \alpha $ possibile che soddisfi la proprietà, e lo chiamiamo "lower densità" di S.
Dimostrare che, se S ha una "lower densità" positiva, allora non necessariamente S/S è denso in $ \mathbb Q $.
Dimostrare che se un insieme $ S \subset \mathbb{N} $ ha una densità positiva, l'insieme S/S è denso in $ \mathbb Q $.
Un altro modo per dire che un S sottoinsieme di N ha abbastanza elementi è questo:
ci chiediamo se esiste un reale $ \alpha $ tale che, per ogni n sufficientemente grande:
$ \frac{c(n)}{n} \ge \alpha $. Un $ \alpha $ esiste sicuramente... lo 0.
Quindi prendiamo il più grande $ \alpha $ possibile che soddisfi la proprietà, e lo chiamiamo "lower densità" di S.
Dimostrare che, se S ha una "lower densità" positiva, allora non necessariamente S/S è denso in $ \mathbb Q $.
Potrebbe non esistere un $ \alpha $ massimo...edriv ha scritto:Quindi prendiamo il più grande $ \alpha $ possibile che soddisfi la proprietà, e lo chiamiamo "lower densità" di S.
edriv ha scritto:Dimostrare che se un insieme $ S \subset \mathbb{N} $ ha una densità positiva, l'insieme S/S è denso in $ \mathbb Q $.
[...]
Dimostrare che, se S ha una "lower densità" positiva, allora non necessariamente S/S è denso in $ \mathbb Q $.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Scusa ma queste due cose non si contraddiconoedriv ha scritto:Dimostrare che se un insieme $ S \subset \mathbb{N} $ ha una densità positiva, l'insieme S/S è denso in $ \mathbb Q $.
[...]
Dimostrare che, se S ha una "lower densità" positiva, allora non necessariamente S/S è denso in $ \mathbb Q $.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
La prima è la densità definita col limite, la seconda è il liminf, sostanzialmente.
Quindi a priori non si contraddicono, ma se credi il contrario, dimostralo.
Quindi a priori non si contraddicono, ma se credi il contrario, dimostralo.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
E' che lo devi dimostrare, gombrendi??
A priori non è così evidente come tu lo possa fare, perché nel 2° caso hai molta più libertà nell'inserire lunghi intervalli di N che non hanno elementi in S...
A priori non è così evidente come tu lo possa fare, perché nel 2° caso hai molta più libertà nell'inserire lunghi intervalli di N che non hanno elementi in S...
Ultima modifica di Tibor Gallai il 02 lug 2009, 17:27, modificato 1 volta in totale.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Ma se la "lower densità" è positiva, allora $ \displaystyle\exists M:\forall n>M:\frac{c(n)}n\ge\alpha>0 $, quindi $ \displaystyle\lim_{n\to\infty}\frac{c(n)}n\ge\alpha>0 $.
Ovvero "lower densità" positiva implica densità positiva, che a sua volta implica $ S/S $ denso su $ \mathbb Q^+ $.
Ovvero "lower densità" positiva implica densità positiva, che a sua volta implica $ S/S $ denso su $ \mathbb Q^+ $.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Right! Ecco l'inghippo!
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
Allora costruisco un sottoinsieme S' di S in questo modo:
$ \displaystyle~S'=S/\{x\} $, con x il più piccolo intero $ \displaystyle~>M:\frac{c(x)}x>\alpha $ (l'M è quello di FeddyStra)
Iterando questo processo all'infinito (con $ \displaystyle~c(\cdot) $ riferita ai nuovi sottoinsiemi) ottengo un sottoinsieme di S con densità $ ~\alpha $...
Abbi pazienza ma continuo a non capire...
$ \displaystyle~S'=S/\{x\} $, con x il più piccolo intero $ \displaystyle~>M:\frac{c(x)}x>\alpha $ (l'M è quello di FeddyStra)
Iterando questo processo all'infinito (con $ \displaystyle~c(\cdot) $ riferita ai nuovi sottoinsiemi) ottengo un sottoinsieme di S con densità $ ~\alpha $...
Abbi pazienza ma continuo a non capire...
Ultima modifica di kn il 02 lug 2009, 18:12, modificato 1 volta in totale.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)