Minimi, minimali
Sia $A$ un insieme. Vorrei capire se sono vere o false le seguenti equivalenze:
i) L'insieme dei minimali ha più di un elemento $<=>A$ non ha minimo?
La $=>$ mi sembra vera, perché il minimo di un insieme è unico e quindi se si hanno più minimali non si può avere un minimo.
Per la <=, bisogna distinguere se $A$ è limitato inferiormente o no. Se $A$ non ha minimo potrebbe essere anche non limitato inferiormente, e in tal caso infA non esisterebbe e in particolare $A$ non avrebbe minimo.
Pertanto la $=>$ mi sembra vera, l'altra implicazione no.
ii) $A$ ha minimo $<=>$ A ha un unico elemento minimale.
La $(=>)$ mi sembra ovvia sempre per l'unicità del minimo.
Come dovrei fare per dimostrare l'altra implicazione? A me sembra vera, perché se $A$ ha un unico elemento minimale (sia esso $a in A$) allora $x<=a => x=a$. Se considerassi un elemento $b in A$ isolato (che non è confrontabile con altri elementi di $A$) sarebbe anch'esso minimale, e quindi contro le ipotesi.
i) L'insieme dei minimali ha più di un elemento $<=>A$ non ha minimo?
La $=>$ mi sembra vera, perché il minimo di un insieme è unico e quindi se si hanno più minimali non si può avere un minimo.
Per la <=, bisogna distinguere se $A$ è limitato inferiormente o no. Se $A$ non ha minimo potrebbe essere anche non limitato inferiormente, e in tal caso infA non esisterebbe e in particolare $A$ non avrebbe minimo.
Pertanto la $=>$ mi sembra vera, l'altra implicazione no.
ii) $A$ ha minimo $<=>$ A ha un unico elemento minimale.
La $(=>)$ mi sembra ovvia sempre per l'unicità del minimo.
Come dovrei fare per dimostrare l'altra implicazione? A me sembra vera, perché se $A$ ha un unico elemento minimale (sia esso $a in A$) allora $x<=a => x=a$. Se considerassi un elemento $b in A$ isolato (che non è confrontabile con altri elementi di $A$) sarebbe anch'esso minimale, e quindi contro le ipotesi.
Risposte
Sulla (i) hai ragione. Per esempio $RR$ non ha minimo ma non ha neanche elementi minimali.
Sulla (ii) hai ragione su $(=>)$. Prova a mostrare che invece l'altra implicazione è falsa.
Sulla (ii) hai ragione su $(=>)$. Prova a mostrare che invece l'altra implicazione è falsa.
Comunque mi sono accorto che la (ii) è la contronominale della (i)[nota]se escludo il caso che i minimali non ci siano proprio, ma questo credo sia impossibile perché data una relazione d'ordine esistono sempre minimali e massimali[/nota] se riformulo le proposizioni in questo modo:
(i) L'insieme dei minimali ha più di un elemento $=>$ $A$ non ha minimo VERA
(ii) $A$ ha minimo $=> A$ ha un unico elemento minimale.
Schema della (i): non$P => Q$
Schema della (ii) non $Q => P$
Queste due proposizioni sono equivalenti, quindi dopo aver dimostrato che la prima è vera la seconda è equivalente e quindi è vera.
(i) L'insieme dei minimali ha più di un elemento $=>$ $A$ non ha minimo VERA
(ii) $A$ ha minimo $=> A$ ha un unico elemento minimale.
Schema della (i): non$P => Q$
Schema della (ii) non $Q => P$
Queste due proposizioni sono equivalenti, quindi dopo aver dimostrato che la prima è vera la seconda è equivalente e quindi è vera.
"HowardRoark":E invece no, per esempio $RR$ non ha minimali né massimali.
data una relazione d'ordine esistono sempre minimali e massimali
In realtà (i) e (ii) non sono una la contronominale dell'altra perché $RR$ è un controesempio per (i) ma non per (ii).
Riesci a trovare un controesempio per (ii)?
"Martino":
E invece no, per esempio $RR$ non ha minimali né massimali.
Mi sono schiarito le idee
"Martino":
Riesci a trovare un controesempio per (ii)?
Se $A$ ha un unico elemento minimale, allora deve essere necessariamente limitato inferiormente, questo è giusto?
Ok forse ci sono. Considero $RR$ per semplicità e gli intervalli $(-oo, -1] uu [0,4)$ con tale relazione d'ordine $xrhoy <=> x<=y$ e $x$ e $y$ sono non negativi. $0$ è un minimale ma non è il minimo, perché ad esempio non è vero che $0 rho -2$.
Per come hai definito la relazione (dove è implicito che sottintendi la riflessività, altrimenti non è un ordine), anche $-1$ è minimale, perché se $x rho (-1)$ allora $x=-1$ dato che $-1$ è negativo.
Ok adesso hai tolto la condizione che $y$ sia non negativo. Comunque non va bene perché $0$ non è minimale, per esempio $-1 rho 0$.
Per come l'ho definita ora, $x$ e $y$ per essere in relazione devono essere non negativi, quindi $-1$ non può essere un minimale. L'unico minimale ora è lo $0$, ma non è minimo perché non è vero che $0 rho -47$.
Scusa se sto editando mille volte i messaggi, ti sto mandando in confusione anche a te
Scusa se sto editando mille volte i messaggi, ti sto mandando in confusione anche a te
Senza che edito il messaggio, in realtà ho sbagliato ancora perché quella non sarebbe una relazione d'ordine (manca la riflessività). Non è vero che $-1 rho -1$ ad esempio.
Il problema non è la riflessività, quella la puoi sempre aggiungere nella definizione di $rho$.
Il problema è che è vero che $0$ è minimale ma per esempio anche $-1$ è minimale. Prova a pensarci.
Il problema è che è vero che $0$ è minimale ma per esempio anche $-1$ è minimale. Prova a pensarci.
Riparto da capo. Considero $RR$ e gli intervalli [nota]in realta non serve neanche prendere $(-oo,k)$, $k<0$, come intervallo: basta una cosa del tipo $(-6,0)$, ad esempio. Osservo che questo intervallo è infinito, benché limitato, e la cosa da notare è proprio che la proposizione è falsa se considero un insieme infinito ma diventa vera se l'insieme è finito[/nota]$(-oo, -1] uu [0,4)$ con tale relazione d'ordine $xrhoy <=> x<=y$ e $x$ e $y$ sono concordi. Adesso la riflessività c'è, 0 è minimale e l'unico candidato minimo, ma non è vero che $0 rho -1$ (non sono concordi), quindi $0$ non è il minimo.
"Martino":
Il problema è che è vero che $0$ è minimale ma per esempio anche $-1$ è minimale. Prova a pensarci.
Con questa mia nuova relazione $-1$ non è minimale, perché $-2 rho -1$ e $-2 != -1$.
Secondo me comunque la proposizione è vera se l'insieme su cui considero la relazione è finito, per questo è un po' difficile immaginarsi un controesempio. Quest'ultimo che ho trovato dovrebbe essere corretto.
Ok adesso il tuo controesempio va bene.
Più in generale considera due insiemi disgiunti $X,Y$, ognuno di essi parzialmente ordinato da una relazione che indicherò con $le$ per entrambi. Definisci un ordine sull'unione $Z = X uu Y$ dicendo che $a leq b$ se e solo se $a,b in X$ e $a le b$ in $X$ oppure $a,b in Y$ e $a le b$ in $Y$. E' facile vedere che questo definisce un ordine in $Z$. Se $X$ ha minimo e $Y$ non ha elementi minimali allora il minimo di $X$ è l'unico minimale di $Z$ ma non è il minimo di $Z$ perché non è confrontabile con gli elementi di $Y$.
Sì certo, se l'insieme è finito ha sicuramente elementi minimali, e se ha un unico minimale allora questo unico minimale è uguale al minimo. Questo si dimostra facilmente (prova).
Più in generale considera due insiemi disgiunti $X,Y$, ognuno di essi parzialmente ordinato da una relazione che indicherò con $le$ per entrambi. Definisci un ordine sull'unione $Z = X uu Y$ dicendo che $a leq b$ se e solo se $a,b in X$ e $a le b$ in $X$ oppure $a,b in Y$ e $a le b$ in $Y$. E' facile vedere che questo definisce un ordine in $Z$. Se $X$ ha minimo e $Y$ non ha elementi minimali allora il minimo di $X$ è l'unico minimale di $Z$ ma non è il minimo di $Z$ perché non è confrontabile con gli elementi di $Y$.
Sì certo, se l'insieme è finito ha sicuramente elementi minimali, e se ha un unico minimale allora questo unico minimale è uguale al minimo. Questo si dimostra facilmente (prova).
"Martino":
Più in generale considera due insiemi disgiunti $X,Y$, ognuno di essi parzialmente ordinato da una relazione che indicherò con $le$ per entrambi. Definisci un ordine sull'unione $Z = X uu Y$ dicendo che $a leq b$ se e solo se $a,b in X$ e $a le b$ in $X$ oppure $a,b in Y$ e $a le b$ in $Y$. E' facile vedere che questo definisce un ordine in $Z$. Se $X$ ha minimo e $Y$ non ha elementi minimali allora il minimo di $X$ è l'unico minimale di $Z$ ma non è il minimo di $Z$ perché non è confrontabile con gli elementi di $Y$.
Grazie per la spiegazione, ora capisco meglio anche il mio controesempio.
"Martino":
Sì certo, se l'insieme è finito ha sicuramente elementi minimali, e se ha un unico minimale allora questo unico minimale è uguale al minimo. Questo si dimostra facilmente (prova).
Sia $A$ limitato. Allora $A={a_1,a_2,...,a_k}$ Sia $b$ l'unico elemento minimale: $a_i <= b => a_i =b$. Quando confronto $b$ con un generico $a_i$ possono succedere due cose:
1) $b$ e $a_i$ non sono confrontabili, ma questo implicherebbe che ci siano altri elementi minimali. Se $a_i$ fosse isolato sarebbe minimale; se non fosse isolato ci sarebbe un elemento $a_j$ in relazione con lui, con $b$ che non è in relazione con $a_j$ (altrimenti per transitività $b$ sarebbe in relazione con $a_i$). Posso andare a ritroso fino a trovare un secondo minimale diverso da $b$, e ciò sarebbe ancora contro l'ipotesi.
2) $b$ e $a_i$ sono confrontabili e, per definizione di minimale, $b<=a_i$. Poiché questo è l'unico caso possibile, allora $b<=a_i AA a_i in A$ e quindi $b$ è il minimo.
Potrebbe andare bene, ma devi spiegare perché nel caso 1 il minimale che ottieni andando a ritroso è diverso da $b$.
L'ho spiegato: $rho$ è una relazione d'ordine, in particolare è transitiva. Se al caso 1) ottenessi $b$ come minimale, allora per transitività $b$ dovrebbe essere in relazione anche con $a_i$.
Mi sono espresso male. Il fatto è che "parli" troppo, dovresti formalizzare di più quello che dici usando le formule.
Quello che intendo dire è che devi spiegare perché andando a ritroso arrivi sicuramente a un elemento $m$ tale che non esiste nessun $x$ tale che $x < m$. La cosa sembra ovvia ma se ci pensi non lo è, perché ti serve usare l'antisimmetria. Da quanto scrivi tu non si capisce che stai usando l'antisimmetria.
Quello che intendo dire è che devi spiegare perché andando a ritroso arrivi sicuramente a un elemento $m$ tale che non esiste nessun $x$ tale che $x < m$. La cosa sembra ovvia ma se ci pensi non lo è, perché ti serve usare l'antisimmetria. Da quanto scrivi tu non si capisce che stai usando l'antisimmetria.
Ok. Andando a ritroso, poiché l' insieme è limitato, arrivo sicuramente ad un $m$ che è minimale. Poi, per l' antisimmetria, se $m<=x$ e $x<=m$ allora $x=m$[nota]potrei andare avanti all' infinito ma è un cane che si morde la coda[/nota]. In effetti avrei dovuto specificarlo, non ci avevo minimamente pensato.
Comunque queste dimostrazioni non so come formalizzarle bene con delle formule, spero che col tempo imparerò.
Comunque queste dimostrazioni non so come formalizzarle bene con delle formule, spero che col tempo imparerò.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo