Relazione di equivalenza

[dave lizewski]

Salve a tutti, sarei grato a chi mi dà una mano per questo esercizio tratto da uno scritto di Algebra 1.
Oltre a non essere sicuro della correttezza delle risposte, la difficoltà che ho incontrato è nel
dover ammettere ipotesi aggiuntive per terminare l'esercizio.
In generale mi sembra piuttosto raro trovare nelle prove scritte all'università dei problemi
con dei testi che danno adito ad interpretazioni e questo mi fa temere di aver preso
qualche cantonata.

Sia $X$ un insieme e $F(X):={f:X->X}$ l'insieme delle funzioni da $X$ in $X$.
Si definisca su $F(X)$ la relazione $sim$ nel seguente modo :
$f$ $sim$ $g$ $<=>$ esiste $S$ sottoinsieme finito di $X$ tale $AA x in X\\S$ vale che $f(x) = g(x)$

1) Verificare che $sim$ è una relazione di equivalenza.

Che $sim$ sia riflessiva e simmetrica segue immediatamente dalla definizione.

Transitività: Siano $f,g,h in F(X)$ tali che $f$ $sim$ $g$ e $g$ $sim$ $h$. Ciò significa che
$EE S_1 t.c. AA x in X\\S_1$ vale che $f(x) = g(x)$
$EE S_2 t.c. AA x in X\\S_2$ vale che $g(x) = h(x)$

Osservo che le due proposizioni sono entrambe vere per tutti gli $x$ che appartengono
sia a $X\\S_1$ che a $X\\S_2$ cioè $AA x in X\\S_1 cap X\\S_2$.
Usando la notazione del complementare $S'$ per indicare il generico insieme $X\\S$ ciò equivale a
$AA x in S_1' cap S_2'$
$<=>$ $AA x in (S_1 cup S_2)'$ (per De Morgan)
$<=>$ $AA x in X\\(S_1 cup S_2)$ (per definizione di complementare)

A questo punto ricordo che per ipotesi $S_1, S_2$ sono finiti.
Se assumo l'ipotesi aggiuntiva che X è infinito allora l'insieme $X\\(S_1 cup S_2)$ è sempre non vuoto
e quindi $AA x in X\\(S_1 cup S_2)$ vale che $f(x) = g(x)$ e $g(x) = h(x)$ cioè che $f(x) = h(x)$
ciò significa che $f$ $sim$ $h$.

Perciò la risposta all'esercizio dovrebbe essere: $sim$ non è una equivalenza a meno di ammettere l'ipotesi
aggiuntiva che l'insieme $X$ sia infinito.

2) Verificare se $sim$ è compatibile con la composizione di funzioni.

Osservo che la domanda presuppone che $sim$ sia una equivalenza quindi assumo l'ipotesi aggiuntiva che
l'insieme $X$ sia infinito.
Siano $f$ $sim$ $g$ e $h$ $sim$ $l$ devo mostrare che $f$ $circ$ $h$ $sim$ $g$ $circ$ $l$.
Ricordo che $f$ $sim$ $g$ significa che $EE S_1 t.c. AA x in X\\S_1$ vale che $f(x) = g(x)$ (1)
La tesi è vera se esiste $S$ tale che $AA x in X\\S$ $(f circ h)(x) = (g circ l)(x)$.
Ma l'uguaglianza $(f circ h)(x) = (g circ l)(x)$ è garantita solo per gli $x$ t.c. $h(x), l(x) in X\\S_1$.
Infatti per tali $x$ accade che
$(f circ h)(x) = (f(h(x)) = (g(l(x)) = (g circ l)(x)$ proprio perchè $h(x), l(x) in X\\S_1$ e per la (1).

Osservo che dalla ipotesi $h$ $sim$ $l$ non segue necessariamente che esistono $x$ tali che $h(x), l(x) in X\\S_1$.
Infatti se prendo $h$, $l$ tali che $h(X), l(X) sube S_1$ allora non posso verificare la tesi.

A questo punto costruisco un controesempio. Definisco le seguenti funzioni su $N$:
$f(0) = 0, f(x) = 1$ per $AA x > 0$
$g(0) = 1, g(x) = 1$ per $AA x > 0$
$h(x) = 0$ per $AA x in N$
$l(x) = 0$ per $AA x in N$
Si verifica che $f sim g$, $h sim l$, ma
$(f circ h)(x) = 0 $ $ AA x in N$ e $(g circ l)(x) = 1 $ $ AA x in N$ e quindi $f circ h$ non $ sim g circ l $

Perciò la risposta all'esercizio dovrebbe essere che $sim$ non è compatibile con la composizione di funzioni.

3) Quante sono le classi di equivalenza rispetto a $sim$ nel caso $X$ sia finito ?

La risposta all'esercizio dovrebbe essere che nel caso $X$ sia finito la relazione $sim$ non è una equivalenza
e quindi non è possibile costruire l'insieme quoziente cioè l'insieme delle classi di equivalenza.

[Principe2]

Intanto mi complimento perche' hai posto una domanda nel modo in cui va posta, ovvero dopo aver 1) studiato 2) ragionato.

L'ultimissima domanda ti avrebbe dovuto dare un suggerimento sulla prima: nel caso finito tutto si banalizza, ogni cosa e' quivalente e...

Riguardo alla seconda domanda, mi sembra che la dimostri, ma non te ne accorgi (se due funzioni sono uguali ALMENO sul complementare di un insieme finito, allora sono uguali sul complementare di un insieme finito..)

Buon ragionamento.

[Stickelberger]

L'ipotesi aggiuntiva che $X$ sia finito, non e' necessaria.
Infatti, se $X-(S_1\cup S_2)$ e' vuoto, allora ogni suo elemento
ha qualunque proprietà'! (l'insieme vuoto non ha elementi....)

Quindi, si tratta di una relazione di equivalenza. Anche se $X$ e'
finito. Infatti, se $X$ e' finito, tutte le funzioni sono equivalenti
e abbiamo a che fare con una unica classe di equivalenza.

[dave lizewski]

Ringrazio sinceramente per le risposte, mi dispiaceva che il mio quesito non ne avesse ricevuto nemmeno una...
Inoltre le vostre osservazioni mi chiariscono le idee. In particolare la possibilità del complementare vuoto l'avevo considerata anch'io ma era rimasta a livello di confusa elucubrazione.
Invece vederla esplicitata mi ha fatto capire che era un ragionamento che andava sviluppato.
Ho pensato, se ammetto il complementare vuoto allora l'equivalenza tra le funzioni diventa quella banale,
la composizione di funzioni è compatibile con l'equivalenza e la classe di equivalenza è l'intero insieme $F(X)$.
Allora mi sono detto: possibile che la risposta a questo esercizio sia così breve e insolita ?
Immagino di aver assunto senza accorgermi l'ipotesi implicita che il complementare sia sempre non vuoto.
Ho quindi imparato che bisogna sempre esplicitare tutte queste considerazioni prima di partire in quarta
a riempire la pagina di formule.

Mi scuso in anticipo se nell'intento di riassumere sono stato un pò impreciso, ma dopo le vostre risposte la
comprensione che penso di avere raggiunto su questo specifico esercizio è per me soddisfacente...