Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Da Aleph zero ad Aleph uno
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 01 Feb 2006 22:12    Oggetto: * QUIZ: Da Aleph zero ad Aleph uno Rispondi citando

Riprendo un quiz sull'infinito avviato nell'albergo celeste.
Premesso che:
  1. Il numero di elementi contenuti in un insieme si chiama cardinalità.
  2. Dato un insieme non vuoto è sempre possibile ottenere da esso dei sottoinsiemi ovvero degli insiemi più piccoli costituiti solo da una parte dell'insieme di partenza.
  3. L'insieme di tali sottoinsiemi si chiama insieme delle parti.
Quanti elementi ha l'insieme delle parti di un insieme finito con cardinalità pari a n?
E quanti elementi ha l'insieme delle parti di un insieme con cardinalità Aleph_0 (numerabile)?

Forse proprio Aleph_1 (infinità non numerabile)?

Forse potrebbe aiutare sapere che un insieme con cardinalità pari ad Aleph_1 si dice avere la potenza del continuo e che il classico esempio di insieme che gode della potenza del continuo è l'intervallo reale [0;1] (ovvero l'insieme dei numeri decimali compresi tra 0 e 1).


L'ultima modifica di ulisse il 25 Feb 2006 20:24, modificato 1 volta
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 01 Feb 2006 23:49    Oggetto: Rispondi citando

scopiazzo spudoratamente dall'atlante di matematica (edizione hoepli: è fantastico) o faccio finta di niente?
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 02 Feb 2006 16:01    Oggetto: Rispondi citando

madvero ha scritto:
scopiazzo spudoratamente dall'atlante di matematica (edizione hoepli: è fantastico) o faccio finta di niente?


Beh... io di solito "scopiazzo" superficialmente solo quando mi stufo di provarci da solo. La scopiazzata superficiale mi fornisce alcuni elementi utili a fare un passo avanti e da lì riprendo con le mie forze. Quando non ce la faccio proprio più allora leggo attentamente e poi, nota la soluzione, ci riprovo comunque da solo.

L'idea per impostare la soluzione di entrambi i quesiti è la seguente:

Chiamiamo A l'insieme a cardinalità numerabile, finita o infinita che sia, e P(A) l'insieme delle sue parti.
Ulisse, per fornire il primo suggerimento, ha scritto:
Poichè A ha cardinalità numerabile possiamo associare ad A una stringa binaria (ovvero una successione di 0 e 1) lunga tanto quanto la cardinalità di A ovvero lunga n se A contiene n elementi o di lunghezza infinita se A contiene infiniti elementi.
Potremo usare tale stringa per descrivere il contenuto dei sottoinsiemi di A.
Ad esempio ad A stesso verrà associata la stringa con tutti i bit a 1 mentre all'insieme vuoto verrà associata la stringa con tutti i bit a 0.
In generale, dati un sottoinsieme di A e la sua stringa corrispondente, lo stato del k-esimo bit mi dirà se il sottoinsieme in esame contiene (bit a 1) oppure non contiene (bit a 0) il k-esimo elemento di A.

Se siamo nel caso di numerabilità finita, manca un passaggio e poi, con un po' di calcolo combinatorio, abbiamo concluso.
Se siamo nel caso di numerabilità infinita serve ancora un ingegnoso stratagemma:
Ulisse, per fornire il secondo suggerimento, ha scritto:
Dobbiamo infatti notare che le successioni infinite di 0 e 1 possono essere viste come la parte decimale di un numero reale compreso tra 0 e 1 (espressa in numerazione binaria ma questo è di poco conto).
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 02 Feb 2006 16:37    Oggetto: Rispondi citando

infatti mi sembrava di ricordare qualcosa a proposito di p(a), e di card(a)... dovrei ripassare prima il calcolo combinatorio, ho delle gravi crepe in merito a permutazioni, combinazioni etc.
stavolta passo.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Jenga
Semidio
Semidio


Registrato: 26/04/05 14:20
Messaggi: 250
Residenza: Villa d'Ogna (BG)

MessaggioInviato: 02 Feb 2006 16:38    Oggetto: Rispondi citando

io non c'ho capito niente neanche leggendo i suggerimenti di Ulisse...
Top
Profilo Invia messaggio privato HomePage MSN
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 02 Feb 2006 16:48    Oggetto: Rispondi citando

io infatti proporrei di abbassare un po' il tiro: prima di passare ad algebra (quella con la a maiuscola) mi converrebbe ripassare almeno il programma di matematica del liceo...
stasera tiro fuori qualcosa che non ricordo bene di calcolo combinatorio (tipo la faccenda dei tre mobili con due cassetti ciascuno) e posto un quesito.
così, al posto di riguardare alcune cose che mi interessano, sfrutto le altrui spiegazioni e impiego metà del tempo !!!
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 02 Feb 2006 17:23    Oggetto: Rispondi citando

madvero ha scritto:
stasera tiro fuori qualcosa che non ricordo bene di calcolo combinatorio (tipo la faccenda dei tre mobili con due cassetti ciascuno) e posto un quesito.
così, al posto di riguardare alcune cose che mi interessano, sfrutto le altrui spiegazioni e impiego metà del tempo !!!


Già... e io impiego il doppio del mio per darti ripetizioni gratis! Evil or Very Mad
Wink

In merito a mobili e cassetti credo che la "faccenda" riguardi calcolo delle probabilità più che il calcolo combinatorio.
Cmq posta pure il quesito.
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 02 Feb 2006 17:38    Oggetto: Rispondi citando

Jenga ha scritto:
io non c'ho capito niente neanche leggendo i suggerimenti di Ulisse...

Quando le cose si fanno complicate di solito aiuta un esempio facile.
Proviamo con un insieme costituito da tre elementi:
A={a,b,c}

Citazione:
Elenchiamo i possibili sottoinsiemi e di fianco ad ognuno di essi riportiamo la stringa binaria che ne descrive il contenuto:
{} 000
{a} 100
{b} 010
{c} 001
{a,b} 110
{a,c} 101
{b,c} 011
{a,b,c} 111
Come vedi i possibili sottoinsiemi di un insieme che contiene n elementi sono tanti quante le possibili stringhe binarie di lunghezza n.
Sei in grado di scrivere la formula che conta le possibili stringhe binarie di lunghezza n?
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 02 Feb 2006 17:58    Oggetto: Rispondi citando

qualcosa fattoriale diviso boh.
fai un altro passettino indietro con qualche link utile ad un rapidissimo ripasso su permutazioni combinazioni e la terza che non ricordo più.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Jenga
Semidio
Semidio


Registrato: 26/04/05 14:20
Messaggi: 250
Residenza: Villa d'Ogna (BG)

MessaggioInviato: 03 Feb 2006 09:44    Oggetto: Rispondi citando

ulisse ha scritto:

Sei in grado di scrivere la formula che conta le possibili stringhe binarie di lunghezza n?


fin qui credo di si...
Citazione:
le stringhe di lunghezza n sono 2^n, contando sia la stringa vuota (tutti zeri) che quella di tutti 1
Top
Profilo Invia messaggio privato HomePage MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 03 Feb 2006 14:05    Oggetto: Rispondi citando

Esatto! Infatti hai risposto alla prima parte del quesito!
Ora sorgono le complicazioni perchè, per la seconda domanda, la risposta 2^infinito=infinito non specifica con che tipo di infinito abbiamo a che fare: numerabile o non numerabile?
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 03 Feb 2006 22:32    Oggetto: Rispondi citando

so mezza risposta:
Citazione:
gli infiniti si misurano in base alla cardinalità: se la cardinalità è uguale a quella dell'insieme N, sono infiniti numerabili, se è superiore non lo sono.
sono assolutamente sicura di aver dimenticato una parte importante e sebbene mi ricordi che la cardinalità di un insieme si indica con card(A), non mi ricordo esattamente il concetto di cardinalità !!!
senza ricordare il concetto, non sono in grado di calcolare la cardinalità di N, perciò non posso paragonarla alla cardinalità di altri insiemi.

forza uli, caccia il prossimo aiutino per riuscire a ricordare il concetto che mi manca e che ho spoilerato.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 04 Feb 2006 20:41    Oggetto: Rispondi citando

La cardinalità è una semplice definizione, per la precisione quella fornita in apertura del topic: la cardinalità di un insieme non è altro che il numero dei suoi elementi.
Ad esempio la cardinalità dell'insieme delle dita della mia mano destra è 5.
Genericamente potrei dire che è numerabile finita.
Numerabile perchè le dita possono essere contate, finita perchè se inizio a contarle, prima o poi finisco (a meno che non schiatti nel frattempo).

Mentre la cardinalità dell'insieme dei numeri naturali è ancora numerabile ma infinita. Posso contarli ma non potrò mai portare a compimento il conteggio.

Detto ciò ecco l'aiutino.

