lemma di Zorn e Assioma della scelta

Messaggioda BenderBendingRodriguez » 07/03/2011, 19:17

Salve a tutti, qualcuno avrebbe la pazienza di spiegarmi con chiarezza il lemma di Zorn e l'assioma della scelta ?
la difficoltà principale che incontro è il definire gli elementi massimali di un dato insieme, da quanto ho compreso ( e non so appunto se abbia o meno frainteso ) gli elementi massimali di un insieme sono quegli elementi che non sono confrontabili ma sono tutti maggiori o uguali a qualche altro elemento dell'insieme considerato, potreste a priori farmi un esempio di un insieme che contenga elementi massimali ? chiedo innanzi tutto questo perché è strettamente legato alla questione del lemma di zorn e ovviamente se non capisco la base del problema non so nemmeno da dove partire.
Il mio testo parte con la definizione di insiemi parzialmente ordinati ( e fin qui credo di aver inteso il concetto ) i quali contengono a loro volta Catene ( che sarebbe se ho ben capito degli insiemi totalmente ordinati ) e queste Catene devono avere maggioranti ( qui c'è un altro concetto da chiarire con più precisione ) e quindi tutta questa roba viene chiamata insieme induttivo.

il lemma dice : ogni insieme induttivo ammette elementi massimali.....

so che questa dimostrazione è poco intuitiva e non costruttiva ma potreste fare un esempio di questi insiemi e denotare con esattezza l'insieme ordinato la catena e i maggioranti e i massimali ?
grazie mille
Ps
io uso il Dikran, e onestamente lo trovo poco chiaro, ho comprato anche il Franciosi/De Giovanni ma lo trovo a volte più chiaro a volte meno, dipende dall'argomento.
BenderBendingRodriguez
Starting Member
Starting Member
 
Messaggio: 1 di 46
Iscritto il: 07/03/2011, 19:02

Messaggioda Martino » 08/03/2011, 10:30

Ciao! Benvenuto nel forum.

Prendiamo un insieme parzialmente ordinato \( \displaystyle (P,\leq) \) .

- Una catena in \( \displaystyle P \) e' un sottoinsieme \( \displaystyle C \subseteq P \) tale che l'insieme \( \displaystyle C \) dotato dell'ordine \( \displaystyle \leq \) (ovviamente ristretto a \( \displaystyle C \) ) e' totalmente ordinato.
- Un elemento massimale di \( \displaystyle P \) e' un elemento \( \displaystyle m \in P \) tale che per ogni altro elemento \( \displaystyle x \in P \) , se accade che \( \displaystyle m \leq x \) allora \( \displaystyle x=m \) . In altre parole l'unico elemento di \( \displaystyle P \) di cui \( \displaystyle m \) e' minore o uguale e' \( \displaystyle m \) stesso.

Osserva che se l'ordine e' totale ed esiste un elemento massimale \( \displaystyle m \) allora esso e' unico. Se infatti \( \displaystyle p \) e' un elemento massimale allora dev'essere \( \displaystyle p \leq m \) per la totalita' dell'ordine e la massimalita' di \( \displaystyle m \) , da cui \( \displaystyle p=m \) per la massimalita' di \( \displaystyle p \) .

Per esempio dato un insieme finito di numeri naturali ordinato tramite l'ordine usuale \( \displaystyle \leq \) , il suo massimo (che esiste data la finitezza) e' un elemento massimale, e data la totalita' dell'ordine tale elemento massimale e' unico.

Un altro esempio: dato un insieme \( \displaystyle X \) , l'insieme \( \displaystyle P(X) \) (l'insieme dei sottoinsiemi di \( \displaystyle X \) ) e' parzialmente ordinato tramite l'inclusione \( \displaystyle \subseteq \) , e \( \displaystyle X \) e' un suo elemento massimale, in effetti l'unico. Pero' anche \( \displaystyle P(X)-\{X\} \) e' parzialmente ordinato da \( \displaystyle \subseteq \) , e qui a priori ci possono essere piu' di un massimale. Per esempio l'insieme \( \displaystyle \{\emptyset,\{1\},\{2\}\} \) con \( \displaystyle \subseteq \) ammette due massimali, \( \displaystyle \{1\} \) e \( \displaystyle \{2\} \) .

\( \displaystyle (P,\leq) \) si dice induttivo se per ogni catena \( \displaystyle C \) di \( \displaystyle P \) esiste \( \displaystyle p \in P \) tale che \( \displaystyle c \leq p \) per ogni \( \displaystyle c \in C \) . Un tale \( \displaystyle p \) si puo' chiamare "limite superiore" di \( \displaystyle C \) .

Lemma di Zorn (LZ). Ogni insieme non vuoto, parzialmente ordinato induttivo ammette massimali.

Ora dovrebbe risultarti chiaro il significato del lemma di Zorn. In pratica ti dice che per mostrare che un insieme ordinato ammette massimali ti basta mostrare che ogni sua catena ammette limiti superiori.

Assioma della scelta (AS). Sia \( \displaystyle H \) una famiglia non vuota di insiemi non vuoti a due a due disgiunti. Allora esiste una funzione \( \displaystyle g:H \to \cup H \) tale che \( \displaystyle g(A) \in A \) per ogni \( \displaystyle A \in H \) .

Qui per \( \displaystyle \cup H \) intendo l'unione degli elementi di \( \displaystyle H \) , cioe' \( \displaystyle \bigcup_{A \in H}A \) .

Ti ricordo che LZ e AS non sono dimostrabili. Sono due enunciati indipendenti dagli assiomi precedenti, e sono equivalenti, nel senso che si implicano a vicenda.

Ora ti dimostro che LZ implica AS. Sia \( \displaystyle H \) una famiglia non vuota di insiemi non vuoti a due a due disgiunti. Dato \( \displaystyle K \subseteq H \) chiamiamo "scelta parziale" una funzione \( \displaystyle f:K \to \cup H \) tale che \( \displaystyle f(A) \in A \) per ogni \( \displaystyle A \in K \) . Per esempio dato \( \displaystyle A \in H \) e dato \( \displaystyle a \in A \) , la funzione \( \displaystyle \{A\} \to \cup H \) che manda \( \displaystyle A \) in \( \displaystyle a \) e' una scelta parziale. L'insieme delle scelte parziali e' ordinato tramite la seguente relazione: date due scelte parziali \( \displaystyle f:K \to \cup H \) e \( \displaystyle g:L \to \cup H \) , diciamo che \( \displaystyle f \leq g \) se \( \displaystyle K \subseteq L \) e \( \displaystyle g|_K=f \) . Chiamiamo \( \displaystyle F \) l'insieme delle scelte parziali dotato di tale ordine (come osservato, tale insieme e' non vuoto). Usiamo ora il lemma di Zorn: per mostrare che esiste un elemento massimale in \( \displaystyle F \) basta mostrare che ogni catena ammette un massimale. Sia \( \displaystyle C \) una catena in \( \displaystyle F \) , e sia \( \displaystyle E \) l'insieme dei domini delle funzioni in \( \displaystyle C \) . Definiamo la funzione \( \displaystyle m: \cup E \to \cup H \) mandando \( \displaystyle A \) nell'immagine \( \displaystyle f(A) \) dove \( \displaystyle f \) e' un elemento di \( \displaystyle C \) al cui dominio appartiene \( \displaystyle A \) . Per costruzione la funzione \( \displaystyle m \) e' ben definita ( \( \displaystyle m(A) \) non dipende dalla particolare \( \displaystyle f \in C \) che si sceglie: se si sceglie \( \displaystyle h \neq f \) allora \( \displaystyle f \leq h \) oppure \( \displaystyle h \leq f \) per la totalita', e in particolare \( \displaystyle f(A)=h(A) \) ). E' tautologico che una tale \( \displaystyle m \) e' un elemento massimale di \( \displaystyle C \) . Per il lemma di Zorn esiste quindi \( \displaystyle g \in F \) massimale. Per concludere basta mostrare che il suo dominio \( \displaystyle D \) e' \( \displaystyle H \) . Se cosi' non fosse esisterebbe \( \displaystyle B \) fuori da \( \displaystyle D \) , e preso \( \displaystyle b \in B \) potremmo definire \( \displaystyle h:D \cup \{B\} \to \cup H \) mandando \( \displaystyle A \in D \) in \( \displaystyle f(A) \) e \( \displaystyle B \) in \( \displaystyle b \) . Si avrebbe che \( \displaystyle g \leq h \) e \( \displaystyle g \neq h \) , assurdo.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 4056 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Messaggioda BenderBendingRodriguez » 08/03/2011, 16:42

devo analizzare bene tutto quello che hai scritto .... comunque sul lemma di Zorn si credo di aver inteso quale sia il problema, cioè devo poter dimostrare che esiste un elemento massimale per ogni catena contenuta nell'insieme parzialmente ordinato cosi facendo ogni elemento massimale ( che poi è unico ) di quella catena si può annoverare tra gli elementi massimali di quell'insieme quindi se prendessimo $n$ catene avremmo $n$ elementi massimali ... vero ?


per il resto cerco di verificare la tua dimostrazione
grazie mille per la disponibilità
BenderBendingRodriguez
Starting Member
Starting Member
 
Messaggio: 2 di 46
Iscritto il: 07/03/2011, 19:02

Messaggioda Martino » 08/03/2011, 17:48

BenderBendingRodriguez ha scritto:devo analizzare bene tutto quello che hai scritto .... comunque sul lemma di Zorn si credo di aver inteso quale sia il problema, cioè devo poter dimostrare che esiste un elemento massimale per ogni catena contenuta nell'insieme parzialmente ordinato cosi facendo ogni elemento massimale ( che poi è unico ) di quella catena si può annoverare tra gli elementi massimali di quell'insieme quindi se prendessimo $n$ catene avremmo $n$ elementi massimali ... vero ?
No! Il lemma di Zorn ti dice che se ogni catena in un insieme induttivo F esiste un elemento massimale allora F ha un elemento massimale. Ma non c'e' motivo per cui un massimale di una catena di F sia un massimale di F.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 4057 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Messaggioda BenderBendingRodriguez » 08/03/2011, 18:01

non riesco a capire la differenza :)

se ogni catena ha un elemento massimale ( e fin qui siamo d'accordo che se c'è è unico, o no ? ) e queste catene sono contenute in un insieme parzialmente ordinato F automaticamente quei massimali non sono degli elementi appartenenti ad F stesso ? forse è questo che confondo ....

per come dici te allora il fatto che un elemento sia massimale per una catena di F non implica che lo sia pure per F ..... potresti se ti va fare un esempio con un insieme specifico ? perché a me non è chiara questa cosa.

( una cosa che anche mi crea fastidi è il concetto di maggiorante, potresti fare un esempio che contenga tutte queste definizioni ? ma un esempio su uno specifico insieme passo per passo cosi che possa individuare una volta per tutte maggioranti minoranti massimali e minimali per poi poter astrarre la cosa anche senza un riferimento esemplificativo )

Stragrazie ancora !
BenderBendingRodriguez
Starting Member
Starting Member
 
Messaggio: 3 di 46
Iscritto il: 07/03/2011, 19:02

Messaggioda Martino » 08/03/2011, 18:32

BenderBendingRodriguez ha scritto:per come dici te allora il fatto che un elemento sia massimale per una catena di F non implica che lo sia pure per F ..... potresti se ti va fare un esempio con un insieme specifico ? perché a me non è chiara questa cosa.
Beh, prendi \( \displaystyle F=\{1,2\} \) con l'ordine usuale. Chiaro che \( \displaystyle \{1\} \) e' una catena di \( \displaystyle F \) , e \( \displaystyle 1 \) e' il suo elemento massimale. Ma \( \displaystyle 1 \) non e' un elemento massimale di \( \displaystyle F \) , dato che \( \displaystyle 1<2 \) .

( una cosa che anche mi crea fastidi è il concetto di maggiorante, potresti fare un esempio che contenga tutte queste definizioni ? ma un esempio su uno specifico insieme passo per passo cosi che possa individuare una volta per tutte maggioranti minoranti massimali e minimali per poi poter astrarre la cosa anche senza un riferimento esemplificativo )
Puoi prendere \( \displaystyle X=\{1,2,3\} \) e \( \displaystyle F=P(X)-\{X\} \) ordinato dall'inclusione. Hai che

\( \displaystyle F=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\} \) .

Prendi per esempio \( \displaystyle T=\{\{1\},\{2\}\} \subset F \) . \( \displaystyle T \) ha un unico maggiorante in \( \displaystyle F \) , \( \displaystyle \{1,2\} \) . Poi per esempio \( \displaystyle C=\{\emptyset,\{2\}\} \) e' una catena in \( \displaystyle F \) e \( \displaystyle \{2\} \) e' il suo elemento massimale. Ma \( \displaystyle \{2\} \) non e' massimale in \( \displaystyle F \) dato che \( \displaystyle \{2\} \subset \{1,2\} \) . Gli elementi massimali di \( \displaystyle F \) sono tre: \( \displaystyle \{1,2\},\{1,3\},\{2,3\} \) .
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 4059 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Messaggioda BenderBendingRodriguez » 08/03/2011, 18:42

e il minimale è l'insieme vuoto ? cioè per tutti è l'insieme vuoto ? e poi dovrebbe corrispondere con il minimo dell'insieme in questo caso ?
BenderBendingRodriguez
Starting Member
Starting Member
 
Messaggio: 4 di 46
Iscritto il: 07/03/2011, 19:02

Messaggioda Martino » 08/03/2011, 20:25

\( \displaystyle \{1,2\} \) ha un unico minimale, \( \displaystyle 1 \) . \( \displaystyle F=P(\{1,2,3\})-\{\{1,2,3\}\} \) e \( \displaystyle C=\{\emptyset,\{2\}\} \) di cui sopra hanno un unico minimale, \( \displaystyle \emptyset \) . Invece i minimali di \( \displaystyle T=\{\{1\},\{2\}\} \) sono \( \displaystyle \{1\} \) e \( \displaystyle \{2\} \) , e sono anche i massimali.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 4061 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Messaggioda BenderBendingRodriguez » 08/03/2011, 21:14

ok allora devo ogni volta tener presente l'insieme sul quale mi propongo di cercare un dato elemento cioè non esiste in questo caso un massimale ( o minimale ) che sia lo stesso per tutti ma devo sempre tener presente l'insieme e il sottoinsieme.

se invece volessimo considerare l'insieme delle parti interamente, cioè senza omettere l'insieme $X$ ?
in questo caso $X$ sarebbe un elemento massimale di questo insieme delle parti ?



Grazie per l'abnorme pazienza, in rete ci sono esercizi con esempi simili a quelli fatti da te ? giusto per fare il callo con insiemi diversi e ovviamente che diano una soluzione per poterla verificare altrimenti mi tocca ogni volta postare qui un esercizio sicuramente semplice per tutti e creare solo post inutili intasando il sito inutilmente.

ps

a breve dovrò assillarvi con un altra domanda riguardante le funzioni .... ( non riesco a capacitarmi di questa cosa io ho ritenuto che fosse un errore del testo ma ovviamente non avendo le competenze non vorrei dire castronerie )
BenderBendingRodriguez
Starting Member
Starting Member
 
Messaggio: 5 di 46
Iscritto il: 07/03/2011, 19:02

Messaggioda Martino » 08/03/2011, 21:19

BenderBendingRodriguez ha scritto:se invece volessimo considerare l'insieme delle parti interamente, cioè senza omettere l'insieme $X$ ?
in questo caso $X$ sarebbe un elemento massimale di questo insieme delle parti ?
Si' certo. Io ho tolto X per farti vedere che di massimali in generale ce ne sono piu' di uno.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 4062 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Prossimo

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite