Stiamo lavorando per ripristinare l'app di Unionpedia nel Google Play Store
UscenteArrivo
🌟Abbiamo semplificato il nostro design per una migliore navigazione!
Instagram Facebook X LinkedIn

Relazione ben fondata

Indice Relazione ben fondata

In matematica, una relazione binaria R si dice ben fondata su una classe X se ogni sottoinsieme non vuoto S ⊆ X ha un elemento minimale rispetto a R, cioè un elemento m per cui, per ogni s ∈ S, non valga s R m. In altre parole, una relazione è ben fondata se: Alcuni autori includono un'ulteriore condizione, vale a dire che R sia simile ad un insieme, cioè che gli elementi minori di un qualunque elemento dato formino a loro volta un insieme.

Indice

  1. 4 relazioni: Lemma del collasso di Mostowski, Logica dimostrativa, Teoria dei tipi intuizionista, Turing riduzione.

Lemma del collasso di Mostowski

Nella logica matematica, il lemma del collasso di Mostowski, noto anche come collasso di Shepherdson-Mostowski, è un teorema della teoria degli insiemi introdotto da Andrzej Mostowski nel 1949 e da John Shepherdson nel 1953.

Vedere Relazione ben fondata e Lemma del collasso di Mostowski

Logica dimostrativa

La logica dimostrativa è una logica modale nella quale l'operatore di necessità è interpretato come: "è dimostrabile che". Il punto è quello di catturare il predicato di prova di una teoria formale ragionevolmente ricca, quale è l'aritmetica di Peano.

Vedere Relazione ben fondata e Logica dimostrativa

Teoria dei tipi intuizionista

La teoria dei tipi intuizionista (nota anche come teoria dei tipi costruttiva o teoria dei tipi di Martin-Löf) è una teoria dei tipi e una fondazione della matematica alternativa.

Vedere Relazione ben fondata e Teoria dei tipi intuizionista

Turing riduzione

In teoria della computabilità, una Turing-riduzione da un problema decisionale A ad un problema decisionale B è una macchina oracolo che decide il problema A dato un oracolo per B (Rogers 1967, Soare 1987).

Vedere Relazione ben fondata e Turing riduzione