Stima per un cardinale
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Stima per un cardinale
Dati $ n $ insiemi, calcolare la miglior stima per la cardinalità dell'insieme i cui elementi sono insiemi ottenuti applicando (ripetutamente) agli $ n $ insiemi dati, le operazioni binarie insiemistiche di unione, intersezione, differenza e differenza simmetrica.
Secondo me se non metti vincoli sugli insimi la migliore stima possibile è la cardinalità delle parti dell'unione deli insiemi.
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Beh no dai, se A = {1,2,3,4,5,6} e B = {2,3,4,5,6,7}, la cardinalità dell'unione è $ ~ 2^7 $ ma non potrai ottenere tutti i sottoinsiemi, perchè 2,3,4,5,6 sono indistinguibili... forse hai inteso male "migliore stima", hai peccato di ottimismo considerando il caso migliore, mentre psion credo stesse pensando a quello peggiore
Io avevo inteso la domanda come: qual'è il max delle cardinalità dell'insieme degli insiemi ottenibili?
Il questo senso, ad esempio, il minimo è 2.
Il questo senso, ad esempio, il minimo è 2.
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Comunque questo è un genere di problema che mi piace assai!
Siano $ ~ A_1,\ldots, A_n $ gli insiemi, sia $ ~ A = \bigcup A_i $, sia X il sottoinsieme di $ ~ \mathcal{P}(A) $ che contenga gli $ ~ A_i $ e sia chiuso per unione, intersezione, complemento ad A. Si vede subito che X è proprio l'insieme di cui vogliamo stimare la cardinalità.
Se $ ~ a \in A $ definiamo $ ~ f(a) = \bigcap_{a \in x \in X} x $. Osserviamo che $ ~ A' = \{ f(a) | a \in A \} $ è una partizione di A: infatti se a,b sono due suoi elementi, f(a) ed f(b) sono uguali o disgiunti, poichè $ ~ a \in f(b) \Rightarrow f(a) \cap f(b) = f(a) $ e $ ~ a \not \in f(b) \Rightarrow f(a) \cap f(b)^C = f(a) $.
Osserviamo anche che f(a)=f(b) se e soltanto se $ ~ \forall x \in X,\ a \in x \Leftrightarrow b \in x $, ovvero due elementi sono in relazione se e soltanto se sono indistinguibili.
Intanto: per come abbiamo definito f, ogni elemento di A' è un elemento di X. Quindi, unione di elementi di A' appartiene ad X. D'altra parte, se $ ~ x \in X, a \in A $, $ ~ a \in x \Rightleftarrow f(a) \subset x $, quindi $ ~ x = \bigcup_{a \in x} a = \bigcup_{a \in x} f(a) $, e ogni elemento di X è unione di elementi di A'. Concludiamo che $ ~ |X| = |\mathcal{P}(A')| $. Quindi |X| è una potenza di 2, ed ovviamente è almeno n.
La stima potrebbe essere quindi "la più piccola potenza di 2 maggiore o uguale ad n". Stima che può essere raggiunta, scegliendo gli $ ~ A_i $ come n sottoinsiemi a caso di un insieme tale che $ ~ 2^{|A|-1} < n $.
Siano $ ~ A_1,\ldots, A_n $ gli insiemi, sia $ ~ A = \bigcup A_i $, sia X il sottoinsieme di $ ~ \mathcal{P}(A) $ che contenga gli $ ~ A_i $ e sia chiuso per unione, intersezione, complemento ad A. Si vede subito che X è proprio l'insieme di cui vogliamo stimare la cardinalità.
Se $ ~ a \in A $ definiamo $ ~ f(a) = \bigcap_{a \in x \in X} x $. Osserviamo che $ ~ A' = \{ f(a) | a \in A \} $ è una partizione di A: infatti se a,b sono due suoi elementi, f(a) ed f(b) sono uguali o disgiunti, poichè $ ~ a \in f(b) \Rightarrow f(a) \cap f(b) = f(a) $ e $ ~ a \not \in f(b) \Rightarrow f(a) \cap f(b)^C = f(a) $.
Osserviamo anche che f(a)=f(b) se e soltanto se $ ~ \forall x \in X,\ a \in x \Leftrightarrow b \in x $, ovvero due elementi sono in relazione se e soltanto se sono indistinguibili.
Intanto: per come abbiamo definito f, ogni elemento di A' è un elemento di X. Quindi, unione di elementi di A' appartiene ad X. D'altra parte, se $ ~ x \in X, a \in A $, $ ~ a \in x \Rightleftarrow f(a) \subset x $, quindi $ ~ x = \bigcup_{a \in x} a = \bigcup_{a \in x} f(a) $, e ogni elemento di X è unione di elementi di A'. Concludiamo che $ ~ |X| = |\mathcal{P}(A')| $. Quindi |X| è una potenza di 2, ed ovviamente è almeno n.
La stima potrebbe essere quindi "la più piccola potenza di 2 maggiore o uguale ad n". Stima che può essere raggiunta, scegliendo gli $ ~ A_i $ come n sottoinsiemi a caso di un insieme tale che $ ~ 2^{|A|-1} < n $.
Ops, proprio adesso mi è venuta in mente l'autostrada per risolverlo (però non elementarmente).
Il punto chiave del problema è far vedere che |X| è una potenza di 2. Per questo, consideriamo $ ~ \mathcal{P}(A) $ come spazio vettoriale su $ ~ \mathbb{F}_2 $. X, essendo chiuso per differenza simmetrica, è un sottospazio, quindi, prendendo una base, |X| è una potenza di 2.
Il punto chiave del problema è far vedere che |X| è una potenza di 2. Per questo, consideriamo $ ~ \mathcal{P}(A) $ come spazio vettoriale su $ ~ \mathbb{F}_2 $. X, essendo chiuso per differenza simmetrica, è un sottospazio, quindi, prendendo una base, |X| è una potenza di 2.
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Intanto chiarisco quale senso do alla locuzione "miglior stima" nel modo più formale possibile :
Per "Stima $ \displaystyle\ S\ $di un insieme $ \displaystyle\ A\ $" intendiamo affermare che $ \displaystyle\ A\ $ è un insieme la cui cardinalità dipende da un numero intero positivo fissato ed esiste una funzione $ S:\ \mathbb{N}\rightarrow\mathbb{N}\cup \{\infty\} $ tale che $ S(n) $ sia un maggiorante della cardinalità che $ \displaystyle\ A\ $ possiede in corrispondenza di $ \displaystyle\ n\ $, convenendo che $ \displaystyle\infty\ $ sia un maggiorante di ogni numero finito. (si quindi per definire $ \displaystyle\ S\ $ occorre l'assioma di scelta usato tacitamente)
Per "Migliore", detto di una stima $ \displaystyle\ S $, intendiamo che essa assuma per ogni $ \displaystyle\ n\in\mathbb{N} $ l'estremo inferiore del sottoinsieme di $ \mathbb{N}\cup \{\infty\} $ che renda $ \displaystyle\ S\ $ una stima in $ \displaystyle\ n\ $. (quindi l'assioma di scelta ora non ci serve più)
Dunque per risolvere il problema dovete costruire una "stima migliore" per la cardinalità dell'insieme formato dagli insiemi ottenibili applicando ad n insiemi dati una successione finita (se vogliamo esagerare una serie indicizzata da un isieme di cardinalità qualsiasi) di operazioni insiemistiche elementari: unioni, intersezioni, differenze, differenze simmetriche.
Per quanto riguarda Edriv la tua soluzione non è completa: si, tutto giusto quello che hai scritto (se nella mia limitata capacità comprensiva ho ricostruito correttamente il tuo ragionamento ) ma non arrivi a stimare questo benedetto cardinale. Posso dire che la mia soluzione è veramente veramente elementare, tanto che faticherei a formalizzarla. Quindi un consiglio per gli utenti più giovani e inesperti: non lasciatevi spaventare dai nostri sproloqui universitari, questo problema è nella sezione giusta e secondo la mia modesta esperienza olimpica penso che, per quanto riguarda la difficoltà, possa considerarsi un provinciale dimostrativo.
Per "Stima $ \displaystyle\ S\ $di un insieme $ \displaystyle\ A\ $" intendiamo affermare che $ \displaystyle\ A\ $ è un insieme la cui cardinalità dipende da un numero intero positivo fissato ed esiste una funzione $ S:\ \mathbb{N}\rightarrow\mathbb{N}\cup \{\infty\} $ tale che $ S(n) $ sia un maggiorante della cardinalità che $ \displaystyle\ A\ $ possiede in corrispondenza di $ \displaystyle\ n\ $, convenendo che $ \displaystyle\infty\ $ sia un maggiorante di ogni numero finito. (si quindi per definire $ \displaystyle\ S\ $ occorre l'assioma di scelta usato tacitamente)
Per "Migliore", detto di una stima $ \displaystyle\ S $, intendiamo che essa assuma per ogni $ \displaystyle\ n\in\mathbb{N} $ l'estremo inferiore del sottoinsieme di $ \mathbb{N}\cup \{\infty\} $ che renda $ \displaystyle\ S\ $ una stima in $ \displaystyle\ n\ $. (quindi l'assioma di scelta ora non ci serve più)
Dunque per risolvere il problema dovete costruire una "stima migliore" per la cardinalità dell'insieme formato dagli insiemi ottenibili applicando ad n insiemi dati una successione finita (se vogliamo esagerare una serie indicizzata da un isieme di cardinalità qualsiasi) di operazioni insiemistiche elementari: unioni, intersezioni, differenze, differenze simmetriche.
Per quanto riguarda Edriv la tua soluzione non è completa: si, tutto giusto quello che hai scritto (se nella mia limitata capacità comprensiva ho ricostruito correttamente il tuo ragionamento ) ma non arrivi a stimare questo benedetto cardinale. Posso dire che la mia soluzione è veramente veramente elementare, tanto che faticherei a formalizzarla. Quindi un consiglio per gli utenti più giovani e inesperti: non lasciatevi spaventare dai nostri sproloqui universitari, questo problema è nella sezione giusta e secondo la mia modesta esperienza olimpica penso che, per quanto riguarda la difficoltà, possa considerarsi un provinciale dimostrativo.
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Argh. Aspetta, chiariamo un po' di cose.
Un insieme A ha una cardinalita'. Questa non dipende da nulla. Al massimo puoi dire di avere una famiglia di insiemi A(n) parametrizzata dai naturali, e cerchi una funzione S che soddisfi
$ S(n) \geq |A(n)| $
per ogni n.
Per costruire una tale S non serve l'assioma della scelta. Essendo la famiglia A(n) data, una stima S e' proprio
$ S(n) = |A(n)| $
e ovviamente questa e' la stima migliore.
In ogni caso nel tuo problema non c'e' una famiglia di insiemi, ma uno solo, e io continuo a non capire il testo
Migliore al variare di cosa? Se gli insiemi sono fissati, c'e' un piu' piccolo sottoinsieme X dell'unione che e' chiuso per intersezioni, unioni ecc. e la cardinalita' di X non e' una funzione di niente. Come ha osservato edriv, puoi definire una relazione di equivalenza dicendo che x e' equivalente a y se sono elementi degli stessi insiemi Ai. Se m e' il numero di classi di equivalenza, allora
$ |X| = 2^m $
Se non e' questo che chiedi, non ho proprio capito la domanda.
Un insieme A ha una cardinalita'. Questa non dipende da nulla. Al massimo puoi dire di avere una famiglia di insiemi A(n) parametrizzata dai naturali, e cerchi una funzione S che soddisfi
$ S(n) \geq |A(n)| $
per ogni n.
Per costruire una tale S non serve l'assioma della scelta. Essendo la famiglia A(n) data, una stima S e' proprio
$ S(n) = |A(n)| $
e ovviamente questa e' la stima migliore.
In ogni caso nel tuo problema non c'e' una famiglia di insiemi, ma uno solo, e io continuo a non capire il testo
Migliore al variare di cosa? Se gli insiemi sono fissati, c'e' un piu' piccolo sottoinsieme X dell'unione che e' chiuso per intersezioni, unioni ecc. e la cardinalita' di X non e' una funzione di niente. Come ha osservato edriv, puoi definire una relazione di equivalenza dicendo che x e' equivalente a y se sono elementi degli stessi insiemi Ai. Se m e' il numero di classi di equivalenza, allora
$ |X| = 2^m $
Se non e' questo che chiedi, non ho proprio capito la domanda.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Credevo di essere stato chiaro ma in effetti non si può mischiare il sacro (leggasi Bourbakismo) con il profano (leggasi intuizione comune del significato delle parole)
.
Riassunto finale:
Situazione
Siano dati n insiemi ---> costruiamo A(n) definito sopra ---> calcoliamo |A(n)|
Problema1
Al variare degli n insiemi di partenza esiste un massimo per |A(n)|? Se esiste chiamiamo "miglior stima" questo massimo e denotiamolo con S(n).
Problema2
Descrivere la funzione che ad n--->S(n).
.
fin qui sei perfettamente coincidente con quello che volevo esprimere, e forse non sono stato molto chiaro e di questo mi scuso, (sul discorso dell'assioma di scelta siamo d'accordo quando dici che per costruire la "stima migliore" non serve, ma se guardi come avevo sviluppato il discorso quella che io avevo chiamato semplicemente "stima" è una funzione di scelta che pesca un elemento qualsiasi nell'insieme dei maggioranti scordandosi che su questo insieme abbiamo un buon ordianmento e dunque un minimo)Nonno Bassotto ha scritto:Argh. Aspetta, chiariamo un po' di cose.
Un insieme A ha una cardinalita'. Questa non dipende da nulla. Al massimo puoi dire di avere una famiglia di insiemi A(n) parametrizzata dai naturali, e cerchi una funzione S che soddisfi
$ S(n) \geq |A(n)| $
per ogni n.
Per costruire una tale S non serve l'assioma della scelta. Essendo la famiglia A(n) data, una stima S e' proprio
$ S(n) = |A(n)| $
e ovviamente questa e' la stima migliore.
Sia A(n) l'insieme formato dagli insiemi ottenibili applicando ad n insiemi dati una successione finita (se vogliamo esagerare una serie indicizzata da un isieme di cardinalità qualsiasi) di operazioni insiemistiche elementari: unioni, intersezioni, differenze, differenze simmetriche.Nonno Bassotto ha scritto: In ogni caso nel tuo problema non c'e' una famiglia di insiemi, ma uno solo, e io continuo a non capire il testo
Al variare degli n insiemi di partenza.Nonno Bassotto ha scritto: Migliore al variare di cosa?
vero ma se la volete vedere in questo modo chiedo di stimare le classi di equivalenza m visto che |X| e funzione di m come tu stesso hai scritto.Nonno Bassotto ha scritto: Se gli insiemi sono fissati, c'e' un piu' piccolo sottoinsieme X dell'unione che e' chiuso per intersezioni, unioni ecc. e la cardinalita' di X non e' una funzione di niente. Come ha osservato edriv, puoi definire una relazione di equivalenza dicendo che x e' equivalente a y se sono elementi degli stessi insiemi Ai. Se m e' il numero di classi di equivalenza, allora
$ |X| = 2^m $
Se non e' questo che chiedi, non ho proprio capito la domanda.
Riassunto finale:
Situazione
Siano dati n insiemi ---> costruiamo A(n) definito sopra ---> calcoliamo |A(n)|
Problema1
Al variare degli n insiemi di partenza esiste un massimo per |A(n)|? Se esiste chiamiamo "miglior stima" questo massimo e denotiamolo con S(n).
Problema2
Descrivere la funzione che ad n--->S(n).
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Ok, però tutto il tuo discorso forse si poteva riassumere in "edriv, cercavo una stima dall'alto, non dal basso!" senza boubakismi vari
Detto questo, per risolvere il problema si potrebbe seguire questi passaggi (mi riconduco al mio primo post):
- definire f(a) come prima
- dimostrare che f(a) = f(b) se e soltanto se $ ~ \forall x \in X,\ a \in x \Leftrightarrow b \in x $
- dimostrare che $ ~ \forall x \in X,\ a \in x \Leftrightarrow b \in x $ se e soltanto se $ ~ \forall i,\ a \in A_i \Leftrightarrow b \in A_i $
- concludere che ogni f(a) si può scrivere come intersezione tra un po' di $ ~ A_i $ e un po' di complementari di $ ~ A_i $
- concludere che gli f(a) sono al più $ ~ 2^n $, e che gli f(a) non vuoti sono al più $ ~ 2^n - 1 $, perchè si toglie l'intersezione dei complementari di tutti gli $ ~ A_i $
- concludere che $ ~ |X| \le 2^{2^n - 1} $
- trovare l'uguaglianza in questo modo: consideriamo $ ~ C = \{1,2,\ldots,n\} $, $ ~ A = \mathcal{P}(C) $, $ ~ A_i = \{x \in A|i \in x \} $, e dimostrare che $ ~ \{f(a) | a \in A \} = \mathcal{P}(C) \setminus \emptyset $.
Detto questo, per risolvere il problema si potrebbe seguire questi passaggi (mi riconduco al mio primo post):
- definire f(a) come prima
- dimostrare che f(a) = f(b) se e soltanto se $ ~ \forall x \in X,\ a \in x \Leftrightarrow b \in x $
- dimostrare che $ ~ \forall x \in X,\ a \in x \Leftrightarrow b \in x $ se e soltanto se $ ~ \forall i,\ a \in A_i \Leftrightarrow b \in A_i $
- concludere che ogni f(a) si può scrivere come intersezione tra un po' di $ ~ A_i $ e un po' di complementari di $ ~ A_i $
- concludere che gli f(a) sono al più $ ~ 2^n $, e che gli f(a) non vuoti sono al più $ ~ 2^n - 1 $, perchè si toglie l'intersezione dei complementari di tutti gli $ ~ A_i $
- concludere che $ ~ |X| \le 2^{2^n - 1} $
- trovare l'uguaglianza in questo modo: consideriamo $ ~ C = \{1,2,\ldots,n\} $, $ ~ A = \mathcal{P}(C) $, $ ~ A_i = \{x \in A|i \in x \} $, e dimostrare che $ ~ \{f(a) | a \in A \} = \mathcal{P}(C) \setminus \emptyset $.
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Perfetto Edriv, tra l'altro non mi ero accorto che nel primo post avevi fatto una stima dal basso tanto efficiente quindi complimenti.
Non vorrei "sporcare" un topic risolto così formalmente ma per appagare la curiosità dei più giovani espongo le mie dilettantistiche elucubrazioni che precedono, in intuizione e semplicità, la tua soluzione anche se essenzialmente coincidenti con essa:
Un insieme è un cerchio disegnato su un foglio di carta, n insiemi possono formare al più $ 2^{n-1} $ zone delimitate da un tratto di penna , qualsiasi operazione insiemistica tra gli insiemi di partenza produce un insieme che è unione disgiunta di qualcuna delle regioni dunque al massimo posso ottenere $ |P(X)| $ risultati diversi dove X è l'insieme che contiene le regioni disegnate sul foglio.
Non vorrei "sporcare" un topic risolto così formalmente ma per appagare la curiosità dei più giovani espongo le mie dilettantistiche elucubrazioni che precedono, in intuizione e semplicità, la tua soluzione anche se essenzialmente coincidenti con essa:
Un insieme è un cerchio disegnato su un foglio di carta, n insiemi possono formare al più $ 2^{n-1} $ zone delimitate da un tratto di penna , qualsiasi operazione insiemistica tra gli insiemi di partenza produce un insieme che è unione disgiunta di qualcuna delle regioni dunque al massimo posso ottenere $ |P(X)| $ risultati diversi dove X è l'insieme che contiene le regioni disegnate sul foglio.
Una domanda interessante potrebbe essere: esibire il caso di uguaglianza disegnando cerchi, o comunque curve chiuse, sul piano.
Esibire il caso di uguaglianza con n insiemi viene intutivo farlo in uno spazio a n-1 dimensioni. È possibile farlo stare sul piano?
Però non vorrei sporcare questo topic combinatorico con una domanda troppo geometrica
Esibire il caso di uguaglianza con n insiemi viene intutivo farlo in uno spazio a n-1 dimensioni. È possibile farlo stare sul piano?
Però non vorrei sporcare questo topic combinatorico con una domanda troppo geometrica
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
[OT] buahauhauhauhauhauh ora tocca a me chiedere delucidazioni sul problema da te posto che mi è oscuro in assai punti, e credo che definire formalmente la questione sia faccenda assai più complicata che spiegare il mio problema [/OT] meglio fermarsi qui prima di arrivare a cose come il corollario che si potrebbe ricavare da questo problema: ogni sigma-algebra generata da un insieme finito è finita... e via dicendo...