Pagina 3 di 7

Inviato: 22 ago 2007, 14:55
da 3C273
Moebius, mi piacerebbe molto vedere la dimostrazione che senza l'assioma della scelta il problema non ha soluzione! Ma forse è meglio parlarne dopo che viene trovata la soluzione più semplice al problema originale?
Però a proposito di questo:
moebius ha scritto:Per il resto, se mi passate il fatto che la negazione dell'assioma della scelta implica che tutti i subset della retta reale sono misurabili (cosa che mi ricordo essere vera ma che adesso non saprei ridimostrare)
ho trovato su wiki che
There exists a model of ZF¬C in which every set in Rn is measurable.
(mentre per esempio la riga sotto dice che "In all models of ZF¬C, the generalized continuum hypothesis does not hold.")
Ora io non me ne intendo abbastanza, quindi chiedo: qui si dice che esiste un modello di ZF¬C in cui vale questa cosa, ma non che vale per ogni modello. Detto questo e fidandoci di wiki, la tua dimostrazione è ancora valida o no?

EvaristeG et al., non riesco a salvare i nanetti sfruttando le informazioni ricavate da quanto dicono i nanetti precedenti! Mi sembra di aver capito che si tratta di generalizzare la strategia classica con un numero finito di nanetti, ma non riesco... tanto per capire, qui non c'è bisogno dell'assioma della scelta?

Stoppa2006 et al., visto che la tua soluzione era corretta devo smettere di insistere a chiedere di cercare una soluzione diversa al problema che ho posto all'inizio; però, visto che comunque vorrei che venisse trovata la soluzione alternativa che secondo me è più semplice, adesso metto in bianco un paio di hint, il primo un po' più oscuro e il secondo molto più esplicito, anzi praticamente è la soluzione:
Hint n. 1 - oscuro
Supponiamo di cambiare per ora il testo del problema: mettiamo i nanetti in fila, in modo che anche noi che dobbiamo disporre i cappelli conosciamo il loro ordinamento, e garantiamo ai nanetti che metteremo i cappelli sulle loro teste secondo una successione (definitivamente) periodica. In questo caso, che strategia potranno applicare? Stavolta ovviamente non c'è bisogno della scelta, visto che le possibili configurazioni sono numerabili... e tutto può essere esplicitato... Ora, trovata questa strategia, generalizzare per configurazioni di cappelli qualsiasi!
Hint n. 2 - esplicito
Chiaramente per prima cosa ordiniamo i nanetti. Considerazione: se due configurazioni di cappelli (le chiamerò anche successioni di cappelli) sono definitivamente uguali, allora se la successione di risposte dei nanetti va bene per l'una, la stessa successione di risposte va bene anche per l'altra, perchè le due successioni di cappelli differiscono per al più un numero finito di termini. Quindi, che fare? Dividere in xxxxxx di xxxxxxxxxxx... poi sfruttare l'xxxxxxx della xxxxxx... e poi le conclusioni sono le stesse della soluzione dell'hint n.1!
P.S.: che sadica che sono, prima nell'hint n.2 al posto delle "xxx" avevo messo le parole, ma poi non ho saputo resistere e le ho sostituite con le "xxx"! :twisted: Comunque non dovrebbe essere difficile capire le "parole censurate"!!! :wink:

Inviato: 27 ago 2007, 14:41
da moebius
Bon... metto qua quello che ho fatto (anche grazie a 3C273) riguardo alla necessita' dell'assioma della scelta per i poveri nanetti.

Dunque... supponiamo che esita una strategia... Hmm no... in realta' sappiamo che esiste, quindi forse sarebbe piu' giusto dire "scegliamo una strategia vincente per i nanetti" :P
Cerchiamo di fare le cose in modo vagamente formale. Detta K la cardinalita' dei nanetti, consideriamo lo spazio probabilizzato (C, m) dove:
C = {configurazioni di cappelli su K nanetti}
m = misura di probabilita' uniforme su C

Dicevamo... Fissata la strategia, consideriamo la successione:
p(n)=probabilita' che, scelta a caso una configurazione di cappelli, i nanetti commettano al piu' n errori (la vorrei monotona...)

