Relazione d'ordine o di equivalenza?

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Relazione d'ordine o di equivalenza? #71553

avt
mori800
Punto
Salve, posto un esercizio che chiede di stabilire se una data relazione binaria è una relazione d'ordine o di equivalenza.

Premetto che grazie a YM sono riuscito a migliorare la cultura (blanda) sulle relazioni binarie che i vari testi di algebra che finora avevo consultato mi avevano permesso di acquisire.Tuttavia vorrei verificare alcune risoluzioni cui sto giungendo.
Spero di non rubare troppo tempo.

Allora, l'esercizio in questione è: nell'insieme

S=\left\{p_1p_2 \ | \ p_1, \ p_2 \ \mbox{sono primi e} \ 2 \le p_1 \le p_2\right\}

si consideri la relazione binaria definita dalla posizione ed una relazione \mathfrak{R} sugli elementi di S definita da:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \ \mbox{e} \ p_2 \le q_2

Stabilire se R è una relazione d'ordine o d'equivalenza.


Io ho proceduto così

- Riflessiva: p_1 = p_1 e p_2 \leq p_2 la prima è immediatamente verificata, la seconda è vera perché p_2 = p_2.

[Piccola nota: se il problema mi avesse assegnato p_2 < q_2 la proprietà riflessiva non sarebbe stata verificata, giusto?]

- Antisimmetrica:

p_1 = q_1 immediatamente verificata;

p_2 \leq q_2,\ p_2 \leq p_2\ \rightarrow\ p_2 = q_2.

- Transitiva: considerati m,n due elementi di S

p_1 = q_1,\ q_1 = m\ \Rightarrow\ p_1 = m

e

p_2 \leq q_2,\ q_2 \leq n\ \Rightarrow\ p_2 \leq n

La relazione è d'ordine.

Aggiungerei che è anche totale perché l'uguaglianza della condizione 1 è sempre verificata mentre la disuguaglianza della condizione 2 prevederebbe per tutti gli elementi  p_2 \leq q_2\mbox{ e } q_2 \leq p_2 vera per q_2 = p_2, o no?

Grazie
 
 

Relazione d'ordine o di equivalenza? #71581

avt
Galois
Amministratore
Ciao Mori800 emt

Dal tuo procedimento noto che fai un po' di confusione tra quali sono le ipotesi e su quello che effettivamente devi dimostrare. Detto questo, procediamo emt

Abbiamo un insieme

S=\left\{p_1p_2 \ | \ p_1, \ p_2 \ \mbox{sono primi e} \ 2 \le p_1 \le p_2\right\}

ed una relazione R sugli elementi di S definita da:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \ \mbox{e} \ p_2 \le q_2

Tale relazione è effettivamente una relazione d'ordine, infatti gode della proprietà riflessiva, antisimmetrica e transitiva.

Dimostriamolo!

Riflessività: consideriamo un elemento p_1p_2 \in S.

Dobbiamo far vedere che

p_1p_2 \ \mathfrak{R} \ p_1p_2

ovvero che

p_1=p_1 \ \mbox{e} \ p_2 \le p_2

il che è indubbiamente vero. La nostra relazione è quindi riflessiva.

Se il problema mi avesse assegnato p_2 < q_2 la proprietà riflessiva non sarebbe stata verificata, giusto?


Se la relazione fosse stata definita nel seguente modo:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \ \mbox{e} \ p_2 < q_2

allora no, la relazione non sarebbe stata riflessiva. Torniamo ora a noi.

Antisimmetria: prendiamo ora due elementi

p_1p_2 \ \mbox{e} \ q_1q_2

di S.

Supponendo che

p_1p_2 \ \mathfrak{R} \ q_1q_2 \ \wedge \  q_1q_2 \ \mathfrak{R} \ p_1p_2

dobbiamo dimostrare che:

p_1p_2 = q_1q_2

Ora:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \ \mbox{e} \ p_2 \le q_2

mentre:

q_1q_2 \ \mathfrak{R} \ p_1p_2 \iff q_1=p_1 \ \mbox{e} \ q_2 \le p_2

Da cui segue che:

p_1=q_1 \ \mbox{e} \ p_2=q_2

ovvero:

p_1p_2=q_1q_2

che è proprio quello che volevamo provare.

Transitività: siano p_1p_2, \ q_1q_2, \ t_1t_2 tre elementi di S.

Affinché la nostra relazione sia transitiva, supponendo che:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \ \mbox{e} \ q_1q_2 \ \mathfrak{R} \ t_1t_2

dobbiamo dimostrare che:

p_1p_2 \ \mathfrak{R} \ t_1t_2

Ora, da

p_1p_2 \ \mathfrak{R} \ q_1q_2

