Cantor was Wrong: sfatare la gerarchia di set infiniti

Di Vitalik Buterin, PhD presso l’Università di Basilea

Un filone di matematica comune sostiene che, anziché essere un solo tipo di infinito, esiste in realtà una gerarchia infinita di diversi livelli di infinito. Considerando che la dimensione dell’insieme dei numeri interi è semplicemente infinita e l’insieme dei numeri razionali è grande quanto gli interi (perché è possibile mappare ogni numero razionale su un numero intero intercalando le cifre del suo numeratore e denominatore, ad esempio 0.456456456 …. = 456/999 = 152/333 -> 135323), la dimensione dell’insieme dei numeri reali è una sorta di infinito ancora più grande, perché non c’è modo di fare una mappatura simile dai numeri reali agli interi.

Prima di tutto, dovrei notare che è relativamente facile vedere che l’affermazione che non esiste una mappatura è falsa. Ecco una semplice mappatura. Per un dato numero reale, dammi un programma (deterministico) di pitone che stamperà le sue cifre (ad es. Per π, che potrebbe essere un programma che calcola approssimazioni sempre migliori usando la serie infinita π = 4 — 4/3 + 4/5 — 4/7 + ... ). Posso convertire il programma in un numero (usando n = int.from_bytes(open('program.py').read(), 'big') ) e quindi output il numero. Fatto. C’è la mappatura da numeri reali a numeri interi.

Ora diamo un’occhiata all’argomento più comune usato per affermare che tale mappatura non può esistere, vale a dire l’argomento diagonale di Cantor. Ecco un’esposizione di UC Denver; è breve, quindi farò solo screenshot del tutto:

Ora, ecco il difetto fondamentale in questo argomento: le espansioni decimali dei numeri reali non sono univoche . Per fornire un controesempio nel formato esatto richiesto dalla “prova”, considerare l’insieme (numeri scritti in binario), con cifre diagonali in grassetto:

  • x[1] = 0. 0 00000...
  • x[2] = 0.0 1 1111...
  • x[3] = 0.00 1 111...
  • x[4] = 0.000 1 11...
  • … ..

La diagonale indica: 01111… .. Se capovolgiamo ogni cifra, otteniamo il numero: y = 0.10000 ……

E qui sta il problema: proprio come in decimale, 0.9999…. è uguale a 1, in binario 0,01111… .. è uguale a 0,10000… .. E quindi anche se la nuova espansione decimale non è nell’elenco originale, il numero y è esattamente uguale al numero x [2].

Si noti che ciò implica direttamente che il problema dell’arresto è di fatto risolvibile. Per capire perché, immagina un programma per computer che qualcuno sostiene non si fermerà. Sia c [1] lo stato del programma dopo un passaggio, c [2] dopo due passaggi, ecc. Sia x [1], x [2], x [3]…. essere un elenco completo di tutti i numeri reali (che esiste, come abbiamo dimostrato sopra), espresso in base 2 ^ D dove D è la dimensione della memoria del programma, quindi uno stato del programma può sempre essere rappresentato come una singola “cifra”. Sia y = 0.c [1] c [2] c [3] …… .. Questo numero fa parte dell’assunzione della lista, quindi è uno dei valori x [i], e quindi può essere calcolato in un po ‘di tempo finito. Ciò ha implicazioni in numerosi settori, in particolare nel dimostrare che le blockchain “complete di Turing” sono effettivamente sicure.

In attesa di brevetto per questa ricerca.