Now... Questa successione, poiche' la strategia funziona, converge ad 1.
Quindi, parlando da bruto analista, scelta una probabilita' P spropositatamente alta a mio piacere (o a piacere dei nanetti, che sono molti piu' di me...), da un certo l in avanti i nanetti hanno almeno la probabilita' P di commettere al piu' n>=l errori.
Vogliamo calcolare in media quanti nanetti sbagliano il colore del proprio cappello tra i primi 4*l.
So...
I primi 4*l nanetti faranno al piu' l errori con probabilita' almeno P.
Dunque, mediamente, al piu' P*l+(1-P)*4*l=l*(4-3P) di loro sbaglieranno.
Credo pero' che nessuno si opporra' se dico che data una configurazione a caso di cappelli la probabilita' di ogni nano di indovinare il proprio colore e' 1/2 (qualsiasi sia la strategia adottata, vincente o meno, le configurazioni buone e quelle cattive sono in biezione). Ossia mediamente sbaglieranno 2*l nanetti su 4*l... Peccato che possa prendere P>2/3 :(

Dove ho barato? All'inizio... ho supposto che ogni sottoinsieme di C (in realta' solo quelli del tipo che mi interessavano) fosse misurabile.
Bon, come dicevo qualche post ago, per quel che mi ricordo:
la negazione dell'assioma della scelta implica che tutti i subset della retta reale sono misurabili
Che mi permetterebbe di dimostrare che per $ K=\aleph_0 $ la non scelta (che posso aggiungere tra le mie ipotesi se non uso la scelta nella strategia) e l'esistenza di una strategia conduce a contraddizione, quindi una eventuale soluzione deve utilizzare l'assioma della scelta (o fatti equivalenti).
Per cardinalita' superiori, le argomentazioni sono sostanzialmente analoghe.
Due paroline su:
3C273 ha scritto: ho trovato su wiki che
Citazione:
There exists a model of ZF¬C in which every set in Rn is measurable.

(mentre per esempio la riga sotto dice che "In all models of ZF¬C, the generalized continuum hypothesis does not hold.")
Ora io non me ne intendo abbastanza, quindi chiedo: qui si dice che esiste un modello di ZF¬C in cui vale questa cosa, ma non che vale per ogni modello. Detto questo e fidandoci di wiki, la tua dimostrazione è ancora valida o no?
Dunque... questo significa che è possibile costruire un modello della teoria degli insiemi in cui non esistono sottoinsiemi non misurabili e che soddisfi la non scelta. L'eventuale esistenza di un modello di ZF¬C in cui esistano sottoinsiemi di R non misurabili porterebbe a concludere che il fatto che ogni sottoinsieme di R sia misurabile e' indipendente dalla non scelta.
In realta' a noi interessa che si possano costruire sottoinsiemi non misurabili di R solo assumendo l'assioma della scelta, cosa che ho trovato sempre su wiki (ammesso che sia vero):
http://it.wikipedia.org/wiki/Sigma-algebra ha scritto: È tuttavia lecito chiedersi se vi siano sottoinsiemi dei numeri reali che non appartangano alla σ-algebra di Lebesgue (tali sottoinsiemi sono anche detti insiemi non misurabili secondo Lebesgue). Ebbene, l'esistenza di tali sottoinsiemi è legata all'assioma della scelta, ovvero essi si possono costruire se e solo se si assume tale assioma.

