OliForum Matematico

Sapete tutti cos'è vero? Il teorema di deduzione nella logica matematica intendo.

Vorrei sapere il perchè, la spiegazione in parole povere , chiare.
Nel libro di Mendelson (introduzione alla logica matematica) non si riesce a capire molto bene (è scritto in maniera che uno che vuole introdursi alla logica matematica non ci si possa introdurre).
Grazie.

No, non lo conosco, almeno con questo nome (magari è una banalità...)

Comunque mi sembra già un buon motivo per spostarlo in Matematica non elementare

Una breve occhiata a wikipedia mi conferma che non è niente di stravagante, ma non è una cattiva idea introdurre l'argomento di cui si parla invece di assumere che tutti sappiano cos'è. Ciao

http://it.wikipedia.org/wiki/Teorema_di_deduzione

per quel che ho capito io: se X è deducibile da Y, allora Y -> X (tautologia)
Questo è quello che ho capito.

Il teorema dice questo: sia X = {X1, X2, ..., Xn} un insieme finito di formule; se, prendendo X come insieme di assiomi, si può dimostrare Y, allora si può dimostrare, senza usare assiomi, la formula (X1 e X2 e ... e Xn) -> Y.
La dimostrazione di questo teorema cambia in base al tipo di logica del primo ordine che si sta usando (deduzione naturale, Hilbert, sequenti, ecc...).
Con la logica del primo ordine di Hilbert (molti assiomi base, ma una sola regola di deduzione, il modus ponens), il teorema non è facile da dimostrare (si dimostra per induzione sulla lunghezza della dimostrazione di Y).
Clamorosamente, con la deduzione naturale il teorema è immediato: la d.n. non ha assiomi base, ma ha molte regole di deduzione, tra le quali una che è praticamente il teorema in questione.

Bene, io dovrei dimostrare il teorema di deduzione nel sistema assiomatico L descritto in Mendelson (introduzione alla logica matematica) che si basa su 3 assiomi e sul modus ponens: (NON lo segnerò con lettere minuscole)
1) A->(B->A)
2) (A->(B->C))->((A->B)->(A->C)
3) (b->a)->((b->A)->B)

e nauralmente in modus ponens : A->B, A | B.
Come si può fare per dimostrare il teorema di deduzione con questi assiomi?

Il tuo sistema è il calcolo delle proposizioni di Hilbert, suppongo (io conoscevo un assioma 3 diverso...).
La dimostrazione è un po' complicata, così ti segnalo le "note di logica 3" di R. Ferro che puoi trovare qui: http://www.scienze.univr.it/fol/main?en ... d=&lang=it
La dimostrazione che cerchi è a pag. 40; fa uso degli assiomi 1 e 2 che coincidono (il terzo è diverso, ma se non viene usato...).

Grazie. Comunque il terzo assioma mi sembra lo stesso.
Avevo detto che le minuscole volevano dire non. Ora provo a vedere se riesco a dimostrare quella cosa