Verificare se una relazione è d'ordine non totale

[gaten]

Salve ragazzi.

Nel prodotto cartesiano $NxN^star$ si consideri la seguente relazione:

$(a,b)pi_1(c,d) <=> (a,b)=(c,d) oppure a^2+b^2
devo verificare se $pi_1$ è una relazione d'ordine non totale in $NxN^star$

in primis, verifico che $pi_1$ è soddisfa le proprietà di riflessività, antisimmetria e transitività:

1)riflessività:

$ AA (a,b) in NxN^star, (a,b)=(a,b) $

2)antisimmetria:

$ AA (a,b),(c,d) in NxN^star, (a,b) pi_1 (c,d) e (c,d) pi_1 (a,b) => (a,b)=(c,d) $

3) transitività:

$ AA (a,b),(c,d),(e,f) in NxN^star, (a,b) pi_1 (c,d) e (c,d) pi_1 (e,f) => (a,b) pi_1 (e,f) $

come verifico l'ultima proprietà?
Inoltre per l'antisimmetria, ho verificato solamente che $(a,b)=(c,d)$ anche perchè la relazione è soddisfatta se è verificata una delle proprità( o $(a,b)=(c,d) oppure a^2+b^2
L'esercizio chiede anche di trovare gli eventuali minimo, massimo, elementi minimali, elementi massimali.

per il minimo, dovrei verificare se;

$ EE (c,d) in NxN^star tale che AA (a,b) in NxN^star, (c,d) pi_1 (a,b)$, analogamente per il massimo. Ma nel mio caso come lo verifico.

Grazie anticiptamente.

[Simonixx]

Ok, vedo di aiutarti...

1. Riflessività verificata.

