Independencia (lógica matemática)
En lógica matemática, la noción de independencia o indecidibilidad se refiere a la imposibilidad de demostrar o refutar un predicado a partir de otros.
Una sentencia σ se dice independiente o indecidible en una teoría lógica T si T no demuestra ni refuta σ; esto es, si no es posible probar σ partiendo de T, ni probar que σ es falsa.
Terminología
El adjetivo indecidible se usa como sinónimo de independiente, por ejemplo, «sentencia indecidible en la teoría T». Sin embargo, indecidible también se usa en el ámbito de la teoría de la computabilidad con otro significado. Un problema indecidible es un problema matemático de respuesta «sí o no» que no puede resolverse mediante un algoritmo. Ambos conceptos son distintos, pero pueden aparecer relacionados entre sí. Por ejemplo, el problema de decisión consistente en determinar si una sentencia es independiente en una teoría T es a menudo indecidible.
También puede ocurrir que «independiente en T» se utilice tan solo en el sentido de «no demostrable en T», en lugar de «no demostrable ni refutable en T», y consistente se utilice entonces en el sentido de «no refutable en T».
Ejemplos de independencia
Muchas sentencias interesantes en teoría de conjuntos axiomática son independientes de la teoría de conjuntos de Zermelo-Fraenkel (ZF). Los siguientes enunciados son independientes de ZF (siempre que ésta sea consistente):
El teorema de incompletitud de Gödel establece la existencia de proposiciones independientes en cualquier teoría que contenga la aritmética de Peano, tales como:
- La sentencia de Gödel G.
- La sentencia que afirma la consistencia de la propia teoría.
Además se conocen enunciados puramente aritméticos, que no involucran directamente conceptos lógicos, independientes de dichos axiomas:
- El teorema de Ramsey fuerte.
- El teorema de Goodstein.
Otro ejemplo muy conocido es el quinto postulado de Euclides, que no puede ser demostrado a partir de los restantes axiomas de la geometría euclídea. Esto demuestra la consistencia de las geometrías no euclídeas.
Referencias
- Ivorra, Carlos, Lógica y teoría de conjuntos, consultado el 10 de abril de 2011..
- Ivorra, Carlos, , archivado desde el original el 4 de julio de 2011, consultado el 10 de abril de 2011..
Enlaces externos
- Esta obra contiene una traducción derivada de «Independence (mathematical logic)» de la Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.