Induzione - Massimali e Minimali
Esercizio che ci ha dato il prof, visto che ci hanno detto lo chiede spesso volevo chiedervi se ci sono errori grossolani e sopratutto se qualche passaggio lo posso ridurre senza perdita di completezza. Grazie 
Sia $(X, \leq)$ un insieme parzialmente ordinato e finito. Dimostrare che $X$ ammette sempre elementi massimali e minimali.
Dimostrazione - Induzione sul numero di elementi di $X$.
(i) $n = 1$ - Se $|X| = 1, \quad X = {x_1}$. Allora, in quanto $X$ è per ipotesi parzialmente ordinato e quindi in particolar modo vale la proprietà riflessiva, $x_1 \leq x_1$.
Ora, $ \forall x \in X, \quad x \leq x_1 \rightarrow x = x_1$ in quanto $x_1$ è l'unico elemento di $X$.
Similmente, $ \forall x \in X, \quad x_1 \leq x \rightarrow x = x_1$ per lo stesso motivo di prima.
$x_1$ è quindi sia massimale che minimale, e per $n = 1$ l'asserto è vero.
(ii) Ipotesi induttiva: $ n - 1 $ vera, ovvero $Y = {x_1, ..., x_{n-1}}$ ammette minimali e massimali. Siano quindi $x_1$ un minimale di $Y$ e $x_2$ un massimale di $Y$.
Tesi: $X = {x_1, ..., x_{n-1}, x_n} = Y uu {y_n}$ ammette minimali e massimali.
Separiamo 3 casi:
1) $x_n$ non è confrontabile con $x_1$ ; allora, $\forall x \in X$ t.c. $x <= x_1 \rightarrow x != x_n \rightarrow x \in Y \rightarrow x = x_1$ per ipotesi induttiva. $x_1$ è quindi minimale di $X$.
2) $x_1 <= x_n$ ; allora, $\forall x \in X, x <= x_1 \rightarrow x = x_1$ Infatti
a) Se $x = x_n$, abbiamo $x_n <= x_1$ e $x_1 <= x_n$, quindi $x_n = x_1$
b) Se $x \in Y, x = x_1$ per ipotesi induttiva.
3) $x_n <= x_1$ ; Allora, $\forall x in X, x <= x_n \rightarrow x = x_n$:
Sia $x != x_n \rightarrow x \in Y$. Poichè $x <= x_n$ e $x_n <= x_1 \rightarrow x <= x_1$ per transitività di $<=$.
Ma per ipotesi induttiva allora $x = x_1 \rightarrow x_1 <= x_n <= x_1 \rightarrow x_n = x_1$ e quindi è massimale.
Quindi $Y$ ammette sempre minimali.
Analogamente per i massimali.
Sia $(X, \leq)$ un insieme parzialmente ordinato e finito. Dimostrare che $X$ ammette sempre elementi massimali e minimali.
Dimostrazione - Induzione sul numero di elementi di $X$.
(i) $n = 1$ - Se $|X| = 1, \quad X = {x_1}$. Allora, in quanto $X$ è per ipotesi parzialmente ordinato e quindi in particolar modo vale la proprietà riflessiva, $x_1 \leq x_1$.
Ora, $ \forall x \in X, \quad x \leq x_1 \rightarrow x = x_1$ in quanto $x_1$ è l'unico elemento di $X$.
Similmente, $ \forall x \in X, \quad x_1 \leq x \rightarrow x = x_1$ per lo stesso motivo di prima.
$x_1$ è quindi sia massimale che minimale, e per $n = 1$ l'asserto è vero.
(ii) Ipotesi induttiva: $ n - 1 $ vera, ovvero $Y = {x_1, ..., x_{n-1}}$ ammette minimali e massimali. Siano quindi $x_1$ un minimale di $Y$ e $x_2$ un massimale di $Y$.
Tesi: $X = {x_1, ..., x_{n-1}, x_n} = Y uu {y_n}$ ammette minimali e massimali.
Separiamo 3 casi:
1) $x_n$ non è confrontabile con $x_1$ ; allora, $\forall x \in X$ t.c. $x <= x_1 \rightarrow x != x_n \rightarrow x \in Y \rightarrow x = x_1$ per ipotesi induttiva. $x_1$ è quindi minimale di $X$.
2) $x_1 <= x_n$ ; allora, $\forall x \in X, x <= x_1 \rightarrow x = x_1$ Infatti
a) Se $x = x_n$, abbiamo $x_n <= x_1$ e $x_1 <= x_n$, quindi $x_n = x_1$
b) Se $x \in Y, x = x_1$ per ipotesi induttiva.
3) $x_n <= x_1$ ; Allora, $\forall x in X, x <= x_n \rightarrow x = x_n$:
Sia $x != x_n \rightarrow x \in Y$. Poichè $x <= x_n$ e $x_n <= x_1 \rightarrow x <= x_1$ per transitività di $<=$.
Ma per ipotesi induttiva allora $x = x_1 \rightarrow x_1 <= x_n <= x_1 \rightarrow x_n = x_1$ e quindi è massimale.
Quindi $Y$ ammette sempre minimali.
Analogamente per i massimali.
Risposte
Up! [Modificata tutta la parte (ii) 
]
]
Salve Gatto89.
Questo tuto esercizio mi incuriosisce ma non riesco bene a capire i passaggi che segui nella prova per induzione.
In particolare non mi è chiaro perché in 1) fai derivare da $x<=x_1$ il fatto che $x!=x_n$.
Non mi è poi chiaro perché nella definizione di $X$ usi il singleton di $y_n$: volendo essere formali e puntigliosi dovresti dopo precisare che $x_n=y_n$.
Potresti chiarire un pò meglio.
Questo tuto esercizio mi incuriosisce ma non riesco bene a capire i passaggi che segui nella prova per induzione.
In particolare non mi è chiaro perché in 1) fai derivare da $x<=x_1$ il fatto che $x!=x_n$.
Non mi è poi chiaro perché nella definizione di $X$ usi il singleton di $y_n$: volendo essere formali e puntigliosi dovresti dopo precisare che $x_n=y_n$.
Potresti chiarire un pò meglio.
In particolare, sei sicuro che la prova per induzione sia possibile.
Diciamo che $\mathfrak{C}^{\star}=\{x_1, x_2, \ldots, x_n\}$ sia l'insieme per il quale vale l'ipotesi induttiva, e sia $\mathfrak{C}=\mathfrak{C}^{\star} \cup \{x_{n+1}\}$ l'insieme per il quale bisogna provare la validità dell'asserto.
Se $x_{n+1}$ non è confrontabile con il massimale $x_2$ di $\mathfrak{C}^{\star}$, cosa ci dice che $x_{n+1}$ non sia confrontabile con gli altri elementi con cui $x_2$ è confrontabile?
Spiego meglio: diciamo che $\mathfrak{C}^{\star}=\{x_1, x_2, x_3, x_4\}$ con $x_1$ minimale e $x_2$ massimale e $x_4$ non confrontabile con alcuno dei restanti elementi. Diciamo che $x_{n+1}:=x_5$ non è confrontabile con $x_2$: non può succedere che $x_5$ sia poi confrontabile con $x_1,x_3,x_4$?
Se questo potesse accadere il tuo punto 1) diventerebbe insufficiente.
Le mie sono solo domande, perché non ho ben capito come funzione questa prova per induzione.
Diciamo che $\mathfrak{C}^{\star}=\{x_1, x_2, \ldots, x_n\}$ sia l'insieme per il quale vale l'ipotesi induttiva, e sia $\mathfrak{C}=\mathfrak{C}^{\star} \cup \{x_{n+1}\}$ l'insieme per il quale bisogna provare la validità dell'asserto.
Se $x_{n+1}$ non è confrontabile con il massimale $x_2$ di $\mathfrak{C}^{\star}$, cosa ci dice che $x_{n+1}$ non sia confrontabile con gli altri elementi con cui $x_2$ è confrontabile?
Spiego meglio: diciamo che $\mathfrak{C}^{\star}=\{x_1, x_2, x_3, x_4\}$ con $x_1$ minimale e $x_2$ massimale e $x_4$ non confrontabile con alcuno dei restanti elementi. Diciamo che $x_{n+1}:=x_5$ non è confrontabile con $x_2$: non può succedere che $x_5$ sia poi confrontabile con $x_1,x_3,x_4$?
Se questo potesse accadere il tuo punto 1) diventerebbe insufficiente.
Le mie sono solo domande, perché non ho ben capito come funzione questa prova per induzione.
"WiZaRd":
Salve Gatto89.
Questo tuto esercizio mi incuriosisce ma non riesco bene a capire i passaggi che segui nella prova per induzione.
In particolare non mi è chiaro perché in 1) fai derivare da $x<=x_1$ il fatto che $x!=x_n$.
Non mi è poi chiaro perché nella definizione di $X$ usi il singleton di $y_n$: volendo essere formali e puntigliosi dovresti dopo precisare che $x_n=y_n$.
Potresti chiarire un pò meglio.
Per la prima parte, il fatto che $x <= x_1 \rightarrow x != x_n$ è perchè, per l'ipotesi del punto 1, $x_n$ non è confrontabile con $x_1$ e quindi è impossibile che sia $x_n <= x_1$.
Per la seconda parte hai totalmente ragione è stato un mio errore di copiatura dal quaderno a qui
"WiZaRd":
In particolare, sei sicuro che la prova per induzione sia possibile.
Diciamo che $\mathfrak{C}^{\star}=\{x_1, x_2, \ldots, x_n\}$ sia l'insieme per il quale vale l'ipotesi induttiva, e sia $\mathfrak{C}=\mathfrak{C}^{\star} \cup \{x_{n+1}\}$ l'insieme per il quale bisogna provare la validità dell'asserto.
Se $x_{n+1}$ non è confrontabile con il massimale $x_2$ di $\mathfrak{C}^{\star}$, cosa ci dice che $x_{n+1}$ non sia confrontabile con gli altri elementi con cui $x_2$ è confrontabile?
Spiego meglio: diciamo che $\mathfrak{C}^{\star}=\{x_1, x_2, x_3, x_4\}$ con $x_1$ minimale e $x_2$ massimale e $x_4$ non confrontabile con alcuno dei restanti elementi. Diciamo che $x_{n+1}:=x_5$ non è confrontabile con $x_2$: non può succedere che $x_5$ sia poi confrontabile con $x_1,x_3,x_4$?
Se questo potesse accadere il tuo punto 1) diventerebbe insufficiente.
Le mie sono solo domande, perché non ho ben capito come funzione questa prova per induzione.
Nel punto 1 infatti dimostro che è $x_1$ ad essere un minimale sfruttando la definizione stessa di minimale (nulla nega infatti che anche $x_n$ possa essere un minimale, ma a me basta dimostrare l'esistenza di uno), e poichè $x_n$ e $x_1$ non sono confrontabili mi riconduco all'ipotesi induttiva.
OK. Chiarissimo.
Vorrei suggerire una dimostrazione alternativa: credo (ma non sono sicuro) che si potrebbe provare il fatto anche con il Lemma di Zorn.
Vorrei suggerire una dimostrazione alternativa: credo (ma non sono sicuro) che si potrebbe provare il fatto anche con il Lemma di Zorn.
Il problema è che non l'abbiamo ancora fatto 
OK.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo