Question

Je lisais la question La cohérence et l'exhaustivité impliquent la solidité? Et la première déclaration dit:

Je comprends que la solidité implique une cohérence.

Ce qui m'avait tout à fait perplexe parce que je pensais que la solidité était une déclaration plus faible que la cohérence (c'est-à-dire que je pensais que les systèmes cohérents devaient être solides mais je suppose que ce n'est pas vrai). J'utilisais la définition informelle que Scott Aaronson utilisait dans son 6.045 / 18.400 Cours au MIT pour la cohérence et la solidité:

  1. Soussses = un système de preuve est solide si toutes les instructions qu'elle prouve sont réellement vraies (tout est prouvable est vrai). c'est-à-dire si ($ phi $ est prouvable) $ implique $ ($ phi $ est vrai). Donc, s'il y a un chemin vers une formule) alors (cette formule est vraie)
  2. Cohérence = un système cohérent ne prouve jamais a et non (a). Ainsi, un seul A ou sa négation peut être vrai.

En utilisant ces définitions (peut-être informelles) à l'esprit, j'ai construit l'exemple suivant pour démontrer qu'il existe un système qui est solide mais pas cohérent:

$$ CharlieSystem triangleq {axioms = {a, neg a }, inférencerrules = {pas ( cdot) } } $$

La raison pour laquelle je pensais que c'était un système audio est que par hypothèse, les axiomes sont vrais. Ainsi et non A sont tous les deux vrais (oui je sais que la loi du milieu exclue n'est pas incluse). Étant donné que la seule règle d'inférence est la négation, nous obtenons que nous pouvons atteindre A et non A des axiomes et nous atteindre mutuellement. Ainsi, nous n'atteignons que de véritables déclarations en ce qui concerne ce système. Cependant, bien sûr, le système n'est pas cohérent car nous pouvons prouver la négation de la seule déclaration du système. Par conséquent, j'ai démontré qu'un système audio pourrait ne pas être cohérent. Pourquoi cet exemple est-il incorrect? Qu'ai-je fait de mal?

Dans ma tête, cela a du sens intuitivement parce que la solidité dit simplement qu'une fois que nous commençons et que nous avons axiomes et lancé les règles d'inférence que nous n'atteignons que les destinations (c'est-à-dire les déclarations) qui sont vraies. Cependant, il ne dit pas vraiment quelle destination nous arrivons. Cependant, la cohérence indique que nous ne pouvons atteindre que des destinations qui atteignent $ a $ ou $ neg a $ (les deux pas les deux). Ainsi, chaque système cohérent doit inclure la loi du milieu exclu comme un axiome, ce qui, bien sûr, je ne l'ai pas fait, puis comprenait la négation du seul axiome comme le seul autre axiome. Donc, il ne pense pas avoir fait quelque chose de trop intelligent, mais quelque chose ne va pas?


Je me rends compte que cela pourrait être un problème car j'utilise la définition informelle de Scott. Même avant d'écrire la question que j'ai vérifiée Wikipédia Mais leur définition n'avait pas de sens pour moi. En particulier la partie qu'ils disent:

en ce qui concerne la sémantique du système

Leur citation complète est:

Chaque formule qui peut être prouvée dans le système est logiquement valide par rapport à la sémantique du système.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top