Stima per un cardinale

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Stima per un cardinale

Messaggio da psion_metacreativo »

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.
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

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...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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 :D
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

Io avevo inteso la domanda come: qual'è il max delle cardinalità dell'insieme degli insiemi ottenibili?
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...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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 $.
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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.
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

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 :D ) 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.
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

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.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

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)
:lol: .
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.
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: In ogni caso nel tuo problema non c'e' una famiglia di insiemi, ma uno solo, e io continuo a non capire il testo :)
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: Migliore al variare di cosa?
Al variare degli n insiemi di partenza.
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.
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.

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).
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

Ah ok, n e' il numero di insiemi. Non avevo letto questa cosa...
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Ok, però tutto il tuo discorso forse si poteva riassumere in "edriv, cercavo una stima dall'alto, non dal basso!" senza boubakismi vari :D

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 $.
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

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.
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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 :P
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

[OT]:twisted: :twisted: :twisted: 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 :twisted: :twisted:[/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...
Rispondi