Le chapitre 1

Le coeur des mathématiques

Le concept de proposition et d'inférence

Cette partie aura pour tâche de rappeler les concepts vus au chapitre 0 de ce cours. Pour cela, nous avons besoin de la définition des mathématiques et de la logique, que nous ne rappellerons pas ici.

En mathématiques, les informations que l'on cherche a démontrer sont formulées dans ce qui est nommé une "proposition". En effet, une proposition logique est une information quelconque, possédant une valeur de vérité (elle est soit vraie, soit fausse). En réalité, cette définition peut s'appliquer à d'autres mots, qui représentent le même objet (tournée de manière plus ou moins similaire) : assertion, énoncé, question... D'un point de vue vocabulaire, il existe pas mal de noms pour des propositions spéciales. Par exemple, une tautologie est une proposition qui est tout le temps vraie(comme la proposition "si je peux m'acheter à manger, alors j'ai de l'argent", qui est vraie dans tous les contextes). À l'inverse, une contradiction logique est une proposition logique toujours fausse(comme la proposition "si je n'ai pas accès à de l'argent, alors je peux acheter à manger", qui est fausse dans tous les contextes). Théoriquement, il est possible de considérer tout ce qui a une valeur de vérité comme une proposition.

En pratique, les propositions suivent une syntaxe assez précise, et assez claire. Pour rappel, une syntaxe représente les règles qui doivent suivre des mots (ou n'importe quel objet qu'on peut "écrire") rendant une phrase correcte. L'exemple le plus simple de syntaxe est la langue française. C'est la même chose pour les propositions (et pour tout ce qui englobe la logique), ou même les nombres. En fait, il faut comprendre que la syntaxe des propositions est très proche de la syntaxe des nombres. Par exemple, imaginez que vous travaillez sur la proposition "je suis un majeur". Vous pouvez la réécrire en entier partout, mais vous allez perdre du temps. Or, il est possible "d'enfermer" cette proposition sous la forme d'une "variable", comme avec les nombres. En d'autres termes, vous pouvez sans soucis écrire cette proposition sous la forme d'une variable "P", que vous pouvez utiliser comme si elle représenter la phrase entière :

Cependant, utiliser l'égalité en logique est peut recommander. En effet, dans notre exemple, on dit que "P" est forcément égal à la proposition "je suis majeur". Or, imaginez la proposition "Q" égal à la phrase "je remplis toutes les conditions nécessaires pour être majeur". Dans les deux cas, vous êtes majeur, mais "P" ne s'écrit pas comme "Q". Si "P" ne s'écrit pas exactement comme "Q", alors "P" n'est pas égale à "Q". Or, elles ont le même sens, on peut donc se demander si il existe un symbole remplaçant l'égalité, mais n'agissant que sur le sens de la proposition. Ce symbôle existe : il s'agit du symbôle "équivaut"(que nous ré-étudierons plus tard), et qui s'écrit comme ceci :

Des fois, ce concept de "variable" est utilisé sans expliciter précisément la valeur de la proposition P : c'est normal. En effet, il est possible d'utiliser des propositions quelconques (et non explicitement définies) grâce à ces variables. Dans ce cas, des informations sont données sur ces propositions pour travailler avec. Ne soyez donc pas surpris si des propositions nommées "A", "B" ou même "P" se baladent toutes seules, sans être explicitées.

En parlant de syntaxe, parlons d'un sujet assez important pour comprendre les énoncés : les parenthèses. En fait, les parenthèses sont utilisées en mathématiques pour indiquer qu'une certaine partie d'une énoncé (la partie entre parenthèse) doit être traitées en priorité et en un bloc. Par exemple, dans le calcul "(3 + 2) * 3", les parenthèses nous permettent de savoir qu'il faut faire le calcul "3 + 2" avant la multiplication par 3. Or, on peut se retrouver dans des cas un peu plus complexes, comme "((3 + 2) * 4 + 8) / ((7 + 8) * (2 - 4))". Dans ce cas, pour ne pas se perdre dans les parenthèses, on peut utiliser des crochets / accolades à la place de certaines paires de parenthèses dans l'énoncé. Dans ce cas, "[(3 + 2) * 4 + 8] / [(7 + 8) * (2 - 4)]" est tout à fait valide (et plus simple à écrire).

Pour trouver correctement la valeur de vérité d'une proposition, il faut s'y prendre... correctement. La façon la plus utilisée est un procédé nommé l'inférence. Une inférence est une façon de démontrer logiquement une proposition (nommée "conclusion"), en s'appuyant sur d'autres propositions appelées "prémisses". Aussi effrayante que semble être cette définition, c'est en réalité très simple, et en voici un exemple (probablement le plus connu). Nous avons deux propositions de bases : "tous les hommes sont mortels" et "Socrate est un homme". Ici, une inférence consiste à dire que "Socrate est un homme, DONC il est mortel", aussi simple que ça. Socrate est utilisé dans l'exemple car il est l'une des grandes inspirations du concept (avec entre autres Aristote, Platon...). L'écriture mathématique actuelle (simplifiée) consiste en quelque chose comme ça :

Les théories mathématiques

Plus haut dans ce cours, nous avons vu le concept de "syntaxe", cependant ce concept ne sert pas à grand chose sans son plus fidèle allié : la sémantique. La sémantique représente un moyen de donner un sens à une proposition énoncé grâce à une syntaxe. En linguistique, ce terme est particulièrement complexe, mais il est bien plus simple en mathématiques. En effet, le "sens" donner aux propositions représente tout simplement leurs valeur de vérité (vraie ou fausse). Dans ce cas, ces propositions deviennent des théorèmes. Cette définition regroupe un grand nombre de concepts : axiomes, inférences, modèle...