2. Antisimmetria... il tuo ragionamento è giusto, anche se farei un piccolo approfondimento, lavorerei per casi.
Supponiamo che la relazione per le coppie $(a, b), (c, d)$ sia verifica per il fatto che $(a,b) = (c,d)$. Dunque sicuramente sono in relazione d'ordine tra loro e, date le ipotesi dell'antisimmetria, presentano l'uguaglianza (data già per ipotesi).
Supponiamo invece che la relazione tra le due coppie sia date perchè $(a, b)pi(c,d)$ perchè $a^2 + b^2 < c^2 + d^2$ e viceversa (quindi siamo nelle ipotesi dell'antisimmetria). Dunque ipotizzando ciò andiamo ad avere una contraddizione, ovvero o la prima somma è minore della seconda, o la seconda è minore della prima, non può verificarsi una situazione del genere! (questo anche perchè la relazione d'ordine data dal segno di "minore" è totale, ovvero "o avviene che $x < y$ o avviene che $y < x$ almeno per i numeri reali... e siccome che i numeri naturali sono contenuti nei reali stiamo apposto!)
Dunque non può accadere nell'ipotesi dell'antisimmetria,che siano in correlazione per questo motivo, dunque possono esserlo SOLO poichè le due coppie sono uguali, e in quest'ipotesi è verificata sempre, ovviamente, la proprietà di antisimmetria.

3. Transitività.

Lavoriamo ancora per casi, così ti faccio vedere bene cosa accade.
Seguiamo il caso più banale, che le coppie siano in relazione poichè sono uguali fra loro. E' ovvio che è valida la transitività.
Ora sono banali anche i casi per cui $(a,b) = (c,d)$ oppure $(c,d) = (e,f)$.
Dunque andiamo al caso per cui la relazione d'ordine tra le coppie sia data dalla disuguaglianza.

$(a,b)pi(c,d) -> a^2 + b^2 < c^2 + d^2$
$(c,d)pi(e,f) -> c^2 + d^2 < e^2 + f^2$

Dunque posso dire che $a^2 + b^2 < c^2 + d^2 < e^2 + f^2 -> a^2 + b^2 < e^2 + f^2 -> (a,b)pi(e,f)$

Se mi dai la definizione di elementi massimali e minimali vedo di vedere anche il resto, ora devo andare.
Al massimo do anche uno sguardo sul web a proposito più tardi...

[gaten]

"Simonixx":
Supponiamo invece che la relazione tra le due coppie sia date perchè $(a, b)pi(c,d)$ perchè $a^2 + b^2 < c^2 + d^2$ e viceversa (quindi siamo nelle ipotesi dell'antisimmetria). Dunque ipotizzando ciò andiamo ad avere una contraddizione, ovvero o la prima somma è minore della seconda, o la seconda è minore della prima, non può verificarsi una situazione del genere! (questo anche perchè la relazione d'ordine data dal segno di "minore" è totale, ovvero "o avviene che $x < y$ o avviene che $y < x$ almeno per i numeri reali... e siccome che i numeri naturali sono contenuti nei reali stiamo apposto!)
Dunque non può accadere nell'ipotesi dell'antisimmetria,che siano in correlazione per questo motivo, dunque possono esserlo SOLO poichè le due coppie sono uguali, e in quest'ipotesi è verificata sempre, ovviamente, la proprietà di antisimmetria.

Potresti chiarirmi meglio questa cosa? Grazie.

Inoltre mi chiedevi la definizione di elementi massimali, minimali, massimi e minimi:

Supponiamo $(S,<=)$ un ordine, se esiste un $m in S : AAa in S, m <= a $ m è detto elemento minimo. Analogamente per il massimo:
$m in S : AAa in S, a <= m $

$m$ è elemento minimale:
$ AA a in S, a <= m => a=m $

$M$ sarà elemento massimale se:
$ AA a in S, M <= a => a=M$

[Simonixx]

Allora, ricapitolando le ipotesi dell'antisimmetria sono:

$(a,b)pi(c,d)$ e $(c,d)pi(a,b)$

Se suppongo che non siano dovute al fatto che $(a,b) = (c,d)$ (ed in questo caso l'antisimmetria è verificata), allora suppongo che lo siano perchè $a^2 + b^2 < c^2 + d^2$ e $c^2 + d^2 < a^2 + b^2$ .

Ma questo non può verificarsi, chiamiamo $t = a^2 + b^2 , s = c^2 + d^2 -> t < s , s < t$

Siamo in una contraddizione: la relazione d'ordine data dal segno di minore è totale, o avviene la prima ipotesi o avviene la seconda ma non entrambe, e l'unica possibilità per cui avvengano entrambe è che siano uguali, ovvero che siamo nell'ipotesi prima ancora considerata... (ovvero che l'antisimmetria sia verificabile, dunque convalidata solo se $(a,b) = (c,d)$)...

Grazie delle definizioni, se dopo ho tempo continuo l'esercizio!

Comunque intanto potresti verificare se questa relazione d'ordine è totale o no...

p.s.: per vedere quali siano massimo, minimo, minimali, massimali ricordati che stai lavorando con coppie di numeri NATURALI. Inoltre, dovresti vedere se, per come lo avete definito voi, $N$ contenga o meno lo 0... (alcuni prof. non ne fanno uso per i numeri naturali, ma lo definiscono già dagli interi..)... Non è difficile: se hai problemi sia con questi che con la verifica della relazione totale dopo ti continuo l'esercizio... (che già ho fatto! e non è difficile!)

[Studente Anonimo]

Osservo che più in generale dati [tex]X[/tex] un insieme qualunque e [tex]A[/tex] un insieme ordinato, [tex]f:X \to A[/tex] una qualsiasi funzione (nel tuo caso, [tex]X=\mathbb{N} \times \mathbb{N}^{\ast}[/tex], [tex]A=\mathbb{N}[/tex] e [tex]f:X \to A[/tex] manda [tex](x,y)[/tex] in [tex]x^2+y^2[/tex]), la relazione [tex]\leq[/tex] su [tex]X[/tex] definita da "[tex]x \leq y[/tex] se [tex]x=y[/tex] oppure [tex]f(x) < f(y)[/tex]" e' una relazione d'ordine su [tex]X[/tex].

Inoltre due elementi distinti di [tex]X[/tex] sono confrontabili tramite [tex]\leq[/tex] se e solo se hanno immagini distinte e confrontabili in [tex]A[/tex]. Ne segue che se l'ordine su [tex]A[/tex] è totale allora l'ordine [tex]\leq[/tex] su [tex]X[/tex] è totale se e solo se [tex]f[/tex] e' iniettiva (e in tal caso possiamo pensare a [tex]X[/tex] come a un sottoinsieme di [tex]A[/tex] con l'ordine indotto, identificandolo con [tex]f(X)[/tex]).

Un elemento [tex]x \in X[/tex] è minimale (risp. massimale) se e solo se [tex]f(x)[/tex] è minimale (risp. massimale) in [tex]f(X)[/tex].

Un elemento [tex]x \in X[/tex] è il minimo (risp. massimo) di [tex]X[/tex] se e solo se [tex]f(x)[/tex] è il minimo di [tex]f(X)[/tex] e [tex]x[/tex] è la sola controimmagine di [tex]f(x)[/tex] in [tex]X[/tex].

[gaten]

Simonixx, per verificare se $pi_1$ è totale, dovrei verificare se le seguenti proprietà sono verificate:

$ AA a, a ≤ a $ (riflessività)
se $ a ≤ b$ e $b ≤ a$, allora $a = b$ (antisimmetria)
se $a ≤ b$ e $b ≤ c$ allora $a ≤ c$ (transitività)
$a ≤ b$ oppure $b ≤ a$ (totalità)

Se si verificano queste proprietà, la relazione d'ordine è totale, altrimenti è parziale(come chiede l'esercizio).

