La Logique, elle, étudie le langage mathématique et cherche à le ramener à un petit nombre de signes et à codifier totalement son utilisation. Si on ajoute le signe "appartient" aux signes de base: non, et, ou, =>, <=>, "quel que soit", "il existe", ainsi qu'aux signes =,(, ), et à quelques signes de variables: x, y, z, t, u, v, w, on obtient un ensemble de 18 signes suffisant pour développer une théorie aussi puissante que les mathématiques, la théorie ZF.

Donc un cours de logique comporte, pour chaque choix des signes de base, une théorie des formules définissant correctement ce que l'on peut appeler "formule", une théorie de la satisfaction définissant le fait qu'un ensemble concret doté de différentes entités (appelé structure) est bien en accord avec une formule donnée, autrement dit la satisfait, et des règles de passage imitant celles connues en mathématiques . On pourrait bien-sur définir la signification d'une formule comme étant une certaine affirmation générale, mais on préfère plutot raisonner à partir d'une structure.

Par ailleurs, les règles de base ne suffisent pas pour pouvoir démontrer de nombreuses formules, et il faut en plus de ces règles des axiomes formant ce qu'on appelle une théorie (Théorie des groupes, Théorie des corps, Théorie d'un ordre total dense sans premier ni dernier élément, Théorie PA des entiers, Théorie ZF,...)

Grace à sa formalisation du langage mathématique la Logique est en mesure de se poser de nombreuses questions nouvelles auxquelles on n'avait pas accès. Beaucoup de ses conclusions ont de quoi surprendre. Nous allons en citer quelques-unes.

THEOREME de compacité: Soit T une théorie infinie, c'est à dire comportant un nombre infini d'axiomes. Alors, si toute sous-théorie finie extraite de T est cohérente, T est elle mème cohérente.
Démonstration: Une théorie cohérente est une théorie qui ne peut pas conduire à une formule comme: F et (non F). Supposons alors que toute sous-théorie de T soit cohérente. Si T conduit à F et (non F), cette démonstration est de longueur finie et utilise en fait un nombre fini d'axiomes de T. Soit alors T0 la sous-théorie de T composée de ces axiomes en nombre fini. Cette sous-théorie conduit, elle aussi, à F et (non F), par la mème démonstration puisque celle-ci ne fait appel qu'aux axiomes de T0. Donc T0 est incohérente, ce qui est contraire à l'hypothèse. Donc T est cohérente.

THEOREME de complétude (énoncé originel): Si tout modèle de la théorie T satisfait la formule F, alors T permet de montrer F.
THEOREME de complétude (énoncé usuel): Toute théorie cohérente a au moins un modèle.

Signalons le fait suivant: une théorie cohérente ayant un modèle infini a alors des modèles de tout cardinal (c'est à dire de toute taille). Donc une théorie ne peut jamais décrire un modèle unique.
Signalons le fait suivant, dont la démonstration est très difficile: La théorie ZF, bien que très puissante, ne permet de démontrer ni AC ni sa négation (AC étant l'axiome du choix qui dit que, pour un ensemble non vide E, il existe une application ou fonction de l'ensemble des parties non vides de E dans E telle que le transformé de toute partie soit dans cette partie). Pour construire les mathématiques, il est donc très utile d'adjoindre à ZF l'axiome AC.

Démonstration du théorème de complétude : voici quelques indications ( Le nom du théorème est sans rapport direct avec la définition suivante: une théorie T est complète si elle permet de trancher de toute question, autrement dit si pour toute formule F la théorie T permet de démontrer F ou permet de démontrer non F. Le théorème, lui, dit que ce qui est vrai dans tous les modèles de T est démontrable depuis T. Ainsi toute théorie T parait "complète" au regard de ce qui est vrai dans tous ses modèles).
Notons que le second énoncé implique le premier. En effet, supposons le second énoncé vrai, et soit F une formule satisfaite dans tous les modèles d'une théorie T que nous supposons cohérente. Alors la théorie T + non F, obtenue en adjoignant la formule non F à T, n'a aucun modèle car sinon ce modèle serait modèle de T, donc de F, et satisferait donc F et non F, ce qui est impossible. Donc T + non F n'est pas une théorie cohérente puisque toute théorie cohérente a un modèle. Finalement, comme T + non F conduit à une absurdité, le raisonnement par l'absurde (admis en logique) mène de T à non(non F), c'est à dire à F. Ainsi T permet de démontrer F, et le premier énoncé est démontré.
Maintenant, soit T une théorie cohérente. Nous allons construire un modèle pour T. Pour cela, pour chaque formule "Il existe x tel que F(x)" appartenant ou non à la théorie T, ajoutons à la théorie T la formule: "Il existe x tel que F(x) =>F(c)", ou c est un signe non encore utilisé. Le problème est de savoir si T + cet axiome est encore cohérente. C'est intuitivement facile à admettre, puisque si un x vérifie F(x) on doit pouvoir le désigner par un signe comme c ! Par ailleurs, si T + l'axiome n'était plus cohérente alors T permettrait de démontrer la négation de cet axiome, équivalente à "il existe x tel que F(x) et non F(c)". Comme T pourrait démontrer ainsi non F(c) pour un c inconnu, elle pourrait démontrer "Quel que soit x non F(x)", qui est contraire à "Il existe x tel que F(x)", donc T serait incohérente, d'ou une absurdité.
Ayant obtenu une théorie cohérente T + l'axiome ajouté, nous pouvons recommencer en ajoutant encore un axiome semblable pour chaque formule en "Il existe". La théorie qui inclut toutes ces théories est, elle aussi, cohérente. Il faut alors la compléter systématiquement en passant en revue toutes les formules et en lui ajoutant celles qui ne lui sont pas contraires . La théorie T* ainsi obtenue est ce que l'on peut appeler une théorie cohérente maximale complète. Appelons C l'ensemble des objets c retenus comme constantes ci-dessus, et décidons pour toute relation R du langage de définir une relation R sur C par imitation. On aura, sur C, ci R cj si la formule ci R cj appartient à T*. On peut alors montrer que C est modèle de T*, donc de T.