Pour déduire des théorèmes, il faut (comme nous l'avons vu) des propositions "de départs" nommées des axiomes. Pour rappel, les axiomes sont des propositions théoriquement indémontrées (mais qui, en pratique, sont tout à fait """"logiques""""" / évidentes, en accord avec les autres sciences et ne nécessitent pas de démonstration) qui servent de bases à toutes les mathématiques. Cependant, il existe un moyen de créer une quantité "infinie" d'axiomes, en définissant un plan pour définir cette quantité infinie d'axiome : les schémas d'axiomes. Les schémas d'axiomes sont un moyen de définir un "plan" (ou un schéma) pour créer une quantité infinie d'axiome. Cependant, une question peut se poser : pourquoi n'est-il pas possible de formuler ces fameux "schéma" sous la forme d'un seul et unique axiome ? En fait, un axiome ne peut pas utiliser directement dans sa formulation l'ensemble des propositions déduites de cette théorie. Cependant, certaines théories nécessitent que des axiomes puissent utiliser toutes ces autres propositions, démontrées avec les autres axiomes: ce concept est là pour ça. Il est à noter que ce concept est extrêmement abstrait : nous en présenterons des exemples clairs dans quelques lignes.

Maintenant, faisons un rappel sur les théories en mathématiques. Pour rappel, une théorie axiomatique est un ensemble d'axiomes, permettant de déduire / démontrer énormément de propositions (incluses dans la théorie). Avant de parler de la théorie axiomatique la plus importante (que nous présenterons dans la suite de ce cours), présentons quelques propriétés importantes sur les théories axiomatiques. Déjà, une théorie axiomatique est dite cohérente (ou consistante) si elle ne permet pas de prouver une proposition et sa négation. En logique classique, si "A" est vrai, alors il ne peut pas être faux (parfaitement évident, principe nommé "tiers exclu"). Cependant, si la théorie dit que "A" est vrai et fausse en même temps, elle est incohérente. C'est comme dire que quelqu'un est un majeur et un mineur en même temps : ça n'a pas de sens, et est impossible (et si une théorie / quelqu'un affirme le contraire, alors il est probablement fou). En général, on ne croise jamais de théorie non-cohérente, car elles sont abandonnées à la première incohérence trouvée.

En général, trouver une incohérence dans une théorie se fait en trouvant ce que l'on appelle un paradoxe. Selon l'Académie Française, un paradoxe logique est une (ou un ensemble de) proposition logique qui semble fonctionnel, mais comporte une contradiction logique (ou qui semble non-fonctionnel, mais l'est bel et bien). Cette définition s'applique à la littérature comme aux mathématiques. Un exemple assez connu est le paradoxe du fromage à trou : "plus on a de fromage avec des trous, plus il y a de trous". Or, "plus il y a de trous, moins il y a de fromages" : "plus il y a de fromage, moins il y a de fromage". La résolution de ce paradoxe peut se faire de pas mal de façons différentes, dont voici un exemple. Ici, on peut relever une contradiction : au début, on considère le vide des trous comme appartenant au fromage, alors que l'on considère le contraire au milieu du paradoxe (comme si nous ne parlions pas du même objet). Donc, la phrase "plus il y a de trous, moins il y a de fromages" est fausse, puis ce que les trous sont inclus dans ce que l'on appelle le fromage, la conclusion est donc aussi fausse. On peut tenter de ne parler que de la "partie consommable du fromage", mais la proposition devient beaucoup plus complexe, et (après étude) ne pose plus de paradoxe. De manière similaire, bien qu'une théorie puisse sembler fonctionnelle, il est parfois possible d'y trouver des incohérences. Cependant, il faut faire attention : certains objets mathématiques sont appelés paradoxe car ils donnent des résultats contre-intuitifs, en restant parfaitement justes. Ces cas précis seront listés au cas par cas.

Les différentes logiques possible

Maintenant que nous savons ce qu'est une proposition, et que nous savons déduire des propositions complexes de propositions plus simple, il ne nous reste plus qu'à savoir comment "déduire" des propositions, et donc comment utiliser des inférences. En effet, comme nous l'avons vu au chapitre 0 de ce cours, plusieurs écoles de philosophies des mathématiques existent pour "démontrer" un propos, et donc pour utiliser les inférences. Selon les auteurs (et leur "philosophie des mathématiques"), les inférences possibles entre plusieurs propriétés peuvent différer, et il est courant d'appeler les différents ensembles d'inférences possibles des "logiques différentes". Il est donc primordial de savoir avec quelle "logique" on va travailler dans la suite.

La logique des propositions / prédicats

La logique classique

Parmi toutes les "logiques" qui existent, une est assez intéressante pour comprendre comment les mathématiciens en sont arrivés là : la logique classique. Historiquement parlant, la logique classique est la première tentative de "parfaitement" formaliser la logique en mathématique au XIXème siècle. Cette logique apparaît au alentour des années 1880 grâce à un mec intelligent, et son livre "Begriffsschrift" ("L'idéographie" en français), bien que très vite rendu obsolète dans les années à venir. Dans les années 1890, le "prussien" (il est né en Prusse-Orientale) un mec intelligentpropose une logique améliorée, beaucoup plus proche de la logique actuelle.

Historiquement, ce concept a frolé la catastrophe, à cause d'un évènement mathématique majeur : la crise des fondements. En effet, la crise des fondements est une période de l'histoire des mathématiques modernes, où la façon dont les mathématiques doivent fonctionner ont fortement été remises en question. Cette crise s'ammorce sur une question précise : et si les fondements utilisées en mathématiques étaient fausses, et que tout ce qui a été déduite via ces dernières l'étaient tout autant ? Cependant cela pose problème : dans les années 1830 (quand ces questions commencent), l'humanité était déjà relativement avancée en science, donc il ne devrait pas y avoir de problèmes. Or, de multiples résultats démontrèrent que des problèmes pouvaient toujours arriver (surtout en analyse). Plus tard, dans les années 1870, différents mathématiciens comme un mec intelligentdécouvrent des paradoxes étranges (Dedeking découvre qu'il y a "la même quantité" de nombres rationnels et de nombres naturels, mais pas de bijections entre les deux). Une grande partie des ces problèmes avait lieu à cause d'une définition... douteuse du concept d'infini. Or, les mathématiciens n'ont pas d'autres choix que de travailler avec, et continuent donc d'essayer de formaliser le plus précisément possible ces ensembles. Un des outils utilisés est la théorie des ensembles (que nous étudierons plus tard), résolvant pas mal de problèmes définitionnels, si utilisée sous forme de fondement des mathématiques. Or, au début des années 1900, cette théorie des ensembles se révèlent problèmatique, et de nombreux paradoxes y sont trouvé. De multiples corrections seront proposés pour résoudre ces problèmes. Au même moment, le concept de théorie mathématique s'affine, permettant de les étudier avec plus de précisions. Beaucoup de concepts apparaissent à ce moment là : cohérence, complétude, contradiction... Ces concepts mettrons un coup de grâce aux mathématiques, surtout à cause du mathématicien un mec intelligent. En effet, il publie un 1931 un théorème admettant que, dans le cas de la théorie des ensembles, nous ne pourrons jamais être sur que cette théorie ne soit pas incohérente. En d'autres termes, la théorie des ensembles (et donc presque toutes les mathématiques modernes) sont peut être complétement fausse, et nous ne savons pas encore pourquoi / comment. C'est ça, la crise des fondements. En réaction apparaissent les courants "philosophiques" des mathématiques, certains permettant d'éviter à coup sur les problèmes (mais à perte de beaucoup de théorèmes), tandis que d'autres continuent de s'appuyer sur la théorie des ensembles (mais à risque de tout perdre si elle se révèle fausse).

En logique classique, dans un contexte donné, une proposition est soit vrai soit fausse (jamais les deux). En d'autres termes, la valeur de vérité d'une proposition peut se représenter avec seulement 1 information (vrai ou faux). Cependant, si le contexte change, la valeur de vérité de la proposition peut changer. Bien que le nombre de contexte est souvent incommensurable, la proposition est, dans chacun de ces contextes, soit vraie, soit fausse. Même si ce concept peut paraître assez évident en logique, dans des cas où une formule dépend d'autres formules, établir sa valeur de vérité en fonction de ses propositions constituantes peut-être un peu dur. Heureusement, comme, dans tous les cas, une proposition est soit vrai soit fausse, c'est aussi le cas pour n'importe quelle proposition, aussi complexe soit elle (et aussi pour ses composantes). Donc, pour une proposition quelconque composée de "n" propositions différentes, ces "n" propositions peuvent toutes être soit vrai, soit fausse, et selon leurs valeur de vérité, la proposition composée est, elle aussi, soit vrai, soit fausse. Or, il est possible de représenter intuitivement cela, grâce à ce que l'on appelle une table de vérité. Une table de vérité est un moyen de représenter les valeurs de vérités une proposition composée selon chaque valeur possibles de chacune de ses propositions composantes. Ce concept peut être très pratique pour illustrer (voir démontrer) comment une proposition complexe se comporte avec ses propositions composantes. Voici deux exemples : une où la proposition "C" est vraie si "A" et "B" le sont toutes les deux (et fausses sinon), et "F" est vrai si "A" est vraie seule ou si "B" est vraie seule (et pas les deux en même temps). Théoriquement, on peut définir des proposition avec encore plus de composantes, mais la table devient longue à écrire (nous le démontrerons plus tard, mais la table doit contenir "2 exposant n" lignes).

Travailler avec des propositions

Dans un certain sens, la "logique des propositions" est la version moderne de la "logique classique". En effet, la logique des propositions (aussi nommé "calcul des propositions") est une forme de logique étudiant les propositions et les relations entre les propositions. Cette forme de logique va nous permettre d'introduire une syntaxe très importante pour mieux comprendre la logique mathématique. Effectivement, la logique propositionnelle nous permet de lier / mettre en relation des propositions entre elles, pour faire des propositions plus complexes. Bien évidemment, elle introduit aussi la syntaxe nécessaire pour le faire.

Pour complexifier nos formules, nous allons les écrire avec des connecteurs logiques. Un connecteur logique est un moyen d'écrire une proposition complexe en coupant cette proposition en "sous-propositions", et d'analyser la proposition de départ en analysant ces sous-propositions. Je vais maintenant vous introduire aux deux connecteurs logiques les plus importants : "et" et "ou".

Je vais maintenant vous introduire aux deux connecteurs logiques les plus importants : "et" et "ou".

Le connecteur logique "et" permet de lier deux propositions en une proposition finale "P", qui n'est vrai QUE SI les deux propositions de bases ("proposition 1" ET "proposition 2") sont vraies (sinon, elle est fausse). Donnons un exemple : "je suis de nationalité française ET je suis majeur". Pour l'analyser, on peut découper cette proposition comme cela : "je suis de nationalité française" ET "je suis majeur". Dans ce cas, on peut analyser indépendamment ces deux propositions. Si les deux sont vraies, alors "je suis de nationalité française ET je suis majeur" l'est aussi. D'ailleurs, cette proposition représente la définition même d'être "citoyen français". Donc, "je suis citoyen français" est vrai si "je suis de nationalité française" ET "je suis majeur" le sont aussi. Cette exemple est assez simple, puisque la phrase de départ comporte le mot "et", cependant, il y a des cas où il faut une certaine analyse pour comprendre les propositions a tirer. D'ailleurs, une proposition qui s'écrit avec un "ET" est nommée une conjonction. Si une proposition "P" s'écrit "A et B" (avec A et B deux autres propositions quelconques), alors on peut écrire "P" sous cette forme, avec un symbôle "chapeau" (représentant le "et") :

En pratique, personne ne va vous insulter si vous écrivez "ET" à la place de ce chapeau. Sa table de vérité est :

Le connecteur logique "ou" permet de lier deux propositions en une proposition finale "P", qui n'est vrai QUE SI l'une des deux propositions de bases ("proposition 1" OU "proposition 2") est vraie, ou si les deux sont vraies (sinon, elle est fausse). Donnons un exemple : "je suis employé OU je suis patron". Pour l'analyser, on peut découper cette proposition comme cela : "je suis employé" OU "je suis patron". Comme dans notre exemple pour le "et", on peut analyser indépendamment ces deux propositions. Si l'une des deux est vraie (ou les deux sont vraies, ce qui est possible si vous êtes un auto-entrepreneur), alors "je suis employé OU je suis patron" l'est aussi. D'ailleurs, cette proposition représente la définition même d'être un "travailleur". Donc, "je suis travailleur" est vrai si "je suis employé", OU si "je suis patron", ou si je suis les deux. Encore une fois, cette exemple est assez simple, puisque la phrase de départ comporte le mot "et", cependant, il y a des cas où il faut une certaine analyse pour comprendre les propositions a tirer. D'ailleurs, une proposition qui s'écrit avec un "OU" est nommée une disjonction. Si une proposition "P" s'écrit "A ou B" (avec A et B deux autres propositions quelconques), alors on peut écrire "P" sous cette forme, avec un symbôle "chapeau" inversé (représentant le "ou") :

En pratique, comme avec le "et", personne ne va vous insulter si vous écrivez "OU" à la place de ce chapeau. D'ailleurs, demanière assez évidente, si "A et B" est vraie, alors "A ou B" est vraie (cependant, l'inverse n'est pas vraie : si "A ou B" est vraie, "A et B" ne l'est pas forcément). Sa table de vérité est :

Le principe du tiers-exclus et la négation logique

En logique classique, le "principe du tiers-exclus" est une forme d'axiome. En effet, le principe du tiers-exclu est un principe logique qui stipule que une proposition NE PEUT QU'ÊTRE vraie ou fausse, mais pas les deux en même temps. Il s'agit d'une loi logique extrêment (particulièrement) évidente : si A est vraie, alors A n'est pas fausse (wow).

Pour bien utiliser ce concept, il faut introduire un nouvel outil de langage : la négation logique d'une proposition. La négation d'une proposition A représente une autre proposition qui est égale à "A est fausse", aussi notée "pas A" ou "non A". Selon la logique que nous avons déjà vu : "A ou pas A". La négation de la proposition "A" s'écrit avec un petit symbôle :

Bien qu'elle ne soit pas très intéressante, on peut construire sa table de vérité :

Cependant, en observant cette table, on peut remarquer quelque chose d'intéressant : la table de vérité de "pas A" est la table de vérité de "A" où les V et les F ont été inversés. En fait, la négation d'une proposition quelconque a pour table de vérité la table de vérité de la proposition de départ où on inverse les V et les F (les parties vraies deviennent fausses, et les parties fausses deviennent vraies). Si on essaye de construire la table de vérité de "pas (pas P)", on remarque qu'elle est parfaitement similaire à celle de P : donc "pas (pas P)" est égal à "P". Démontrer une proposition en démontrant que sa négation est fausse (ou mène à une contradiction logique absurde) est une méthode de raisonnement nommée le raisonnement par l'absurde.

On peut donc chercher la négation du "ET" et du "OU" (démontrée juste ici) :

Avec quelques observations, on se rend compte que la négation de "A et B" est "(pas A et pas B) ou (A et pas B) ou (B et pas A)". La négation de "A ou B" est "pas (A et B)". Donc, si nous avons une proposition quelconque, on peut en déduire sa négation, et si nous démontrons la validité / fausseté de la négation, alors on obtient la fausseté / validité de la proposition de départ. Si la négation est plus simple à démontrer que la proposition de départ, alors cela peut être un bon moyen de gagner du temps.

L'implication et l'équivalence

Maintenant, je vais vous présenter deux autres connecteurs, qui, quand on les découvrent, peuvent paraître plus abstrait : l'implication et l'équivalence.

Le connecteur logique "implique" permet de lier deux propositions en une proposition finale "P", qui, si "A implique B" n'est vrai QUE SI la proposition A n'est vraie QUE QUAND la proposition B l'est aussi. À l'inverse des deux autres connecteurs, nous ne pouvons pas intervertir A et B. En général, en français, le connecteur logique "A implique B" se traduit par "si A alors B". Pour l'analyser, prenons un exemple très proche de l'exemple du "ET" : "si je suis citoyen français, je suis de nationalité française". Dans ce cas, on peut analyser indépendamment les propositions "je suis citoyen français" et "je suis de nationalité française". Bien évidemment, si vous êtes citoyen français, vous êtes de nationalité française : "je suis citoyen français" implique "je suis de nationalité française", et ceux dans tous les cas. Cependant, l'inverse ("je suis de nationalité française" implique "je suis citoyen français") est fausse : un mineur de nationalité française n'est pas un citoyen français. Dans le cas de propositions quelconques "A" et "B", si vous avez une proposition P "A implique B", alors la proposition "B implique A" (où l'on inverse le A et le B) est nommée la réciproque de P (comme nous l'avons expérimenté, elle n'a pas toujours la même valeur de vérité que P).

La table de vérité de l'implication est assez difficile à déduire. Essayons de la construire pour la proposition P stipulant "A implique B". Pour rappel, Le connecteur logique "implique" permet de lier deux propositions en une proposition finale "P", qui, si "A implique B" n'est vrai QUE SI la proposition A n'est vraie QUE QUAND la proposition B l'est aussi. Donc, si "A et B", alors P est vraie. Or, si "pas A et pas B", alors rien n'empêche P d'être vraie. Finalement, si "B et pas A" est vraie, c'est la même chose : rien n'empêche P d'être vraie. Cependant, si "A et pas B" est vraie, alors "A" est vraie quand "B" ne l'est pas : l'implication est fausse. D'ailleurs, la proposition "A et pas B" est la négation de l'implication.

L'implication se note avec une sorte de double flèche (ici, "A implique B") :

L'implication est au coeur d'une loi logique assez évidente, mais qui est une règle d'inférence primaire de la logique : le modus ponens. Le modus ponens est est une loi logique affirmant que si "A implique B" et "A" est vraie, alors "B" est vraie. Cependant, ce n'est pas la seule loi d'inférence commenceant par "modus" : on dénombre aussi le modus tollens. le modus ponens est est une loi logique affirmant que si "A implique B" et "A" est vraie, alors "B" est vraie. Historiquement parlant, ces lois font parties d'un ensemble de lois similaires, développés par les grecques dans leur étude de la logique.

Il existe un moyen de démontrer plus facilement une implication : la contraposée. La contraposée est un moyen de prouver une implication P "A implique B", en prouvant que "pas A implique pas B". En d'autres termes : si A est fausse, alors B est aussi fausse. Ce raisonnement peut être plus simple dans certains cas.

Nous avons vu l'implication dans le cas où nous ne connaissons pas le comportement de sa réciproque. Cependant, si une implication et sa réciproque sont vraies, nous avons un nouveau type de connecteur : l'équivalence. Le connecteur logique "équivaut" permet de lier deux propositions en une proposition finale "P", qui n'est vraie QUE SI les deux propositions de bases sont toutes les deux vraies ou toutes les deux fausses (elles ont l'exact même valeur de vérité). Dans ce cas, sa table de vérité est exactement la même que celle de "(A implique B) ET (B implique A)". Réciproquement, d'une équivalence, on peut en déduire ces deux implications comme vraies. On peut en déduire que, dans une équivalence, l'ordre ne change pas ("A équivaut à B" est parfaitement... équivalent à "B équivaut à A"). D'ailleurs, démontrer "A équivaut à B" revient souvent à démontrer que "(A implique B) et (B implique A)". Un exemple assez simple est encore l'exemple du "ET" : comme nous l'avons prouvé, la proposition "être de nationalité française ET être majeur" est équivalente à la proposition "être citoyen français" (sauf si les institutions ne font pas leur travail, mais cela reste rare). Une propriété très intéressante : si deux propriétés sont équivalentes, alors remplacer l'une d'elle par l'autre ne change absolument pas les valeurs de vérités, et donc ne pose aucun problème logique.

L'équivalence se note comme l'implication, avec une flèches sur les deux bords :

Travailler avec les prédicats

Pour l'instant, nous nous sommes mis d'accord sur le fait que toute proposition est soit vraie, soit fausse, et pas les deux. Cependant, imaginez une proposition "le nombre n est pair". Sa véracité dpend entièrement du nombre "n", qui est une variable : elle peut donc être vraie ou fausse selon n, ce qui, au mieux, rentre en contradiction avec la définition de proposition, et au pire pose de gros problèmes de logique. Heureusement, pour travailler avec des variables dans des propositions, on peut utiliser un autre objet : un prédicat. Un prédicat est un schéma de proposition utilisant une variable externe, qui permet d'obtenir une proposition concrète (soit vraie soit fausse) selon la valeur précise de la variable. Dans ce cas, "le nombre n est pair" est un prédicat, qui est vrai si... n est pair (2, 4, 6...).

Cependant, il est possible de transformer un prédicat en une proposition, de manière assez simple. En effet, reprenons notre prédicat d'exemple : "le nombre n est pair". Vu comme ça, nous ne pouvons pas en tirer grand chose. Cependant, il existe un objet mathématique qui va nous permettre d'en obtenir une proposition : les quantificateurs. En logique mathématique, un quantificateur est un objet mathématique utilisable pour poser le contexte d'utilisation de la variable d'un prédicat (la transformant en proposition). En fait, avec un quantificateur, on transforme le prédicat en une proposition, en changeant la façon dont le prédicat doit interpréter la variable (de telle manière que le prédicat devient une proposition). D'un point de vu purement vocabulaire, la quantification (en logique mathématique) est l'action de quantifier un prédicat quelconque. Pour bien comprendre, il nous faut voir les deux quantificateurs principaux : le quantificateur universel et le quantificateur existentiel.

Le premier quantificateur utilisé est le quantificateur universel. Le quantificateur universel transforme un prédicat en une proposition vraie si TOUTES les propositions formulables avec ce prédicat sont vraie. En d'autres termes, si la proposition constitué d'un quantificateur universel d'une variable et un prédicat est vraie, alors toutes les propositions de ce prédicat seront vraie, quelle qu'elle soit. Généralement, pour une variable "x", ce quantificateur se traduit à l'écrit sous la forme "pour tout x", "tous les x"... Dans notre exemple, on peut formuler la proposition sous cette forme : "tous les nombres n sont pairs", une proposition qui est fausse. En effet, il existe des nombres entiers "n" qui ne sont pas pair (comme 3). Cependant, la proposition "tous les nombres n admettent un élément supérieur, noté n + 1" est vraie (testez avec tous les nombres "n" que vous voulez, il y aura toujours un nombre "n + 1"). Pour un prédicat "P(n)", la proposition "pour tout n, P(n)" s'écrit comme ça (avec un "A" verticalement inversé, représentant le quantificateur universel, venant du mot allemand "alle", voulant dire "tous") :

Ici, il manque juste la mention de "nombres", que nous introduirons plus tard. Sans cette mention, il est admis que la nature du "n" dépend du contexte de la formule.

Le deuxième quantificateur utilisé est le quantificateur existentiel. Le quantificateur existentiel transforme un prédicat en une proposition vraie si il existe AU MOINS UNE proposition vraie formulable avec ce prédicat. En d'autres termes, si la proposition constitué d'un quantificateur existentiel d'une variable et un prédicat est vraie, alors il existe une (ou plusieurs) proposition de ce prédicat vraie. Généralement, pour une variable "x", ce quantificateur se traduit à l'écrit sous la forme "il existe un x tel que". Dans notre exemple, on peut formuler la proposition sous cette forme : "il existe un nombre n pair", une proposition qui est vraie. En effet, il existe au moins un (et même, une infinité) nombre entier "n" qui est pair : 2. Cependant, la proposition "il existe un nombre n admettant une partie décimale non nulle" est fausse (de manière assez évident, aucun nombre entier ne s'écrit avec des nombres après la virgule). Pour un prédicat "P(n)", la proposition "il existe un n tel que P(n)" s'écrit comme ça (avec un "E" horizontalement inversé, représentant le quantificateur existentiel) :

Même problème que pour le quantificateur universel : il manque la mention de "nombres", que nous introduirons aussi plus tard. Comme pour avant, sans cette mention, il est admis que la nature du "n" dépend du contexte de la formule.

Comme nous l'avons évoqué, il est possible de formuler la négation de propositions construites avec un quantificateur. Dans le cas du quantificateur universel, une proposition utilisant le quantificateur universel pour une variable "n" est fausse si il existe un (ou plusieurs) "n" quelconque donnant une proposition fausse. Donc :

Dans le cas du quantificateur existentiel, une proposition utilisant le quantificateur existentiel pour une variable "n" est fausse si TOUS les "n" donnent une proposition fausse. Donc :

La théorie centrale des mathématiques

La théorie des ensembles

Maintenant que nous avons les bases de la logique, nous pouvons aborder notre première théorie mathématique importante : la théorie des ensembles. La théorie des ensembles est une théorie mathématique développé à la fin du XIXème siècle, pour être utilisée comme socle des mathématiques. Son principal fondateur est le mathématicien allemand un mec intelligent, qui l'a proposé dans une suite d'articles mathématiques entre 1874 et 1900. L'idée semblait être complexe : unir toutes les mathématiques (nombres, géométries, fonctions...) sous une seule théorie. Même si, historiquement, cette théorie a mis beaucoup de temps à se faire accepter, elle a finalement réussi sa mission : presque toutes les mathématiques modernes en dépend.

Ici, un ensemble est un objet mathématique qui peut "contenir" d'autres objets (on dit que ces objets appartiennent à l'ensemble), et qui est parfaitement cohérent dans la théorie des ensembles. Cette définition se rapproche beaucoup d'une autre : celle des classes. Une classe est un objet mathématique qui peut "contenir" d'autres objets (on dit que ces objets appartiennent à l'ensemble), mais qui n'est pas forcément cohérent dans la théorie des ensembles. Ceci peut paraître assez bizarre, mais une classe peut ne pas fonctionner dans la théorie que nous allons énoncer (là où un ensemble doit obligatoire fonctionner), comme elle peut fonctionner (dans ce cas, elle est aussi un ensemble). D'ailleurs, un ensemble est une classe, mais une classe n'est pas forcément un ensemble. Nous verrons plus tard en quoi cette distinction est utile. Une façon intéressante de représenter un ensemble peut être la suivante (ici, l'ensemble des nombres impairs entre 0 et 10) :

Il existe un symbôle précis pour indiquer qu'on objet "a" appartient à un ensemble "S" :

D'ailleurs, "l'objet "a" appartient à l'ensemble "S"" est une proposition, dont la véricaté dépend de... beaucoup de choses (généralement dépendant du contexte précis de "a" ou "S"). Ce symbôle permet de faire quelque chose de très intéressant : on peut utiliser ce symbôle dans un quantificateur logique, pour spécifier qu'on objet que l'on quantifie appartient à un certain ensemble. Nous pouvons donc répondre à la question de tout à l'heure "comment spécifier que notre proposition "pour tout n, P(n)" ne fonctionne qu'avec des nombres" : on a juste à rajouter ce symbôle (on admet pour l'instant que "N" est l'ensemble des nombres entiers naturels) :

Puisque l'on parle d'ensembles, parlons d'un terme extrêment similaire : un sous-ensemble. Un sous-ensemble (ou partie) d'un ensemble A est un ensemble contenant uniquement des éléments de A (et pas plus). Il n'est pas exclu qu'un sous-ensemble contienne la totalité des éléments de A... comme ne contient aucun élément (il est défini comme étant quand même un sous-ensemble de A). Ce concept nous permet d'en introduire un autre : l'inclusion. Un ensemble est dit inclu dans un autre ensemble B lorsque que TOUS ses éléments appartiennent aussi à B. Donc, si un ensemble A est inclu dans un autre ensemble B, alors A est un sous-ensemble de B (et vice-versa, si A est un sous-ensemble de B, alors il est inclu dans B). La notation mathématique est assez similaire à celle de l'appartenance, à la différence prêt que le "U" retourné n'est pas barré. Vous trouverez aussi la définition mathématique rigoureuse du concept. Pour une traduction mathématique - français, lisez "pour tout ensemble A et B, A est inclu ou égal à B si (et seulement si) pour tous les éléments possibles, si un élément appartient à A, alors il appartient à B".

Cette notation autorise A à être égal à B : on pourrait parler de "inclu ou égal". Cependant, il existe une notation où A n'est pas égal à B, nommée "inclusion stricte", se notant avec une petite barre en dessous du "U", toujours avec la définition mathématique rigoureuse. Pour une traduction mathématique - français, lisez "pour tout ensemble A et B, A est strictement inclu dans B si (et seulement si) pour tous les éléments possibles, si un élément appartient à A, alors il appartient à B, et si il existe un élément dans B qui n'est pas dans A".

La théorie des ensembles "ZFC"

La première version de la théorie proposée par Cantor n'était pas très bien axiomatisée. Une version plus solide apparaîtra entre les années 1908 et 1920 : la théorie des ensembles "ZFC". La théorie des ensemble "ZFC" (pour Zemerlo - Fraenkel - choix) est une version axiomatisée et cohérente (pour l'instant) de la théorie des ensembles de Cantor. Comme son nom l'indique, elle a été développée par 2 mathématiciens majoritairement : un mec intelligentet un mec intelligent. Le suffixe "choix" représente un axiome précis, que l'on peut ignorer (dans ce cas, on parle de théorie des ensembles "ZF"). Présentons les premiers axiomes de cette théorie, proposés par Zemerlo entre 1889 et 1908.

Le premier axiome est l'axiome d'extensionnalité. L'axiome d'extensionnalité dit que si deux ensembles possèdent exactement les mêmes éléments, alors ils sont égaux. Dans le cas d'ensembles normaux, l'ordre des éléments n'importe pas. De manière illustré, l'axiome confirme cette égalité :

Cet axiome permet d'introduire une première manière de définir un ensemble : la définition par extension. Un ensemble est dit "défini par extension" quand il est défini par une égalité avec un ensemble dont les éléments sont explicitement indiqués. Ce nom vient du fait que c'est l'axiome d'extension qui permet d'attribuer les éléments voulus à l'ensemble. Voici quelques exemples de définitions par extension :

Il est à noter que, en général, ces ensembles sont notés entre crochets "{}", avec des éléments séparés par des virgules, ou des points virgules. De manière purement mathématique, l'axiome peut s'énoncer de plusieurs manières équivalentes. La première n'utilise que des équivalences, et la deuxième découpe la première équivalence en deux implications (généralement plus utilisé dans les démonstrations). Pour une traduction mathématique - français, lisez "pour tout ensemble A et B, A et B sont égaux si (et seulement si) tous les éléments de B sont des éléments de A, et tous les éléments de A sont des éléments de B".

Pour prouver simplement que deux ensembles sont les mêmes, il existe une technique assez puissante : la double inclusion. Deux ensembles A et B sont égaux si (et seulement si) A est "inclu ou égal" à B et B est "inclu ou égal" à A. Cette proposition se démontre assez facilement grâce à cette axiome.

Le deuxième axiome est l'axiome de l'ensemble vide. L'axiome de l'ensemble vide est un axiome garantissant l'existence d'un ensemble vide dans la théorie. Comme son nom l'indique : l'ensemble vide est un ensemble ne contenant aucun élément. Par définition, la proposition "l'élément "e" appartient à l'ensemble vide" est toujours fausse. Selon l'axiome d'extensionnalité, on en déduit qu'il n'y en a qu'un seul (démontré ici). En réalité, certains auteurs négligent cet axiome, car il peut être déduit grâce à des théorèmes beaucoup (mais alors, vraiment beaucoup) plus complexes. Cet ensemble se note ainsi :

De manière purement mathématique, cet axiome est assez simple à énoncer. Pour une traduction mathématique - français, lisez "il existe un ensemble noté [symbôle de l'ensemble vide] tel que, pour tout "x", "x" n'appartient pas à [symbôle de l'ensemble vide]".

Le troisième axiome est l'axiome de la paire. L'axiome de la paire est un axiome confirmant que, pour deux ensembles quelconques A et B, il existe un ensemble contenant deux éléments : A et B (nommée paire de A et B). Cet axiome peut paraître assez évident, mais il reste important à énumérer. Selon l'axiome d'extensionnalité, on en déduit qu'il n'y en a qu'un seul (démontré ici).

De manière purement mathématique, cet axiome est aussi assez simple à énoncer, mais un peu plus dur à traduire. Pour une traduction mathématique - français, lisez "pour tout ensemble A et B, il existe un ensemble C dont les éléments sont TOUS les éléments possibles qui sont soit A, soit B".

Le quatrième axiome est l'axiome de la réunion. L'axiome de la réunion affirme que, pour tout ensemble A dont les éléments sont des ensembles, il existe un ensemble B tel que tous ces éléments appartiennent à un sous-ensemble C de A, et tous les éléments des sous-ensembles de A appartiennt à B. Cet axiome peut paraître un peu bizarre, mais il est cependant très important dans plein de démonstrations. Par exemple, en le couplant avec l'axiome de la paire, on peut prouver qu'il existe un ensemble C tel que, pour tout ensemble A et B, C est composé de tous les éléments de A et B (et pas plus).

De manière purement mathématique, cet axiome est assez difficile à énoncer... et aussi à traduire. Pour une traduction mathématique - français, lisez "pour tout ensemble A, il existe un ensemble B dont les éléments sont TOUS les éléments possibles tel qu'il existe un ensemble C dans A tel que B appartiennent à C".

Le cinquième axiome est l'axiome de l'ensemble des parties. L'axiome de l'ensemble des parties est un axiome qui assure l'existence, pour tout ensemble A, d'un ensemble des parties de A. En théorie des ensembles, l'ensemble des parties (ou ensemble puissance) d'un ensemble E est un ensemble contenant la totalité des sous-ensembles (pas forcément ordonnés) possibles dans l'ensemble E (en incluant l'ensemble vide et E). Comme pour les autres axiomes, il peut paraître relativement évident, mais reste assez important dans la théorie. Il ne faut cependant pas oublier de lui ajouter certains sous-ensembles de A souvent oubliés : A lui même et l'ensemble vide.

De manière purement mathématique, cet axiome est assez facile à énoncer et à traduire. Pour une traduction mathématique - français, lisez "pour tout ensemble A, il existe un ensemble P dont les éléments sont TOUS les éléments possibles inclus dans A".

Le sixième axiome est l'axiome de l'infini. Cet axiome est un peu bizarre, mais infiniment important (sans mauvais jeu de mots). L'axiome de l'infini stipule qu'il existe un ensemble contenant un élément de départ nommé "0", et tel que tous les éléments "n" de cet ensemble admettent un élément précis (défini via une fonction), nommé "successeur de n" ou "successeur(n)". Les premiers éléments de cet ensemble sont "0", "successeur(0)", "successeur(successeur(0))"... En fait, cet ensemble représente exactement l'ensemble des nombres entiers naturels(qui respectent eux aussi cette exacte propriété). Dans ce cas, on peut écrire "successeur(n)" comme "n + 1" (on défini donc l'opération "a + b" comme l'utilisation de la fonction successeur "b" fois sur un nombre entier naturel "a"). Nous définirons toutes les propriétés nécessaires dans la dernière partie du chapitre. Comme pour tout nombre naturel, on peut trouver un nombre supérieur (sous la forme "n + 1"), cette ensemble admet une infinité d'éléments (d'où le nom de l'axiome).

De manière purement mathématique, cet axiome est... difficile à énoncer. En réalité, il est théoriquement possible de l'énoncer de plusieurs façons différentes. Dans notre cas, nous allons utiliser la version proposée par le mathématicien hongrois un mec intelligent. Ce mathématicien a proposé une façon assez pratique de solidement construire cette ensemble : le "0" représente l'ensemble vide, et le "successeur" comme une fonction transformant un élément "b" en un ensemble représentant l'union de l'ensemble ne contenant que "b" et de "b" lui même. Pour une traduction mathématique - français, lisez "il existe un ensemble A qui contient l'ensemble vide et dont tout élément "b" admet un "successeur" (appartenant à A) si il appartient à A".

Cette axiome nous permet de faire quelque chose de très intéressant : introduire une nouvelle forme de raisonnement. En effet, il nous permet d'introduire le raisonnement dit "par récurrence". Le raisonnement par récurrence est un principe de raisonnement permettant de prouver que si un prédicat "P(n)" est vraie pour "P(a)" et que, pour tout élément "k" d'un ensemble "N", "P(k) implique p(successeur(k))", alors "P(n)" est vraie pour tout "n" supérieur à "a". En utilisant le formalisme des nombres, on peut dire que, si "P(0)" est vraie et "P(n) implique P(n + 1)", alors "P(1)" est vraie, "P(2)" aussi, et tout "P(n)" l'est également. Ce type de raisonnement nous sera très utile dans pleins de contextes impliquant cette axiome (et donc, impliquant les nombres entiers naturels).

Le septième axiome n'est... pas un axiome à proprement parlé, mais un schéma d'axiome : le schéma d'axiome de compréhension. Le schéma d'axiome de compréhension est un schéma d'axiome construisant un axiome par propriété, stipulant que, pour tout ensemble "A", il existe une classe "B" dont tous les éléments sont les éléments de A rendant une propriété "P" vraie (déduite grâce aux autres axiomes). Ici, on défini bien "B" comme une classe, car il peut poser certains problèmes dans ZFC (que nous verrons juste après ce schéma d'axiome). Cependant, un axiome que nous définirons tout à l'heure nous permet d'affirmer que "B" est presque toujours un ensemble(ce qui est possible car un ensemble est une classe). Si aucun élément de l'ensemble ne vérifie la propriété, alors l'ensemble obtenu est l'ensemble vide. Cet axiome permet de faire quelque chose de très pratique : introduire la définition d'ensemble par compréhension. Un ensemble est dit "défini en compréhension" quand il est défini comme tous les éléments d'un autre ensemble vérifiant une propriété spécifique. Ce nom vient du fait que c'est le schéma d'axiome de compréhension qui atteste de l'existence de cette ensemble. De manière abstraite, un ensemble B défini par compréhension s'énonce comme ceci (lisez "B est l'ensemble de tous les éléments x possibles respectant la propriété P(x) (et donc, où P(x) est vraie)") :

Prenons un exemple plus concret : un ensemble A défini par extension et un ensemble B défini par compréhension. Pour définir l'axiome B comme tous les éléments de A vérifiant la propriété P "l'élément est pair", on doit utiliser une relation d'appartenance entre "x" et "A" :

De manière purement mathématique, cet axiome est moyennement complexe à énoncer et à traduire. Nous allons commencer par citer une version simplifiée, puis la version finale. Pour une traduction mathématique - français de la version simplifiée (la première), lisez "pour tout ensemble A, il existe un ensemble B tel que, pour tout élément "x" de B, "x" est un élément de A et "x" respecte la propriété "P"". Pour une traduction mathématique - français de la version complète (la seconde, où l'on introduit le fait que la propriété puisse avoir besoin de variables indépendantes), lisez "pour toute variable "v0", "v1" ... jusq'à "vn", pour tout ensemble A, il existe un ensemble B tel que, pour tout élément "x" de B, "x" est un élément de A et "x" respecte la propriété "P" à laquelle on applique les variables du début de l'axiome".

Sur cet axiome s'achève notre présentation des axiomes proposés par Zemerlo en première instance. Cependant, cette théorie est insuffisante, et admet une quantité monstrueuse de paradoxes (paradoxes de Russell, paradoxe de Richard, paradoxe de Berry...). Historiquement, le plus connue est celui de Russell. En effet, le paradoxe de Russell est un paradoxe de la théorie des ensembles proposé par Zemerlo, où Russell crée un ensemble représentant l'ensemble des ensembles n'appartenant pas à eux-mêmes (autorisé par le schéma axiome de compréhension), mais qui ne peut ni appartenir ni ne pas appartenir à lui même (ce qui pose une contradiction). Donc, cet ensemble ne peut pas exister : le schéma d'axiome de compréhension est donc incohérent. Déjà, il faut savoir que, lors de la publication originale de la théorie des ensembles, des axiomes similaires à "l'axiome de compréhension" existés déjà, et presque tous admettaient que "B" est un ensemble. Ce paradoxe démontre que, si l'axiome de compréhension permet de toujours admettre que "B" est un ensemble, alors des paradoxes logiques apparaissent.

Une version corrigée était nécessaire : c'est ce que va fraire Fraenkel. En 1922, Fraenkel publie en 1922 une version complétée de la théorie, nommée "théorie des ensembles ZF", où beaucoup de ces paradoxes sont résolues. Cette théorie modifie légèrement les axiomes que nous avons déjà vu, et rajoute un nouvel axiome et un nouveau schéma d'axiome. C'est dans ce contexte là que "B" a dû être assumé comme étant une classe, qui est très souvent (dans les mathématiques courantes) un ensemble.

L'axiome proposé par Fraenkel est l'axiome de fondation. L'axiome de fondation est un axiome obligeant tout ensemble "A" à posséder un élément qui, dans sa forme "ensemble", ne contient aucun élément de "A". Ici, quand on dit qu'un élément est sous une forme "ensemble", cela signifie que nous devons l'utiliser comme un ensemble (ce qui est, dans ZFC, toujours possible, quelque soit l'élément : nombre, espaces... mais nous verrons comment plus tard). Cet axiome peut aussi sembler un peu bizarre, mais il permet de contrer quelques-uns des paradoxes de la théorie. En effet, en l'utilisant avec l'axiome de l'ensemble des parties, on peut démontrer un résultat très important : un ensemble ne peut pas se contenir lui même, et aucun élément (sous forme d'ensemble) d'un ensemble contient ce même ensemble (ni les éléments des éléments...), démontré juste ici.

Cette axiome n'est pas très dur à énoncer, mais un peu plus à traduire. Pour une traduction mathématique - français, lisez "pour tout ensemble x, si x n'est pas vide, alors il existe un élément de y qui, dans sa forme (ensemble), ne contient aucun élément de x".

Finalement, le dernier schéma d'axiome obligatoire proposé par Fraenkel est le schéma d'axiome de remplacement. Le schéma d'axiome de remplacement est un schéma d'axiome garantissant que toute classe se comportant comme une fonction peut être restreinte à un ensemble se comportant comme une fonction (en utilisant comme antécédent un ensemble). À l'inverse des autres axiomes, celui si n'est ni simple, ni intuitif, et nous y reviendrons quand nous parlerons de la logique mathématique avancée. Cependant, il permet de résoudre beaucoup de paradoxes que nous avons vu auparavant. En effet, c'est ce schéma d'axiome qui stipule si une classe obtenue via l'axiome de compréhension est une classe ou un ensemble.

L'axiome du choix

L'axiome du choix est un axiome assez bizarre, car il n'est pas aussi utilisé que les autresn et parfois exclu de la théorie. L'axiome du choix est un axiome permettant l'existence d'un moyen d'extraire un élément quelconque d'un ensemble, une infinité de fois (et donc, dans une infinité d'ensemble), pour construire un nouvel ensemble. Pour des raisons de formalisme, l'axiome dit que tous ces ensembles doivent être défini dans un ensemble plus grand (bien que ça ne change rien au coeur du concept). Nuance importante : l'axiome permet l'existence de ce moyen, mais il n'oblige pas à l'expliciter. En général, ce moyen est une fonction (si vous ne savez pas ce que c'est, ou que vous ne savez pas bien le définir, voyez cela comme le nom que l'on donne à ce moyen). Donc, ce moyen peut être parfaitement naturel, comme totalement aléatoire (et non-explicité).

