Système formel Un système formel est une construction mathématique rigoureuse qui vise à capturer et organiser notre raisonnement logique. Il se compose de trois éléments essentiels :
Les symboles de base forment l’alphabet du système. Dans un système arithmétique, on trouve par exemple les chiffres 0, 1, 2…, les opérateurs +, ×, les symboles logiques comme ∧ (et), ∨ (ou), ¬ (non), ainsi que des variables et des quantificateurs ∀ (pour tout) et ∃ (il existe). Les règles de formation déterminent comment construire des formules bien formées à partir de ces symboles. Elles précisent quelles combinaisons de symboles ont un sens mathématique. Par exemple, “∀x (x + 0 = x)” est une formule bien formée, tandis que “)0 + ∀x(” ne l’est pas. Les règles d’inférence constituent le moteur du raisonnement. Elles spécifient comment dériver de nouvelles formules à partir de formules déjà établies. Le modus ponens en est l’exemple le plus classique : si nous avons “A implique B” et “A”, alors nous pouvons conclure “B”. À partir de ces éléments, un système formel distingue deux types de formules : les axiomes, qui sont des vérités admises sans démonstration, et les théorèmes, qui sont des formules dérivées des axiomes par application répétée des règles d’inférence. Définitions clés Complétude et incomplétude Un système formel est dit complet si toute formule bien formée du système est soit démontrable (c’est un théorème), soit réfutable (sa négation est un théorème). En d’autres termes, pour toute proposition P du système, soit P soit ¬P est démontrable. Cette propriété semble naturelle : intuitivement, toute affirmation mathématique devrait être soit vraie soit fausse, et un système parfait devrait pouvoir le déterminer. L’incomplétude désigne précisément l’absence de cette propriété : il existe des formules qui ne peuvent être ni démontrées ni réfutées dans le système.
...