Infiniti nanetti

[3C273]

@EvaristeG:
senza dubbio il problema non vieta ai nanetti di "numerarsi" prima che i cappelli vengano attribuiti perchè questo fa parte della strategia scelta a priori, però (come dice MateCa) la disposizione è una forma di comunicazione in tutto e per tutto, e questo è vietato dal testo:

non possono comunicare in nessun modo.

In ogni caso se permettessimo ai nani di comunicare disponendosi in un certo modo direi che la soluzione più semplice è quella di MateCa! Però vorrei capire una cosa della soluzione di Evariste: la sol l'ho capita, tutto a posto, ma alla fine scrivi che:

L'unico che può morire in questo modo è l'eventuale massimo del buon ordinamento scelto dai nani, che però possono evitare anche questa perdita, scegliendo il primo ordinale che abbia la loro cardinalità.

EDIT: no niente tutto a posto, avevo fatto una domanda a questo proposito ma ora mi sono risposta da sola

Per curiosità: mi sono stupita anche leggendo che

nel problema classico i nani sono in fila e parlano uno per volta

quale sarebbe il problema "classico"? chiede la stessa cosa? Infatti mi stupisce che i nani possano parlare uno per volta, visto che c'è soluzione anche nel caso molto più restrittivo in cui parlano tutti insieme... per quanto riguarda mettersi in fila, invece, insisto che secondo me l'atto di "ordinarsi" fa parte integrante della scelta della strategia, e che quindi non è necessario specificarlo nel testo...

Detto ciò... un po' mi spiace che il problema sia finito in MNE, perchè la soluzione può essere esposta in maniera semplicissima ed è a tutti gli effetti comprensibile a tutti... però, leggendo i post che sono stati scritti (soprattutto l'ultimo di Stoppa 2006 ) mi rendo conto che il posto migliore è MNE!
E... a proposito appunto di quel post...

@Stoppa2006:
ho un paio di osservazioni sulla tua soluzione: innanzitutto, mi sembra che tu abbia affrontato il problema nel caso in cui ogni nano veda solo i suoi successori, e NON i precedenti (altrimenti sarebbe incerto tra $ 2 $ possibilità e non $ 2^n $). Questo però mi sa che l'hai inventato perchè non è richiesto dal testo! In ogni caso, visto che la soluzione c'è comunque, mettiamoci nella situazione che proponi tu, quindi ogni nano vede solo i suoi successori nell'ordinamento di $ \omega $.

Premesso che ho fatto fatica a leggere il tuo messaggio perchè non me ne intendo di queste cose, mi spieghi il passaggio in cui dici che poichè la successione delle "f" è decrescente allora è definitivamente costante? Perchè magari è una scemata, ma non l'ho capito...
EDIT: era davvero una scemata, adesso ho capito! bastava pensarci un attimo!

Poi chiedo un altro chiarimento, credo che sia ovvio, ma giusto per intenderci...: quando dici che due nani rispondono la stessa cosa NON intendi che rispondono entrambi bianco o entrambi nero giusto? Intendi che rispondono il colore che ciascuno di loro avrebbe in testa seguendo la STESSA configurazione di cappelli congetturata, giusto? credo che sia ovvio, ma sai, meglio chiedere conferma così ci capiamo!

Comunque la tua soluzione mi SEMBRA giusta, ma non me ne intendo abbastanza da capirlo con certezza... diciamo che la mia soluzione credo che sia concettualmente simile, ma è messa giù in maniera molte più semplice!

Un'ultima osservazione: è vero (almeno credo) che, come dici tu, il problema senza zorn non si può fare. Ma è anche vero, come ho già scritto, che ragionando in termini di assioma della scelta invece che di lemma di zorn (anche se poi sono equivalenti) la soluzione ha un aspetto molto più semplice e accessibile a tutti... nel senso che semmai (in generale) le difficoltà stanno nel fare le cose senza l'assioma della scelta, ma utilizzarlo senza porsi troppe domande viene (fin troppo) naturale. Quindi inviterei tutti a ragionare in maniera più semplice... anche se, ripeto, la soluzione di Stoppa2006 sembrerebbe corretta... Poi comunque scriverò anche la mia soluzione! D'altra parte, quando salterà fuori una soluzione semplice, allora sì che vorrò ri-complicare le cose e farvi un po' di domande a proposito dell'assioma della scelta!

Una domandona la anticipo, ma premetto che ne so poco di queste cose e quindi faccio la domanda proprio perchè non so la risposta: abbiamo scritto tutti che questo problema senza zorn non si può risolvere. Se è vero, dimostrarlo... altrimenti risolverlo senza...

[EvaristeG]

Innanzitutto, la mia, più che una soluzione, era una presa in giro ... secondariamente, quella di MateCa è la mia, solo che io ci ho ricamato un po' mettendo i nanetti in tante file, contro il muro etc etc, ma è equivalente: tutto si riduce nel guardare il successore.
Poi, un warning: utilizzare assiomi e teoremi senza porsi troppe domande è fisica, non matematica , quindi attenzione a farlo con cose come l'assioma di scelta.

Infine, la versione classica è questa, in più varianti:
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?

Poi, possiamo usare infiniti nani, ma supporre che ci sia la nebbia con visibilità (misurata in nani ) finita e continuare su questo genere...

[3C273]

Poi, un warning: utilizzare assiomi e teoremi senza porsi troppe domande è fisica, non matematica , quindi attenzione a farlo con cose come l'assioma di scelta.

E io infatti sono fisica... non so se lo sapevi, ma comunque hai colpito in pieno! però sinceramente non penso di meritarmi la frecciatina, perchè ce l'ho per "vizio" di controllare tutto (e in particolare ultimamente mi sono proprio fissata con l'assioma della scelta), e infatti ho pure scritto (testuali parole) che utilizzare l'assioma della scelta senza porsi troppe domande viene fin troppo naturale!!! Però hai perfettamente ragione, usare teoremi e assiomi senza conoscerli a fondo è pericoloso, e a questo proposito infatti attendo con ansia che salti fuori una soluzione semplice a questo problema perchè poi ho un sacco di domande da fare! ...detto questo però vorrei lanciare una mini-frecciatina anch'io: sbaglio oppure ci sono diversi teoremi che si studiano in analisi I o II la cui dimostrazione "classica" si basa sull'implicita assunzione dell'assioma della scelta?
(adesso non saprei dire quale, ma mi sembra ce ne siano, poi magari sbaglio) E quindi anche i matematici spesso usano la scelta con un po' troppa naturalezza! Comunque, scherzi a parte, hai ragione Evariste... io ho scritto quello che ho scritto solo per invitare la gente a scrivere una soluzione al problema dei nanetti che fosse facilmente comprensibile anche a chi non ha mai sentito parlare di $ \aleph_0, \,\omega $, buon ordinamento, lemma di Zorn... tutto qui Così dopo facciamo partire una bella discussione sull'assioma della scelta da cui spero di imparare un po' di cose!

Ancora una cosa, ma non ti arrabbiare : l'avevo capito che la tua sol è la stessa di quella di MateCa, ma perchè complicare le cose quando sono semplici? Complicare le cose semplici è fisica, non matematica!

Per il resto... ecco perchè non ci intendevamo sul "problema originale": perchè per me quello dei nanetti in fila (in numero finito) con addosso cappelli di 2 o più colori che parlano uno alla volta è proprio un problema completamente diverso! Sia per la soluzione (che non c'entra niente) sia per il fatto che lì, appunto, si possono e si devono sfruttare le informazioni che danno i nani precedenti quando parlano! Invece il problema 3, il 3bis e il 4 si risolvono tutti in un colpo solo direi... ed è il problema che ho postato io tranne che per il fatto che non c'è bisogno di farli parlare uno alla volta (ci tengo a scriverlo perchè a me a prima vista proprio questo sembrava talmente assurdo... era proprio la cosa che rendeva il problema bellissimo perchè mi sembrava assolutamente impossibile!)
Che dire del problema 5... fenomenale... credo che tu l'abbia sparato lì a caso ma voglio pensarci!!! E penserò anche a come utilizzare la "nebbia" per formulare un nuovo problema!!!
Ciao!

[3C273]

EDIT: ops, non so cos'ho combinato... volevo aggiungere un pezzo al messaggio precedente, ed è finita che l'ho postato due volte... comunque adesso ho modificato il precedente e questo l'ho tolto... scusate! ciao!

[EvaristeG]

In realtà 3, 3bis, 4 si risolvono, nel caso in cui i nani parlino uno per volta, in un modo abbastanza diverso, potendo sfruttare l'informazione. Il problema è come "passare" l'informazione.

A margine e off topic, l'unico teorema di analisi I in cui si usa la scelta è questo:
una funzione surgettiva ha un'inversa destra, almeno per quel che ne so.
Per analisi II, beh, dipende cosa c'è, secondo te, in analisi II, ad esempio se ci includi teoremi sugli spazi di Banach&co, può essere, ma se parliamo di eq diff e calcolo in n dimensioni reali, non credo... cmq non è questo il topic per parlarne.

Sempre più a margine, la mia non era una complicazione, ma un modo per rendere la soluzione un po' più romanzata...

E quasi fuor dal foglio, non credo che il non nominare esplicitamente lemma di zorn, ordinali e cardinali semplifichi di molto la soluzione, semplicemente nasconde sotto il tappeto la parte difficile...

[SkZ]

[ ...detto questo però vorrei lanciare una mini-frecciatina anch'io: sbaglio oppure ci sono diversi teoremi che si studiano in analisi I o II la cui dimostrazione "classica" si basa sull'implicita assunzione dell'assioma della scelta?
(adesso non saprei dire quale, ma mi sembra ce ne siano, poi magari sbaglio) E quindi anche i matematici spesso usano la scelta con un po' troppa naturalezza!

Se ben ricordo, l'Assioma della Scelta e' tra i piu' controversi assiomi della Matematica. Mi pare che qualche matematico si opponga anche al suo status e uso.
Diciamo che e' roba da Matematici e e' bene usarlo se sai quello che fai.

[3C273]

Grazie per i commenti sull'utilizzo della scelta in Analisi I e II... comunque hai ragione, è davvero OT... (la mia comunque era solo una battuta, come del resto quella sulle complicazioni - quando ho detto che sono cose da fisici - tanto più che 1. io sono fisica; 2. adoro romanzare i problemi, anche quelli più rigorosi!)

A proposito dei problemi 3, 3bis e 4 vorrei pensarci un attimo... la mia soluzione se non sbaglio dovrebbe sistemarli tutti insieme ma prima di esprimermi vorrei rifletterci su un po'... e poi vorrei pensare a quale può essere la sol che hai in mente tu in cui ci si passa l'informazione...

Invece per quanto riguarda la tua ultima affermazione ti chiederei davvero di aspettare di leggere la soluzione che ho in mente io... (sì, così poi magari mi dici che è sbagliata!!!) perchè ci terrei davvero a riparlarne! Non voglio dire che non si usi l'assioma della scelta nè voglio nasconderlo... dico solo che vorrei ri-chiedere dopo il tuo parere! Perchè se i nanetti sono numerabili a me sembra davvero semplice! Ma non voglio insistere, ne parliamo dopo ok? Anche perchè ho un sacco di domande a cui mi piacerebbe trovare delle risposte

Ciao e grazie!

[3C273]

Se ben ricordo, l'Assioma della Scelta e' tra i piu' controversi assiomi della Matematica. Mi pare che qualche matematico si opponga anche al suo status e uso.
Diciamo che e' roba da Matematici e e' bene usarlo se sai quello che fai.

Senza dubbio! E poi non solo "qualche matematico si oppone": per quello che mi ricordo, una volta fissati gli assiomi di Zermelo-Frenkel (come si scrive?) esistono proprio due teorie degli insiemi distinte, una con la scelta e una con la sua negazione.
Però ragazzi, vorrei chiarire una cosa: giuro che io non volevo mettermi a discutere su una cosa che so di non sapere! Ho solo posto un problema che mi sembrava carino, la cui soluzione sembrerebbe (usiamo il condizionale che è meglio, se no poi mi bastonate!!! ) far uso dell'assioma della scelta. Ma siccome il problema secondo me è molto bello, volevo solo una soluzione per i poveri nanetti! Se poi ne avrete voglia, si potrà discutere questa soluzione in altri termini, ma di certo io non mi metterò a discutere... però farò un sacco di domande !
Buona serata!

[Stoppa2006]

@3C273 Io intendevo che il nano n-esimo è incerto tra 2^n sequenze possibili tra quelle dell'insieme A, e sceglie la minima.

Quando i nani dicono la stessa cosa intendo la stessa sequenza e non certo lo stesso colore.

Il fatto che la "f" decrescendte implica definitivamente costante è una proprietà che caratterizza i buoni ordini, nel senso che un 'insieme totalmente ordinato è un buon ordine se e solo se ogni successione decrescente è definitivamente costante (però per dimostrare un verso serve l'assioma di scelta...).

La situazione che ogni nano vede solo i suoi successori, l'ho scelta perchè era comoda per la soluzione, comunque se un nano vede tutti vede anche i suoi successori, quindi al massimo avendo più informazioni si salveranno più nani.

[Stoppa2006]

Faccio qualche considerazione sui problemi di EvarseG:

Il problema 3 e 3 bis si risolvono come ho risolto quello di 3C273. La generalizzazione del 4 a un'infinità qualunque di nani si fa allo stesso modo purchè si beneordinino prima di entrare, e per la generalizzazione a un numero arbitrario di cappelli basta considerare la rappresentazione dei reali in base m (numero dei cappelli).
Per il caso con infiniti cappelli non sono sicuro che questo tipo di considerazioni funzioni, anche se penso che basti bene-ordinare i cappelli.

[EvaristeG]

In realtà 3, 3bis, 4 si risolvono, nel caso in cui i nani parlino uno per volta, in un modo abbastanza diverso, potendo sfruttare l'informazione. Il problema è come "passare" l'informazione.

[Stoppa2006]

Non capisco come mai la non vada bene come dico io? Anche in quel modo muoiono al più un numero finito di nani, pur non parlando uno alla volta.

[EvaristeG]

Oh santi numeri ... nessuno ha detto che non va bene, semplicemente nella versione ordinata c'è un modo totalmente diverso di risolvere il problema, che è una diretta generalizzazione della soluzione al punto 1).

[moebius]

Che bello... almeno vedo che non e' piaciuto solo a me e a 3C273!!! (ed alla simpatica "tizia" canadese che me lo ha proposto e che ho rincorso per le scale mentre le gridavo "Axiom of choice!!!!")
By the way...
Da vero matematico sfigato oggi ho quasi saltato il pranzo per comprare dei libri scontati... fa nulla... quindi ho pensato di passare a scrivere due righe.
Per ora dico solamente a tutti gli interessati, ma mi riservo di essere piu' preciso in seguito (magari domani) che "partendo" dall'assioma della scelta e non dal lemma di Zorn (tanto sono equivalenti, ma tanto gia' lo sapevate vero? ) esiste una dimostrazione molto piu' intuitiva che secondo me potrebbe passare a cuor leggero per olimica... ok, magari chiudendo un occhio o due...
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), credo di avere una dimostrazione del fatto che l'assioma della scelta (e quindi sue equivalenze) sono necessarie a salvare i nanetti...
Dotto rules!

Ah si... voglio salvare anche i nanetti di EvaristeG e invito anche voi a farlo

[pic88]

Allora.. Premesso che io ho risolto il problema 2 così:

- Esiste la strategia per 2 nani, ed è "il primo dice il colore del secondo";

- Se esiste per n nani, allora per n+1 si usa la strategia degli n, solo che il primo "corregge" il colore che deve dire "aggiungendovi" il colore dell'ultimo, che tutti fino all'n-esimo nano conoscono (i colori sono numeri di $ {\mathbb{Z}_m} $ e l'addizione è da farsi in quell'insieme), di modo che i primi n indovinano poiché esiste la strategia per n; l'ultimo, riconosciuta la strategia e dunque il colore che avrebbe dovuto dire il primo in assenza di lui, risale al proprio colore.

Ora, come si fa con infiniti nani?

intuitivamente, il problema assomiglia a quello dell'albero con infiniti nodi (le sequenze per cui esiste una strategia) di cui ognuno ha un numero finito di figli (sequenze con un elemento in più) e dunque esiste un ramo infinito. Ma non sono sicuro che sia equivalente al problema esposto, per cui attendo altre idee.