Logo de SAASF

Le chapitre 1

Contenu

Chapitre 1 - démonstrations

Le raisonnement mathématique

La première démonstration mené sera comment la proposition "non (A et B)" peut s'écrire sous la forme "(pas A et pas B) ou (A et pas B) ou (B et pas A)".

Maintenant, démontrons que la proposition "pas (A ou B)" peut s'écrire "pas A et pas B", toujours grâce aux tables de vérités.

La théorie des ensembles

Fonctionnement de la double inclusion

Démontrons que un ensemble A et un ensemble B sont égaux si (et seulement si) A est "inclu ou égal" à B et B est "inclu ou égal" à A.

∀A∀B(A⊆B∧B⊆A⇔A=B)

Si A est "inclu ou égal" à B, alors (par définition) :

∀A∀B[A⊆B⇔∀x(x∈A⇒x∈B)]

Si B est "inclu ou égal" à A, alors (par définition) :

∀A∀B[B⊆A⇔∀x(x∈B⇒x∈A)]

Donc, si A est "inclu ou égal" à B ET B est "inclu ou égal" à A, alors :

∀A∀B{A⊆B∧B⊆A⇔[∀x(x∈A⇒x∈B)]∧[∀y(y∈B⇒y∈A)]}

Par imbrication des deux propositions, on peut obtenir la proposition suivante :

∀A∀B[A⊆B∧B⊆A⇔∀x(x∈A⇒x∈B∧x∈B⇒x∈A)]

Or, on a une double implication, doit on en déduit une équivalence :

∀A∀B[A⊆B∧B⊆A⇔∀x(x∈A⇔x∈B)]

On reconnaît l'axiome d'extensionnalité : un ensemble A et un ensemble B sont égaux si (et seulement si) A est "inclu ou égal" à B et B est "inclu ou égal" à A.

Résultats obtenus grâce à l'axiome de fondation

Démontrons qu'un ensemble ne peut pas appartenir lui même.

Prenons un ensemble quelconque bien fondé (qui respecte donc les axiomes). Il existe donc obligatoire le singleton (bien fondé) ne contenant que cet ensemble.

∀E,∃F∀y[y ∈F ⇔y =E]
F ={E}

Selon l'axiome de fondation, il existe un élément de ce singleton tel que l'intersection entre cet élément et le singleton donne l'ensemble vide. Or, il n'a qu'un seul élément : l'ensemble de départ, qui doit donc obligatoirement respecter cet axiome.

∀x[x≠∅⇒∃y(y∈x∧y∩x=∅)]
⇒∃y ∈{E},y ∩{E} =∅
⇒E ∩{E} =∅

Par définition de l'intersection, cela implique qu'il n'y a aucun élément dans "E" qui ne soit aussi dans "{E}". Cela implique qu'il n'y a pas l'élément "E" dans "E".

⇒¬[∃z ∈E,z ∈{E}]
⇒¬[∃z ∈E,z =E]
⇒¬[E ∈E]

Au final, un ensemble bien fondé ne peut pas appartenir à lui même.

Démontrons maintenant par l'absurde qu'un ensemble E ne peut pas contenir un ensemble contenant E, où dont un de ces éléments contient E (ou dont un des ces éléments contient E...). Cette démonstration est bien plus compliquée que la précédente.

Supposons qu'un ensemble E contienne lui même un ensemble contenant E, où dont un de ces éléments contienne E (ou dont un des ces éléments contienne E...).

E ∈E1,E1∈E2,E2∈E3,...,En - 1∈En,En∈E

Dans ce cas, selon l'axiome de la réunion, il est possible de découper E pour en obtenir un nouvel ensemble "B(0)" ne contenant que les éléments des éléments de E. De manière itérative, si les éléments de E contiennent des ensembles, alors on réitère l'opération pour créer l'ensemble "B(n)" jusqu'à tomber sur l'ensemble "E".

B(0) ={E1,...,éléments de E}
B(1) ={E2,...,éléments de E1}
...
B(n - 1) ={En,...,éléments de En - 1}
B(n) ={E,...,éléments de En}

Maintenant, construisons un ensemble assez complexe : l'ensemble contenant les éléments de tous les "B(n)" unis pour "n" entier naturel, que nous nommons "F".

