Relazioni di equivalenza
Siano $A = {f | f : N \rightarrow N}$ e sia $\omega$ la relazione di equivalenza definita su $A$ nel seguente modo:
$f \omega g$ se ${n \in N | f(n) \ne g(n)}$ è finito.
Devo dimostrare che l'insieme quoziente $A / \omega$ è infinito.
Pensavo alle funzioni costanti (come la guida dell'esercizio dice)...
Quindi definendo $f_{i}$ la mappa costante tale per cui $\forall n \in N, f(n) = i$ si ha che $f_{j} \not\in [f_{i}]$ se $j \ne i$ perché l'insieme dei naturali su cui esse differiscono ha cardinalità $N$ e quindi non è finito...
Quindi $[f_{i}] \in A / \omega$ per ogni naturale $i$. Ovvero le classi di equivalenza delle funzioni costanti rappresentano una partizione di $A$....(adesso forse ho detto una cavolata)...
Però come dimostro che ... è inifinto?
Qualcuno mi può dare una mano su come risolvere questo esercizio?? Grazie
$f \omega g$ se ${n \in N | f(n) \ne g(n)}$ è finito.
Devo dimostrare che l'insieme quoziente $A / \omega$ è infinito.
Pensavo alle funzioni costanti (come la guida dell'esercizio dice)...
Quindi definendo $f_{i}$ la mappa costante tale per cui $\forall n \in N, f(n) = i$ si ha che $f_{j} \not\in [f_{i}]$ se $j \ne i$ perché l'insieme dei naturali su cui esse differiscono ha cardinalità $N$ e quindi non è finito...
Quindi $[f_{i}] \in A / \omega$ per ogni naturale $i$. Ovvero le classi di equivalenza delle funzioni costanti rappresentano una partizione di $A$....(adesso forse ho detto una cavolata)...
Però come dimostro che ... è inifinto?
Qualcuno mi può dare una mano su come risolvere questo esercizio?? Grazie
Risposte
Se un insieme ha almeno tanti elementi quanti \(\mathbb N\), è infinito. Perché?
"Desirio":
Ovvero le classi di equivalenza delle funzioni costanti rappresentano una partizione di $A$....(adesso forse ho detto una cavolata)...
$f(n)=n$? $f(n)=n^2$?
"megas_archon":
Se un insieme ha almeno tanti elementi quanti \(\mathbb N\), è infinito. Perché?
Perché non posso trovare una corrispondenza biunivoca fra $N$ e questo altro insieme con più elementi di $N$?
Giusto?
"ghira":
[quote="Desirio"]Ovvero le classi di equivalenza delle funzioni costanti rappresentano una partizione di $A$....(adesso forse ho detto una cavolata)...
$f(n)=n$? $f(n)=n^2$?[/quote]
Queste sono altre funzioni che ovviamente non appartengono a nessuna classe di equivalenza data da $[f_{i}]$ con $f_{i}$ costante...
"Desirio":
Queste sono altre funzioni che ovviamente non appartengono a nessuna classe di equivalenza data da $[f_{i}]$ con $f_{i}$ costante...
Sì. Quindi le classi di equivalenza delle funzioni costanti non rappresentano una partizione di $A$.
"ghira":
[quote="Desirio"]
Queste sono altre funzioni che ovviamente non appartengono a nessuna classe di equivalenza data da $[f_{i}]$ con $f_{i}$ costante...
Sì. Quindi le classi di equivalenza delle funzioni costanti non rappresentano una partizione di $A$.[/quote]
Ok... quindi come ci arrivo a dimostrare che è infinito? Che ha una cardinalità comunque maggiore di $N$ ?
Basta trovare un sottoinsieme del quoziente in biiezione con \(\mathbb N\), appunto. Se le costanti sono a due a due in classi di equivalenza diverse, eccolo. Certamente non sono una partizione.
"megas_archon":
Basta trovare un sottoinsieme del quoziente in biiezione con \(\mathbb N\), appunto. Se le costanti sono a due a due in classi di equivalenza diverse, eccolo. Certamente non sono una partizione.
Grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo