Définitions par clôture
=======================
Autrement dit : définitions par récurrence

Récurrence sur ℕ (technique de démonstration)
Définition de fonctions récursives

Ici : définition d'un ensemble par récurrence
-> ensembles particuliers :
   * propriétés : "être pair" P(n) == n est pair
     peut être vu comme un ensemble : l'ensemble des nombres vérifiant P(n)
   * relations binaires : ensemble de paires
     Relation binaire entre A et B == sous-ensemble du produit cartésien A x B
   * fonctions : relations fonctionnelles (et éventuellement totales)

Définition de l'ensemble ℕ (définition de Peano)
(a) 0 ∈ ℕ    
(b) si n ∈ ℕ, alors n+1 ∈ ℕ

Justifier que 4 ∈ ℕ
On part de 0 ∈ ℕ  (a)
On déduit 1 ∈ ℕ   (b)
On déduit 2 ∈ ℕ   (b)
On déduit 3 ∈ ℕ   (b)
Enfin on déduit 4 ∈ ℕ  (b)

Deux autres formules pour définir un ensemble E
(a) 1 ∈ E
(b) si n ∈ E alors n+2 ∈ E
L'ensemble I des nombres impairs vérifie ces formules :
           1 ∈ I, et si n impair, alors n+2 impair également