F =B(0) ∪B(1) ∪... ∪B(n)

Ce nouvel ensemble "F" est lui aussi découpable en un ensemble des parties, contenant l'ensemble de tous les sous-ensembles possibles de F. Ce même ensemble contient le sous-ensemble de F composé de tous les ensembles permettant de passer de E à... E.

{E0,E1,E2,...,En}

Or, il n'existe pas d'élément de cet ensemble tel que l'intersection de cet ensemble et d'un de ces éléments donne l'ensemble vide (les seules intersection possible sont "E(k) inter {E}" avec k inférieur à n, qui sont égal à "E(k + 1)" si k est strictement inférieur à "n", et à... "E(0)" sinon). Donc, cet ensemble ne peux pas exister dans ce contexte. Donc, l'ensemble des parties de "F" ne peut pas le contenir. Or, si il ne le contient pas, il n'est plus l'ensemble des parties de "F", donc un ensemble des parties de "F" ne posant aucun problème ne peut pas exister. Donc, si "F" ne peut pas avoir d'ensemble des parties, il ne peut pas exister, et quelque chose qui a mené à sa construction ne fonctionne pas : E contenant lui même un ensemble contenant E, où dont un de ces éléments contienne E (ou dont un des ces éléments contient E...).

Unicité des ensembles admis par les axiomes

Démontrons qu'il n'existe qu'un seul ensemble ne contenant aucun élément : l'ensemble vide. Procédons avec une démonstration par l'absurde.
Supposons l'existence un ensemble E, étant un ensemble ne contenant aucun élément, inégal à l'ensemble vide. Si cet ensemble ne contient aucun élément, selon l'axiome d'extensionnalité, il est égal à l'ensemble vide (que nous avons défini comme impossible). Si cet ensemble contient au moins un élément, selon l'axiome d'extensionnalité, il est inégal à l'ensemble vide... mais il contient au moins un élément (que nous avons défini comme impossible).
Donc, toutes les possibilités mènent à une contradiction, E ne peut pas exister, il n'y a donc qu'un seul ensemble ne contenant aucun élément : l'ensemble vide.

Démontrons qu'il n'existe qu'un seul ensemble qui, pour tout ensemble A et B, représente la paire de A et B. Procédons avec une démonstration par l'absurde, extrêmement similaire à celle utilisée pour démontrer l'unicité de l'ensemble vide.
Supposons l'existence un ensemble E, étant un ensemble contenant la paire de A et B, inégal à l'ensemble vide. Si cet ensemble ne contient que A et B, selon l'axiome d'extensionnalité, il est égal à C (que nous avons défini comme impossible). Si cet ensemble ne contient pas que A et B, selon l'axiome d'extensionnalité, il est inégal à C... mais il ne contient pas A et B.
Donc, toutes les possibilités mènent à une contradiction, E ne peut pas exister, il n'y a donc qu'un seul ensemble ne contenant que A et B : C.

En procédant comme ceci, on peut prouver l'unicité d'énormément d'ensembles définis grâces aux axiomes :
- Singleton d'un objet "A"
- Réunion dans un ensemble "A"
- Ensemble des parties d'un ensemble "A"
- Union et intersection entre deux ensembles "A" et "B"
- Élément provenant de la fonction successeur

Résultats liés au produit cartésien

Prouvons que tout ensemble E et F donne un produit cartésien valide, grâce aux axiomes.

Créons un nouvel ensemble A, étant l'union de E et F :

A =E ∪F

On peut obtenir l'ensemble des parties de A (dont l'existence est garanti par l'axiome de l'ensemble des parties), contenant ainsi toutes les paires possibles entre un élément de E et un élément de F. Il contient aussi tous les singletons des éléments de E et F.

∀x,y,[{x ∈E ∧y ∈F} ⇒{x,y} ∈P(A)]
∀x [x ∈A ⇒{x} ∈P(A)]

De manière à ne pas se casser la tête, on peut définir l'ensemble des parties de... l'ensemble des parties de A, contenant toutes les paires définis comme les couples de Kuratowski entre tous x dans E et y dans F.

∀x,y,[{x,y} ∈P(A) ∧{x} ∈P(A) ⇒{{x},{x,y}} ∈P(P(A))]
∀x,y,{{x},{x,y}} ={{x,y},{x}} =(x,y)