ps. Riguardo i massimi, minimi, minimali e massimali, non saprei come verificarli.

Grazie

[Simonixx]

Mi piace come lavora Martino *-* Certo che ancora non sono matematicamente preparato per lavorare così su un questo tipo di esercizio xD

Comunque!

(a,b) è minimo se data una qualsiasi coppia (c,d), $a^2 + b^2 < c^2 + d^2$
Questo accade nei numeri naturali ovviamente con la coppia (0,0) poichè lo zero è minore di qualsiasi altro numero naturale, quindi anche di qualsiasi altra somma che dia un numero naturale. Detto questo possiamo dire che gli elementi minimali non ve ne sono: non c'è una coppia (c,d) tale che se $(a,b)pi(c,d) -> (a,b) = (c,d)$ escludendo (0,0) stesso.
Per quanto riguarda il massimo, siamo nei numeri naturali, non vi è una coppia finita (a,b) tale che, qualsiasi coppia (c,d) che io prenda $(c,d)pi(a,b)$ a parte una coppia di infiniti... ma non si può considerare! Ugualmente non vi sono elementi massimali...

Per sapere se è totale, basta vedere che questa relazione d'ordine, supponendo che le coppie non siano uguali, è definita da una disuguaglianza che è una relazione d'ordine totale nei numeri naturali, dunque o avviene che la prima somma è minore della seconda, o viceversa.

[gaten]

Scusami , Simonix, quindi tu per verificare minimi e massimi fai:

se esiste $(c,d) in NxN^star : AA (a,b) in NxN^star , (c,d) <= (a,b) $ in questo caso $(c,d)$ è detto minimo di $NxN^star$
giusto?

Ma perchè consideri? $a^2+b^2
(perdona il mio dubbio).

Inoltre, per sapere se è totale bisognerebbe verificare se:
$AA (a,b),(c,d) in NxN^star, (a,b) pi_1 (c,d)$ oppure $(c,d) pi_1 (a,b)$ e nel mio caso come applico tale concetto?

aggiungo che nello stesso esercizio, chiede:

Posto $X={(1,1),(0,1),(2,1),(1,2),(2,2),(4,1)}$ si studi il sottoinsieme ordinato $(X, pi_1)$, disegnando il diagramma di Hasse e determinando eventuali minimi, massimi, minimali, massimali, minoranti, maggioranti, est. inferiore e est. superiore in NxN*.

Seguendo il tuo ragionamento direi che la coppia $(0,1)$ rappresenta il minimo dell'insieme $X$, in quanto

la somma 0+1 è sempre < rispetto alla somma degli elementi che formano le altre coppie.(sbaglio?)
Mentre 4+1 è sempre > rispetto alla somma degli elementi che formano le altre coppie (quindi rappresenta il massimo).

[Simonixx]

Guarda che lo hai detto te! Definendo in quel modo il minimo stai dicendo che $(a,b) <= (c,d)$ per qualsiasi coppia (c,d) che si prenda. Ma il concetto è che la nostra relazione d'ordine non è data da $<=$ ma da $pi$ che è data da $a^2 + b^2 < c^2 + d^2$ ed è per questo che verifico ciò per minimi, massimi, el. massimali e minimali!

E' una relazione d'ordine totale perchè per la relazione $<$ che è una relazione totale, o accade $a^2 + b^2 < c^2 + d^2$ o viceversa!


L'esercizio seguente lo stai svolgendo bene: quelli sono il minimo ed il massimo!
Ora, secondo le definizioni, trova il resto!

[gaten]

Simonixx, l'esercizio dice:

Si verifichi che $pi_1$ è una relazione di ordine non totale in $NxN^star$, e si
determinino in $( NxN^star, pi_1)$ gli eventuali minimo, massimo, elementi minimali, elementi massimali.

P.S

"Simonixx":Ma il concetto è che la nostra relazione d'ordine non è data da ≤ ma da π che è data da a2+b2

Ma la relazione è definita per:
$(a,b)=(c,d)$ oppure $a^2+b^2
perchè prendi in considerazione solamente la seconda condizione?

[Simonixx]

Nell'altro caso è tutto banalmente verificato.