L'ensemble ℕ vérifie aussi ces formules
L'ensemble {1, 3, 5} ∪ [6, ∞[ également
Celui qui nous intéresse : le plus petit (qu'on peut obtenir en faisant
l'intersection de tous)

Définition de la suite de Fibonacci (Fₙ)
(a) F(0) = 0
(b) F(1) = 1
// (c) F(n+2) = F(n+1) + F(n)
(c) Si F(n) = a et F(n+1) = b, alors F(n+2) = a + b
Notation encore plus explicite de cette fonction comme une relation :
Définir la relation R(x, y) == F(x) = y

(a) R(0, 0)
(b) R(1, 1)
(c) Si R(n, a) et R(n+1, b), alors R(n+2, a+b)

(a) (0, 0) ∈ R
(b) (1, 1) ∈ R
(c) Si (n, a) ∈ R et (n+1, b) ∈ R, alors (n+2, a+b) ∈ R

Dérivation (justification)
(4, 3) ∈ R (c)
* (3, 2) ∈ R (c)
  ** (2, 1) ∈ R (c)
     *** (1, 1) ∈ R (b)
     *** (0, 0) ∈ R (a)
  ** (1, 1) ∈ R  (b)
* (2, 1) ∈ R (c)
  ** (1, 1) ∈ R (b)
  ** (0, 0) ∈ R (a)
  
On a justifié (3, 2) ∈ R,
c'est-à-dire "F(3) = 2" si on suppose que la relation est bien fonctionnelle.


Ingrédients d'une définition par clôture d'un ensemble E :
- des formules appelées "formules d'inférence", qui sont de la forme
  (hypothèses) ⟹ e ∈ E
  Certaines sans hypothèses : (a) et (b) pour fibonacci
  -> cas de base
  Certaines avec des hypothèses : (c) pour fibonacci
  -> cas inductifs (~ héréditaires)
E est défini comme "le plus petit ensemble vérifiant toutes les formules"

Note : dans certains cas ce n'est pas défini
(a) (¬ x ∈ E) ⟹ x ∈ E

Forme plus précise des formules d'inférence :
      ∀x₁...∀xᵢ, P₁(x₁,...,xᵢ) ∧ ... ∧ Pₙ(x₁,...,xᵢ) ⟹ e(x₁,...,xᵢ) ∈ E

Notation alternative (règle d'inférence)

         P₁     P₂     ...     Pₙ
         ------------------------
                   e ∈ E

Pour les cas de base (sans prémisses)

         ---------
           e ∈ E

Au-dessus : les hypothèses (ou prémisses)
En-dessous : la conclusion
Toutes les variables sont (implicitement) quantifiées universellement

Justifier (4, 3) ∈ R
Nouvelle présentation de la dérivation : "arbre de dérivation"
Arbre dont les sommets sont des formules (ici, de la forme (a,b) ∈ R)
Et dont les relations père/fils correspondent aux relations conclusion/prémisses

-------(b)  -------(a)
(1,1)∈R     (0,0)∈R
-------------------(c)  ----------(b)   -------(b)   -------(a)
    (2, 1) ∈ R          (1, 1) ∈ R      (1,1)∈R      (0,0)∈R
    ------------------------------      --------------------(c)
             (3, 2) ∈ R                   (2, 1) ∈ R
             ----------------------------------------(c)
                          (4, 3) ∈ R

Justifier qu'un élément n'appartient pas à l'ensemble E défini par clôture ?
e ∈ E s'il existe une dérivation de la formule e ∈ E
e ∉ E s'il n'existe pas de dérivation de la formule e ∈ E
Autrement dit : aucun arbre de dérivation ne peut produire e ∈ E

Dans le cas de Fibonacci, si on s'intéresse à
(a, b) ∈ R
On a une seule règle possible
-> si a = 0, seule règle possible (a)
-> si a = 1, seule règle possible (b)
-> si a > 1, seule règle possible (c)

      (1, x)∈R           (0, y)∈R  
      ---------------------------  (5 = x + y)
              (2, 5) ∈ R

Principe d'inversion : les formules de la forme e ∈ E (pour E défini par
clôture) ne peuvent être justifiées *que* par mes règles d'inférence.

Principe : si e ∈ E est vraie, alors cette formule a été déduite de l'une des
règles d'inférence, et donc les prémisses de cette règle sont vraies.
(mais on ne sait pas toujours à coup sûr quelle est la règle concernée)



Principe de récurrence (ou principe d'induction)

L'ensemble E défini par des formules d'inférence φ₁ à φₙ est le plus petit
ensemble vérifiant toutes les formules
(c'est-à-dire le plus petit ensemble tel que
* φ₁(E) est vraie
  .... et
* φₙ(E) est vraie

Tout ensemble F tel que φ₁(F) ... φₙ(F) sont vraies contient E
E ⊆ F ?
∀x∈E, x∈F
∀x, x∈E ⟹ x∈F

Pour tout ensemble F,
Si φ₁(F) et φ₂(F) et ... et φₙ(F),
alors ∀x∈E, x∈F

Pour toute propriété P,
Si P(0)
et ∀n, P(n) ⟹ P(n+1)
alors ∀x∈ℕ, P(x)

Si on a un ensemble E, défini par clôture avec les règles d'inférence φᵢ
On en déduit un principe de récurrence (ou principe d'induction)
qui permet de démontrer des propriétés vraies pour tous les éléments de E,
principe qui est lié aux règles φᵢ

Pour toute propriété P,
Si φ₁(P) est vraie
et ...
et φₙ(P) est vraie
alors
∀e∈E, P(e)

Préciser la notation : φᵢ(P) == la formule φᵢ dans laquelle j'ai remplacé toutes
les occurences de E par P (ou toutes les occurrences de x∈E, par P(x))


Définition des entiers pairs par deux règles d'inférence
- 0 ∈ Pair
- ∀n, n∈Pair ⟹ n+2∈Pair

Principe de récurrence associé :
Soit P une propriété telle que :
- P(0)
- ∀n, P(n) ⟹ P(n+2)
Alors
∀n, n∈Pair ⟹ P(n)


Groupes A1 et 2 ==> Robin https://discord.gg/YyQc9w
Groupes A5 et 2bis ==> avec moi, ici
Demain, Groupes 3 et 4 ==> avec Nicolas, on vous précise les modalités


==============================================
Exercice 1

1. Toute personne dans P a exactement deux parents

∀x∈P, ∃y∈P, ∃z∈P, y ≠ z
                  ∧ parent(y,x)
                  ∧ parent(z,x)
                  ∧ (∀w∈P, parent(w, x) ⟹ w=y ∨ w=z)

2. Définir la relation "ascendant" (parents, parents de parents de parents ...)

Cas de base : les parents sont des ascendants
∀xy∈P, parent(x,y) ⟹ ascendant(x,y)

   parent(x,y)
----------------
 ascendant(x,y)

Cas héréditaire : parent d'un ascendant

∀xyz∈P, parent(z,y) ∧ ascendant(y,x) ⟹ ascendant(z,x)

parent(z,y)     ascendant(y,x)
------------------------------
        ascendant(z,x)

3/4. Fratries et cousinades

∀xy∈P, (∃z∈P parent(z,x) ∧ parent(z,y)) ⟹ fratrie(x,y)
∀xyz∈P, (parent(z,x) ∧ parent(z,y)) ⟹ fratrie(x,y)

(∃x.A) ⟹ B   ~   (¬∃x.A) ∨ B   ~   ∀x.(¬A) ∨ B   ~   ∀x.(A ⟹ B)

parent(z,x)    parent(z,y)
--------------------------
      fratrie(x,y)

Cousins : enfants de personnes de la même fratrie

∀xy∈P, (∃z₁z₂∈P parent(z₁,x) ∧ parent(z₂,y) ∧ fratrie(z₁,z₂)) ⟹ cousin(x,y)
∀xyz₁z₂∈P, (parent(z₁,x) ∧ parent(z₂,y) ∧ fratrie(z₁,z₂)) ⟹ cousin(x,y)

parent(z₁,x)     parent(z₂,y)    fratrie(z₁,z₂)
-----------------------------------------------
                cousin(x,y)

Cousin au sens large : un ascendant commun


======================================
Exercice 2.

Traduction des règles d'inférence en formules
(a)  N₂(0)
(b)  N₂(1)
(c)  ∀x, N₂(x) ⟹ N₂(x+2)

1. Dérivations de N₂(4) et N₂(5)

-------(a)
 N₂(0)
-------(c)
 N₂(2)
-------(c)
 N₂(4)


-------(a)
 N₂(1)
-------(c)
 N₂(3)
-------(c)
 N₂(5)

2. ∀x∈ℕ, N₂(x)

Tentative par récurrence sur ℕ
- Cas de base : N₂(0), ok, justifié par (a)
- Hérédité : Soit n tel que N₂(n), on veut justifier N₂(n+1)
  Problème : on a besoin de N₂(n-1)

Possible avec la récurrence forte, ou en prenant la proposition plus générale
N₂(x) ∧ N₂(x+1)

3. Schéma de preuve par induction lié à N₂

Soit une propriété P,
Si
  (a)  P(0)
  (b)  P(1)
  (c)  ∀x, P(x) ⟹ P(x+2)
alors
  ∀x, N₂(x) ⟹ P(x)

En combinant avec la question 2, on obtient une nouvelle manière de faire une
récurrence sur les entiers.

Soit une propriété P,
Si
  (a)  P(0)
  (b)  P(1)
  (c)  ∀x, P(x) ⟹ P(x+2)
alors
  ∀x∈ℕ, P(x)


4. Étude d'une fonction récursive p:ℕ⟶bool fonctionnant par pas de 2

∀x∈ℕ, si p(x) = true alors x est pair

On pose P(x)  ~  "si p(x) = true alors x est pair"
              ~   p(x) = true  ⟹  x pair

Démonstration avec le principe de récurrence de N₂

On doit justifier (a), (b), et (c), pour le P qui vient d'être défini

(a)   P(0)  ~  p(0) = true ⟹ 0 pair       Vraie car 0 pair
(b)   P(1)  ~  p(1) = true ⟹ 1 pair       Vraie car p(1) = false ≠ true
(c)   Soit x tel que P(x) est vraie
                     p(x) = true ⟹ x pair
                     p(x) = false  ∨  x pair

      Objectif : P(x+2)
                 p(x+2) = true ⟹ x+2 pair
                 p(x+2) = false ∨ x+2 pair

p(x+2) = p(x)
Si p(x+2) = false, propriété P(x+2) vraie
Si p(x+2) = true, alors p(x) = true,
   donc x est pair par hypothèse d'induction / de récurrence
   d'où x+2 pair, et P(x+2) vraie


==========================================
Exercice 3.

1. Définir la relation "être lié à"

ami(x,y)            ami(x,z)    lié(z,y)
--------(a)         --------------------(b)
lié(x,y)                  lié(x,y)

2. Principe d'induction

Soit P(x) telle que ...(les mêmes formules qui définissent E)... alors ∀x∈E,P(x)

Soit P(x,y) une propriété (qui concerne une paire de personnes)
telle que
(a) ∀xy, ami(x,y) ⟹ P(x,y)
(b) ∀xyz, (ami(z,x) ∧ P(z,y)) ⟹ P(x,y)
Alors
    ∀xy∈P, lié(x,y) ⟹ P(x,y)


Alternativement
(b') ∀xyz, (ami(x,z) ∧ P(z,y)) ⟹ P(x,y)
en appliquant la symétrie supposée pour ami.

3.a)  ∀xyz, ami(x,z) ⟹ lié(z,y) ⟹ lié(x,y)
   ~  ∀xyz, (ami(x,z) ∧ lié(z,y)) ⟹ lié(x,y)
   C'est exactement la formule (b)

3.b)  ∀xyz, lié(x,z) ⟹ ami(z,y) ⟹ lié(x,y)
   ~  ∀xyz, (lié(x,z) ∧ ami(z,y)) ⟹ lié(x,y)

On voudrait faire une récurrence
x ------------------lié------------------- z ---ami--- y
On découpe petit à petit lié(x,z)
x --------------lié---------- z' ---ami--- z ---ami--- y
x --------------lié---------- z' ---ami--- z ---lié--- y
x --------------lié---------- z' ---------lié--------- y

   ~  ∀xyz, (lié(x,z) ∧ ami(z,y)) ⟹ lié(x,y)
   ~  ∀ab,  Q(a,b)

A ⟹ (B ⟹ C)   ~   (A ∧ B) ⟹ C

Formules Q qui pourraient marcher (syntaxiquement)
- Q(a,b)  ~  ∀z, lié(a,z) ⟹ (ami(z,b) ⟹ lié(a,b))
- Q(a,b)  ~  ∀y, lié(a,b) ⟹ (ami(b,y) ⟹ lié(a,y))
- Q(a,b)  ~  ∀x, lié(x,a) ⟹ (ami(a,b) ⟹ lié(x,b))

Pour le mettre sous la forme ∀ab∈P, lié(a,b) ⟹ P(a,b)

∀ab, lié(a,b) ⟹ (∀y, ami(b,y) ⟹ lié(a,y))

On définit P(a,b)  ~  ∀y, ami(b,y) ⟹ lié(a,y)

Avec ce P on a bien équivalence entre
   ∀ab∈P, lié(a,b) ⟹ P(a,b)
   (la conclusion qu'on peut espérer obtenir en réussissant notre preuve
    par récurrence)
et
   ∀xyz, lié(x,z) ⟹ ami(z,y) ⟹ lié(x,y)
   (notre objectif)

Donc, preuve par récurrence pour P

(a) ∀xy, ami(x,y) ⟹ P(x,y)

Soit a et b tels que ami(a,b)
(On veut démontrer P(a,b))
Soit y tel que ami(b,y)
(On veut démontrer lié(a,y))

               ami(b,y)
               --------(a)
ami(a,b)       lié(b,y)
-----------------------(b)
        lié(a,y)


(b') ∀xyz, (ami(x,z) ∧ P(z,y)) ⟹ P(x,y)
Rappel    P(a,b)  ~  ∀y, ami(b,y) ⟹ lié(a,y)

Soient x, y et z tels que ami(x,z) et P(z,y) 
                                      ∀w, ami(y,w) ⟹ lié(z,w)
(on veut démontrer P(x,y) ~ ∀v, ami(y,v) ⟹ lié(x,v))
Soit v tel ue ami(y,v)
(on veut démontrer lié(x,v))

Nos hypothèses :
(1) ami(x,z)
(2) ∀w, ami(y,w) ⟹ lié(z,w)  (hypothèse de récurrence)
(3) ami(y,v)
Objectif
lié(x,v)

On combine (3) et (2) (avec w = v) pour obtenir lié(z,v)
Ensuite ami(x,z) et lié(z,v) donnent lié(x,v) avec la règle (b)


4. Symétrie de lié
∀xy, lié(x,y) ⟹ lié(y,x)