| dbpprop:abstract
|
- In general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields.
- Vollständigkeit ist eine Eigenschaft formaler Systeme bzw. Kalküle. Man unterscheidet semantische Vollständigkeit („Alles, was wahr ist, ist beweisbar. “), klassische Vollständigkeit („Eine der zwei Aussagen <math>\mathit A\,</math> und <math>\neg A</math> ist stets beweisbar. “) und syntaktische Vollständigkeit („Wird eine nicht beweisbare Aussage als Axiom verwendet, so ist die Widerspruchsfreiheit verletzt, d.h. alles wird beweisbar. “). Semantische Vollständigkeit ist das Pendant zur Korrektheit, in dem Sinn, dass ein Kalkül korrekt ist, wenn jede in ihm beweisbare (ableitbare) Aussage gilt („Alles, was beweisbar ist, ist wahr. “) Ein korrekter Kalkül ist insbesondere widerspruchsfrei, denn in einem Kalkül, der nicht widerspruchsfrei ist, d. h. in dem ein Widerspruch beweisbar ist, ist insbesondere alles, was falsch ist, beweisbar. Wenn ein Kalkül korrekt und vollständig ist, können in ihm genau alle wahren Aussagen abgeleitet werden. Kurt Gödel bewies, dass die Prädikatenlogik erster Stufe nicht nur korrekt, sondern auch vollständig ist. Er bewies weiter, dass alle Systeme, die so mächtig sind wie die Arithmetik, entweder nicht vollständig oder nicht widerspruchsfrei sind, sowie dass sich Vollständigkeit und Widerspruchsfreiheit eines solchen Systems nicht innerhalb des Systems selbst beweisen lassen. Ähnliches folgt aus der von Alan Turing formal bewiesenen Unlösbarkeit des Halteproblems.
- On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématique qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il faut préciser dans chaque contexte. Dans le cas contraire, on parle d'incomplétude, surtout dans le contexte de la logique mathématique. Un espace métrique est complet quand toute suite de Cauchy d'éléments de cet espace converge, voir espace complet. Un espace mesurable est complet quand tout sous-ensemble d'un ensemble de mesure nulle est mesurable, voir mesure. En logique mathématique un jeu de règles ou d'axiomes est complet quand il formalise entièrement la sémantique attendue. Cela peut se préciser de façons très différentes. On a les deux notions de complétude suivantes pour la sémantique de Tarski. Un système de déduction pour une logique donnée, est complet quand il démontre les formules valides dans tous les modèles de cette logique. Plus précisément, on dit qu'une formule se déduit sémantiquement d'une théorie quand dans tout modèle de la théorie, pour toute interprétation de ses variables libres, la formule est valide. Un système de déduction est correct, fidèle ou adéquat quand toute déduction est valide sémantiquement. Il est complet quand toutes les déductions sémantiques peuvent se dériver dans le système. On parle de théorème de complétude quand il existe un système de déduction fidèle qui est complet (le système de déduction doit être raisonnable, c’est-à-dire que l'ensemble des preuves dans le système doit être récursif). Une théorie axiomatique est complète quand tout énoncé du langage de la théorie est déterminé par déduction dans la théorie : il est soit démontrable, soit de négation démontrable. Cette notion est étroitement liée à celle de théorie décidable mais ne se confond pas avec elle. Le premier théorème d'incomplétude de Gödel énonce que, sous des hypothèses raisonnables, aucune théorie arithmétique cohérente n'est complète. Il a pour conséquence qu'il n'y a pas système de déduction raisonnable qui capture entièrement la sémantique attendue, à savoir la vérité dans un modèle, celui des entiers naturels (le modèle standard de l'arithmétique). En calcul propositionnel un système de connecteurs est complet quand il permet de décrire toutes les fonctions de la sémantique, toutes les fonctions booléennes dans le cas de la logique classique. En théorie de la calculabilité ou en théorie de la complexité un ensemble ou un problème de décision est complet dans une classe, si, cet ensemble ou problème appartient à la classe, et si, pour une notion de réduction adéquate, tout ensemble ou problème de la classe se réduit à celui-ci. Ainsi le problème de l'arrêt, plus exactement l'ensemble des entiers n tels que la machine de code n s'arrête pour l'entrée n, est complet dans la classe des ensembles récursivement énumérables (pour la réduction récursive). La satisfaisabilité d'un ensemble de clauses du calcul propositionnel est un problème NP-complet, c’est-à-dire complet dans la classe des problèmes solubles en temps non déterministe polynomial (pour la réduction polynomiale). En théorie des ordres, un treillis est complet quand tout ensemble non vide possède une borne supérieure et une borne inférieure, voir comme cas particulier les algèbres de Boole complètes. Dans le contexte de l'informatique théorique, en théorie des domaines, un ordre partiel complet (cpo) est un ensemble partiellement ordonné qui a un plus petit élément et dont toutes les chaînes ont une borne supérieure. En théorie des graphes, un graphe (ou un sous-graphe) non orienté est complet quand toute paire de sommets est reliée par une arête.
- A completude é um meta-resultado lógico importante, que garante que toda sentença válida pode ser formalmente derivada, estabelecendo assim uma certa relação entre o universo semântico e sintático de um determinado cálculo lógico: Dizemos que uma dada lógica é completa se para toda tautologia φ, podemos apresentar uma derivação formal para φ, à partir de um conjunto vazio de premissas. Esta noção de completude também é denominada por alguns autores completude fraca. Dizemos que uma determinada lógica é fortemente completa se, dado um conjunto de fórmulas <math>\Gamma \cup \{\varphi\}</math>, temos: se <math> \varphi \,\!</math> é consequência lógica (ou consequência semântica) do conjunto de premissas <math> \Gamma \,\!</math> em conjunto com uma fórmula arbitrária <math> \alpha \,\!</math>, então pode-se apresentar uma dedução formal de <math> \varphi \,\!</math> à partir deste mesmo <math>\Gamma \,\!</math>. Em símbolos, denotamos isto por: <math>\Gamma \models \varphi</math> implica <math>\Gamma \vdash \varphi</math> Uma outra definição simples de uma lógica completa diz que nenhum axioma ou regra de inferência extra precisa ser adicionado à teoria forma desta lógica para que ela para que ela seja capaz de derivar formalmente todas as fórmulas válidas.
- Ett formellt system i logiken sägs vara fullständigt om varje sann sats i systemet kan bevisas utgående från axiomen i systemet, dvs <math>\Gamma \models \varphi \Rightarrow \Gamma \vdash \varphi</math> Ett berömt teorem av Kurt Gödel säger att alla tillräckligt komplexa system är ofullständiga.
|
| rdfs:comment
|
- In general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields.
- Vollständigkeit ist eine Eigenschaft formaler Systeme bzw. Kalküle. Man unterscheidet semantische Vollständigkeit („Alles, was wahr ist, ist beweisbar. “), klassische Vollständigkeit („Eine der zwei Aussagen <math>\mathit A\,</math> und <math>\neg A</math> ist stets beweisbar. “) und syntaktische Vollständigkeit („Wird eine nicht beweisbare Aussage als Axiom verwendet, so ist die Widerspruchsfreiheit verletzt, d.h. alles wird beweisbar. “).
- On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématique qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il faut préciser dans chaque contexte. Dans le cas contraire, on parle d'incomplétude, surtout dans le contexte de la logique mathématique. Un espace métrique est complet quand toute suite de Cauchy d'éléments de cet espace converge, voir espace complet.
- A completude é um meta-resultado lógico importante, que garante que toda sentença válida pode ser formalmente derivada, estabelecendo assim uma certa relação entre o universo semântico e sintático de um determinado cálculo lógico: Dizemos que uma dada lógica é completa se para toda tautologia φ, podemos apresentar uma derivação formal para φ, à partir de um conjunto vazio de premissas. Esta noção de completude também é denominada por alguns autores completude fraca.
- Ett formellt system i logiken sägs vara fullständigt om varje sann sats i systemet kan bevisas utgående från axiomen i systemet, dvs <math>\Gamma \models \varphi \Rightarrow \Gamma \vdash \varphi</math> Ett berömt teorem av Kurt Gödel säger att alla tillräckligt komplexa system är ofullständiga.
|
![[RDF Data]](/statics/sw-cube.png)