Au final, tous les couples de Kuratowski possibles des éléments de E et F sont définis dans P(P(A)). Finalement, en utilisant le schéma d'axiome de séparation, on peut trouver un moyen d'extraire dans P(P(A)) tous les couples qui nous intéressent, formant le produit cartésien de E et F (ici noter C).

C ={(x,y) ∈P(P(A)),x ∈E ∧y ∈F} ⇔C =E X F

Cet ensemble existe donc pour tout ensemble E et F.

Les nombres entiers naturels

L'opération addition

Trucs à démontrer :

a +successeur(b) =successeur(a +b)
∀n,k∈N,n =k⇔successeur(n) =successeur(k)⇔n +1 =k +1

Prouvons que l'addition entre tous nombres entiers naturels donne un nombre entier naturel. Procédons par récurrence.

Posons l'hypothèse de récurrence pour tout entier naturel m, P(m) = "pour tout nombre entier naturel n, n + m est un nombre entier naturel".
Déjà, par définition de l'addition, pour tout nombre entier naturel n, n + 0 = n. Comme nous l'avons dit, n est un nombre entier naturel. Donc, P(0) est vraie.

En suite, prouvons que si P(k) avec k un nombre entier naturel quelconque, alors P(k + 1). Commençons par supposer que P(k) soit vrai.

∀n,k∈N,∃q∈N,n +k =q

Déjà, comme P(k), alors q est un nombre entier naturel. Par définition de N, successeur(k) = k + 1 est un nombre entier naturel. Comme on rajoute un "+ 1" à gauche de l'égalité, on doit en rajouter un à droite de l'égalité pour qu'elle reste juste (comme nous l'avons vu plus haut), et en faire une équivalence. Donc :

n +k =q ⇔n +k +1 =q +1 =successeur(q)

Ici, par définition de N, successeur(q) un nombre entier naturel. Nous reconnaissons donc la forme de P(k + 1). Donc, si P(k) est vraie, P(k + 1) l'est aussi.

Donc, P(0) est vraie et P(k) implique P(k + 1). Selon le principe de récurrence, P est vraie pour tout nombre entier naturel. Finalement :

∀n,k∈N,∃a∈N,n +k =a

Démontrons que, pour tout nombre entier naturel a, b et c : (a + b) + c = a + (b + c) (et donc, que les parenthèses n'ont pas d'importance). Procédons par récurrence.

Posons l'hypothèse de récurrence pour tout entier naturel c, P(c) = "pour tout nombre entier naturel a et b, (a + b) + c = a + (b + c)".
Déjà, par définition de l'addition, si c = 0, alors :

(a +b) +c =a +b
a +(b +c) =a +(b) =a +b

Donc, P(0) est vraie. Maintenant, cherchons P(1).

(a +b) +c =(a +b) +1 =successeur(a +b)
a +(b +c) =a +(b +1) =a +successeur(b) =successeur(a +b)

Donc, P(1) est vraie.

En suite, prouvons que si P(k) avec k un nombre entier naturel quelconque supérieur ou égal à 1, alors P(k + 1). Commençons par supposer que P(k) soit vrai.

∀a,b∈N,(a +b) +k =a +(b +k)

Appliquons notre équivalence vue plus haut (en rajoutant des parenthèses) :

∀a,b∈N,(a +b) +k =a +(b +k) ⇔((a +b) +k) +1 =(a +(b +k)) +1

Dans le cas de nos deux formes appliquons l'hypothèse de récurrence :

∀a,b∈N,((a +b) +k) +1 =(a +(b +k)) +1 =(a +b) +(k +1) =a +((b +k) +1)

Réappliquons-là à droite :

∀a,b∈N,(a +b) +(k +1) =a +((b +k) +1) =a +(b +(k +1))

Nous reconnaissons donc la forme de P(k + 1). Donc, si P(k) est vraie, P(k + 1) l'est aussi.

Donc, P(0) et P(1) est vraie et P(k) pour tout cas supérieur ou égal à 1 implique P(k + 1). Selon le principe de récurrence, P est vraie pour tout nombre entier naturel. Finalement :

∀a,b,c∈N,(a +b) +c =a +(b +c)