L'idée de cet axiome est de pouvoir utiliser cette fameuse "fonction", dans des cas divers et variés, et dans des ensembles infinis. Son énoncé mathématique est... assez complexe. Pour une traduction mathématique - français, lisez "pour tout ensemble X non vide, il existe une fonction f allant de X vers la réunion de tous les ensembles A appartenant à X (comme permis par l'axiome de la réunion), transformant les éléments A de X (des ensembles) en un élément quelconque de A".

Les propriétés basiques des ensembles

Les ensembles peuvent posséder un grand nombre de propriétés, souvent assez basiques.

La propriété la plus "évidente" d'un ensemble est son cardinal. Le cardinal d'un ensemble est une façon de représenter le nombre d'éléments que contient l'ensemble. Cette définition est infiniment plus simple dans le cas où l'ensemble est fini. Ici, un ensemble est "fini" si il n'est pas possible de trouver de nouveaux éléments dans l'ensemble (que nous n'avons pas déjà trouvé) après en avoir consulter une certaine quantité. Le cardinal d'un ensemble fini est un nombre (entier naturel) représentant le nombre d'éléments distincts appartenant à l'ensemble. Par exemple, le cardinal de l'ensemble {1, 3, 4, 7, 9} est 5 (il y a 5 éléments dedans). La définition rigoureuse (avec des symbôles mathématiques complexes et tout le bazard) est particulièrement complexe, et nous ne pouvons pas l'étudier pour l'instant (dans le cas des ensembles finis, nous nous contenterons de compter les éléments dans l'ensemble).

Singletons, pairs et couples

Nous allons présenté quelques mots de vocabulaire assez simple, mais très utilisé. Un singleton est ensemble fini de cardinal 1 (il ne contient qu'un seul élément). En général, ces ensembles sont presque toujours exprimé en extension (comme le singletion {5}). On peut assez facilement prouver que, pour tout élément possible, il existe (obligatoirement) un singleton contenant cet élément : utilisez l'axiome de la paire sur cet élément et l'ensemble vide, puis l'axiome de la réunion sur l'ensemble obtenu, et vous obtenez le singleton voulu. Un concept assez similaire est la paire. Une paire est ensemble fini de cardinal 2 (il ne contient que deux éléments). Dans la théorie ZFC, son existence est garantie par l'axiome de la paire, présenté plus haut.

Comme nous l'avons vu, dans un ensemble, l'ordre n'importe pas, voir n'existe pas : c'est donc le cas pour la paire. Cependant, il est possible de donner un ordre aux éléments d'une paire, grâce à un autre objet similaire : le couple. Un couple est une paire où un des deux objets doit être écrit avant l'autre (et donc, il s'agit d'une paire où il y a un ordre d'écriture des éléments). Il s'agit toujours d'un ensemble, mais défini de manière un peu différente, pour donner un ordre aux éléments. Jetons un petit coup d'oeil à ce qui différencie une paire d'un couple dans leur définition. Une paire peut simplement être écrit comme ça :

Ici, l'ordre n'a pas d'importance. Donc, nous allons devoir trouver un moyen permettant d'écrire des couples, pour rendre l'ordre important. Déjà, notons que l'écriture d'un couple se fait en remplaçant les accolades par des parenthèses. Nous allons utiliser la représentation proposé par le mathématicien polonais un mec intelligent. Dans cette proposition, un couple "C" formé d'un élément "x" puis d'un élément "y" se note :

Dans ce cas, le couple devient un ensemble contenant deux éléments : un singleton contenant le premier élément, et une paire contenant les deux éléments. On peut donc distinguer le premier élément de l'autre. On peut écrire le couple opposé, est constater (grâce à l'axiome d'extension) qu'il n'est pas égal au couple de départ (le singleton du "premier élément" n'est pas le même) :

