Relazione d'ordine o di equivalenza?

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.
#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 = p_1p_2 | p_1, p_2 sono primi e 2 ≤ p_1 ≤ p_2

si consideri la relazione binaria definita dalla posizione ed una relazione mathfrakR sugli elementi di S definita da:

p_1p_2 mathfrakR q_1q_2 ⇔ p_1 = q_1 e p_2 ≤ q_2

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

Io ho proceduto così

- Riflessiva: p_1 = p_1 e p_2 ≤ 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 ≤ q_2, p_2 ≤ p_2  →  p_2 = q_2.

- Transitiva: considerati m,n due elementi di S

p_1 = q_1, q_1 = m ⇒ p_1 = m

e

p_2 ≤ q_2, q_2 ≤ n ⇒ p_2 ≤ 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 ≤ q_2 e q_2 ≤ p_2 vera per q_2 = p_2, o no?

Grazie

#71581
avt
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 = p_1p_2 | p_1, p_2 sono primi e 2 ≤ p_1 ≤ p_2

ed una relazione R sugli elementi di S definita da:

p_1p_2 mathfrakR q_1q_2 ⇔ p_1 = q_1 e p_2 ≤ 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 ∈ S.

Dobbiamo far vedere che

p_1p_2 mathfrakR p_1p_2

ovvero che

p_1 = p_1 e p_2 ≤ 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 mathfrakR q_1q_2 ⇔ p_1 = q_1 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 e q_1q_2

di S.

Supponendo che

p_1p_2 mathfrakR q_1q_2 ∧ q_1q_2 mathfrakR p_1p_2

dobbiamo dimostrare che:

p_1p_2 = q_1q_2

Ora:

p_1p_2 mathfrakR q_1q_2 ⇔ p_1 = q_1 e p_2 ≤ q_2

mentre:

q_1q_2 mathfrakR p_1p_2 ⇔ q_1 = p_1 e q_2 ≤ p_2

Da cui segue che:

p_1 = q_1 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 mathfrakR q_1q_2 e q_1q_2 mathfrakR t_1t_2

dobbiamo dimostrare che:

p_1p_2 mathfrakR t_1t_2

Ora, da

p_1p_2 mathfrakR q_1q_2

segue che

p_1 = q_1 e p_2 ≤ q_2

mentre da

q_1q_2 mathfrakR t_1t_2

si ha

q_1 = t_1 e q_2 ≤ t_2

Ovvero, mettendo insieme i due risultati:

p_1 = q_1 = t_1 ⇒ p_1 = t_1

e

p_2 ≤ q_2 ≤ t_2 ⇒ p_2 ≤ 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 e q_1q_2

sono due elementi di S, allora:

p_1p_2 mathfrakR q_1q_2 oppure q_1q_2 mathfrakR p_1p_2

Tale proprietà non è, evidentemente, soddisfatta!

Prendi ad esempio p_1 = 2 e q_1 = 3

Essendo p_1 ≠ 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
#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 ⇔ p_1 = q_1 ∧ p_2 ≤ q_2 .

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

p_1 = p_2 ∧ q_1 ≤ 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!

#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, e a_2 due suoi elementi, diremo che una relazione mathfrakR definita su X è antisimmetrica se e solo se:

a_1 mathfrakR a_2 ∧ a_2 mathfrakR a_1 ⇒ 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 mathfrakR per vedere se è antisimmetrica prendiamo due elementi di S

p_1p_2 e q_1q_2

e supponiamo, cioè assumiamo che:

p_1p_2 mathfrakR q_1q_2

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

e

q_1q_2 mathfrakR 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 mathfrakR q_1q_2

per com'è definita la nostra relazione si ha:

(1) p_1 = q_1 e p_2 ≤ q_2

Ancora, avendo supposto che

q_1q_2 mathfrakR p_1 = p_2

si ha

(2) q_1 = p_1 e q_2 ≤ p_2

Mettendo insieme (1) e (2) abbiamo:

p_1 = q_1

e

p_2 ≤ q_2, q_2 ≤ 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