Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] il numero di caratteri che essa contiene. La stella Σ* di Σ è l'insieme (infinito) di tutte le stringhe sull'alfabeto, inclusa la stringa vuota. Un linguaggio L è un insieme finito o infinito di stringhe su Σ, cioè L∈Σ*.
Posto che con l'alfabeto Σ si ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. La topologia degli insiemi di punti
Roger Cooke
Brian Griffith
La topologia degli insiemi di punti
La topologia generale o topologia degli insiemi [...] di nuovo a F(x) il principio dell'assenza di angoli e la dimostrazione restava valida. Era quindi naturale considerare un insiemeinfinito di punti di accumulazione che avessero però a loro volta solo un numero finito di punti di accumulazione e così ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1981-1990
1981-1990
1981
Il sistema operativo MS-DOS. Tale sistema, realizzato dalla Microsoft e destinato a dominare nel suo settore, è utilizzato per la prima [...] dei minori. Il matematico americano Neil Robertson e l'inglese Paul Seymour dimostrano il teorema dei minori: in ogni insiemeinfinito di grafi finiti, ne esiste uno che è minore di un altro. Per dimostrare questo profondo risultato di matematica ...
Leggi Tutto
Il Contributo italiano alla storia del Pensiero: Scienze (2013)
La logica e i fondamenti della matematica tra Ottocento e Novecento
Mario Piazza
I fondamenti della geometria
Nella seconda metà dell’Ottocento, in tutta Europa il baricentro delle ricerche geometriche [...] (principio d’induzione).
I primi quattro assiomi garantiscono che N è un insiemeinfinito, mentre il principio d’induzione serve a identificare N tra tutti gli insiemiinfiniti. Peano prosegue definendo le quattro operazioni di base dell’aritmetica e ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] Se la classe dei gruppi finiti fosse elementare dovrebbe coincidere con ModTGF. Sia ora C un insiemeinfinito di nuove costanti individuali cn per n∈ℕ e consideriamo l'insieme
[5] X = TGF ∪ {ci = cj |i≠j con i,j∈ℕ} .
Per compattezza, perché X abbia ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. La teoria degli insiemi
Gabriele Lolli
La teoria degli insiemi
La teoria degli insiemi è universalmente considerata, nella sua concezione e impostazione [...] di L del teorema di Löwenheim-Skolem, per controllare a che livelli sono inseriti, se inseriti, i sottoinsiemi di un insiemeinfinito dato.
Per l'assioma di scelta le cose sono più facili, una volta che ci si renda conto che la corrispondenza ...
Leggi Tutto
spazio proiettivo
Luca Tomassini
Dati due insiemi P,Q e una relazione R⊂P×Q, consideriamo la tripla C={P,Q,R} e chiamiamo ogni elemento di P un punto e ogni elemento di Q una linea. Se (p,l)∈R è valida [...] di P. Punti e linee sono evidentemente sottospazi. Talvolta si impone a C un ulteriore assioma: (d) Esiste un insiemeinfinito di punti tale che ogni sottospazio che li contiene contiene P stesso. Una geometria proiettiva che soddisfi (d) è detta ...
Leggi Tutto
aritmetica di Presburger
Luca Tomassini
Versione semplificata dell’aritmetica di Peano, ottenuta da quest’ultima eliminando l’operazione di moltiplicazione. Più precisamente, l’aritmetica di Presburger [...] assioma di induzione al primo livello della logica si paga un prezzo molto alto: esso è sostituito da un insiemeinfinito di assiomi, uno per ciascuna proprietà P. La caratteristica fondamentale dell’aritmetica di Presburger è proprio di poter essere ...
Leggi Tutto
calcolabilità
Fabrizio Luccio
La teoria che studia la possibilità di calcolare una funzione dagli interi sugli interi mediante un modello astratto di computazione come per es. la macchina di Turing. [...] poste nei primi decenni del Novecento come conseguenza degli studi sugli insiemiinfiniti sviluppatisi negli anni precedenti. Infatti gli algoritmi di calcolo appartengono a un insiemeinfinito numerabile (cioè i cui elementi possono essere messi in ...
Leggi Tutto
alef
alef [Lat. aleph, dall'ebraico 'alep 〈àlef〉 "toro"] [ALG] Nome della prima lettera dell'alfab. ebr., indicata nella scrittura con א, con cui s'indica la potenza di un insiemeinfinito: per es., [...] con א₀ (leggi "a. zero") s'indica la potenza del-l'insieme di tutti i numeri naturali (potenza del numerabile). ...
Leggi Tutto
infinito
agg. e s. m. [dal lat. infinitus, comp. di in-2 e finitus, part. pass. di finire «limitare»]. – 1. agg. a. Che non ha principio né fine; che non ha limiti: il tempo i.; lo spazio i.; la misericordia di Dio è i.; i. silenzio (Leopardi)....
insieme
insième (ant. insème) avv. e s. m. [lat. ĭnsĕmul, rifatto nel lat. volg. in *insĕmel per sostituzione di semel «una volta» a simul «insieme»]. – 1. avv. Esprime in genere i seguenti rapporti: a. Compagnia, unione: siamo usciti i. io...