Citazione:
Osserva come abbiamo proceduto per contare i sottoinsiemi di A nel caso la cardinalità di A sia finita.
Abbiamo dovuto cercare un isomorfismo (sostanzialmente significa un'analogia anche se molto più rigorosa e forte) tra P(A) e le stringhe binarie di lunghezza n dopodichè abbiamo contato le seconde certi che, grazie all'isomorfismo, queste sono tante quanti i sottoinsiemi di A.
Ora però le cose si complicano. Infatti se A ha una infinità numerabile di elementi allora anche le stringhe binarie hanno lunghezza infinita e il calcolo 2^n ora diventa 2^infinito che non sappiamo "quantificare".
Occorre un altro isomorfismo!
Ovvero dobbiamo trovare un insieme che sappiamo quanti elementi contiene e che sia isomorfo all'insieme delle successioni (binarie) infinite.

Cosa ti fa ricordare una successione infinita di numeri preceduti da uno zero e una virgola ovvero una roba del tipo 0,010010111010110.... ?
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19480
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 06 Feb 2006 22:20    Oggetto: Rispondi citando

Think Think Think

...

passo !!!
Top
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 07 Feb 2006 12:57    Oggetto: Rispondi citando

Ecco gli ultimi passaggi della soluzione:
Citazione:
I numeri decimali, Mad!
Ovvero i numeri reali compresi tra 0 e 1 che noi, comunemente, chiamiamo numeri decimali perchè rappresentabili con "0," seguito da una successione infinita di cifre da 0 a 9.
I numeri razionali, quelli che hanno solo un numero finito di cifre dopo la virgola, possono comunque essere rappresentati da una successione infinita nella quale, da un certo posto in poi, ci sono solo degli 0.

Passando a notazione binaria non cambia nulla se non che le successioni saranno composte solo dalle due cifre 0 e 1.

E' possibile dimostrare che ogni numero decimale è rappresentabile come successione infinita di cifre dopo la virgola (sostanzialmente lo abbiamo appena fatto mettendo a posto anche i numeri razionali) e che ad ogni successione infinita di cifre corrisponde un numero decimale (è praticamente la definizione di numero decimale). Così facendo abbiamo dimostrato che le successioni infinite sono tante quanti i numeri reali dell'intervallo [0;1]. (In realtà manca ancora una quisquilia ma non voglio appesantire una spiegazione già pesante).
Quanti sono tali numeri? Dall'analisi sappiamo che ogni intervallo di R gode della potenza del continuo ovvero che contiene un'infinità non numerabile di elementi.
Quindi se A ha cardinalità infinita numerabile, P(A) ha cardinalità infinita non numerabile.
Top
Profilo Invia messaggio privato HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 09 Feb 2006 22:18    Oggetto: Rispondi citando

In analisi 2 ho preso un tiratissimo 22 millant'anni fa... Embarassed
Il ripassino è servito, ma...
ulisse ha scritto:
Detto ciò ecco l'aiutino.

Citazione:
Cosa ti fa ricordare una successione infinita di numeri preceduti da uno zero e una virgola ovvero una roba del tipo 0,010010111010110.... ?


Citazione:
Quindi, se non ho capito male, l'insieme delle stringhe binarie di lunghezza infinita altri non è che un sottoinsieme dell'insieme infinito non numerabile [0;1], mentre un qualsiasi sottoinsieme ha cardinalità < della cardinalità dell'insieme di partenza, ma scrivere x<infinito non ha molto senso, inquanto x appartiene comunque all'insieme [0;infinito)
Dopo il riassunto, mi verrebbe da dire che la cardinalità di un insieme infinito numerabile è proprio un infinito non numerabile.


Qualcuno mi spiega che cosa ho appena detto? Hypno
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 19 Feb 2006 16:56    Oggetto: Rispondi

[quote="Benny"]
Citazione:
Quindi, se non ho capito male, l'insieme delle stringhe binarie di lunghezza infinita altri non è che un sottoinsieme dell'insieme infinito non numerabile [0;1]

No, non è un sottoinsieme di [0,1] ma è proprio [0,1].
Infatti ogni numero di [0,1] può essere espresso in forma decimale ovvero come successione infinita di cifre dopo la virgola.
E viceversa ogni successione etc etc è un ben preciso numero decimale.

Citazione:
un qualsiasi sottoinsieme ha cardinalità < della cardinalità dell'insieme di partenza

Anche questo non è corretto. Riguardando il quiz dell'albergo celeste ne hai subito un esempio: i numeri interi sono tanti quanti il suo sottinsieme dei numeri pari.

L'avere almeno un sottoinsieme che ha la stessa cardinalità dell'insieme di partenza è una caratteristica propria degli insiemi infiniti (numerabili o meno che sia).
Tanto che un modo per definire gli insiemi a cardinalità infinita è proprio questo: un insieme ha cardinalità infinita se può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio.
Citazione:
Dopo il riassunto, mi verrebbe da dire che la cardinalità di un insieme infinito numerabile è proprio un infinito non numerabile.


Questo, invece è corretto.
Top
Profilo Invia messaggio privato HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Pagina 1 di 1

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi