Funzione numerabilità dei razionali
Ciao a tutti,
è da diverso tempo che mi chiedo, dato che l'insieme dei numeri razionali è numerabile, esiste una funzione f tale che dato un numero n∈ N restituisce un numero q∈Q?
Ho questo dubbio, in quanto cercando in rete, tutte le dimostrazioni riguardanti la la numerabilità di Q sono fatte in modo costruttivo partendo dalla solita tabella con q=r/c..., ma non sono riuscito a trovare nessuna dimostrazione analitica.
Quindi vi chiedo, esiste un modo per esprimere la corrispondenza biunivoca tra N e Q tramite una funzione, o la corrispondenza può essere solo dimostrata ma non esiste alcuna funzione per esprimerla?
Grazie.
è da diverso tempo che mi chiedo, dato che l'insieme dei numeri razionali è numerabile, esiste una funzione f tale che dato un numero n∈ N restituisce un numero q∈Q?
Ho questo dubbio, in quanto cercando in rete, tutte le dimostrazioni riguardanti la la numerabilità di Q sono fatte in modo costruttivo partendo dalla solita tabella con q=r/c..., ma non sono riuscito a trovare nessuna dimostrazione analitica.
Quindi vi chiedo, esiste un modo per esprimere la corrispondenza biunivoca tra N e Q tramite una funzione, o la corrispondenza può essere solo dimostrata ma non esiste alcuna funzione per esprimerla?
Grazie.
Risposte
Il procedimento costruttivo con "la tabella con q=r/c" e' una funzione a tutti gli effetti!
Quel procedimento ti da' un modo costruttivo per definire una funzione. Guarda ad esempio qui.
Se stai chiedendo se esiste una funzione "piu' bella", la risposta dipende da quanto "piu' bella" la vorresti.
Quel procedimento ti da' un modo costruttivo per definire una funzione. Guarda ad esempio qui.
Se stai chiedendo se esiste una funzione "piu' bella", la risposta dipende da quanto "piu' bella" la vorresti.
C'è anche la costruzione dei razionali mediante insieme quoziente di $ZZtimesNN_0$ o a volte $ZZtimesZZ_0$ definendo sul prodotto cartesiano una relazione di equivalenza
Poi c'è il teorema di numerabilita di un prodotto cartesiano
Poi c'è il teorema di numerabilita di un prodotto cartesiano
"Pappappero":
Il procedimento costruttivo con "la tabella con q=r/c" e' una funzione a tutti gli effetti!
Quel procedimento ti da' un modo costruttivo per definire una funzione. Guarda ad esempio qui.
Se stai chiedendo se esiste una funzione "piu' bella", la risposta dipende da quanto "piu' bella" la vorresti.
Si, ma intendevo una funzione esprimibile analiticamente, anche perche se uno vuole esprimere dalla relazione a che valore razionale corrisponde il numero 100000000,non può corstrursi una tabella con un milione righe...
Invece l'espressione proposta da anto_zoolander mi piace molto, sebbene non proprio immediata, penso possa essere usata su un calcolatore per calcolare la corrisondenza con qualsiasi numero.
Grazie.
Esiste un modo 'naturale' di costruire una biiezione tra un insieme e un suo quoziente?
"Pappappero":
Esiste un modo 'naturale' di costruire una biiezione tra un insieme e un suo quoziente?
Ho provato a tradurre la tua domanda in inglese, e ho trovato queste fantastiche risposte: http://math.stackexchange.com/a/1067928/395943.
È incredibile come a volte trovando le giuste parole chiave si riesce a trovare quello che si cerca...
Grazie!
Siamo tutti d'accordo sul fatto che esiste una corrispondenza biunivoca tra N e Q.
Prendiamone una e chiamiamola f, Per la precisione, f:N-->Q.
Tu vuoi sapere quanto vale f(100000000)?. Facile, vale f(100000000). E spero siamo tutti d'accordo che, una volta precisata f, abbiamo a disposizione pure un algoritmo che ci permette di calcolare f(n) per ogni n.
Non ti piace? Mi sa di no. Ma se tu sapessi che f(n) = una espressione analitica mostruosamente complicata(n), saresti più contento? Non credo. Il punto è quello già evidenziato da Pappappero nell'ultima riga della sua prima risposta. O da Douglas S. Stones nella sua risposta alla domanda che hai linkato su stackexchange.
Vuoi una funzione computabile? No problem, ce l'hai già (procedimento diagonale di Cantor).
Vuoi che soddisfi limiti di memoria o di numero di operazioni necessarie er calcolarla? E quali operazioni consideri?
Vuoi una espressione analitica che utilizzi quali funzioni? Polinomi, funzioni razionali, irrazionali, esponenziali e parenti stretti?
Etc.
Prendiamone una e chiamiamola f, Per la precisione, f:N-->Q.
Tu vuoi sapere quanto vale f(100000000)?. Facile, vale f(100000000). E spero siamo tutti d'accordo che, una volta precisata f, abbiamo a disposizione pure un algoritmo che ci permette di calcolare f(n) per ogni n.
Non ti piace? Mi sa di no. Ma se tu sapessi che f(n) = una espressione analitica mostruosamente complicata(n), saresti più contento? Non credo. Il punto è quello già evidenziato da Pappappero nell'ultima riga della sua prima risposta. O da Douglas S. Stones nella sua risposta alla domanda che hai linkato su stackexchange.
Vuoi una funzione computabile? No problem, ce l'hai già (procedimento diagonale di Cantor).
Vuoi che soddisfi limiti di memoria o di numero di operazioni necessarie er calcolarla? E quali operazioni consideri?
Vuoi una espressione analitica che utilizzi quali funzioni? Polinomi, funzioni razionali, irrazionali, esponenziali e parenti stretti?
Etc.
"Fioravante Patrone":
Siamo tutti d'accordo sul fatto che esiste una corrispondenza biunivoca tra N e Q.
Prendiamone una e chiamiamola f, Per la precisione, f:N-->Q.
Tu vuoi sapere quanto vale f(100000000)?. Facile, vale f(100000000). E spero siamo tutti d'accordo che, una volta precisata f, abbiamo a disposizione pure un algoritmo che ci permette di calcolare f(n) per ogni n.
Non ti piace? Mi sa di no. Ma se tu sapessi che f(n) = una espressione analitica mostruosamente complicata(n), saresti più contento? Non credo. Il punto è quello già evidenziato da Pappappero nell'ultima riga della sua prima risposta. O da Douglas S. Stones nella sua risposta alla domanda che hai linkato su stackexchange.
Vuoi una funzione computabile? No problem, ce l'hai già (procedimento diagonale di Cantor).
Vuoi che soddisfi limiti di memoria o di numero di operazioni necessarie er calcolarla? E quali operazioni consideri?
Vuoi una espressione analitica che utilizzi quali funzioni? Polinomi, funzioni razionali, irrazionali, esponenziali e parenti stretti?
Etc.
Si, ho capito che qualsiasi algoritmo che permette di stabilire una corrispondenza biunivoca può considerarsi una funzione, tuttavia un procedimento per costruzione grafica, benchè traducibile in algoritmo non può essere tradotto in una formula direttamente computabile.
Senza un'espressione analitica credo sia anche abbastanza difficile stabilire i requisiti di memoria etc...
La mia era una semplice curiosità e penso sia la risposta anto_zoolander e che le diverse risposte trovate su stackexchange soddisfano la mia domanda...
Quale è migliore è difficile dirlo, credo sia abbastanza soggettivo e come dici tu ogni metedo può essere migliore in base ai limiti di memoria o operazioni necessarie.
Le espressioni per quanto possano essere complesse per un'essere umano, possono essere usate in modo immediato se immesse in un software come per esempio wolfram..., mentre una algoritmo anche se semplice richiede di sviluppare un programma ad hoc.
Per me non sarebbe nemmeno un grosso problema sviluppare un algoritmo che usa il metodo diagonale di cantor dato che sono uno sviluppatore, tuttavia il difetto di usare un programma ad hoc è che è difficilmente riutilizzabile per fare analisi sui dati o se si desidera integrarlo con altre formule/espressioni.
Io comunque sono contento e soddisfatto delle risposte che ho ricevuto, sto approfondendo l'argomento studiando la numerabilità del prodotto cartesiano e altri concetti relativi, e per questo vi ringrazio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo