Théorèmes

Lemme de Zorn Contexte : Théorie des Ensembles Ordonnés Pour comprendre le lemme de Zorn, il est nécessaire de maîtriser plusieurs concepts de la théorie des ordres. Soit $(E, \le)$ un ensemble muni d’une relation d’ordre. Ensemble Partiellement Ordonné : La relation $\le$ est une relation d’ordre partiel si elle est réflexive, antisymétrique et transitive….

Théorème du Point Fixe de Kleene Contexte : Ordres Partiels Complets et Fonctions Continues Pour énoncer le théorème, nous avons besoin de structures mathématiques spécifiques : Ensemble Partiellement Ordonné (Poset) : Un ensemble $D$ muni d’une relation d’ordre $\sqsubseteq$ (réflexive, antisymétrique, transitive). Ensemble Dirigé : Un sous-ensemble $X \subseteq D$ est dirigé si pour toute…

Théorème de Tarski sur l’Indéfinissabilité de la Vérité Contexte : Langage Formel et Vérité Considérons un langage formel $L$ (comme le langage de l’arithmétique) capable d’exprimer des énoncés sur les nombres naturels. Un tel langage peut être interprété dans une structure, le modèle standard de l’arithmétique (l’ensemble $\mathbb{N}$ avec les opérations usuelles $+, \times$). Dans…

Théorème de la Déduction Contexte : Systèmes de Déduction En logique propositionnelle et en logique du premier ordre, un système de déduction est un ensemble de règles permettant de dériver des formules (théorèmes) à partir d’un ensemble d’axiomes. La notation $T \cup \{A\} \vdash B$ signifie qu’il existe une démonstration formelle de la formule $B$…

Théorème de Löwenheim-Skolem Contexte : Langage et Modèles Ce théorème s’applique à des théories du premier ordre. Un langage (ou une signature) est un ensemble de symboles de constantes, de fonctions et de relations. Une théorie est un ensemble d’axiomes formulés dans ce langage. Un modèle d’une théorie est une structure mathématique (un univers et…

Théorème de Cantor-Bernstein Contexte : Comparaison des Cardinalités En théorie des ensembles, pour comparer les « tailles » (cardinalités) de deux ensembles $A$ et $B$, on utilise les notions d’injection et de bijection. Dire que $|A| \le |B|$ signifie qu’il existe une injection de $A$ dans $B$ (on peut associer à chaque élément de $A$ un élément…

Théorème de Cantor Contexte : Cardinalité et Ensemble des Parties Pour comprendre le théorème de Cantor, il faut se familiariser avec deux notions de base de la théorie des ensembles : Cardinalité : La cardinalité d’un ensemble, notée $|A|$, est une mesure du « nombre d’éléments » de cet ensemble. Deux ensembles ont la même cardinalité s’il…

Second Théorème d’Incomplétude de Gödel Contexte : La Formalisation de la Consistance Le premier théorème d’incomplétude repose sur la capacité d’un système formel $T$ (suffisamment puissant) à parler de sa propre démontrabilité via la numérotation de Gödel. Le second théorème pousse cette idée plus loin en formalisant la notion de consistance. Un système $T$ est…

Premier Théorème d’Incomplétude de Gödel Contexte : Systèmes Formels et Arithmétique Pour comprendre ce théorème, il faut considérer un système formel (comme l’arithmétique de Peano ou la théorie des ensembles ZFC) qui est : Suffisamment puissant pour exprimer au minimum l’arithmétique de base (addition, multiplication sur les entiers naturels). Consistant (ou cohérent) : Il est…

Théorème de Complétude de Gödel Contexte : Logique du Premier Ordre Avant d’énoncer le théorème, il est essentiel de définir deux concepts centraux en logique du premier ordre. Soit $T$ un ensemble d’axiomes (une théorie) et $\varphi$ une formule (un énoncé). Conséquence Syntactique (Démontrabilité) : On dit que $\varphi$ est une conséquence syntaxique de $T$,…