En lògica matemàtica, la noció d'independència o indecidibilitat es refereix a la impossibilitat de demostrar o refutar un predicat a partir d'altres.
Una sentència σ s'anomena independent o indecidible en una teoria lògica T si T ni demostra ni refuta σ; és a dir, si no és possible demostrar σ partint de T, ni demostrar que σ és falsa.
Terminologia
L'adjectiu indecidible s'usa com a sinònim d'independent, per exemple, «sentència indecidible en la teoria T». No obstant això, indecidible també s'usa en l'àmbit de la teoria de la computabilidad amb un altre significat. Un problema indecidible és un problema matemàtic de resposta «sí o no» que no pot resoldre's mitjançant un algoritm. Ambdós conceptes són diferents, però poden aparèixer relacionats entre si. Per exemple, el problema de decisió consistent en determinar si una certa sentència és independent en una teoria T és sovint indecidible.
També pot ocórrer que «independent en T» s'utilitzi només en el sentit de «no demostrable en T», en lloc de «no demostrable ni refutable en T», i consistent s'ulitizie llavors en el sentit de «no refutable en T».
Exemples d'independència
Moltes sentències interessant en la teoria axiomàtica de conjunts són independents en la teoria de conjunts de Zermelo-Fraenkel (ZF). Els següents enunciats són independents de ZF (sempre que aquesta sigui consistent):
El teorema d'incompletesa de Gödel estableix l'existència de proposicions independents en qualsevol teoria que contingui l'aritmètica de Peano, tals com:
A més es coneixen enunciats purament aritmètics, que no involucren directament concepte lògics, independents d'aquests axiomes:
- El teorema fort de Ramsey.
- El teorema de Goodstein.
Un altre exemple moly conegut el cinquè postulat d'Euclides, que no pot ser demostrat a partir de la resta d'axiomes de la geometria euclidiana. Això demostra la consistència de les geometries no euclidianes.
Referències