Navigation – Plan du site
Logic and Philosophy of Science in Nancy (I)

Gödel’s Incompleteness Phenomenon—Computationally

Saeed Salehi
p. 23-37

Résumés

Nous soutenons que le théorème de complétude de Gödel est équivalent à la complétabilité de théories consistentes, et que son théorème d'incomplétude est équivalent au fait que cette complétion n'est pas constructive, en ce sens qu'il existe des théories consistantes et récursivement énumérables qui ne peuvent être étendues à aucune théorie complète et consistente et récursivement énumérable. Toutefois, n'importe quelle théorie consistente et décidable peut être étendue à une théorie complète, consistente et décidable. Donc la déduction et la consistence ne sont pas décidables en logique, et un analogue du théorème de Rice est valable pour les théories récursivement énumérables : toutes leurs propriétés non-triviales sont indécidables.

Haut de page

Accès au texte / extrait

Cairn

Texte intégral en libre accès disponible sur le portail Cairn. Le texte intégral en libre accès sera disponible à cette adresse en janvier 2018.
Consulter cet article

Plan

1 Introduction
2 Completeness and completability
3 Incompleteness and incompletability
3.1 An undecidable but RE-completable theory
3.2 An RE-incompletable theory
4 Rice’s theorem for RE theories

Aperçu du début du texte

1 Introduction

The incompleteness theorem of Kurt Gödel has been regarded as the most significant mathematical result in the twentieth century, and Gödel’s completeness theorem is a kind of the fundamental theorem of mathematical logic. To avoid confusion between these two results, it is argued in the literature that the completeness theorem is about the semantic completeness of first order logic, and the incompleteness theorem is about the syntactic incompleteness of sufficiently strong first order logical theories. In this paper we look at these two theorems from another perspective. We will argue that Gödel’s completeness theorem is a kind of completability theorem, and Gödel-Rosser’s incompleteness theorem is a kind of incompletability theorem in a constructive manner. By Gödel’s semantic incompleteness theorem we mean the statement that any sound and sufficiently strong and recursively enumerable theory is incomplete. By Gödel-Rosser’s incompleteness theorem we mean the statemen...

Haut de page

Pour citer cet article

Référence électronique

Saeed Salehi, « Gödel’s Incompleteness Phenomenon—Computationally », Philosophia Scientiæ [En ligne], 18-3 | 2014, mis en ligne le 27 novembre 2014, consulté le 26 juin 2017. URL : http://philosophiascientiae.revues.org/968 ; DOI : 10.4000/philosophiascientiae.968

Haut de page

Auteur

Saeed Salehi

University of Tabriz & IPM (Iran)

Haut de page

Droits d’auteur

Tous droits réservés

Haut de page