Stabilire se si tratta di relazione di equivalenza o d'ordine
Salve, ci sono spesso esercizi in cui si chiede di stabilire se una relazione è di equivalenza o di ordine. Il problema è che ho alcuni dubbi nel dimostrare di che relazione si tratta. Forse il mio problema è banale. Ad esempio consideriamo quest'esercizio:
Sia $m in Z$ e sia $R$ la relazione binaria in $Z$ definita ponendo $AAx, y in Z, xRy iff m|x^3-y^3$
Stabilire se la relazione è di equivalenza e stabilire se è di ordine.
So che una relazione è di equivalenza se rispetta le 3 proprieta elencate di seguito ovvero:
$AAx in S, xRx$ (riflessiva)
$AAx, y in S, xRy rArr yRx$ (simmetrica)
$AAx, y, z in S, xRy$ e $yRz rArr xRz$ (transitiva)
Per la relazione d'ordine invece so che abbiamo le stesse proprietà della relazione d'equivalenza, cambia solo la simmetrica che diventa asimmetrica e quindi:
$AAx, y in S, xRy$ ma non accade che $yRx$ (asimmetrica)
Adesso, riprendendo l'esercizio proprosto prima, credo che la relazione non sia riflessiva in quanto ad esempio prendendo $x = 3$ abbiamo che $3^3 - 3^3 = 0$, pertanto non può esserci nessun $m in Z$ che divide $0$
Possiamo quindi già dire che la relazione non è di equivalenza né di ordine. Sembra strano però che abbia già finito l'esercizio
Dove sbaglio?
Sia $m in Z$ e sia $R$ la relazione binaria in $Z$ definita ponendo $AAx, y in Z, xRy iff m|x^3-y^3$
Stabilire se la relazione è di equivalenza e stabilire se è di ordine.
So che una relazione è di equivalenza se rispetta le 3 proprieta elencate di seguito ovvero:
$AAx in S, xRx$ (riflessiva)
$AAx, y in S, xRy rArr yRx$ (simmetrica)
$AAx, y, z in S, xRy$ e $yRz rArr xRz$ (transitiva)
Per la relazione d'ordine invece so che abbiamo le stesse proprietà della relazione d'equivalenza, cambia solo la simmetrica che diventa asimmetrica e quindi:
$AAx, y in S, xRy$ ma non accade che $yRx$ (asimmetrica)
Adesso, riprendendo l'esercizio proprosto prima, credo che la relazione non sia riflessiva in quanto ad esempio prendendo $x = 3$ abbiamo che $3^3 - 3^3 = 0$, pertanto non può esserci nessun $m in Z$ che divide $0$
Possiamo quindi già dire che la relazione non è di equivalenza né di ordine. Sembra strano però che abbia già finito l'esercizio
Dove sbaglio?
Risposte
1. Non mi risulta che una relazione binaria per essere una relazione d'ordine debba essere asimmetrica: deve essere piuttosto antisimmetrica, i.e. \( \forall x,y \in S, x \sim y \land y \sim x \implies x = y \).
2. Non mi risulta che non esistano interi che siano divisori di \( 0 \): dati due interi \( a, b \), si dice che \( a \) divide \( b \) (o che \( a \) è un divisore di \( b \) o che \( b \) è un multiplo di \( a \)) se esiste un intero \( c \) t.c. \( a \cdot c = b \), sicché, poiché qualunque intero moltiplicato per \( 0 \) fa \( 0 \), tutti gli interi sono divisori di \( 0 \).
2. Non mi risulta che non esistano interi che siano divisori di \( 0 \): dati due interi \( a, b \), si dice che \( a \) divide \( b \) (o che \( a \) è un divisore di \( b \) o che \( b \) è un multiplo di \( a \)) se esiste un intero \( c \) t.c. \( a \cdot c = b \), sicché, poiché qualunque intero moltiplicato per \( 0 \) fa \( 0 \), tutti gli interi sono divisori di \( 0 \).
Ti rispondo ad entrambi i punti:
1. Molto strano, ho controllato proprio ora sulle dispense del mio prof. Ti cito il testo alla lettera:
"Sia S un insieme non vuoto. Una relazione binaria in S la diremo d'ordine largo se è riflessiva, asimmetrica e transitiva."
Probabilmente l'errore sta sulle dispense del prof. che mi ha indotto all'errore.
2. In effetti non sapevo che tutti gli interi (anche negativi) dividono 0, ora lo so. Domani vedrò di proseguire nello svolgimento dell'esercizio e ti aggiornerò sui progressi.
1. Molto strano, ho controllato proprio ora sulle dispense del mio prof. Ti cito il testo alla lettera:
"Sia S un insieme non vuoto. Una relazione binaria in S la diremo d'ordine largo se è riflessiva, asimmetrica e transitiva."
Probabilmente l'errore sta sulle dispense del prof. che mi ha indotto all'errore.
2. In effetti non sapevo che tutti gli interi (anche negativi) dividono 0, ora lo so. Domani vedrò di proseguire nello svolgimento dell'esercizio e ti aggiornerò sui progressi.
Puoi lasciare il link (se esiste) alle dispense del tuo Professore?
Spiego.
Tu dai scritto:
Quando si da il nome di proprietà asimmetrica a questa proprietà, allora si da il nome di proprietà antisimmetrica alla seguente proprietà: \( \forall x, y \in S, x R y \land y R x \implies x = y \). Ci sono tuttavia alcuni testi sui quali si scambia l'uso dei termini asimmetrica ed antisimmetrica ed altri testi nei quali si usa il solo termine asimmetrica ma riferendolo alla condizione \( \forall x, y \in S, x R y \land y R x \implies x = y \). Tutto sta quindi nel capire quale convenzione è stata adottata nel testo cui stai facendo riferimento.
In ogni caso, data una relazione binaria \( \mathfrak{R} \) in un insieme \( S \), questa è d'ordine se e solo se valgono le proprietà seguenti:
P1) \( \forall x \in S, x \mathfrak{R} x \);
P2) \( \forall x,y \in S, x \mathfrak{R} y \land y \mathfrak{R} x \implies x = y \);
P3) \( \forall x,y,z \in S, x \mathfrak{R} y \land y \mathfrak{R} z \implies x \mathfrak{R} z \).
Spiego.
Tu dai scritto:
"GlassPrisoner91":
cambia solo la simmetrica che diventa asimmetrica e quindi:
\( \forall x,y \in S,xRy \) ma non accade che \( yRx \) (asimmetrica)
Quando si da il nome di proprietà asimmetrica a questa proprietà, allora si da il nome di proprietà antisimmetrica alla seguente proprietà: \( \forall x, y \in S, x R y \land y R x \implies x = y \). Ci sono tuttavia alcuni testi sui quali si scambia l'uso dei termini asimmetrica ed antisimmetrica ed altri testi nei quali si usa il solo termine asimmetrica ma riferendolo alla condizione \( \forall x, y \in S, x R y \land y R x \implies x = y \). Tutto sta quindi nel capire quale convenzione è stata adottata nel testo cui stai facendo riferimento.
In ogni caso, data una relazione binaria \( \mathfrak{R} \) in un insieme \( S \), questa è d'ordine se e solo se valgono le proprietà seguenti:
P1) \( \forall x \in S, x \mathfrak{R} x \);
P2) \( \forall x,y \in S, x \mathfrak{R} y \land y \mathfrak{R} x \implies x = y \);
P3) \( \forall x,y,z \in S, x \mathfrak{R} y \land y \mathfrak{R} z \implies x \mathfrak{R} z \).
"GlassPrisoner91":
2. In effetti non sapevo che tutti gli interi (anche negativi) dividono 0, ora lo so.
Ne dubito molto, non dirmi che non ti è mai capitato, dalle medie finora, un caso simile $0/5=0$ ? O questo $0/11=0$ ?
"G.D.":
Puoi lasciare il link (se esiste) alle dispense del tuo Professore?
[url]mega:#F!kdoj1SbS!j1nV2icAgc75UXPh1yenVg[/url]
La dispensa in questione è il pdf "cap 1-2"
"axpgn":
Ne dubito molto, non dirmi che non ti è mai capitato, dalle medie finora, un caso simile $ 0/5=0 $ ? O questo $ 0/11=0 $ ?
Certo, hai ragione, in effetti mi è sfuggita una sciocchezza.
Riprendendo l'esercizio, allora...
La relazione è quindi riflessiva in quanto $x$ è in relazione con se stesso, ovvero nel caso $x = 2$ ad esempio, abbiamo che $2^3 - 2^3 = 8 - 8 = 0$, e come abbiamo detto $EE m in Z : m|0$. Quindi in questo caso $m$ è uguale a tutti i numeri interi positivi e negativi.
La relazione non è simmetrica, correggetemi se sbaglio, in quanto presi come esempio $x = 2$ e $y = 3$ si ha che $2^3 - 3^3 = -19$. Ora, gli unici numeri che dividono $-19$ sono $-1$ e $-19$, quindi $m$ può essere uguale a $-1$ o $-19$. Pertanto in questo caso dire che $xRy$ non è lo stesso di $yRx$ perchè in quest'ultimo caso abbiamo che $3^2 - 2^3 = 19$ perciò $m = 1$ o $19$
Infine la relazione è transitiva in quanto, per farla breve, $m = -1$ divide sia $x^3 - y^3$ che $y^3 - z^3$ quindi $x^3 - z^3$
(Non ho capito però se nell'esercizio la condizione da controllare è se $EE m in Z$ oppure $AA m in Z$)
Tuttavia temo di aver sbagliato qualcosa nell'esercizio.
La relazione è quindi riflessiva in quanto $x$ è in relazione con se stesso, ovvero nel caso $x = 2$ ad esempio, abbiamo che $2^3 - 2^3 = 8 - 8 = 0$, e come abbiamo detto $EE m in Z : m|0$. Quindi in questo caso $m$ è uguale a tutti i numeri interi positivi e negativi.
La relazione non è simmetrica, correggetemi se sbaglio, in quanto presi come esempio $x = 2$ e $y = 3$ si ha che $2^3 - 3^3 = -19$. Ora, gli unici numeri che dividono $-19$ sono $-1$ e $-19$, quindi $m$ può essere uguale a $-1$ o $-19$. Pertanto in questo caso dire che $xRy$ non è lo stesso di $yRx$ perchè in quest'ultimo caso abbiamo che $3^2 - 2^3 = 19$ perciò $m = 1$ o $19$
Infine la relazione è transitiva in quanto, per farla breve, $m = -1$ divide sia $x^3 - y^3$ che $y^3 - z^3$ quindi $x^3 - z^3$
(Non ho capito però se nell'esercizio la condizione da controllare è se $EE m in Z$ oppure $AA m in Z$)
Tuttavia temo di aver sbagliato qualcosa nell'esercizio.
Stai facendo un po' di confusione.
Iniziamo con la questione proprietà asimmetrica o proprietà antisimmetrica.
Nel PDF che hai linkato, a pag. 13 si pone:
dopo di che a pag. 14 si pone (coerentemente con quanto sopra):
Mentre tu avevi scritto
Hai quindi scambiato (relativamente alla convenzione usata nel PDF) la formula associata alla proprietà asimmetrica con quella associata alla proprietà antisimmetrica, probabilmente enunciata a lezione: da questo scambio è nato il mio intervento, ovviamente incoerente con le posizioni assunte nel tuo PDF.
Veniamo adesso all'esercizio.
La traccia dice:
Non si fanno ipotesi su \( m \in \mathbb{Z} \) e tale \( m \) va scelto prima di andare a considerare la relazione \( \mathfrak{R} \): quindi non devi andare a trovare l'intero \( m \) che rende la relazione una relazione d'equivalenza/d'ordine ma devi supporre assunto a priori un qualunque intero \( m \) e verificare se la relazione è d'equivalenza/d'ordine. Non so se rendo l'idea.
Inoltre la prova della validità della proprietà riflessiva/simmetrica/asimmetrica/transitiva non va prodotta per esempi: per esempi (più propriamente per controesempi) si prova che una proprietà non vale per tutti gli elementi di un dato insieme, la prova che una data proprietà vale per tutti gli elementi di un insieme va prodotta con una dimostrazione.
Uso la proprietà riflessiva per spiegare queste due cose a proposito dell'esercizio.
Scelto a priori un qualunque \( m \in \mathbb{Z} \), la relazione è riflessiva perché \( x^{3}-x^{3} = 0 \) e qualunque sia \( m \in \mathbb{Z} \) si ha che \( m \cdot 0 = 0 = x^{3} - x^{3} \), sicché \( m \mid x^{3} - x^{3} \).
La relazione a me risulta anche simmetrica e, come hai scritto, transitiva.
Iniziamo con la questione proprietà asimmetrica o proprietà antisimmetrica.
Nel PDF che hai linkato, a pag. 13 si pone:
Sia \( S \) un insieme e sia \( \mathfrak{R} \) una relazione binaria in \( S \), diremo che:
(1) \( \mathfrak{R} \) è riflessiva se \( \forall x \in S, x \mathfrak{R} x \)
(2) \( \mathfrak{R} \) è simmetrica se \( \forall x,y \in S, x \mathfrak{R} y \implies y \mathfrak{R} x \)
(3) \( \mathfrak{R} \) è transitiva se \( \forall x,y,z \in S, x \mathfrak{R} y \text{ e } y \mathfrak{R} z \implies x \mathfrak{R} z \)
(4) \( \mathfrak{R} \) è asimmetrica se \( \forall x,y \in S, x \mathfrak{R} y \text{ e } y \mathfrak{R} x \implies x = y \)
(5) \( \mathfrak{R} \) è antiriflessiva se \( \forall x \in S, x \cancel{\mathfrak{R}} x \)
dopo di che a pag. 14 si pone (coerentemente con quanto sopra):
Sia \( S \) un insieme non vuoto. Una relazione binaria in \( S \) la diremo di ordine largo se è riflessiva, asimmetrica e transitiva.
Mentre tu avevi scritto
Per la relazione d'ordine invece so che abbiamo le stesse proprietà della relazione d'equivalenza, cambia solo la simmetrica che diventa asimmetrica e quindi:
\( \forall x,y \in S, xRy \) ma non accade che \( y R x \) (asimmetrica)
Hai quindi scambiato (relativamente alla convenzione usata nel PDF) la formula associata alla proprietà asimmetrica con quella associata alla proprietà antisimmetrica, probabilmente enunciata a lezione: da questo scambio è nato il mio intervento, ovviamente incoerente con le posizioni assunte nel tuo PDF.
Veniamo adesso all'esercizio.
La traccia dice:
Sia $ m in Z $ e sia $ R $ la relazione binaria in $ Z $ definita ponendo $ AAx, y in Z, xRy iff m|x^3-y^3 $
Stabilire se la relazione è di equivalenza e stabilire se è di ordine.
Non si fanno ipotesi su \( m \in \mathbb{Z} \) e tale \( m \) va scelto prima di andare a considerare la relazione \( \mathfrak{R} \): quindi non devi andare a trovare l'intero \( m \) che rende la relazione una relazione d'equivalenza/d'ordine ma devi supporre assunto a priori un qualunque intero \( m \) e verificare se la relazione è d'equivalenza/d'ordine. Non so se rendo l'idea.
Inoltre la prova della validità della proprietà riflessiva/simmetrica/asimmetrica/transitiva non va prodotta per esempi: per esempi (più propriamente per controesempi) si prova che una proprietà non vale per tutti gli elementi di un dato insieme, la prova che una data proprietà vale per tutti gli elementi di un insieme va prodotta con una dimostrazione.
Uso la proprietà riflessiva per spiegare queste due cose a proposito dell'esercizio.
Scelto a priori un qualunque \( m \in \mathbb{Z} \), la relazione è riflessiva perché \( x^{3}-x^{3} = 0 \) e qualunque sia \( m \in \mathbb{Z} \) si ha che \( m \cdot 0 = 0 = x^{3} - x^{3} \), sicché \( m \mid x^{3} - x^{3} \).
La relazione a me risulta anche simmetrica e, come hai scritto, transitiva.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo