Dimostrare che una Relazione transitiva, non è una funzione
Riflettendo su alcuni esercizi di esame sugli insiemi mi è venuta questa intuizione.
Data una relazione $R$ da un insieme $A$ in sé, se $R$ è transitiva allora la relazione non è una funzione da $A$ in sé (escluso il caso molto semplice in cui $A$ ha un solo elemento)
L'intuizione è che se in A ho due elementi o più. Non riesco a trovare R che sia transitiva e al tempo stesso una funzione.
Ad esempio se ho $A= {1,2,3} $ e ho la relazione d'ordine $<=$
è vero che
$1<=2$
è vero
$2<=3$
ed è anche vero
$1<=3$ (transitività)
Ma siccome al valore 1, associo due valori diversi 2 e 3 non è più una funzione. (se avessi avuto l'insieme ${1}$ sarebbe stata una funzione) Qualche suggerimento su come dimostrarlo? Intuitivamente si vede che se la relazione è una funzione allora ogni elemento ha come immagine un unico elemento
$(a,b)$
$(b,c)$
$(a,c) <=> a=b , b=c $ e "per induzione" su n elementi dovrebbe uscire che gli elementi sono tutti uguali allora l'insieme ha un unico elemento.
Data una relazione $R$ da un insieme $A$ in sé, se $R$ è transitiva allora la relazione non è una funzione da $A$ in sé (escluso il caso molto semplice in cui $A$ ha un solo elemento)
L'intuizione è che se in A ho due elementi o più. Non riesco a trovare R che sia transitiva e al tempo stesso una funzione.
Ad esempio se ho $A= {1,2,3} $ e ho la relazione d'ordine $<=$
è vero che
$1<=2$
è vero
$2<=3$
ed è anche vero
$1<=3$ (transitività)
Ma siccome al valore 1, associo due valori diversi 2 e 3 non è più una funzione. (se avessi avuto l'insieme ${1}$ sarebbe stata una funzione) Qualche suggerimento su come dimostrarlo? Intuitivamente si vede che se la relazione è una funzione allora ogni elemento ha come immagine un unico elemento
$(a,b)$
$(b,c)$
$(a,c) <=> a=b , b=c $ e "per induzione" su n elementi dovrebbe uscire che gli elementi sono tutti uguali allora l'insieme ha un unico elemento.
Risposte
Per mostrare che una cosa non è vera in matematica puoi utilizzare dei controesempi. Quello che hai trovato ti è un controesempio alla proposizione "Data una relazione $R$, se questa gode della proprietà transitiva, allora non può essere una funzione".
ok dovrebbe essere così la dimostrazione:
Definizione di funzione:
se date due coppie $(a,b) , (c,d)$ con $a,b,c,d$ appartenenti ad $A$ allora $a=b => c=d$
Relazione transitiva:
presi $(a,b)$ e $(b,c)$ appartenenti alla relazione $R$ allora $(a,c)$ appartiene alla relazione.
quello che voglio provare:
Una Relazione Transitiva da A in sè, non è una funzione se A ha più di un elemento
suppongo di avere una relazione transitiva che sia una funzione, ovvero ho
$(a,b) , (b,c) \epsilon R $
allora ho
$(a,c) \epsilon R$
ma siccome è una funzione,
da $(a,b),(a,c)$ deduco che $b$ è $c$.
trovo $R={(a,b),(b,b)}$
Quindi l'intuizione era sbagliata perchè ho trovato un insieme $A={a,b}$ con una relazione binaria transitiva che è ancora una funzione. Dovrei quindi "aggiornare" l'intuizione:
Una Relazione Transitiva da A in sè, non è una funzione se A ha più di due elementi
Questo adesso lo posso dimostrare, perchè ripetendo i passaggi di prima mi riduco ad avere $R={(a,b),(b,b)}$ ovvero due elementi di A, ma ero partito dall'ipotesi di averne 3 (più di 2), quindi assurdo. (e non ho disturbato nessun principio di induzione)
Teorema: (non vorrei che qualcuno si offendesse se lo chiamo così vista la semplicità che può avere per voi XD, sempre ammesso che quello che ho scritto sia corretto)
Una Relazione Transitiva da A in sè, non è una funzione se A ha più di due elementi .
Definizione di funzione:
se date due coppie $(a,b) , (c,d)$ con $a,b,c,d$ appartenenti ad $A$ allora $a=b => c=d$
Relazione transitiva:
presi $(a,b)$ e $(b,c)$ appartenenti alla relazione $R$ allora $(a,c)$ appartiene alla relazione.
quello che voglio provare:
Una Relazione Transitiva da A in sè, non è una funzione se A ha più di un elemento
suppongo di avere una relazione transitiva che sia una funzione, ovvero ho
$(a,b) , (b,c) \epsilon R $
allora ho
$(a,c) \epsilon R$
ma siccome è una funzione,
da $(a,b),(a,c)$ deduco che $b$ è $c$.
trovo $R={(a,b),(b,b)}$
Quindi l'intuizione era sbagliata perchè ho trovato un insieme $A={a,b}$ con una relazione binaria transitiva che è ancora una funzione. Dovrei quindi "aggiornare" l'intuizione:
Una Relazione Transitiva da A in sè, non è una funzione se A ha più di due elementi
Questo adesso lo posso dimostrare, perchè ripetendo i passaggi di prima mi riduco ad avere $R={(a,b),(b,b)}$ ovvero due elementi di A, ma ero partito dall'ipotesi di averne 3 (più di 2), quindi assurdo. (e non ho disturbato nessun principio di induzione)
Teorema: (non vorrei che qualcuno si offendesse se lo chiamo così vista la semplicità che può avere per voi XD, sempre ammesso che quello che ho scritto sia corretto)
Una Relazione Transitiva da A in sè, non è una funzione se A ha più di due elementi .
Io direi che serve qualcosa di più: una relazione transitiva da $A$ in sè, chiamiamola $ccR$, non è una funzione se $EE a,b,c in A$ (diversi tra loro a due a due) tali che $(a,b) in ccR$ e $(b,c) in ccR$
sono d'accordo. "se A ha più di 2 elementi" non mi piaceva molto come frase. Invece "diversi tra loro a due a due" mi convince 
Grazie!
Grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo