1. Assioma della scelta generalizzato

Oltre la matematica elementare: teoria, esercizi, e riflessioni sulle varie branche della matematica che si fanno all'università.

1. Assioma della scelta generalizzato

Messaggioda Gizeta » 05/10/2014, 20:38

Sia [tex]\mathscr{F}[/tex] una famiglia di sottoinsiemi (non necessariamente disgiunti) di un insieme [tex]E[/tex], allora [tex]\exists \phi:\mathscr{F} \rightarrow E[/tex] t.c. [tex]\phi(X) \in X[/tex], con [tex]X \in \mathscr{F}[/tex].
[tex]\phi[/tex] è detta funziona di scelta.

Dati due insiemi [tex]A[/tex] e [tex]B[/tex] e una funzione [tex]\phi:A \rightarrow B[/tex], [tex]\phi(X)[/tex] è la solita immagine di [tex]X\in \tau(A)[/tex] [insieme delle parti di [tex]A[/tex]] definita come {[tex]y:y \in B[/tex] e [tex]\exists x \in X: y=f(x)[/tex]}.

Buon divertimento :D

p.s. Sarebbe bello creare una staffetta anche per questa sezione, se l'idea vi piacesse potrei rendere questo il problema 1.
Ultima modifica di Gizeta il 14/10/2014, 7:28, modificato 3 volte in totale.
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Re: Assioma della scelta generalizzato

Messaggioda afullo » 06/10/2014, 12:12

Hmm, la domanda quale sarebbe? :)
afullo
 
Messaggi: 1373
Iscritto il: 13/03/2013, 22:06

Re: Assioma della scelta generalizzato

Messaggioda hyka » 06/10/2014, 13:04

Se si parla di AC, partecipo anche io :lol:

Sia \(A\) un insieme e \(A_i\) una sua partizione indicizzata da un insieme \(I\). Questo è equivalente a dire che esiste una funzione suriettiva \(\tau : A \to I\). Questa mappa è detta fibrato(in inglese bundle, e forma una bella categoria). Ora, da ogni indice si può risalire alla partizione di \(A\), dunque \(A_i = \{a : A . \tau(a) = i\}\) sarà detta fibra di \(i\) (nota tecnica, con \(:\) intendo qualcosa di simile a \(\in\) e il \(.\) lo uso per separare espressioni, può essere considerato come una \(,\) o un tale che).

Una funzione \(f: A \to B\) è detta:
  • inj se ogni fibra contiene al più un elemento, o equivalentemente se \(f(a_1) = f(a_2) \Rightarrow a_1 = a_2\)
  • sur se ogni fibra è non-vuota
  • mono se per ogni insieme \(T\) e per ogni coppia di frecce \(\alpha_1, \alpha_2 : T \to A\) si ha che \(f \circ \alpha_1 = f \circ \alpha_2 \Rightarrow \alpha_1 = \alpha_2\)
  • epi se per ogni insieme \(T\) e ogni coppia di frecce \(\alpha_1, \alpha_2 : B \to T\) si ha che \(\alpha_1 \circ f = \alpha_2 \circ f \Rightarrow \alpha_1 = \alpha_2\)
  • split-mono se esiste una funzione \(r: B \to A\) tale che \(r \circ f = 1_A\) (\(1_A\) è l'identità di \(A\), la funzione \(r\) è detta sinistro-inversa o retrazione di \(f\))
  • split-epi se esiste una funzione \(s : B \to A\) tale che \(f \circ s = 1_B\) (la funzione \(s\) è detta destro-inversa o sezione di \(f\))

Dimostrare (se non lo avete mai fatto) che in \(Sets\)(la categoria degli insiemi) si ha \(\text{inj} \Leftrightarrow \text{mono} \Leftrightarrow \text{split-mono}\) e \(\text{sur} \Leftrightarrow \text{epi} \Leftrightarrow \text{split-epi}\) (ho scritto in \(Sets\) perché le ultime quattro definizioni valgono in qualsiasi categoria e non sempre quella doppia implicazione è vera).

Hint:
Testo nascosto:
\(\text{sur} \Leftrightarrow \text{split-epi}\) è l'assioma della scelta
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Assioma della scelta generalizzato

Messaggioda Gizeta » 06/10/2014, 19:23

afullo ha scritto:Hmm, la domanda quale sarebbe? :)


Dimostrare la proposizione contenuta nel mio post precedente (prime due righe) :lol:

@Hyka

Sai che ho scoperto che la mia prof di algebra tratterà anche un po' di teoria delle categorie? :lol:

Ho letto il problema di sfuggita, proverò a risolverlo in questi giorni (anche perché devo far un po' di pratica con l'AC).

Il termine fibrato mi fa venire in mente la fibra, ossia data [tex]f:A \rightarrow B[/tex] e [tex]y\in B[/tex] definiamo fibra di [tex]y[/tex] [tex]f^{-1}([/tex] {[tex]y[/tex]}[tex])[/tex].

In particolare, se [tex]f[/tex] è suriettiva, possiamo individuare [tex]\mathscr{F}=[/tex]{[tex]f^{-1}([/tex] {[tex]y[/tex]}[tex]):y \in B[/tex]}, questa è una partizione di [tex]A[/tex] (si verifica facilmente) e ovviamente è definita dalla relazione di equivalenza [tex]x \sim y \iff f(x)=f(y)[/tex] [il [tex]\iff[/tex] sarebbe con la scritta "DEF" sotto, ma non riesco a riprodurre tale simbolo in latex].


Infine definiamo [tex]g=[/tex]{[tex][x] \mapsto f([x])=f(x): \mathscr{F} \rightarrow B[/tex]}, e questa è anche iniettiva [infatti, possiamo pensare di aver contratto in un unico "punto" (i.e. la classe di equivalenza) tutti i punti di [tex]A[/tex] con una uguale immagine in [tex]B[/tex]].

Se [tex]\tau[/tex] è l'applicazione canonica di [tex]A[/tex] sul quoziente [tex]\mathscr{F}[/tex] [[tex]\tau=[/tex]{[tex]x \mapsto [x]: A \rightarrow \mathscr{F}[/tex]}], allora [tex]f=g \circ \tau[/tex].

E questo è un modo per rendere anche iniettiva una funzione suriettiva; un altro è quello per cui Prodi tira in ballo l'assioma della scelta, ossia trovare una opportuna restrizione di [tex]f[/tex] {[tex]f \mid_{\sigma}=[/tex]{[tex]x \mapsto f(x):C \rightarrow B[/tex]}}, con [tex]C \subset A[/tex] (e da qui alla necessità dell'assioma della scelta il passo è breve: come deve essere [tex]C[/tex]?).
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Re: Assioma della scelta generalizzato

Messaggioda hyka » 07/10/2014, 12:45

Gizeta ha scritto:Dimostrare la proposizione contenuta nel mio post precedente (prime due righe) :lol:
...
E questo è un modo per rendere anche iniettiva una funzione suriettiva; un altro è quello per cui Prodi...


Sono andato a vedere su quel libro, in buona sostanza da

Prodi ha scritto:Data comunque una partizione \(\{X : X \in \mathscr{F}\}\) di un insieme \(E\) esiste un sottoinsieme di \(E\) che ha uno e un solo elemento in comune con ciascuno degli \(X \in \mathscr{F}\).


si vuole dimostrare quanto detto.

Allora, dall'ipotesi si ha che per ogni \(X\) non vuoto, considerando \(\mathscr{F} = \{X\}\) esiste un insieme \(Y\) sottoinsieme di \(X\) tale che \(|X \cap Y| = 1\). Chiamiamo \(x\) l'elemento dell'intersezione. Allora l'ipotesi è equivalente a dire che da ogni insieme vuoto si può "scegliere" un elemento.
E ora è fatta, infatti basta esplicitare la funzione che associa ad ogni insieme contenuto della partizione una sua "scelta" di un suo elemento.


@Hyka

Sai che ho scoperto che la mia prof di algebra tratterà anche un po' di teoria delle categorie? :lol:


Non male :lol:
Ultima modifica di hyka il 07/10/2014, 17:35, modificato 2 volte in totale.
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Assioma della scelta generalizzato

Messaggioda Gizeta » 07/10/2014, 15:37

Umh, sinceramente non riesco a capire.
Ad esempio, cosa intendi con [tex]\mathscr{F}=X[/tex] [presumo la tua [tex]F[/tex] sia la mia [tex]\mathscr{F}[/tex]]?
Poi parli di partizione, ma quale?
E, infine, non ho capito se stai cercando di spiegare intuitivamente l'assioma della scelta o se stai cercando di dimostrare quello generalizzato.

:lol:

Se stai cercando di fare quest'ultimo, partiamo dal fatto che ci piacerebbe applicare l'assioma della scelta [classico] e ci serve, dunque, una partizione che non abbiamo, come si fa?

Testo nascosto:
Avrai visto cosa suggerisce Prodi: considerare insiemi formati da coppie del tipo [tex](x,X)[/tex] con [tex]X \in \mathscr{F}[/tex] e [tex]x \in X[/tex].
In tal modo...

si riesce a rendere "distinguibili" gli elementi comuni ad elementi diversi di [tex]\mathscr{F}[/tex], infatti, ad esempio, [tex](x,X) \not = (x, X')[/tex], sebbene all'atto pratico siano lo stesso elemento di [tex]E[/tex]... e la nostra partizione è bella che servita

Non male


Ha riacquistato la mia fiducia :lol:
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Re: Assioma della scelta generalizzato

Messaggioda hyka » 07/10/2014, 17:16

Grazie per averlo segnalato, ho corretto i typo, vedi se ti torna ora :roll:

Testo nascosto:
Scritto nell'ora di pausa tra due lezioni mentre preparavo da mangiare, e la cosa divertente è che avevo scritto F = {X} ma in latex bisogna mettere lo slash prima delle graffe :evil:


In sostanza ho cercato di mostrare che da ogni insieme non vuoto si può scegliere un elemento (altra formulazione equivalente di AC in Set) e quindi dato ogni insieme della famiglia posso associargli un elemento a caso di quelli che contiene, avendo così \(\phi(X) \in X\) (l'ho detta a parole, volendo si scrive formalmente).


Piccola chicca: gli insiemi \((X, x) . x \in X\) sono detti insiemi puntati, e insieme alle mappe che "preservano i punti" formano un'altra categoria :lol:

Edit.
Sono partito dalla definizione che da Prodi, ho dimostrato una formulazione equivalente e da quell'altra ho dimostrato le tue prime due righe(se non ho commesso errori).
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Assioma della scelta generalizzato

Messaggioda Gizeta » 12/10/2014, 16:31

Hyka, emh... la tesi sarebbe che la funzione esiste, quindi o la costruisci (come ho fatto io) oppure, se preferisci la formulazione equivalente dell'AC, mostri che esiste un sottoinsieme di [tex]E[/tex] che contiene uno e un solo elemento preso da ognuno dei sottoinsiemi componenti [tex]\mathscr{F}[/tex].

Inoltre, non riesco ancora a capire di quale partizione parli (se ti riferisci a [tex]\mathscr{F}[/tex], forse non mi sono espresso bene nel testo: i sottoinsiemi di [tex]E[/tex] che compongono [tex]\mathscr{F}[/tex] non sono necessariamente disgiunti e non necessariamente ricoprono [tex]E[/tex], dunque [tex]\mathscr{F}[/tex] non è una partizione di [tex]E[/tex]) e continuo ad avere oscuro il significato della notazione [tex]\mathscr{F} = \{X\}[/tex] (cioè, per me quello vuole dire che [tex]\mathscr{F}[/tex] è composto da un solo elemento e questo è [tex]X[/tex], mentre probabilmente tu intendi che [tex]\mathscr{F}[/tex] è una famiglia di insiemi).

:D

Ne ho anche un altro sull'AC, ma lo posto dopo che è saltata fuori la soluzione di questo.

p.s. Scusa il ritardo, ma nei giorni scorsi non riuscivo a rispondere a causa di problemi tecnici del forum.
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Re: Assioma della scelta generalizzato

Messaggioda hyka » 13/10/2014, 11:30

Gizeta ha scritto:Inoltre, non riesco ancora a capire di quale partizione parli (se ti riferisci a [tex]\mathscr{F}[/tex], forse non mi sono espresso bene nel testo: i sottoinsiemi di [tex]E[/tex] che compongono [tex]\mathscr{F}[/tex] non sono necessariamente disgiunti e non necessariamente ricoprono [tex]E[/tex], dunque [tex]\mathscr{F}[/tex] non è una partizione di [tex]E[/tex]) e continuo ad avere oscuro il significato della notazione [tex]\mathscr{F} = \{X\}[/tex] (cioè, per me quello vuole dire che [tex]\mathscr{F}[/tex] è composto da un solo elemento e questo è [tex]X[/tex], mentre probabilmente tu intendi che [tex]\mathscr{F}[/tex] è una famiglia di insiemi).


Ho usato lo stesso simbolo per indicare qualcosa di diverso(mea culpa). Con \(\mathscr{F} = \{X\}\) intendevo la partizione banale(trivial partition) del generico insieme \(X\) di cui stavo parlando.

Gizeta ha scritto:Hyka, emh... la tesi sarebbe che la funzione esiste, quindi o la costruisci (come ho fatto io) oppure, se preferisci la formulazione equivalente dell'AC, mostri che esiste un sottoinsieme di [tex]E[/tex] che contiene uno e un solo elemento preso da ognuno dei sottoinsiemi componenti [tex]\mathscr{F}[/tex].


Provo a costruire esplicitamente la funzione.

Gizeta ha scritto:Sia [tex]\mathscr{F}[/tex] una famiglia di sottoinsiemi (non necessariamente disgiunti) di un insieme [tex]E[/tex], allora [tex]\exists \phi:\mathscr{F} \rightarrow E[/tex] t.c. [tex]\phi(X) \in X[/tex], con [tex]X \in \mathscr{F}[/tex]


Per ogni elemento \(X\) di \(\mathscr{F}\)(sottoinsieme non-vuoto di \(E\)), possiamo considerare la sua partizione banale \(\mathscr{G} = \{X\}\), allora Prodi ci dice che esiste un sottoinsieme \(Y \subset X\) (la notazione di Prodi e quella del tuo problema overlappano perciò sto cambiando le lettere) tale che \(| Y \cap X | = 1\).

Allora \(\phi : \mathscr{F} \to E\) che manda ogni \(X \in \mathscr{F}\) in \(\text{extract}(Y \cap X) \in X \subset E\) è la funzione desiderata.

Con \(\text{extract}\) intendo la funzione che estrare l'unico elemento da ogni singoletto, cioè la funzione \(\{\{x\}\} \to \{x\}\) definita come \(\{x\} \mapsto x\) (tra l'altro è l'unica possibile funzione con questo tipo :roll: )
hyka
 
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Assioma della scelta generalizzato

Messaggioda Gizeta » 13/10/2014, 16:12

Continua a non convincermi, sorry :cry:
Al di là di ogni tecnicismo, la partizione banale... è l'insieme [tex]X[/tex] stesso (si, ok, l'insieme dell'insieme, ma poi ti riferisci agli elementi di [tex]X[/tex]), quindi mi stai dicendo che puoi scegliere un elemento da ciascuno di questi... ma questa è proprio la tesi.
Inoltre la funziona di scelta classica applicata alle partizioni banali di ogni insieme [tex]X[/tex] altro non è che la funzione identica [tex]I_X[/tex] (infatti hai poco da scegliere: c'è un solo elemento dentro la partizione!) [e [tex]\tau(\{X\})=\{\{X\},\emptyset\}[/tex]].
Mi sembra una cane che si morde la coda, ma magari non riesco bene a capire cosa intendi.

Ma poi il suggerimento di Prodi ti fornisce una bellissima partizione di [tex]\mathscr{F}[/tex] e il resto è tutto in discesa, perché non usarlo?


Testo nascosto:
Siano [tex]T=[/tex]{[tex](x,X): X \in \mathscr{F}[/tex] e [tex]x \in X[/tex]} e [tex]T_x=[/tex] {[tex](x,X):x \in X[/tex]}.
Sia [tex]\mathscr{T}=[/tex]{[tex]T_x:X \in \mathscr{F}[/tex]}...


p.s. postate anche qualche altro problema carino con cui possiamo divertirci :lol:
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Prossimo

Torna a Matematica Universitaria

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti