Pagina 1 di 1

Famiglie disgiunte

Inviato: 31 mar 2018, 14:22
da jordan
Mostrare che esiste una collezione $(A_i)_{i \in I}$ di sottoinsiemi infiniti di interi positivi tali che:
(i) $A_i \cap A_j$ è finito per ogni $i\neq j$;
(ii) $I$ non è numerabile.

Re: Famiglie disgiunte

Inviato: 01 apr 2018, 00:25
da RiccardoKelso
Ciao, sono sempre io. Spero quadri.
Testo nascosto:
Espongo una funzione $F$ iniettiva che va dall'insieme delle successioni binarie (alias $\{f|f:\mathbb{N} \rightarrow \{0,1\}\}$) in se stesso e tale per cui l'insieme immagine, visto come sottoinsieme delle parti di $\mathbb{N}$, soddisfa le richieste. (un numero naturale $i$ appartiene a un certo insieme se e solo se l'elemento $i-esimo$ della successione corrispondente all'insieme è $1$)
Sia $f$ una successione binaria (considereremo poi l'usuale corrispondenza quasi-biunivoca tra successioni binarie e reali $\in (0,1)$, in cui ogni numero viene associato all'espansione in base $2$ della sua parte decimale). Allora $F(f)$ agirà nel seguente modo.
$\forall \space k \in \mathbb{N} \setminus \{0\} \space \exists ! \space n_k \in \mathbb{N} \space |\space \displaystyle \sum_{i=0}^{n_k-1}i < k\leq \displaystyle \sum_{i=0}^{n_k}i$.
Inoltre, fissati $f,k$ (e quindi $n_k$), $\exists !\space m_k \in \mathbb{N}, \space 0\leq m_k\leq n_k\space | \space \frac{m_k}{n_k} \leq f < \frac{m_k+1}{n_k}$.
Ora possiamo definire $F(f)(k)=1 \iff k=m_k+\displaystyle \sum_{i=0}^{n_k-1}i$
Notiamo che $\forall f$, $F(f)$ non è definitivamente nulla, cioè il suo corrispondente sottoinsieme è infinito: $\forall \space k \space \exists ! \space r_k \in \mathbb{N}, n_k-1<r_k\leq n_k \space | \space F(f)(r_k)=1$.
La (i) è vera in quanto dati $f,g \in (0,1), f<g, \exists \space l \in \mathbb{N} \space | \space f+\frac{1}{l}<g$, da cui segue (esplicitando la nuova dipendenza) $m_{k,f}<m_{k,g}\space \forall \space k \space | \space n_k>l$. In questo modo abbiamo anche mostrato l'iniettività.
La (ii) è conseguenza dell'iniettività e del fatto che le successioni binarie siano più che numerabili.

Re: Famiglie disgiunte

Inviato: 02 apr 2018, 12:18
da jordan
Ciao Riccardo, mi fa piacere che provi a risolverli :) Avrei alcuni dubbi a riguardo:

1) Cosa significa $\frac{m_k}{n_k} \le f < \frac{m_k+1}{n_k}$?

2) Cosa significa $f<g$? Intendi l'ordine prodotto $f(k)\le g(k)$ per ogni $k$ e $f(k)<g(k)$ per almeno un $k$? (In questo caso "$\le$" sarebbe un ordine parziale per cui è possibile che $f\not\le g$ e $g\not\le f$.)

3) Ammesso che ti restringi a un sottoinsieme totalmente ordinato $X$ delle possibili $f$, come mostri che $X$ non è numerabile?

Re: Famiglie disgiunte

Inviato: 02 apr 2018, 13:17
da RiccardoKelso
Non sono stato chiaro. Quando una successione binaria appare in una disuguaglianza (come appunto nei casi $\frac{m_k}{n_k} \le f < \frac{m_k+1}{n_k}$ e $f<g$) mi riferisco a quel numero reale compreso tra $0$ e $1$ la cui parte decimale ha espansione in base $2$ uguale alla successione stessa. Per intenderci, la successione identicamente nulla corrisponde al numero $0$, la successione avente $1$ come primo elemento e poi solo zeri corrisponde al numero $\frac{1}{2}$... Per evitare i soliti problemi escludiamo le successioni i cui elementi sono definitivamente uguali a $1$.

Re: Famiglie disgiunte

Inviato: 02 apr 2018, 18:28
da jordan
Va bene, ora ho capito, mi pare che funzioni. Avrei alcuni suggerimenti riguardo come hai scritto la dimostrazione:
1. Se parti dallo spazio di Cantor $\{0,1\}^{\mathbf{N}}$ (che non usi mai) per poi identificarlo in una "quasi-biezione" con $[0,1)$, allora parti direttamente da $[0,1)$;
2. Al posto di $(n_k)$ e $(m_k)$, puoi prendere una qualunque successione $(a_k)$ che cresce abbastanza velocemente (per esempio $k^2$) e cosi definire, per ogni $x \in [0,1)$, la sua "migliore approssimazione" in $[a_k,a_{k+1})$.
3. Definisci tutti i termini che usi, come quell' $m_{k,f}$..

Provo a riscrivere la tua dimostrazione:
"Per ogni $x \in [0,1)$, sia $a_x=(a_{x,n})$ la successione definita da $a_{x,n}:=n^2+\lfloor x(2n+1)\rfloor$ per ogni $n$ e definiamo $\mathscr{A}_x:=\{a_{x,n}:n\ge 1\}$. Allora $\mathscr{A}_x \cap \mathscr{A}_y$ è finito per ogni $x\neq y$ e la (ii) è ovvia."

Visto che ci sono, scrivo anche quella che conoscevo:
"Identifichiamo $\mathbf{N}$ con $\mathbf{Q}$ e, per ogni irrazionale $\theta$, sia $(a_{\theta,n})$ una successione di razionali che converge a $\theta$. Allora la famiglia $\{\{a_{\theta,n}:n\in \mathbf{N}\}: \theta \text{ irrazionale }\}$ soddisfa le ipotesi."

Re: Famiglie disgiunte

Inviato: 02 apr 2018, 18:41
da RiccardoKelso
jordan ha scritto: 02 apr 2018, 18:28 Visto che ci sono, scrivo anche quella che conoscevo:
"Identifichiamo $\mathbf{N}$ con $\mathbf{Q}$ e, per ogni irrazionale $\theta$, sia $(a_{\theta,n})$ una successione di razionali che converge a $\theta$. Allora la famiglia $\{\{a_{\theta,n}:n\in \mathbf{N}\}: \theta \text{ irrazionale }\}$ soddisfa le ipotesi."
Grazie, mi ero dimenticato di chiedertela.

Sì, la dimostrazione mi sembra essere perfettamente analoga a quella. Francamente imputerei la presenza di passaggi o giri di parole inutili al fatto che prima di scrivere (senza la calma necessaria) quella soluzione non abbia liberato la mente da tutte le idee precedentemente scartate :lol:

Spero di farmi sentire presto sul topic della permutazione infinita