segue che

p_1=q_1 \ \mbox{e} \ p_2 \le q_2

mentre da

q_1q_2 \ \mathfrak{R} \ t_1t_2

si ha

q_1=t_1 \ \mbox{e} \ q_2 \le t_2

Ovvero, mettendo insieme i due risultati:

p_1=q_1=t_1 \Rightarrow p_1=t_1

e

p_2 \le q_2 \le t_2 \Rightarrow p_2 \le t_2.

La relazione è quindi transitiva e di conseguenza è una relazione d'ordine.

-------------

Rimane da stabilire se è una relazione d'ordine totale.

Una relazione è d'ordine totale se, presi due qualsiasi di elementi di S, essi sono sempre confrontabili mediante la relazione, ovvero se:

p_1p_2 \ \mbox{e} \ q_1q_2

sono due elementi di S, allora:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \ \mbox{oppure} \ q_1q_2 \ \mathfrak{R} \ p_1p_2

Tale proprietà non è, evidentemente, soddisfatta!

Prendi ad esempio p_1=2 \ \mbox{e} \ q_1 = 3

Essendo p_1 \neq q_1

i due elementi non sono confrontabili tramite la relazione la quale quindi, pur essendo una relazione d'ordine, non è di ordine totale.
Ringraziano: Omega, CarFaby, mori800, darkfog

Relazione d'ordine o di equivalenza? #71588

avt
mori800
Punto
Riguardo all'esercizio: è evidente che non ho saputo focalizzarmi al meglio su ciò che era opportuno dimostrare emt

Ma un dubbio permane e riguarda la dimostrazione dell' antisimmetria. Io, dalla traccia, so che

p_1p_2 R q_1q_2 \iff p_1=q_1 \wedge p_2 \leq q_2 .

Come arrivo a dire che, per essere antisimmetrica si deve verificare che

p_1 = p_2 \wedge q_1 \leq q_2 ?

Cioè, questa nuova posizione che faccio è dovuta alla tesi stessa dell' antisimmetria (p_1p_2 = q_1q_2)?

Farò comunque altri esercizi sulla base della tua spiegazione e dovrò riguardare quelli già fatto prima di leggerla. Grazie tanto per la risposta!

Relazione d'ordine o di equivalenza? #71593

avt
Galois
Amministratore
Per quanto riguarda l'antisimmetria della relazione (che ti sta creando problemi) è bene rivedere la definizione di relazione antisimmetrica.

Preso un insieme A e detti a_1, \ \mbox{e} \ a_2 due suoi elementi, diremo che una relazione \mathfrak{R} definita su X è antisimmetrica se e solo se:

a_1 \mathfrak{R} a_2 \ \wedge \ a_2 \mathfrak{R} a_1 \ \Rightarrow \ a=b

Cioè per dimostrare che una relazione (definita su un insieme) è antisimmetrica dobbiamo considerare due suoi generici elementi e supporre che il primo sia in relazione col secondo ed il secondo col primo.

A questo punto, sfruttando le proprietà della relazione, dobbiamo vedere se i due elementi coincidono. Se è così la relazione è antisimmetrica altrimenti no.

Tornando al nostro insieme S ed alla nostra relazione \mathfrak{R} per vedere se è antisimmetrica prendiamo due elementi di S

p_1p_2 \ \mbox{e} \ q_1q_2

e supponiamo, cioè assumiamo che:

p_1p_2 \ \mathfrak{R} \ q_1q_2

(cioè che il primo elemento è in relazione con il secondo)

e

q_1q_2 \ \mathfrak{R} \ p_1p_2

cioè il secondo è in relazione con il primo.

Tenendo presente questo dobbiamo vedere se i due elementi coincidono, cioè se:

p_1p_2 = q_1q_2

Come lo facciamo? Sfruttando quello che abbiamo supposto!

Poiché:

p_1p_2 \ \mathfrak{R} \ q_1q_2

per com'è definita la nostra relazione si ha:

(1) \ p_1=q_1 \ \mbox{e} \ p_2 \le q_2

Ancora, avendo supposto che

q_1q_2 \ \mathfrak{R} \ p_1=p_2

si ha

(2) \ q_1=p_1 \ \mbox{e} \ q_2 \le p_2

Mettendo insieme (1) e (2) abbiamo:

p_1=q_1

e

p_2 \le q_2, \ q_2 \le p_2

da cui, ovviamente:

p_2=q_2

Da cui ne segue che:

p_1p_2=q_1q_2

cioè i due elementi coincidono e quindi la relazione è antisimmetrica.
Ringraziano: Omega, Pi Greco, CarFaby, mori800
  • Pagina:
  • 1
Os