Inviato: 28 ago 2007, 12:22
da 3C273
Molto molto bella! (soprattutto dopo che l'ho capita :oops: !!!)

[Stream of consciousness Mode ON]
AVVERTENZE:
1. somministrare solo a cervelli già rodati nel campo delle pippe mentali e delle follie insensate
2. si declina ogni responsabilità in caso di somministrazione a cervelli sani
3. prima della somministrazione, fare un lungo respiro poichè quanto segue è un periodo unico senza nemmeno un punto


mi rimane piuttosto oscuro il punto in cui si dice che assumendo la non scelta [esiste un modello in cui] tutti i sottoinsiemi di R sono misurabili, non tanto per la dimostrazione di cui non mi pongo il problema perchè è fuori dalla mia portata, quanto per le conclusioni: voglio dire, se ho capito bene concludiamo che nello specifico modello della teoria degli insiemi di ZF con annessa definizione di R a cui siamo abituati a pensare, tutti i sottoinsiemi di R sono misurabili se e solo se si assume la non scelta, ma questo non vieta a priori di costruire un altro modello della stessa teoria in cui i nanetti potrebbero forse farcela senza assumere la scelta, della qual cosa ci interessa poco perchè comunque non si parlerebbe più di R come lo si definisce abitualmente, ma di una cosa molto più generica (se ho ben capito, il meglio che si possa fare con una teoria al prim'ordine, che è comunque ben poco rispetto a quello che ci piacerebbe, visto che per esempio provando a descrivere i naturali con una teoria del prim'ordine spuntano come funghi modelli di N di qualsiasi cardinalità), ma soprattutto ci interessa poco perchè di meglio non sappiamo fare, e in ogni caso i nanetti così sono contenti perchè loro sono molto più avanti di noi, perchè per loro la scelta non è un problema e si salvano?
[Stream of consciousness Mode OFF]

Inviato: 28 ago 2007, 12:41
da 3C273
A proposito... a parte i miei flussi di coscienza che non siete obbligati a sopportare... :shock:
Mi rivolgo a EvaristeG, Stoppa2006, MateCa e a tutti quelli che sembravano interessati al problema: avete letto i miei due hint, di cui il secondo è praticamente la soluzione? Sarei curiosa di sapere cosa ne pensate, visto che ne avevamo parlato tanto! Mi rendo conto che qualsiasi cosa contenga l'assioma della scelta è complicata a priori, ma volevo sapere il vostro parere adesso che la soluzione è stata (più o meno :lol: ) esplicitata! A me continua a sembrare bella anche se usa uno degli assiomi più "spinosi" che ci siano! What do you make of it? :) (Accetterò qualsiasi eventuale insulto!!! :wink: )

Inviato: 28 ago 2007, 15:31
da 3C273
Ripensavo al problema simile al mio che ha proposto EvaristeG, cioè il problema in cui ci sono infiniti (numerabili) nanetti che parlano uno alla volta, a cui vengono messi in testa cappelli bianchi o neri, e che devono in qualche modo passarsi un'informazione mentre rispondono... allora io mi ero messa in testa (non so perchè) che questo problema si dovesse poter risolvere senza l'assioma della scelta, ma non riuscivo a fare niente.

Ora però ho trovato una soluzione che fa uso dell'assioma della scelta ma che permette di far sbagliare ogni volta al più un nanetto... e la soluzione è semplicemente un misto di due soluzioni, le quali sono:
1. la soluzione che ho proposto io per il problema iniziale di questo thread
2. la soluzione al problema classico con un numero finito di nanetti che parlano uno per volta...

Ovvero:
il primo nano dice un colore a seconda della parità del numero (finito) di nanetti che hanno in testa un colore diverso da quello che sarebbe previsto dal rappresentante della classe di equivalenza che contiene la configurazione di cappelli uscita (secondo la relazione "due successioni/configurazioni sono in relazione sse differiscono per al più un numero finito di termini/cappelli"). E tutti gli altri nanetti quindi sanno cosa devono rispondere.
Ecco così sbaglia al più un nanetto, ma comunque mi serve la scelta per poter definire a priori il rappresentante di ogni classe di equivalenza... era questo che intendevi, EvaristeG, oppure avevi in mente tutt'altro?

Inviato: 28 ago 2007, 18:47
da edriv
Metto anche io qualche osservazione su questo bel problema di cui tra l'altro abbiamo già discusso nel pub "Il Re Leone" una sera di Cesenatico :P

Sia A l'insieme delle funzioni da N = {1,2,...} a {0,1}, o meglio, 2 = {0,1}, e grazie a Stoppa che mi delizia con questa bella notazione :)

Definiamo la funzione $ \displaystyle d: A \times A \rightarrow \mathbb{N} \cup \{0\} \cup \{\infty\} $ come:
- d(a,b) = 0 se a=b
- d(a,b) = infinito se a,b non sono definitivamente uguali
- d(a,b) = k se a,b sono definitivamente uguali e la k-esima cifra è la più lontanta in cui le sequenze discordano.

Si verifica facilmente che la distanza così definita è una metrica su A (a parte il fatto che c'è un infinito nel codominio, vabeh).

Ora, io credo che (e questo è un atto di fede, visto che non l'ho dimostrato, ma è più perchè non ho voglia che per altro) che una strategia dei nani che permette a loro di salvarsi è una funzione f da A in A tale che:
- $ \displaystyle d(a,f(a)) $ è finita
- $ \displaystyle d(f(a),f(b)) \le d(a,b) - 1 $ (supponendo a diverso da b)

Quindi d è una funzione che accorcia le distanze mandando ogni punto nelle vicinanze di se stesso.
Nella soluzione di 3C273, si sceglie un elemento per ogni classe di equivalenza (secondo la relazione d(a,b) è finita) e si manda tutti gli elementi di quella classe nell'elemento scelto. Così chiaramente la nostra funzione accorcia le distanze, però è necessario scegliere un elemento per classe.

Per dimostrare che è necessario l'assioma della scelta bisogna un po' vedere come funziona quell'accorciamento, e far vedere che anche se non sceglie qualche elemento almeno sceglie qualcosa... almeno questa è la strada che proverò.

Inviato: 29 ago 2007, 15:51
da 3C273
Ciao edriv!

Innanzitutto una curiosità: come funziona questa "famosa" notazione di Stoppa? 2={0,1}???

Il tuo modo di vedere il problema sembra molto interessante...
Ma quell'atto di fede mi costa moltissima fatica!
Voglio dire che probabilmente è vero che le strategie che permettono ai nani di salvarsi sono tutte e sole quelle che accorciano le distanze, ma a me non sembra ovvio! :?
Ci ho pensato e diciamo che non ho trovato controesempi :lol: ma questo non mi tranquillizza del tutto... forse tu ci hai pensato di più e riesci a convincermi che hai ragione anche senza una vera e propria dimostrazione?
Se invece dici che la dimostrazione non l'hai fatta ma sono solo conti o comunque cose macchinose, allora la dimostrazione non mi interessa e mi basta sapere che si può fare :D :D :D

A parte questo, se dovessi andare avanti per questa strada per dimostrare che una funzione di quel tipo sfrutta necessariamente una funzione di scelta, mi raccomando scrivi i tuoi ragionamenti perchè sono curiosa! Boh io non saprei da che parte cominciare, così a pelle mi sembra una strada complicata ma non voglio essere scettica a priori! Invece hai letto la dimostrazione di moebius del fatto che senza scelta non si può fare? Secondo me è molto bella, però sfrutta un risultato di cui non mi sono ancora chiarissime le ipotesi, ovvero che tutti i sottoinsiemi di R sono misurabili se tolgo la scelta...
(quello che non mi è ancora chiaro è in quale modello questa cosa vale, ovvero, mi è stato detto che in quello "normale" vale, ma cos'è esattamente il modello "normale"? a te la risposta moebius!)

Ciao ciao!

Inviato: 29 ago 2007, 16:19
da edriv
Per la notazione di Stoppa: il modo più comune (o meglio, l'unico di cui ho sentito) per definire i numeri naturali a partire dalla teoria degli insiemi è questo.
0 è l'insieme vuoto
1 è l'insieme che contiene 0
2 è l'insieme che contiene 0,1
3 è l'insieme che contiene 0,1,2
... ovvero, lo 0 è l'insieme vuoto, e si definisce $ ~ n+1 = n \cup \{n\} $.
Vedi l'assioma dell'infinito, che l'hanno inventato proprio per questo: http://it.wikipedia.org/wiki/Assioma_dell'infinito

Tornando al mio intervento... no, non credo che la dimostrazione sia contosa e macchinosa, ma quando scopri una cosa bella non cerchi di dimostrarla per paura che sia falsa :D Dunque proviamo:
Una sequenza infinita di nani coi cappelli bianchi e neri diventa un elemento di A.
Data una certa strategia dei nani, definiamo f(a) come la sequenza delle risposte dei nani se fossero messi in fila come a. Cioè, a è la sequenza vera, e f(a) è la sequenza "secondo i nani".

Prima la freccia più facile: se f è una strategia buona, allora f è un accorciamento.
- data una sequenza a, f(a) deve essere definitivamente uguale ad a, altrimenti infiniti nani morirebbero, quindi d(a,f(a)) è finita.
- se tutte le cifre di a,b sono uguali a partire dalla k-esima, allora il k-1-esimo nano, sia nella situazione a che nella b, vedrà la stessa cosa, quindi darà la stessa risposta. Lo stesso con i nani successivi. Quindi tutte le cifre di f(a),f(b) a partire dalla k-1-esima saranno uguali, e quindi $ ~ d(f(a),f(b)) \le d(a,b) - 1 $

Ora la freccia più difficile: se f è un accorciamento, allora esiste una strategia buona dei nani che funziona come f.
La strategia è questa: dico all'n-esimo nano che, se vede la stringa a, la sua risposta deve essere la n-1-esima cifra di f( 000...n zeri...00a ). Siccome se, al posto degli n zeri avessi messo qualsiasi altra n-stringa, la risposta sarebbe stata la stessa (usando appunto l'ipotesi che $ ~ d(f(a),f(b)) \le d(a,b) - 1 $), viene fuori che usando questa strategia, per ogni sequenza a la previsione che torna è proprio f(a).
Inoltre la strategia è buona proprio perchè d(a,f(a)) è finita e quindi muoiono sempre finiti nani.

Inviato: 29 ago 2007, 16:26
da 3C273
Ecco, stavo ripensando ai nanetti di Evariste che a differenza dei miei parlano uno dopo l'altro:
EvaristeG ha scritto:1) ci sono n nanetti in fila, il primo vede tutti, il secondo tutti meno il primo etc; hanno in testa cappelli colorati di bianco o di nero. Ognuno, in ordine, dice un colore. Se indovina il proprio cappello vive, sennò muore. Mostrare che si salvano tutti tranne al più uno.
2) stessa cosa ma con $ m $ colori.
3) stessa cosa ma con numerabili nani e 2 colori, solo che ne muoiono un numero finito
3bis) mostrare che ne può morire un numero qualunque purchè finito
4) estendere selvaggiamente, con cardinalità arbitrarie di nani e 2 (o un num finito di) colori
5) e con infiniti colori?
Allora, i punti (1) e (2) sono veramente famosi e credo che li conoscano tutti.


