Esercizio relazione binaria: d'ordine o d'equivalenza con numeri primi

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

Esercizio relazione binaria: d'ordine o d'equivalenza con numeri primi #71719

avt
mori800
Punto
Salve, l'esercizio che propongo dà una relazione binaria e chiede di determinare se si tratta di una relazione d'equivalenza o d'ordine. È definito nello stesso insieme di uno fatto pochi giorni fa ma presenta una piccola differenza nella traccia.

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

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \vee  p_1 \cdot   q_1 = 21

Stabilire se \mathfrak{R} è una relazione d'ordine o una relazione d'equivalenza.


Così come Galois mi ha mostrato negli altri esercizi, parto dal dimostrare prima riflessività e transitività e poi, eventualmente, antisimmetria o simmetria.

Riflessività

Presi p_1 e p_2 \in S devo verificare che:

p_1p_2 \ \mathfrak{R} \ p_1p_2 \iff p_1 = p_1 \vee p_1 \cdot p_1 = 21

Ora, p_1 = p_1 è sempre verificato.

Ma non c'è un numero primo che moltiplicato per se stesso dia come risultato 21. A questo punto non so come procedere perché non sono sicuro che la proprietà sia verificata.
Onde evitare di creare un botta e risposta poco usufruibile dagli altri utenti, chiedo se sia possibile, a chi mi risponderà, completare anche sinteticamente questo esercizio.
Così eviterò di aprire un altro post per verificare l'eventuale soluzione

Grazie
 
 

Esercizio relazione binaria: d'ordine o d'equivalenza con numeri primi #71752

avt
Galois
Coamministratore
Rieccoci qui mori800 emt

Noto con piacere che piano piano inizi a prenderci la mano e che, ancora una volta, purtroppo, sei stato tradito dall'errata lettura della traccia dell'esercizio.

Abbiamo l'insieme

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

e la seguente relazione definita sugli elementi di S:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \vee  p_1 \cdot   q_1 = 21

Attenzione al connettivo logico \vee . È il caso di spendere due parole.

Date due proposizioni P \ \mbox{e} \  Q:

P \ \vee \ Q

è una nuova proposizione la quale è vera solo nel caso in cui almeno una delle due proposizioni da cui è formata è vera mentre è falsa quando tutte e due sono false.

Alla luce di ciò torniamo alla definizione della nostra relazione

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \vee  p_1 \cdot   q_1 = 21

Per com'è definito il connettivo logico \vee che lega le due proposizioni:

p_1=q_1, \ p_1 \cdot q_1 = 21

Abbiamo che i due elementi di S: p_1p_2 \ \mbox{e} \ q_1q_2 sono in relazione tramite \mathfrak{R} se e solo se almeno una delle due è vera, cioè non devono essere, necessariamente, vere entrambe.

Chiarito questo andiamo a vedere se la nostra è una relazione d'ordine o una relazione d'equivalenza. Partiamo dalla proprietà riflessiva.

Riflessività

Sia p_1p_2 \in S

Affinché la nostra relazione sia riflessiva deve valere

p_1=p_1 \ \vee \ p_1 \cdot p_1=21

Ora, essendo, ovviamente, p_1=p_1, una delle due proposizioni che definiscono la relazione è verificata, ragion per cui

p_1p_2 \ \mathfrak{R} \ p_1p_2.

Transitività

Siano p_1p_2, \ q_1q_2, \ t_1t_2 \in S tali che

p_1p_2 \mathfrak{R} q_1q_2 \ \mbox{e} \ q_1q_2 \mathfrak{R} t_1t_2 (ipotesi)

Affinché la nostra relazione sia transitiva deve valere:

p_1p_2 \mathfrak{R} t_1t_2 (tesi)

Iniziamo con l'esplicitare la prima ipotesi:

p_1p_2 \mathfrak{R} q_1q_2 \iff p_1=q_1 \ \vee \ p_1 \cdot q_1 = 21

Osserviamo che, non essendo 21 un quadrato perfetto non esisterà alcun numero (a maggior ragione primo) che moltiplicato per se stesso dia 21. Ne segue che le due condizioni che definiscono la nostra relazione non si possono verificare contemporaneamente. Ragioniamo quindi per casi:

\bullet \ \mbox{Supponiamo che valga} \ p_1=q_1

Ora, per la seconda ipotesi:

q_1q_2 \mathfrak{R} t_1t_2 \iff q_1=t_1 \ \vee \ q_1 \cdot t_1 = 21

Poiché stiamo supponendo che sia p_1=q_1

sostituendo p_1 al posto di q_1 abbiamo:

p_1=t_1 \ \vee \ p_1 \cdot t_1 = 21

il che implica: p_1p_2 \ \mathfrak{R} t_1t_2

Per ora ci siamo. Non abbiamo finito però. Dobbiamo vedere cosa accade

\bullet \ \mbox{Supponendo che valga} \ p_1 \cdot q_1=21

Essendo p_1 \ \mbox{e} \ q_1 due numeri primi,

p_1 \cdot q_1=21 \iff p_1=3 \ \mbox{e} \ q_1=7 \ \ \mbox{oppure} \ p_1=7 \ \mbox{e} \ q_1=3

In entrambi i casi, per la seconda ipotesi fatta:

q_1q_2 \mathfrak t_1t_2 \iff q_1=t_1 \ \vee \ q_1 \cdot t_1 = 21

Ora, se viene verificata la prima condizione (q_1=t_1) allora, se

q_1=3=t_1, \ p_1=7 (per quanto detto prima)

e di conseguenza p_1 \cdot t_1 = 21 ovvero

p_1p_2 \mathfrak{R} t_1t_2

Mentre se

q_1=7=t_1, \ p_1=3 (per quanto detto prima)

ed ancora p_1 \cdot t_1 = 21 ovvero

p_1p_2 \mathfrak{R} t_1t_2

Se invece della seconda ipotesi viene soddisfatta la seconda condizione:

q_1 \cdot t_1 = 21

potendo essere q_1=7 \ \mbox{da cui} \ p_1=3

oppure

q_1=3 \ \mbox{da cui} \ p_1=7

si avrà, nel primo caso:

t_1 =\frac{21}{7} = 3 = p_1

nel secondo

t_1 =\frac{21}{3} = 7 = p_1

Ad ogni modo sarà quindi

p_1p_2 \mathfrak{R} t_1t_2

ovvero la relazione è transitiva.


Ora, basta osservare che l'uguaglianza tra due numeri è, indubbiamente, una relazione simmetrica:

p_1=q_1 \iff q_1=p_1

inoltre il prodotto gode della proprietà commutativa, cioè

p_1 \cdot q_1 = q_1 \cdot p_1

Alla luce di queste due banali osservazioni possiamo concludere che la nostra relazione:

p_1p_2 \ \mathfrak{R} \ q_1q_2 \iff p_1=q_1 \vee  p_1 \cdot   q_1 = 21

gode anche della proprietà simmetrica, ovvero

p_1p_2 \ \mathfrak{R} \ q_1q_2 \Rightarrow q_1q_2 \ \mathfrak{R} \ p_1p_2

La nostra relazione è quindi d'equivalenza.

emt
Ringraziano: Omega, Pi Greco, Ifrit, CarFaby, mori800

Esercizio relazione binaria: d'ordine o d'equivalenza con numeri primi #71766

avt
mori800
Punto
Ciao Galois, spero di portarti via sempre meno tempo con i prossimi esercizi!

Riguardo alla soluzione non posso fare altro che constatare che l'approssimazione con cui interpreto la traccia continua a farmi sbagliare.
Detto ciò, avrei due domande sull'esercizio entrambe legate all'operatore \vee e alla possibilità che dà di utilizzare una sola delle due condizioni per verificare le proprietà della relazione.

In particolare, abbiamo ritenuto la proprietà riflessiva valida perchè almeno una delle due condizioni veniva rispettata (p_1=p_1).

Quello che mi chiedo è: quando abbiamo dimostrato la transitività, potevamo bloccare la dimostrazione quando ci siamo accorti che

p_1 = t_1\ \Rightarrow\ p_1p_2\ R\ t_1t_2 ?

Senza valutare, in pratica, la seconda condizione?

La seconda domanda scaturisce da questa perché, ragionando allo stesso modo per la simmetria, avrei potuto facilmente dimostrare che

p_1p_2\ R\ q_1q_2\ \iff\ p_1=p_2\ \ \wedge\ \ q_1q_2\ R\ t_1t_2\ \iff\ p_2=p_1

trovare che

p_1=p_2

mi avrebbe portato ad affermare, erroneamente, che era dimostrata l'antisimmetria della relazione. Errore che non avrei commesso valutando anche la seconda delle condizioni.

In sostanza è vero che l'operatore \vee permette di utilizzare anche solo una delle due condizioni per dimostrare una proprietà ma è sempre necessario valutarle tutte onde evitare erronee considerazioni?

Esercizio relazione binaria: d'ordine o d'equivalenza con numeri primi #71777

avt
Galois
Coamministratore
In realtà è proprio per com'è definito il connettivo logico \vee che dobbiamo andare a verificare entrambe le condizioni.

Cerco di spiegarmi meglio.

Per quanto riguarda la verifica della proprietà transitiva abbiamo supposto

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

per poi vedere se (sempre e comunque) vale:

p_1p_2 \mathfrak{R} t_1t_2

cioè, la proprietà transitiva così come tutte le altre, deve valere per ogni coppia di elementi che si scelgono nell'insieme S.

La prima ipotesi:

p_1p_2 \mathfrak{R} q_1q_2

vale a patto che venga verificata almeno una delle due condizioni:

p_1=q_1 \ \vee \ p_1 \cdot q_1 = 21

Poiché la validità dell'una non implica la validità dell'altra (non per niente ho fatto questa osservazione)


Osserviamo che, non essendo 21 un quadrato perfetto non esisterà alcun numero (a maggior ragione primo) che moltiplicato per se stesso dia 21. Ne segue che le due condizioni che definiscono la nostra relazione non si possono verificare contemporaneamente.


Dobbiamo per forza distinguere i due casi, quello in cui vale la prima delle due condizioni (che automaticamente esclude la validità della seconda) e quello in cui vale la seconda (che esclude la prima).

Escludendo dall'esame, come tu proponi, la verifica della seconda condizione non possiamo concludere nulla. Cioè, se prendiamo due elementi di S p_1p_2 \ \mbox{e} \ q_1q_2 tali da soddisfare la seconda condizione che definisce la relazione che succede? Dobbiamo verificarlo! emt

Per quanto riguarda l'antisimmetria, se la relazione fosse antisimmetrica (e non lo è) dovrebbe valere:

p_1p_2 \mathfrak{R} q_1q_2 \ \mbox{e} \ q_1q_2 \mathfrak{R} p_1p_2 \Rightarrow p_1p_2=q_1q_2

per qualunque coppia di elementi appartenenti ad S

Se prendo ad esempio:

p_1=q_1=5, \ p_2=3, \ q_2=11

allora

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

in quanto p_1=q_1

ma, come puoi vedere

p_1p_2 \neq q_1q_2
Ringraziano: Omega, Pi Greco, mori800
  • Pagina:
  • 1
Os