Esercizo su relazione d'ordine.

[Pasquale 90]

Buonasera,
Se considero la relazione $ le $ in $NN$ definita:

$x le y <=> EE n in NN $ tale che $y=x^n$

provare che $le$ è una relazione d'ordine non totale, e che $(NN, le)$ è privo di minimo e di massimo, inoltre
determinare gli elementi minimali di $(NN,le)$.

Per provare che $le$ è una relazione d'ordine non totale, semplicemente devo esibire una coppia di elementi $x,y$ in $NN$ che non siano confrontabili, ad esempio $x=2$ $y=5$ si ha

$5 ne 2^n \ ,\ forall n in NN , 2 ne 5^n \,\ forall n in NN.$

Per provare che $(NN, le)$ è privo di minimo e di massimo, per il minimo dovrei far vedere che per ogni elemento di $x in NN$ esiste un elemento $y in NN$ tale che $y
Grazie per l'eventuale aiuto .


Ciao

[solaàl]

Chiama \(\mathfrak N = (\mathbb N, \preceq)\) l'insieme dei numeri naturali dotato della relazione d'ordine parziale che hai scritto (lo chiamo così per non confonderlo con \((\mathbb N,\le)\) che userò tra un attimo).

Allora \(\mathfrak N\) è l'unione disgiunta di una famiglia infinita di copie di \(\mathbb N\): difatti è evidente che ogni sottoinsieme del tipo
\[
A_m = \{m^n \mid n\in\mathbb N \}
\] è una catena (semplicemente perché \(m\preceq m^2\preceq m^3\preceq\dots\)), che ciascunn \(A_m\) è isomorfo a \(\mathbb N\), e che ogni elemento di \((\mathbb N, \le)\) appartiene a una e una sola catena \(A_m\). Questo determina una biiezione
\[
\mathbb N \to \coprod_{m\in \mathbb N}A_m
\] che, per costruzione, è anche monotona, quindi \((\mathbb N,\preceq) \cong \coprod_{m\in \mathbb N}A_m \cong \coprod_{m\in \mathbb N}\mathbb N\).

Che non ci sia un minimo o un massimo è facile: non esiste nemmeno un elemento confrontabile con ogni altro elemento!

E per finire, chi sono i minimali di \(\coprod_{m\in \mathbb N}A_m\)? Beh, ciascuno degli addendi è una copia di \(\mathbb N\), e ciascuna copia di \(\mathbb N\) ha minimo (zero, o uno, a seconda di dove inizi a contare i naturali; ma attento che allora \(A_0=\{0\}\)!)

[Pasquale 90]

Non voglio passare per il polemico, ma scusami da un esercizio che richiede di determinare elementi minimo ecc, richieda tutta questa teoria ?

Ciao

[solaàl]

Non ho capito la domanda...

[marco.ruggiero]

Si verifica, banalmente(mediante un semplice controesempio), che $1$ non può essere nè il minimo nè il massimo di $(NN,<=)$. Se per assurdo $(NN,<=)$ è dotato di minimo, si avrebbe, in particolare, $x<=1<=>1=x^n, n in NN$ e quest'ultima uguaglianza è verificata, se e solo se $x=1$, assurdo. Analogamente, se $(NN,<=)$ è dotato di massimo $y$, si avrebbe in particolare $y>=1=>y=1$, assurdo

[Pasquale 90]

Non voglio contraddire il tuo messaggio postato salaàl, ma mi sembra troppo smoderato, per un esercizio che richiede di applicare solo la definizione.

Quindi non so se avete notato, io ho scritto in corsivo per ogni e esiste appositamente, cioè la definizione di minimo in un insieme $S$ ordinato è

$x in S$ è minimo se e solo se $x le y$ per ogni $y in S$

se volessi dire che un insieme non ha minimo posso dire

$forall x in S, \ EE y in S$ tale che $y ??

Ciao

Cita

Segnala

[marco.ruggiero]

"Pasquale 90":$∀x∈S, ∃y∈S$ tale che $y

Poichè l'ordine non è totale, è più corretto dire

$∀x∈S, ∃y∈S: x\cancel{<=}y$, cioè, può accadere, sia che $x$ e $y$ non siano confrontabili, sia che $x>y$.

[G.D.5]

Per provare che \( \le \) è una relazione d'ordine non totale devi innanzitutto provare che essa è una relazione d'ordine, dopo, e solo dopo, devi esibire almeno una coppia di elementi \( x \) e \( y \) non confrontabili, i.e. tali che non si abbia né \( x \le y \) né \( y \le x \) (e ovviamente devi dimostrare che non si ha né il primo né il secondo caso).

[Pasquale 90]

Buongiorno G.D.

per provare che la relazione d'ordine, devo verificare oltre alla riflessività e la transitività che la relazione $le$ è antisimmetrica, i.e.

siano $x,y in NN$ tali che $x le y$ e $ylex$,

per come è stata definita la relazione ottengo $y=x^n \"e"\ x=y^n $ con $n in NN,$ e devo far vedere che $x=y.$
Quindi si ha $y=x^n$ e $x=y^n$ contemporaneamente se e solo se quando $n=1$ per cui per tale valore si ha $x=y$ e $y=x$ quindi la relazione è antisimmetrica.
Inoltre, lo potrei anche provare che la relazione è antisimmetrica per assurdo, i.e.
$x ne y$ con $x,y in NN$ per ipotesi si ha

$y=x^n=x\x^(n-1)=y^nx^(n-1) <=> y-y^nx^(n-1)=0$

allora

$y(y^(n-1)x^(n-1)-1)=0 <=> y=0 \or y^(n-1)x^(n-1)=1$

quindi si ha $0ne y in NN$ e $y^(n-1)x^(n-1)=1 <=> y=x=1$ sono entrambi false.

La riflessività è banale, la ottengo per $n=1$, invece la transitività

siano $x,y, in NN$ tali che $x le y$ e $ylez$

dalla definzione ottengo che

$x le y <=> EE n in NN: y=x^n$

$yle z <=> EE m in NN: z=y^m$

devo far vedere che $z=x^n$, ma queste sono vere se e solo se $n=m=1$.
Su quest'ultima osservazione non sono molto convinto.

Ciao

[G.D.5]

"Pasquale 90":Buongiorno G.D.

per provare che la relazione d'ordine, devo verificare oltre alla riflessività e la transitività che la relazione $le$ è antisimmetrica, i.e.

siano $x,y in NN$ tali che $x le y$ e $ylex$,

per come è stata definita la relazione ottengo $y=x^n \"e"\ x=y^n $ con $n in NN,$ e devo far vedere che $x=y.$

Sì però non sta mica scritto da qualche parte che l'esponente è lo stesso.

"Pasquale 90":
Quindi si ha $y=x^n$ e $x=y^n$ contemporaneamente se e solo se quando $n=1$

Non è mica vero: se $x = y = 1$, allora va bene anche $n = 1000$.

"Pasquale 90":
invece la transitività

siano $x,y, in NN$ tali che $x le y$ e $ylez$

dalla definzione ottengo che

$x le y <=> EE n in NN: y=x^n$

$yle z <=> EE m in NN: z=y^m$

devo far vedere che $z=x^n$, ma queste sono vere se e solo se $n=m=1$.
Su quest'ultima osservazione non sono molto convinto.

Ciao

$2 \le 8$ e $n = 3$; $8 \le 64$ e $n = 2$.

[G.D.5]

"mario9555":... sia che $x>y$.

Nel quale caso allora sarebbe $ y < x $, da cui $ y \le x $ e quindi $x$ e $y$ sono confrontabili.
Inoltre i quantificatori sono stati usati male.

[marco.ruggiero]

"G.D.":
Nel quale caso allora sarebbe y
Forse sono stato poco chiaro... Intendevo dire che è plausibile sia l'una che l'altra eventualià, ma ovviamente, solo una di queste può presentarsi per poter scartare x come possibile minimo.

"G.D.":
Inoltre i quantificatori sono stati usati male.

Perché? Ricordo che stiamo esprimendo che S è privo di minimo.

[G.D.5]

"mario9555":
Perché? Ricordo che stiamo esprimendo che S è privo di minimo.

OK. Errore mio. Credo di aver frainteso perché il tuo intervento inizia con

"mario9555":
Poichè l'ordine non è totale

sicché ho preso fischi per fiaschi e ho capito che si stava parlando di come esprimere in simboli il fatto che l'ordinamento non fosse totale. Chiedo scusa.

[Pasquale 90]

Ciao

Provo che $ le $ è un ordine in $NN$ ma non totale

$le$ è riflessiva se e soltanto se, per ogni $x in NN$ tali che $x le x$, cioè

$x le x <=> EE n in N \:\ x=x^n$ con $n=1$

$le$ è asimmetrica se e soltanto se per ogni $x,y in NN$ tali che $x le y$ e $yle x$ si ha $x=y$, cioè

$x le y <=> EE n in N \:\ x=y^n$,

$ylex <=> EE m in N \:\ y=x^m$

ovviamente se $m=1=n$ è banale invece nel caso in cui $n,m ge 2$ si ha:
$y=x\*\x^(m-1)=y^n\*\x^(m-1)$ quindi $y-y^n\*\x^(m-1)=y(1-y^(n-1)x^(m-1))=0$ dalla legge dell' annullamento del prodotto si ha $y=0 \or\ 1-y^(n-1)x^(m-1)=0$
Allora $y=0 notin NN$ quindi va scartata, allora $y^(n-1)\*\x^(m-1)-1=0 <=> y=x=1$ per ogni $n,m ge 2$ in particolare $x=y$.