I punti (3) e (4) mi confondono, nel senso che:
a. se non uso la scelta non ci riesco;
b. se la uso riesco a farne sbagliare al massimo uno (il primo) sia se uso 2 colori sia (con una piccola accortezza) con un numero qualsiasi di colori finito, e con cardinalità qualsiasi dei nani (anche grazie alle chiacchierate con moebius!!!)... e quindi perchè chiedere che sbagli un numero finito se si può chiedere che ne sbagli 1? Anche per il punto (3bis), se riesco a farne sbagliare 1 solo chiaramente a tutti gli altri posso dire di fare giusto o sbagliato apposta a mio piacere, quindi non capisco il senso della domanda... (invece il (3bis) avrebbe senso se i nanetti parlassero tutti insieme)

...e quindi (assumendo che il problema non sia stupido) concludo che EvaristeG vuole una soluzione che NON faccia uso dell'assioma della scelta. Ma sono giorni che ci penso e non mi viene niente di niente... quindi invito tutti a pensare a salvare i nanetti di Evariste!


Per quanto riguarda il punto (5), esattamente come per il (3) e per il (4), sempre usando la scelta mi sembra (dovrei ripensarci) che anche questo si risolva con qualsiasi cardinalità di nani e qualsiasi cardinalità di colori (facendo sbagliare finiti nanetti se parlano tutti insieme e solo 1 se parlano uno per volta - anche se a pensarci bene far parlare più che numerabili nanetti uno per volta non ha senso, ma va be'...). Dovrei ripensarci un momento ma al momento non vedo controindicazioni...


Detto questo, come si aiutano i nanetti di Evariste senza scelta? Aiuto!!!!! :shock: :cry: :roll: :(

Inviato: 29 ago 2007, 16:41
da 3C273
edriv ha scritto:Ora la freccia più difficile: se f è un accorciamento, allora esiste una strategia buona dei nani che funziona come f.
La strategia è questa: dico all'n-esimo nano che, se vede la stringa a, la sua risposta deve essere la n-1-esima cifra di f( 000...n zeri...00a ). Siccome se, al posto degli n zeri avessi messo qualsiasi altra n-stringa, la risposta sarebbe stata la stessa (usando appunto l'ipotesi che $ ~ d(f(a),f(b)) \le d(a,b) - 1 $), viene fuori che usando questa strategia, per ogni sequenza a la previsione che torna è proprio f(a).
:oops: :oops: :oops:
...io sinceramente non ho capito bene... ci penso ancora un po', poi, se continuassi a non capire, prossimamente ti chiederò un chiarimento...
:oops: :oops: :oops:

Inviato: 29 ago 2007, 16:47
da edriv
Allora, prendiamo il nano n e una stringa a.
Consideriamo tutte le stringhe che cominciano con n cifre a caso, e poi continuano come se ci attaccassi a. La distanza tra due di queste stringhe è minore o uguale ad n. Quindi la distanza delle loro immagini secondo f è minore o uguale ad n-1. Quindi hanno tutte la n-1-esima cifra uguale. Chiamiamo x questa cifra. E allora dico al nano n: se vedi davanti a te una stringa uguale ad a, la tua risposta deve essere x!
Facendo questo per ogni nano, e per ogni stringa, ottengo una certa strategia per i nani. Per ogni stringa a, sia g(a) la stringa delle risposte che darebbero i nani se fossero disposti come a. Verificare che le funzioni f e g coincidono.

Inviato: 29 ago 2007, 17:43
da moebius
Ci devo pensare (infatti me lo stampo e me lo leggo con calma)... l'idea di una metrica sulle configurazioni mi piace molto... era una cosa di cui mi ero interessato per altre cose tempo fa e che, mio malgrado, non mi aveva portato dove volevo :(
Pero', indipendentemente, non mi e' chiaro come si possa estrapolare da cio' l'esistenza di una funzione di scelta (ossia costruire una funzione di scelta)...
Mi sembrano ancora problemi troppo lontani. Anche ammesso di poter identificare ogni famiglia non vuota di insiemi con le parti di un insiemone enorme tranne un tot di robe di cui non ci frega niente, ci son cose che non mi sono ancora molto chiare visto che f non estrae elementi :(
Print....

Inviato: 29 ago 2007, 17:54
da edriv
Ora vedi un po' come ne estrapolo una scelta :D
Sappiamo che $ ~ d(a,b) > d(f(a),f(b)) $ se a,b sono punti distinti nella stessa classe. (ovvero con distanza finita).
Prendiamo un qualsiasi elemento x. Allora:
$ ~ d(x,f(x)) > d(f(x),f(f(x))) > d(f(f(x)), f(f(f(x)))) > ... $ , assurdo, a meno che due coincidano da un certo punto in poi. Quindi, per un certo n, posto $ ~ f^n(x) = y $, y = f(y). Quindi, la f ha un punto fisso per ogni classe.

Supponiamo di avere due punti fissi distinti a,b nella stessa classe. Avremo che $ ~ d(f(a),f(b)) = d(a,b) < d(a,b) $, assurdo.
Quindi in ogni classe c'è un unico punto fisso, e questa è la nostra scelta :wink:

Inviato: 29 ago 2007, 17:56
da 3C273
edriv ha scritto:Quindi hanno tutte la n-1-esima cifra uguale.
Non vorrei dire un'altra scemata, ma volevi dire che hanno tutte l'n-esima cifra uguale?

Ora comunque mi sembra di aver capito, grazie! :) Però continuo a chiedermi da che parte si possa cominciare per legare questa (per altro molto interessante) descrizione di "strategia buona" alla necessità di assumere la scelta... sono un po' dubbiosa... mi sembra molto interessante di per sè, ma così a pelle poco utile per quanto riguarda il proposito di dimostrare la necesssità di assumere la scelta... :? ma ovviamente aspetto con ansia di leggere eventuali tue idee!!!

Per quanto riguarda quella che ormai abbiamo definito la "notazione di Stoppa" (che ne sarà lieto!), ora ho capito, e tra l'altro avevo pure già sentito la definizione di N secondo Zermelo Fraenkel... prima non ci avevo nemmeno pensato perchè (senti un po' l'idiozia!) siccome sono particolarmente scema mi sembrava che tu intendessi che 2={0,1} era una notazione abbreviata per... l'insieme delle funzioni da N={1,2,...} a {0,1}! Cosa che effettivamente non aveva molto senso!!! :oops: :lol:

Inviato: 29 ago 2007, 17:58
da moebius
come non detto... ho letto la versione corretta! :P