L'obtension du premier élément se fait donc par le singleton, et l'obtension du second se fait en prenant l'élément de la paire qui n'est pas dans le singleton.

Les opérations sur les ensembles

L'union et l'intersection

L'union et l'intersection sont des opérateurs permettant de réaliser une opération logique entre deux ensembles. En effet, l'union (ou réunion) de deux ensembles A et B représente un nouvel ensemble C qui contient tous les éléments de A et de B (tous les éléments qui sont dans A ou dans B). En terme mathématique (lisez "pour tout ensemble A et B, il existe un ensemble C tel que, pour tous les éléments x possibles, x est dans C équivaut à dire que x est dans A ou B (ou les deux)") :

Les deux appellations (union et réunion) sont possibles, et désignent l'exact même chose. Son existence est assez facilement déductible, grâce à la combinaison de l'axiome de la paire et de l'axiome de la réunion. En fait, "l'union" est un opérateur, ce marquant avec une sorte de grand "U" :

C'est assez simple à illustrer.

L'intersection est un opérateur aussi simple à comprendre. L'intersection de deux ensembles A et B représente un nouvel ensemble C qui contient tous les éléments étant en même temps dans A et dans B. Il s'agit de l'union où vous remplacez le "ou" de la définition mathématique par un "et". En terme mathématique (lisez "pour tout ensemble A et B, il existe un ensemble C tel que, pour tous les éléments x possibles, x est dans C équivaut à dire que x est dans A et B") :

