Méthodes de démonstrations

Ce document présente des méthodes usuelles qui peuvent être utiles dans des démonstrations courantes.

# Contraposé

Si on a du mal à démontrer une propriété, on peut essayer de démontrer sa contraposée

C’est-à-dire ne pas démontrer $P\implies Q$ mais $\neg Q\implies\neg P$

# Absurde

On montre un énoncé $P$ en montrant que ::$\neg P$ aboutit à une contradiction

# Récurrence

# Récurrence simple

On initialise la démonstration avec le plus petit entier possible du domaine de définition de $n$ que l’on oublie pas de fixer

On fait l’hérédité : on montre que si $P(n)$ est vrai, alors $P(n+1)$ l’est aussi. Pour ça, il peut être utile de marquer $P(n)$ et $P(n+1)$ côte à côte et chercher comment faire le lien entre les deux.

On peut conclure en exhibant les cas qu’on avait éventuellement exclus de l’ensemble de définition de $n$ et avec une petite phrase.

# Récurrence forte

C’est le même principe que la récurrence sauf que l’on a plusieurs hypothèses de récurrence.

On cherche donc à montrer que $P(0),P(1),\dotsc, P(n)\implies P(n+1)$

Ce qui revient à faire une récurrence simple sur $H(n)$ : “$P(0),P(1),\dotsc, P(n)$”

# Analyse-synthèse

• Phase d’analyse :: on cherche à trouver la forme de ce que l’on cherche

• Phase de synthèse :: on part de la forme trouvée et on regarde si ça marche

# Disjonction

Disjonction :: on examine tous les cas possibles pour montrer que la propriété est vraie

# Existence

# Existence simple

Pour prouver un énoncé du type $\exists x\in E,\mathscr{P}(x)$, on peut :

• Utiliser un exemple
• Utiliser un théorème d’existence

# Existence large

Pour prouver un énoncé du type $\forall x\in E,\mathscr{P}(x)$

• On fixe $x\in E$
• On essaye de montrer $\mathscr{P}(x)$

# Existence stricte

Pour prouver un énoncé du type $\exists!x\in E,\mathscr{P}(x)$

• On prouve $\exists x\in E,\mathscr{P}(x)$
• On prouve l’unicité d’un tel $x$

# Égalité de deux ensembles

Pour prouver que deux ensembles sont égaux, on peut montrer que l’ensemble $A$ est inclus dans l’ensemble $B$ et vice-versa.

# Un ensemble est inclus dans un autre

Pour prouver que $E$ est inclus dans $F$, il faut utiliser le format suivant :

Montrons que $E\subset F$

Prenons donc un élément de $E$ c’est-à-dire définition de l'élément

Montrons que cet élément appartient à $F$ c’est-à-dire que cet élément vérifie $\mathscr{P}\left(\text{F}\right)$

# Unicité

Pour montrer l’unicité d’une solution on peut montrer que :: si l’on essaye de chercher une autre variable aboutissant à la vérification de la propriété, on retrouvera forcément la même variable :

$x$ vérifie la propriété

Soit $y$ vérifiant aussi la propriété, alors $y=x$

Voir le PDF