$le$ è transitiva presi $x,y, x in NN$ tali che $x le y$ e $y le z$ si ha $x le z$, facciamo vedere che $x le z$ ossia facciomo vedere che esiste un $p in NN$ tale che $z=x^p$.
Essendo che

$xle y <=> EE n in NN \:\ y=x^n$

$yle z <=> EE m in NN \:\ z=y^m$

allora $z=y^m=y^(m-1)\y=y^(m-2)y\y=y\y\y\y\\y....\y=x^n\x^n\x^n\x^n\v^n\....\x^n=x^(n*m)=x^p$
dove $p in NN$ quindi si ha la transitività per $p=m*n in NN$

Inoltre presi due elementi ad esempio $2,3 in NN$ si ha che $2 ne 3^n $ per ogni $n in NN$ e sia $3 ne 2^n$ per ogni $n in NN$ per tale non sussiste la relazione d'ordine totale.

Invece per il minimo e il massimo, essendo che $le$ non è una relazione d'ordine totale allora le definizioni del $"min"$ e del $"max"$ non sussistono, quindi non esiste ne il minimo e ne il massimo in $(NN,le).$

Gli elementi minimali di $NN$ sono gli elementi $x in NN$ tali che \(\displaystyle \require{cancel} \cancel{\exists} \) $y in NN$ tale che $y

$y EEn in NN \:\ x=y^n$

questa relazione è eseguibile in $N$ se e solo se $y$ sia la potenza ennesima di un numero naturale.
Quindi nel nostro caso, gli elementi minimali sono tutti e soli gli $x in NN$ tali che non sono potenza di nessun numero naturale, se non di se stessi con esponente pari ad uno.

Ciao

[marco.ruggiero]

Ti sei complicato un pò troppo la vita. Per la riflessività va bene. Per quanto riguarda l'asimmetria e la transitività, bastava fare una semplice sostituzione

$y=x^m=(y^n)^m=y^(mn)$ , e quindi dividendo per $y$,si ha $1=y^(mn-1)=>y=1$(ovviamente, va analizzato a parte il caso in cui $m=n=1$, come ha fatto)

Quindi, $x=y^n=1=>x=y$

Anche per la transitività, si può procedere così:

$z=y^m=(x^n)^m=x^(nm)$

"Pasquale 90":Inoltre presi due elementi ad esempio 2,3∈N si ha che 2≠3n per ogni n∈N e sia 3≠2n per ogni n∈N per tale non sussiste la relazione d'ordine totale.

Ok

"Pasquale 90":Invece per il minimo e il massimo, essendo che ≤ non è una relazione d'ordine totale allora le definizioni del min e del max non sussistono, quindi non esiste ne il minimo e ne il massimo in (N,≤).

Questo non è vero. Controesempio:

Consideriamo l'insieme $S={a,b,c}$, e definiamo in S la relazione binaria $<=$ ponendo: $a<=a,a<=b,b<=b,a<=c,c<=c$. $<=$è una relazione d'ordine in $S$, ma non è totale(infatti $b$ e $c$ non sono confrontabili), tuttavia $minS=a$

La dimostrazione del fatto che $(NN,<=)$ non è dotato di minimo e massimo, te l'ho fornita in un precedente post.

"Pasquale 90":Quindi nel nostro caso, gli elementi minimali sono tutti e soli gli x∈N tali che non sono potenza di nessun numero naturale, se non di se stessi con esponente pari ad uno.

Ok.

[Pasquale 90]

Ciao mario955, grazie per la risposta

"mario9555":
Consideriamo l'insieme $ S={a,b,c} $, e definiamo in S la relazione binaria $ <= $ ponendo: $ a<=a,a<=b,b<=b,a<=c,c<=c $. $ <= $è una relazione d'ordine in $ S $, ma non è totale(infatti $ b $ e $ c $ non sono confrontabili), tuttavia $ minS=a $
.

ma quì non mi trovo, non voglio dire che la tua dimostrazione non sia corretta, ma si può procedere anche diversamente, cioè
$P=:$ Sia $S ne emptyset$ e sia $le$ una relazione di buon ordine, $Q=:$allora $le$ una relazione d'ordine totale in $S$
Quindi posso dire \(\displaystyle \require{cancel} \cancel{Q} \) $to$ \(\displaystyle \require{cancel} \cancel{P} \) almeno per il minimo quello che ho scritto dovrebbe avere senso, tu come dici ?

Ciao

[marco.ruggiero]

Qual è la definizione di relazione di buon ordine? Dire che $R$ non è una relazione di buon ordine, che cosa equivale a dire? Penso che il problema sia nella risposta che dai alle suddette domande.