Si les deux ensembles ne partagent aucun élément en commun, C vaudra l'ensemble vide. Son existence demande un peu plus de réflexion, mais se déduit grâce à l'axiome de l'ensemble vide. Cet opérateur se marque avec le même symbôle que l'union à l'envers :

Il est aussi assez simple à illustrer.

Le produit cartésien

Le produit cartésien est une opération très importante pour pas mal d'autres objets mathématiques. Le produit cartésien (aussi nommé produit cartésien binaire) de deux ensembles est une opération sur deux ensembles, permettant d'obtenir un ensemble contenant tous les couples possibles entre chaque élément du premier ensemble et chaque élément du second ensemble (dans cet ordre précis). Voici un exemple assez simple : le tableau qui suit représente le produit cartésien (cases blanches) de l'ensemble {1, 2, 3, 4, 5} (cases rouges) et de l'ensemble {1, 2, 3, 4, 5} (cases bleues).

Voici un autre exemple : le tableau qui suit représente le produit cartésien (cases blanches) de l'ensemble {A, B, C, D} (cases rouges) et de l'ensemble {1, 2, 3, 4, 5} (cases bleues).

La définition mathématique pure de cet opérateur est assez simple :

Quelque soit les ensembles de départ, les utiliser via cet opérateur donne un nouvel ensemble fonctionnel (démontré ici), et heuresement, car il serait difficile de s'imaginer qu'il existe des ensembles pour lesquelles cela ne marche pas.

Les objets centraux des mathématiques

Qu'est ce qu'est une relation mathématique ?

Avant d'introduire quoi que ce soit d'autre en mathématiques, un objet extrêmement important est l'application mathématique. En mathématique, une relation est un objet permettant d'énoncer des propositions entre plusieurs éléments d'un même ensemble quelconque. Par exemple, dans un ensemble de nombres entiers naturels, la relation "inférieur" est définie, et donne une proposition juste juste pour tout "m" et "n" où... m est inférieur à n (comme "3 est inférieur à 5"). Cette définition pose un problème : il existe des objets infiniment proche de cette définition, mais qui n'en font pas partie, car pas "dans un même ensemble quelconque". C'est le cas de la relation d'appartenance "un élément a appartient à un ensemble E", où il n'existe pas vraiment "d'ensemble" généralisant en même temps le concept d'élément et d'ensemble. Pour éviter ce problème, nous allons dire que, dans ce cas précis, on ne parle pas d'ensemble, mais de classe (il existe une classe contenant tous les ensembles et éléments possibles). Pour tout le reste, la définition avec les ensembles fonctionne. Il est très fréquent (voir même, presque tout le temps appliqué) d'appeler une relation avec un simple symbôle comme "=", "<" ou "~", et de disposer les objets à lier entre eux aux côtés de la relation, comme "3 + 4 = 7". Deux éléments "a" et "b" liés par une relation "~" sont dit "en relation entre eux par la relation "~"".

Le concept de relation est donc un moyen "syntaxique" d'énoncer des proprositions facilement. Comme tout objet "syntaxique", la chose la plus importante avec ces relations est la façon dont on l'écrit, mais aussi les propriétés possibles via cette simple écriture. Commenceons par une propriété simple : l'arité. L'arité d'une relation est le nombre d'élément que la relation lie entre eux. Dans de très nombreux cas, la relation est dite binaire. Une relation est dite binaire quand elle est d'arité 2 (et donc, qu'elle lie 2 objets entre eux, comme "3 est inférieur à 7"). Cependant, avec un peu de réflexion, on peut facilement énumérer des relations d'arité aussi grande que l'on veut.

Qu'est ce qu'est une application mathématique ?

En mathématique, une application est un objet permettant de lier les éléments de deux ensembles quelconques entre eux. Ce premier ensemble se nomme généralement "ensemble de départ", et le deuxième ensemble se nomme "ensemble d'arrivée". Une chose très importante : tous les ensembles de l'ensemble de départ doivent être liés à exactement un élément de l'ensemble d'arrivée. D'un point de vue rigoureux, une application peut se représenter sous la forme d'un ensemble de couples entre un élément de l'ensemble de départ et un élément de l'ensemble d'arrivée, pour tous les éléments de l'ensemble d'arrivée. Comme tous ces couples sont des couple contenant un élément de l'ensemble de départ et un élément de l'ensemble d'arrivée, il s'agit d'un sous-ensemble du produit cartésien de l'ensemble de départ et d'arrivée (contenant, lui, tous les couples, même ceux qui ne sont pas concernés par l'application). Une façon très utilisé pour représenter ce concept est celui de diagramme sagittal, où l'on peut lier graphiquement les éléments un à un entre les deux ensembles. Voici un exemple en bas :

L'arithmétique élémentaire

Qu'est ce qu'est l'arithmétique ?

Souvent, quand vous demandez à quelqu'un sa définition des mathématiques, il est fort probable que sa définition ne soit pas celle des mathématiques générales... mais celle de l'arithmétique. En effet, l'arithmétique est la branche des mathématiques étudiant les nombres communs (entiers, rationnels et réels). Bien que cette partie n'est peut être pas la plus importante en mathématiques abstraites, il me semblait important de l'ajouter au premier cours, pour directement faire le lien "logique - nombres". De plus, elle permet de nous donner un premier objet définie "dans le marbre" pour présenter des concepts plus complexes, qui auront besoin d'une très grande rigueur.

Comme pour la théorie des ensembles, l'arithmétique a subit de nombreux remaniement pendant son histoire. Historiquement, on retrouve déjà des traces d'études précises des nombres 1000 ans avant J.C.,via les phéniciens. Plus récemment (dernier millénaire avec J.C.), les grecs se sont aussi emparés de l'affaire, avec de très grands noms : un mec intelligent, un mec intelligent, un mec intelligent...

Axiomatiquement définir les nombres entiers naturels

Historiquement, définir précisément les nombres entiers naturels n'a pas été une mince affaire. Au début (de l'histoire humaine), un nombre entier naturel représentait une quantité précise d'un certain objet, que l'on peut donc compter. Cette définition est très concrète (avec la notion d'objet à compter), bien que l'abstraction apparaitra petit à petit avec l'invention d'une notation précise pour les nombres. D'un point de vue notationnelle, les nombres ont longtemps étaient notés de manière très concrète, comme le nombre de points que représentait le nombre en question(c'est le cas des nombres hiéroglyphes égyptiens ou des os d'Ishango). Cependant, des systèmes plus abstraits utilisant des symbôles à la place de dénombrage apparaissent des l'arrivée des sumériens, avec leur système base 60, et chez les civilisations suivantes : grecques, romains... Le grecs un mec intelligentles défini comme une collection d'objets unitaire (valant 1). Dans ce cas, l'addition (et, globalement, toutes propriétés des nombres entiers naturels) est très facilement définie, en rapprochant physiquement deux collections d'objets représentant les nombres à additionner. Pendant longtemps, le nombre "zéro" n'était pas normalisé comme étant un nombre entier naturel, et son utilisation de la sorte dépend des auteurs. Cependant, l'arrivée de la logique avancée à la fin du XIXème siècle va forcer les mathématiciens à vouloir axiomatiser tout ça. Pour cela, de nombreux mathématiciens tentent des choses : un mec intelligent, un mec intelligentavec son système d'axiome précis, un mec intelligent... La célèbre théorie des ensembles ZFC (que l'on a déjà présenté plus tôt dans ce cours) offre un axiome permettant de les définir : l'axiome de l'infini. L'arrivée de la crise des fondements va bouleverser toutes ces définitions, mais cela ne va pas arrêter les mathématiciens ayant travaillé dessus.

Grâce à la théorie des ensembles ZFC, on peut axiomatiquement définir l'ensemble des nombres entiers naturels, comme étudié au collège. Pour cela, nous allons utiliser l'axiome de l'infini. Pou rappel, l'axiome de l'infini stipule qu'il existe un ensemble contenant un élément de départ nommé "0", et tel que tous les éléments "n" de cet ensemble admettent un élément précis (défini via une fonction), nommé "successeur de n" ou "successeur(n)". Donc, cet ensemble contient "successeur(0)", "successeur(successeur(0))"... En fait, cet ensemble se comporte exactement comme l'ensemble des nombres entiers naturels. En effet, on peut définir "successeur(0) = 1", "successeur(successeur(0)) = 2"... D'un point de vue vocabulaire, il est parfaitement évident que le successeur de 0 est 1, que celui de 1 est 2, que celui de 56 est 57...

Pour manipuler les nombres entiers naturels, il existe un élément de syntaxe très pratique : l'opération. Une opération est une action où, gràce à une (ou plusieurs) valeur de départ (nommée opérande), on y définit une égalité représentant une (ou plusieurs) valeurs traitées via les valeurs de départs. Cette définition est très générale, car souvent, la définition précise du mot "opération" est ambiguë. Cependant, une opération (comme "2 + 3") n'est pas une proposition, et donc pas une relation, bien qu'il soit courant de mettre en relation une opération avec un résultat juste, ou non (comme "2 + 3 = 5", qui est une relation juste). Généralement, une opération prend 1 ou 2 éléments en entrée. Les cas les plus célèbres sont l'addition et la multiplication.

L'opération la plus élémentaire entre deux nombres entiers naturels est l'addition. D'un point de vue rigoureux, une addition entre deux nombres entiers naturels représente une opération entre deux nombres entiers naturels "a" et "b", donnant comme valeur la valeur partant de "a" obtenue après la répétition de "b" fois l'objet "successeur". Cette définition est une définition un peu complexe pour parler de l'addition comme nous la connaissons tous. Elle est parfaitement équivalente au fait d'imaginer "x" et "y" objets dans sa tête, de les mettre à côté, et de compter la totalité des nombres, comme appris en petite section. Comme tout le monde le sait, elle se note avec une croix "+".

Elle fonctionne pour tous les nombres entiers naturels existant. Dans le cas où l'un des deux nombres est 0, le résultat de l'opération donne le nombre qui n'est pas 0. Pour tout nombre entier naturel, additionner deux nombres entiers naturels donnera toujours comme résultat un nombre entier naturel(démontré ici par récurrence). De plus, l'ordre de réalisation de plusieurs additions entre elles n'a pas d'importance sur le résultat final (démontré ici par récurrence) : (2 + 3) + 4 = 2 + (3 + 4) = 9 .

La deuxième opération la plus élémentaire entre deux nombres entiers naturels est la multiplication. D'un point de vue rigoureux, une multiplication entre deux nombres entiers naturels représente une opération entre deux nombres entiers naturels "a" et "b", donnant comme valeur la valeur partant de "a" obtenue après la répétition de "b" fois l'opération d'addition de "a" avec lui même. Comme tout le monde le sait, elle se note avec une croix légèrement tourner, comme un x : "*".

De plus, nous pouvons définir deux relations d'ordres précises dans l'ensemble des nombres entiers naturels : supérieur et inférieur. Un nombre entier naturel "a" est dit strictement supérieur à un nombre entier naturel "b" si nous pouvons obtenir "a" en appliquant une ou plusieurs fois la fonction successeur (en additionnant 1) à "b". Dans ce cas, "b" est dit strictement inférieur à "a". Cette définition est parfaitement équivalente au fait d'imaginer "a" et "b" objets dans sa tête, de les mettre à côté, et de dire que "a" objets représente plus d'objets que "b" objets. La relation "strictement supérieur" se note avec un chapeau tourné vers la droite, et la relation "strictement inférieur" avec un chapeau tourné vers la gauche :

Une autre relation similaire existe : supérieur ou égal et inférieur ou égal. Un nombre entier naturel "a" est dit supérieur ou égal à un nombre entier naturel "b" si "a" est supérieur à "b" ou si "a" est égal à "b". C'est pour cela que nous éviterons d'utiliser les termes supérieur ou inférieur seules : on risque de se tromper d'opérateur. La relation "supérieur ou égal" se note avec un chapeau tourné vers la droite sous ligné, et la relation "inférieur ou égal" avec un chapeau tourné vers la gauche sous ligné :

D'ailleurs, l'ensemble des nombres entiers naturels est bien ordonné par ces 4 relations.

Les ensembles dénombrables

Les ensembles dénombrables sont une catégorie d'ensembles infinis très précis. Un ensemble infini est dénombrable si il est équipotent (et donc, si il existe une bijection) à l'ensemble des nombres entiers naturels. En d'autres termes (plus simple) : un ensemble infini est dénombrable si il est possible de lister tous ses éléments, comme on listerait les nombres entiers naturels. Voici un exemple, où l'on montre que l'ensemble des nombres entiers naturel pair a le même cardinal que celui... des nombres entiers naturels.

Cette notion est utile, car la notion de "taille" d'un ensemble devient inutilisable pour des ensembles infini. Dans ce cas précis, la notion de cardinal d'un ensemble infini est utile : si un ensemble est dénombrable, on dit qu'il a le même cardinal que N. Le "cardinal de N" se note avec un symbôle assez précis : la lettre de l'alphabet hébreu "aleph", avec comme indice le nombre "0".

Ce concept donne des résultats... assez bizarre. En effet, bien que N soit inclu dans Z, il existe une bijection de N vers Z, exprimable de manière particulièrement simple.

Cette bijection est assez simple : si "n" est pair, "-1 exposant n" est positif, sinon il est négatif. Grâce à ça, on peut aller dans les positifs, comme dans les négatifs. En suite, on multiplie cette valeur par la partie entière (vers le haut) de n divisé par 2. Donc, pour un nombre impair puis pair consécutif, n divisé par 2 a la même valeur. Donc, on peut aller dans les positifs et leur attribuer une valeur, puis dans les négatifs et leur attribuer l'exact même valeur (opposé, bien évidemment). Successivement, on y attribue toutes les valeurs possibles dans Z.

De plus, N et N X N sont équipotents, et donc ont le même cardinal. Il existe une bijection assez simple à comprendre entre N et N X N : la fonction de couplage de Cantor.

Si ce concept existe, on peut en déduire le concept opposé : les ensembles infinis indénombrables. Un ensemble infini est indénombrable si il n'existe pas de surjections sur l'ensemble des nombres entiers naturels (il existe des éléments qui ne sont pas reliables à un nombre entier naturel). C'est le cas des nombres réels. Imaginez cette disposition de nombres réels, où nous les considérons dénombrables.

Nous pouvons trouver un nombre (en rouge), qui est un nombre réel. Maintenons, prenons le nombre où l'on rajoute 1 au chiffre de tous les chiffres après la virgule du nombre rouge (sans exceptions, où l'on met un "0" si l'on croise un "9"). Ce nombre est un nombre réel, il devrait donc être quelque part dans ce tableau. Or, il ne peut pas être le premier nombre : sa première décimale après la virgule est différente. Il ne peut pas être le deuxième nombre : sa deuxième décimale après la virgule est différente. Il ne peut pas être le n-ième nombre : sa n-ième décimale après la virgule est différente. Donc, il existe un nombre réel qui ne peut pas être ici : l'ensemble des réels n'est pas dénombrable. Le cardinal de l'ensemble des nombres réels est souvent noté "2 exposant aleph 0" :

En utilisant le théorème de Cantor, on peut prendre comme exemple l'ensemble des parties de N, qui est indénombrable.