Ramsey usando gli ultrafiltri
Sia \(p \) un ultrafiltro non principale su \( \mathbb{N} \).
a) Dimostra che per ogni \( A \in p \rtimes p \) esiste un insieme infinito \( Y \subseteq \mathbb{N} \) con \( Y^{(2)} \subseteq A \), dove identifichiamo \( \{ n,m\} \in Y^{(2)} \) con \( (\min(n,m),\max(n,m) ) \in \mathbb{N}^2 \).
Hint: costruisci l'insieme \(Y = \{ y_1,y_2,\ldots \} \) induttivamente prendendo \( y_1 \in A_p \), \( y_2 \in A_p \cap A_{y_1} \), \( y_3 \in A_p \cap A_{y_1} \cap A_{y_2} \), etc.
b) Usa a) per dare una dimostrazione alternativa al teorema di Ramesey per i 2-sets.
Notazione:
Per \(n \in \mathbb{N} \) e \(A \subseteq \mathbb{N}^2 \), definiamo \( A_n = \{ m \in \mathbb{N} : (n,m) \in A \} \). E per un ultrafiltro \(p \) definiamo \(A_p = \{ n \in \mathbb{N} : A_n \in p \} \), allora definiamo \( p \rtimes p = \{ A \subseteq \mathbb{N}^2 : A_p \in p \} \).
Per a) ho pensato di fare così: scelgo \( y_1 \in A_p \). Ora scegliamo \(y_2 \in \in A_p \cap A_{y_1} \) ed in particolare abbiamo che siccome \( y_2 \in A_{y_1} \) allora \( (y_1,y_2 ) \in A \). Induttivamente è chiaro che se abbiamo se per \(k \geq 2 \) abbiamo che \( Y_k= \{ y_1 ,\ldots, y_k \} \) con \( Y_k^{(2)} \subset A \) e con \( y_i \in A_p \cap A_{y_1} \cap \ldots \cap A_{y_{i-1}} \) allora scegliendo \( y_{k+1} \in A_p \cap A_{y_1} \cap \ldots \cap A_{y_k} \) risulta che \( Y_{k+1}^{(2)} \subseteq A \). In effetti poiché \( Y_k^{(2)} \subset A \) allora basta controllare che \( (y_i , y_{k+1} ) \in A \) per ogni \( 1 \leq i \leq k \) ma questo segue per costruzione per come abbiamo scelto l'elemento \( y_{k+1} \) poiché per ogni \( 1 \leq i \leq k \) risulta che \( y_{k+1} \in A_{y_i} \) da cui risulta che \( (y_i, y_{k+1} ) \in A \).
Dimostrando quindi che per ogni \( k \geq 2 \) abbiamo che \( Y_{k}^{(2)} \subseteq A \), ora facendo andare \( k \to \infty \) otteniamo il risultato.
Domanda non ho troppo capito a cosa mi serva prendere gli elementi che stanno anche in \( A_p \) cioè non mi basta prendere \( y_i \in A_{y_1 } \cap \ldots \cap A_{y_{i-1} } \) ?
Per b) devo pensarci
a) Dimostra che per ogni \( A \in p \rtimes p \) esiste un insieme infinito \( Y \subseteq \mathbb{N} \) con \( Y^{(2)} \subseteq A \), dove identifichiamo \( \{ n,m\} \in Y^{(2)} \) con \( (\min(n,m),\max(n,m) ) \in \mathbb{N}^2 \).
Hint: costruisci l'insieme \(Y = \{ y_1,y_2,\ldots \} \) induttivamente prendendo \( y_1 \in A_p \), \( y_2 \in A_p \cap A_{y_1} \), \( y_3 \in A_p \cap A_{y_1} \cap A_{y_2} \), etc.
b) Usa a) per dare una dimostrazione alternativa al teorema di Ramesey per i 2-sets.
Notazione:
Per \(n \in \mathbb{N} \) e \(A \subseteq \mathbb{N}^2 \), definiamo \( A_n = \{ m \in \mathbb{N} : (n,m) \in A \} \). E per un ultrafiltro \(p \) definiamo \(A_p = \{ n \in \mathbb{N} : A_n \in p \} \), allora definiamo \( p \rtimes p = \{ A \subseteq \mathbb{N}^2 : A_p \in p \} \).
Per a) ho pensato di fare così: scelgo \( y_1 \in A_p \). Ora scegliamo \(y_2 \in \in A_p \cap A_{y_1} \) ed in particolare abbiamo che siccome \( y_2 \in A_{y_1} \) allora \( (y_1,y_2 ) \in A \). Induttivamente è chiaro che se abbiamo se per \(k \geq 2 \) abbiamo che \( Y_k= \{ y_1 ,\ldots, y_k \} \) con \( Y_k^{(2)} \subset A \) e con \( y_i \in A_p \cap A_{y_1} \cap \ldots \cap A_{y_{i-1}} \) allora scegliendo \( y_{k+1} \in A_p \cap A_{y_1} \cap \ldots \cap A_{y_k} \) risulta che \( Y_{k+1}^{(2)} \subseteq A \). In effetti poiché \( Y_k^{(2)} \subset A \) allora basta controllare che \( (y_i , y_{k+1} ) \in A \) per ogni \( 1 \leq i \leq k \) ma questo segue per costruzione per come abbiamo scelto l'elemento \( y_{k+1} \) poiché per ogni \( 1 \leq i \leq k \) risulta che \( y_{k+1} \in A_{y_i} \) da cui risulta che \( (y_i, y_{k+1} ) \in A \).
Dimostrando quindi che per ogni \( k \geq 2 \) abbiamo che \( Y_{k}^{(2)} \subseteq A \), ora facendo andare \( k \to \infty \) otteniamo il risultato.
Domanda non ho troppo capito a cosa mi serva prendere gli elementi che stanno anche in \( A_p \) cioè non mi basta prendere \( y_i \in A_{y_1 } \cap \ldots \cap A_{y_{i-1} } \) ?
Per b) devo pensarci
Risposte
Forse scegliendo \( y_j \in A_p \) mi garantisce che \( A_{y_j} \in p \) e quindi siccome \(p\) non è principale allora \( A_{y_j} \) è infinito e quindi posso continuare la procedura all'infinito? Altrimenti prima o poi potrebbero esaurirsi gli \( y_j \) a partire da un certo \( j \) ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo