Non so bene dove mettere questo messaggio, visto che ci sono alcuni thread in cui Mind ha sollevato la questione. Inoltre, non è proprio quel che si può dire un argomento di matematica elementare, quindi lo piazzo qua e spero che qualcuno di quelli interessati all'argomento lo legga.
<B>Definizioni preliminari</B>
Siano $ \mathcal{A}\ ,\ \mathcal{B} $ insiemi.
Chiamiamo funzione da $ \mathcal{A}\textrm{ in }\mathcal{B} $ un sottoinsieme $ \mathcal{F}\subseteq \mathcal{A}\times\mathcal{B} $ t.c. se $ (a,b) \textrm{ e } (a,b') \in \mathcal{F} $ allora $ b=b' $ (a discrezione si può aggiungere che $ \forall\ a \in\mathcal{A}\ \exists\ b\in\mathcal{B} \textrm{ t.c. } (a,b)\in\mathcal{F} $ ma non addentriamoci nei particolari). Diremo allora che $ \mathcal{F}:\mathcal{A}\to\mathcal{B}\textrm{ e }(a,b)\in\mathcal{F}\Leftrightarrow b=\mathcal{F}(a) $
Chiamiamo operazione su $ \mathcal{A} $ un'applicazione $ \circledast : \mathcal{A}\times\mathcal{A}\to\mathcal{A} $ e indichiamo come $ a\circledast b $ l'immagine della coppia (a,b) tramite essa.
<B>Il succo della questione</B>
Sia $ \mathcal{A} $ un insieme e siano $ \left(\mathcal{F}_i\right)_{i \in \mathcal{I}} $ una famiglia di funzioni di $ \mathcal{A} $ in sè parametrizzata in un certo insieme $ \mathcal{I} $ e $ \left(\circledast_j\right)_{j\in\mathcal{J}} $ una famiglia di operazioni su $ \mathcal{A} $ parametrizzata su un certo insieme $ \mathcal{J} $.
Sia inoltre $ \mathcal{X}=(x_k)_{k\in\mathbb{N}} $ uno spazio di variabili.
Allora si può dare la definizione (induttiva) di formula chiusa sull'insieme $ \mathcal{A} $ dotato delle operazioni $ \left(\circledast_j\right)_{j\in\mathcal{J}} $ rispetto alle funzioni $ \left(\mathcal{F}_i\right)_{i \in \mathcal{I}} $ come segue:
1) $ \forall\ a\in\mathcal{A} $, $ (a) $ è una formula chiusa; $ \forall\ x\in\mathcal{X} $, $ (x) $ è una formula chiusa;
2) se $ \alpha,\ \beta $ sono formule chiuse, anche $ (\alpha\circledast_j\beta) $ lo è $ \forall\ j\in\mathcal{J} $
3) se $ \alpha $ è una formula chiusa, anche $ \left(\mathcal{F}_i(\alpha)\right) $ lo è $ \forall\ i\in\mathcal{I} $
4) niente altro è una formula chiusa.
Penso che questa sia una definizione sufficientemente rigorosa di formula chiusa da soddisfare anche Mind. Ovviamente, caveat lector, in quanto l'ho partorita sul momento, dopo (in senso non temporalmente sequenziale) qualche chiacchierata con alcuni amici sull'argomento.
In tal modo, prima di parlare di formula chiusa, si dovrebbe specificare una terna insieme-operazioni-funzioni.
Ovviamente si può rimaner d'accordo che, qualora sia ovvio che l'insieme di cui si parla può essere dotato di una certa struttura algebrica (che è quella solita ed usuale) e non si specifica nessuna funzione su di esso, si intenda la terna insieme-sue proprie operazioni algebriche-nulla.
Ad esempio, se si parla di $ \mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C} $, si intenderanno come operazioni le quattro operazioni di campo (nei limiti della loro validità), eventualmente aggiungendo le esponenziazioni dove possibile. Certo, se ad esempio si vuole intendere che $ n! $ è una formula chiusa, bisogna dirlo...
Bene, io ho dato del mio. Chi è d'accordo? Chi propone definizioni alternative?
Mind, saresti soddisfatto di una simile trattazione?
EDIT : mancavano le variabili.
"...in formula chiusa..."
"...in formula chiusa..."
Ultima modifica di EvaristeG il 10 mar 2005, 17:53, modificato 1 volta in totale.
Beh, nell'insieme delle funzioni ci metteri di default tutte quelle funzioni che hanno un nome e un cognome (log, exp, sqrt, sin, cos, come minimo...).
Sei sicuro che così non riesci a generare le sommatorie? (che è la cosa su cui siamo probabilmenti tutti d'accordo nel dire che NON è in forma chiusa)
Sei sicuro che così non riesci a generare le sommatorie? (che è la cosa su cui siamo probabilmenti tutti d'accordo nel dire che NON è in forma chiusa)
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
MindFlyer
Re: "...in formula chiusa..."
Assolutamente no. Comunque apprezzo lo sforzo (quantunque, se proprio volessimo formalizzarci, non dovremmo certo dare definizioni in questo modo, o i logici potrebbero offendersi!).EvaristeG ha scritto:Penso che questa sia una definizione sufficientemente rigorosa di formula chiusa da soddisfare anche Mind.
Mind, saresti soddisfatto di una simile trattazione?
Vedi, il fatto è che mi era chiaro fin dall'inizio che l'insieme delle formule chiuse dovesse essere chiuso per composizione, comprendere le funzioni costanti, etc etc. La cosa che mi mancava, e su cui tace anche la tua "definizione", era proprio quel benedetto insieme di funzioni e operazioni di base, da comporre per ottenere tutte le altre! Allora, vogliamo metterci i logaritmi? Le funzioni trigonometriche? I fattoriali? Boh? E' soltanto questa la questione su cui mi intestardisco ogni volta che vedo un problema la cui domanda è "Quanti sono... ?", oppure "Esprimere in forma chiusa... ".
Come dice Marco, per ogni problema andrebbe chiaramente specificato questo insieme di funzioni, o altrimenti la richiesta sarebbe insensata!
Formula chiusa
Concordo con la necessita' di definire cosa sia esattamente una "formula chiusa". E penso che una definizione di tipo ricorsivo sia la piu' appropriata.
Sarebbe da deinifre le operazioni unarie e le operazioni binarie consentite. Inoltre la generazione dovrebbe essere di tipo finitario (onde evitare il problema delle sommatorie infinite...).
Forse si potrebbe provare con la seguenta definizione:
Consideriamo la struttura degli ineri positivi $ n\in\mathbb{N} $.
Siano:
$ \{\alpha_i\}_{i\in I} $ operatori unari (con identita');
$ \{\beta_j\}_{j\in J} $ gli operatori binari (con identita');
definiti su tale struttura.
Sia $ \mathcal{FC} $ l'insieme delle formule chiuse, allora:
$ {} \\ \epsilon\in\mathcal{FC} \\ n\in\mathbb{N}\Rightarrow n\in\mathcal{FC} \\ \Phi\in\mathcal{FC}\Rightarrow\alpha_i(\Phi)\in\mathcal{FC} \\ \Phi,\Psi\in\mathcal{FC}\Rightarrow\beta_j(\Phi,\Psi)\in\mathcal{FC} \\ $
generando in modo finitario.
Un $ \Phi\in\mathcal{FC} $ avra' $ \textrm{Dom}(\Phi)\subset\mathbb{N}^k, \textrm{Im}(\Phi)\subset\mathbb{N} $. Diremo che una $ \phi:A\subset\mathbb{N}^k\longrightarrow\mathbb{N} $ e' riducibile in forma chiusa se esiste, una $ \Phi\in\mathcal{FC} $ con lo stesso dominio e tale che per ogni N in A si ha $ \Phi(N)=\phi(N) $.
E' solo una bozza di idea, ma penso che su questa strada possa andare...
Sarebbe da deinifre le operazioni unarie e le operazioni binarie consentite. Inoltre la generazione dovrebbe essere di tipo finitario (onde evitare il problema delle sommatorie infinite...).
Forse si potrebbe provare con la seguenta definizione:
Consideriamo la struttura degli ineri positivi $ n\in\mathbb{N} $.
Siano:
$ \{\alpha_i\}_{i\in I} $ operatori unari (con identita');
$ \{\beta_j\}_{j\in J} $ gli operatori binari (con identita');
definiti su tale struttura.
Sia $ \mathcal{FC} $ l'insieme delle formule chiuse, allora:
$ {} \\ \epsilon\in\mathcal{FC} \\ n\in\mathbb{N}\Rightarrow n\in\mathcal{FC} \\ \Phi\in\mathcal{FC}\Rightarrow\alpha_i(\Phi)\in\mathcal{FC} \\ \Phi,\Psi\in\mathcal{FC}\Rightarrow\beta_j(\Phi,\Psi)\in\mathcal{FC} \\ $
generando in modo finitario.
Un $ \Phi\in\mathcal{FC} $ avra' $ \textrm{Dom}(\Phi)\subset\mathbb{N}^k, \textrm{Im}(\Phi)\subset\mathbb{N} $. Diremo che una $ \phi:A\subset\mathbb{N}^k\longrightarrow\mathbb{N} $ e' riducibile in forma chiusa se esiste, una $ \Phi\in\mathcal{FC} $ con lo stesso dominio e tale che per ogni N in A si ha $ \Phi(N)=\phi(N) $.
E' solo una bozza di idea, ma penso che su questa strada possa andare...
Ah, Mind, leggi i post degli altri prima di criticare, su...
Tu dici :
somma, differenza, prodotto, divisione, esponenziazione
come operazioni e di
funzioni trigonometriche, esponenziale, inverse delle funzioni trigonometriche, logaritmo, radice n-esima
come funzioni.
Ho già detto che aggeggi un po' più controversi come i fattoriali dovrebbero essere specificati dal propositore del problema, o quanto meno gli altri dovrebbero chiedere (con educazione, non con toni di inutile polemica) se i fattoriali siano utilizzabili.
Detto questo, tutti abbiamo l'idea intuitiva di cosa vuol dire "in formula chiusa" (se ne sei sprovvisto, io ne ho due e te ne cedo volentieri una) e non mi sembra il caso di rompere tanto l'anima su simili questioni.
Inoltre, ho controllato. La definizione che ho proposto io si ritrova in alcuni libri e quindi mi sembra di poter dire che quanto meno non è parto malato della mia sola immaginazione.
Del resto, non è molto utilizzabile per dimostrare che qualcosa non è scrivibile in formula chiusa (precisati i precisanda) in quanto diventerebbe assai complicato.
Però, la definizione proposta mi sembra un criterio abbastanza chiaro per decidere se una certa espressione è una formula chiusa o meno.
Quindi smettila di rompere, Mind!
Tu dici :
Ma io avevo scritto:La cosa che mi mancava, e su cui tace anche la tua "definizione", era proprio quel benedetto insieme di funzioni e operazioni di base, da comporre per ottenere tutte le altre! Allora, vogliamo metterci i logaritmi? Le funzioni trigonometriche? I fattoriali? Boh? E' soltanto questa la questione su cui mi intestardisco ogni volta che vedo un problema la cui domanda è "Quanti sono... ?", oppure "Esprimere in forma chiusa... ".
Ovviamente bisogna specificare, ma cmq è abbastanza ovvio che su N si parli di :In tal modo, prima di parlare di formula chiusa, si dovrebbe specificare una terna insieme-operazioni-funzioni.
Ovviamente si può rimaner d'accordo che, qualora sia ovvio che l'insieme di cui si parla può essere dotato di una certa struttura algebrica (che è quella solita ed usuale) e non si specifica nessuna funzione su di esso, si intenda la terna insieme-sue proprie operazioni algebriche-nulla.
Ad esempio, se si parla di N,Z,Q,R,C, si intenderanno come operazioni le quattro operazioni di campo (nei limiti della loro validità), eventualmente aggiungendo le esponenziazioni dove possibile. Certo, se ad esempio si vuole intendere che è una formula chiusa, bisogna dirlo...
somma, differenza, prodotto, divisione, esponenziazione
come operazioni e di
funzioni trigonometriche, esponenziale, inverse delle funzioni trigonometriche, logaritmo, radice n-esima
come funzioni.
Ho già detto che aggeggi un po' più controversi come i fattoriali dovrebbero essere specificati dal propositore del problema, o quanto meno gli altri dovrebbero chiedere (con educazione, non con toni di inutile polemica) se i fattoriali siano utilizzabili.
Detto questo, tutti abbiamo l'idea intuitiva di cosa vuol dire "in formula chiusa" (se ne sei sprovvisto, io ne ho due e te ne cedo volentieri una) e non mi sembra il caso di rompere tanto l'anima su simili questioni.
Inoltre, ho controllato. La definizione che ho proposto io si ritrova in alcuni libri e quindi mi sembra di poter dire che quanto meno non è parto malato della mia sola immaginazione.
Del resto, non è molto utilizzabile per dimostrare che qualcosa non è scrivibile in formula chiusa (precisati i precisanda) in quanto diventerebbe assai complicato.
Però, la definizione proposta mi sembra un criterio abbastanza chiaro per decidere se una certa espressione è una formula chiusa o meno.
Quindi smettila di rompere, Mind!
-
MindFlyer
Secondo me nella tua definizione, EvaristeG, non determini quando una funzione arbitraria possa essere esprimibile in forma chiusa; mentre aggiungendo la condizione sul dominio non importa come sia espressa la formula (una formula chiusa può avere più espressioni...), basta che dominio ed immagine degli elementi siano uguali, prendi ad esempio:
$ \phi(n)=1+2+....+n $
questa, secondo la tua definizione non e' formalmente una formula chiusa, mentre aggiungendo la condizione sul dominio abbiamo che la funzione
$ \Phi(n)=\frac{n(n+1)}{2} $
e' l'associata in $ \mathcal{FC} $ della $ \phi $.
$ \phi(n)=1+2+....+n $
questa, secondo la tua definizione non e' formalmente una formula chiusa, mentre aggiungendo la condizione sul dominio abbiamo che la funzione
$ \Phi(n)=\frac{n(n+1)}{2} $
e' l'associata in $ \mathcal{FC} $ della $ \phi $.
La mia intenzione era solo di specificare che cosa la dicitura "formula chiusa" volesse significare.
Se un problema chiede di "trovare una formula chiusa per", verificare che l'espressione fornita da un solutore è una formula chiusa equivale solo a controllare che sia ottenibile da termini e variabili nella maniera che io ho indicato.
Poi, dire cosa significa che una funzione è esprimibile tramite formula chiusa è quello che hai aggiunto tu.
Btw : nessuno può considerare l'espressione
$ \sum_{i=0}^n i $
come una formula chiusa rispetto all'insieme dei naturali con le usuali operazioni e funzioni.
Invece
$ n(n+1)/2 $
vi rientra a pieno titolo. Se apri un testo di logica troverai che le definizioni riguardanti le "formule" sono sempre date (quando si può) a prescindere dal modello interpretativo usuale delle stesse (e quindi dalla semantica); per questo ho parlato di insiemi operazioni e funzioni generiche, invece che di N, +,-,x,/ e delle funzioni "con nome e cognome".
La tua definizione pretende anche di dire che a noi non interessa la scrittura della formula, ma solo il sottoinsieme del prodotto $ \mathcal{A}^k\times\mathcal{A} $ che le è associato in quanto funzione di k variabili a valori in $ \mathcal{A} $. Questo non è sbagliato (infatti è proprio quello che ci interessa), ma visto che la definizione di "formula chiusa" riguarda solo successioni finite di simboli e non funzioni, mi sembra più corretto darla in tutta generalità, lasciando poi per sottointeso che una funzione esprimibile in formula chiusa sia quello che dici tu.
@Mind : ripeto, l'ironia non è sempre la miglior risposta
Se un problema chiede di "trovare una formula chiusa per", verificare che l'espressione fornita da un solutore è una formula chiusa equivale solo a controllare che sia ottenibile da termini e variabili nella maniera che io ho indicato.
Poi, dire cosa significa che una funzione è esprimibile tramite formula chiusa è quello che hai aggiunto tu.
Btw : nessuno può considerare l'espressione
$ \sum_{i=0}^n i $
come una formula chiusa rispetto all'insieme dei naturali con le usuali operazioni e funzioni.
Invece
$ n(n+1)/2 $
vi rientra a pieno titolo. Se apri un testo di logica troverai che le definizioni riguardanti le "formule" sono sempre date (quando si può) a prescindere dal modello interpretativo usuale delle stesse (e quindi dalla semantica); per questo ho parlato di insiemi operazioni e funzioni generiche, invece che di N, +,-,x,/ e delle funzioni "con nome e cognome".
La tua definizione pretende anche di dire che a noi non interessa la scrittura della formula, ma solo il sottoinsieme del prodotto $ \mathcal{A}^k\times\mathcal{A} $ che le è associato in quanto funzione di k variabili a valori in $ \mathcal{A} $. Questo non è sbagliato (infatti è proprio quello che ci interessa), ma visto che la definizione di "formula chiusa" riguarda solo successioni finite di simboli e non funzioni, mi sembra più corretto darla in tutta generalità, lasciando poi per sottointeso che una funzione esprimibile in formula chiusa sia quello che dici tu.
@Mind : ripeto, l'ironia non è sempre la miglior risposta
-
MindFlyer
