Cantor, procedimentodiagonalediCantor, procedimentodiagonaledi detto anche argomento diagonalediCantor, è il metodo per dimostrare che l’insieme dei numeri razionali Q è numerabile (primo procedimento [...] diagonale). Il primo procedimento opera sullo schema
in cui ogni razionale positivo compare almeno una volta. Scrivendo i numeri nell’ordine indicato dalle frecce, previa omissione di quelli equivalenti a frazioni già elencate, si ottiene ...
Leggi Tutto
paradosso
Dal gr. παράδοξος, comp. di παρα- nel sign. di «contro» e δόξα «opinione»; lat. paradoxum. Affermazione, proposizione, tesi, opinione che, per il suo contenuto o per la forma in cui è espressa, [...] . Questo discorso è analogo a quello relativo al procedimentodiagonalediCantor. P. di Berry (è una presentazione semplificata di quello di Jules Antoine Richard): in italiano vi è un numero finito di sillabe, perciò finito è anche il numero delle ...
Leggi Tutto
cardinalita
cardinalità nozione introdotta da G. Cantor che generalizza il concetto intuitivo di “numero di elementi di un insieme” astraendo dalla natura e dall’ordine degli elementi stessi. La nozione, [...] spazio tridimensionale euclideo hanno la stessa potenza. Attraverso il concetto di cardinalità si dimostra che esistono “diversi tipi di infinito”: il cosiddetto procedimentodiagonalediCantor stabilisce che l’insieme N dei numeri naturali e l ...
Leggi Tutto
R
R (insieme dei numeri reali) insieme numerico, denotato con il simbolo R, che comprende tutti i numeri che è possibile scrivere in forma decimale, con parte decimale finita, infinita periodica o infinita [...] dei numeri naturali) e perciò l’insieme dei numeri trascendenti possiede la stessa cardinalità di R, la cardinalità del continuo (→ Cantor, procedimentodiagonaledi; → continuo, ipotesi del).
R è l’unico campo archimedeo completo
Come nel caso dei ...
Leggi Tutto
Fondamenti della matematica e teoria algoritmica dell'informazione
Gregory J. Chaitin
Ciò che possiamo dimostrare intorno ai fondamenti della matematica usando i suoi stessi metodi costituisce la metamatematica, [...] cose che non possono essere ottenute mediante calcolo, facendo un uso brillante del procedimentodiagonalediCantor, usato in teoria degli insiemi, che egli applica all'elenco di tutti i numeri reali calcolabili. In tal modo Turing ottiene un numero ...
Leggi Tutto
calcolabilita
calcolabilità in logica, termine che indica la possibilità di descrivere in modo sequenziale, deterministico e finito, una procedura di calcolo che consenta di pervenire a un dato risultato. [...] totali, indicata con φ1, φ2, φ3, ..., e si definisce per ognuna di esse la funzione ƒ(x) = φ(x) + 1. Con un ragionamento analogo al procedimentodiagonaledi → Cantor, si può dimostrare che tale funzione non è una funzione calcolabile totale. ...
Leggi Tutto
CantorCantor Georg (San Pietroburgo 1845 - Halle, Sassonia-Anhalt, 1918) matematico e logico tedesco. Nato in Russia da famiglia tedesca, iniziò gli studi universitari presso il Politecnico di Zurigo [...] nel 1874, Cantor dimostrò l’esistenza di due insiemi infiniti non equipotenti, non aventi cioè la stessa cardinalità, i numeri naturali e i numeri reali, utilizzando per la prima volta il cosiddetto procedimentodiagonale per dimostrare che ...
Leggi Tutto
INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] ordine qualsiasi si dice "ricorsivamente enumerabile". Ora, con un tipico procedimentodiagonale alla Cantor, si mostra che i linguaggi individuati da macchine di Turing sono ricorsivamente enumerabili: anzi, come vedremo, coincidono con essi. Dalla ...
Leggi Tutto
intuizionismo
intuizionismo concezione della matematica secondo cui l’affermazione di esistenza di enti matematici è lecita solo se si dispone di un metodo che ne garantisca la costruibilità. In questo [...] insieme R dei numeri reali è superiore alla cardinalità del numerabile (→ Cantor, procedimentodiagonaledi). Per Brouwer, mentre continua a rimanere valido il principio di non contraddizione, non è invece possibile accettare il principio del → terzo ...
Leggi Tutto