204SM - LOGICA 2021, Sezione: (24 marzo 2022 h.11/13, aula 3 edificio C5) Insiemi elencabili e costruzioni diagonali | Moodle@Units

Home Corsi Supporto

Schema della sezione

Dapprima in termini intuitivi, poi con riferimento alla teoria dei numeri, stabiliamo che:
esistono insiemi elencabili il cui complemento non è elencabile;
esistono insiemi diofantei il cui complemento non è diofanteo.
Dal secondo di questi risultati, insieme al teorema DPRM (dalle iniziali dei cognomi di Martin D. Davis, Hilary Putnam, Julia Robinson, Yuri V. Matiyasevich) discenderà l'insolubilità algoritmica del 10^o problema di Hilbert.
- Seleziona attività Dispensetta divulgativa sulla nozione di insieme enumerabile e sulla costruzione diagonale di un insieme enumerabile in cui complemento non è enumerabile
  
  Dispensetta divulgativa sulla nozione di insieme enumerabile e sulla costruzione diagonale di un insieme enumerabile in cui complemento non è enumerabile File PDF
- Seleziona attività Dispensa non altrettanto elementare sull'esistenza di un insieme diofanteo universale, grazie al quale si può costruire un insieme diofanteo il cui complemento non è diofanteo
  
  Dispensa non altrettanto elementare sull'esistenza di un insieme diofanteo universale, grazie al quale si può costruire un insieme diofanteo il cui complemento non è diofanteo File PDF
  
  Di questa dispensa potete saltare il paragrafo 2.3 e la seconda appendice. Della terza appendice vi serve solo il richiamo dell'enunciato del teorema cinese dei resti.