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<x$ invece per il massimo dovrei procedere analogamente ?

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...

[mario9555]

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<x$

??

Ciao

[mario9555]

$∀x∈S, ∃y∈S$ tale che $y<x$

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.]

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.]

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.

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$.

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$.