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    QP\implies Q mais ¬Q    ¬P\neg Q\implies\neg P

# Absurde

On montre un énoncé PP en montrant que ::¬P\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 nn que l’on oublie pas de fixer

On fait l’hérédité : on montre que si P(n)P(n) est vrai, alors P(n+1)P(n+1) l’est aussi. Pour ça, il peut être utile de marquer P(n)P(n) et P(n+1)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 nn 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),,P(n)    P(n+1)P(0),P(1),\dotsc, P(n)\implies P(n+1)

Ce qui revient à faire une récurrence simple sur H(n)H(n) : “P(0),P(1),,P(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 xE,P(x)\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 xE,P(x)\forall x\in E,\mathscr{P}(x)

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

# Existence stricte

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

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

# Égalité de deux ensembles

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

# Un ensemble est inclus dans un autre

Pour prouver que EE est inclus dans FF, il faut utiliser le format suivant :

Montrons que EFE\subset F

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

Montrons que cet élément appartient à FF c’est-à-dire que cet élément vérifie P(F)\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 :

xx vérifie la propriété

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

Voir le PDF