Relations d'ordre
-----------------

Notion de plus petit/de plus grand :  <, >, <=, >=

Propriétés attendues :
- transitivité :
  ∀abc, a < b ∧ b < c ⟹ a < c
  ∀abc, a > b ∧ b > c ⟹ a > c
  ∀abc, a <= b ∧ b <= c ⟹ a <= c
  ∀abc, a => b ∧ b => c ⟹ a => c

- totalité :
  ∀ab ∈ ℕ, a <= b ∨ b <= a
  version adaptée à la relation stricte :
  ∀a≠b ∈ ℕ, a < b ∨ b < a

- réflexivité :
  ∀a, a <= a
  (pas valide pour <)

- anti-symétrie :
  la comparaison entre deux éléments différents ne peut se faire que
  dans un sens
  ∀ab, a <= b ∧ b <= a ⟹ a = b
  il y a une seule manière de comparer deux éléments différents

  Version stricte
  ∀ab, a < b ∧ b < a ⟹ a = b
  vraie aussi. Pourquoi ?

Notion d'ordre : relation binaire qui est
- réflexive
- anti-symétrique
- transitive
Ordre total : si on a en plus la totalité

Exemples :
(ℕ, <=)
(ensembles, ⊆)

A ⊆ A
A ⊆ B ∧ B ⊆ A ⟹ A = B
A ⊆ B ∧ B ⊆ C ⟹ A ⊆ C 

⊆ ordre.
total ?
P(ℕ) : {1} et {2} incomparables


Minimum :
- x∈A est le minimum d'un ensemble A s'il est plus petit que tous les autres
  == ∀y∈A, x <= y

Si A ⊆ ℕ, A admet-il un minimum ?
Si A ⊆ ℝ, pas de minimum à chaque fois : ]0; 1]
Si A ⊆ ℤ, pas de minimum à chaque fois : ]-infini, 0]

Si A ⊆ P(ℕ), A admet-il un minimum ? (pour l'ordre ⊆)
∅ est le minimum de P(ℕ)
Les parties de ℕ admettent-elles toutes un minimum ?
A = { {1}, {2} }
On n'a pas un élément plus petit que tous les autres

Les 'éléments' {1} et {2} sont appelés des éléments 'minimaux'

Élément minimal :
- x∈A est un élément minimal s'il est plus petit que tous les éléments
  avec lesquels il est comparable
  == ∀y∈A, y <= x ⟹ x = y
  Autrement dit : pas possible d'en trouver un plus petit

Pour un ordre total, la notion de 'minimum' suffit.
Pour un ordre non total, la notion de 'minimal' est la plus utile.

Petites propriétés :
- minimum unique (s'il existe)
- élément minimal pas unique a priori, mais devient unique si l'ordre
  est total
  un élément minimal pour un ordre total est aussi le minimum
  

Minorant de A : n'importe quel élément plus petit que tous les
éléments de A

Dans un cas où A ⊆ E, les minorants de A peuvent être pris dans E\A
(c'est-à-dire à l'extérieur de A)

Borne inférieure de A : le maximum des minorants de A.
Borne peut exister ou non, peut être dans A ou non.
- Si A admet un minimum, alors c'est aussi la borne inférieure


Quand est-ce qu'un programme ne termine pas ?

1/ Boucle infinie
  while True:
      pass

2/ (λx.xx)(λx.xx) (digression, rdv en M1)

3/ Appels récursifs infinis
  let rec f x = x * (f (x-1))

  def f(x):
      return x * f(x-1)

Notion de 'variant' (s'applique à une boucle)
- un nombre *positif* qui décroît strictement à chaque tour de boucle
Si on en trouve un, on peut justifier que le programme s'arrête, car
on ne peut pas descendre sous 0
L'ensemble des valeurs prises par le variant admet un minimum (et donc
ce minimum correspond au dernier tour)
Le variant est calculé en fonction des valeurs des variables

Équivalent pour les appels récursifs : nombre positif qui décroît
strictement à chaque appel récursif
(ne dépend plus des variables, mais des paramètres des appels)

Problème de la terminaison : indécidable.
Cela signifie :
- qu'on peut se prononcer sur des programmes particuliers
- qu'on ne peut pas avoir une technique (=algo) qui marche à coup sûr

---Digression---
Idée de preuve d'indécidabilité de l'arrêt (de la terminaison)
- supposons qu'il existe un algo A qui s'applique un un algorithme B et
  une entrée e, et qui dit s'il s'arrête ou non
  A(B, e)  répond  vrai  si B(e) s'arrête
- On définit C(B, e) : si A(B, e) dit vrai, je boucle, sinon je m'arrête
- Une fois qu'on applique C à lui-même...
----------------
Vérifications trompeuses des ordres de grandeur :
- problème de l'hydre, ou suite de Goodstein
----------------


Cette notion de variant est exprimée sur (ℕ, <=)
- nombre entier positif, avec décroissance stricte

Décroissance stricte sur (ℤ, <=) ?
- ne garantit pas l'arrêt, car décroissance vers -infini possible

Décroissance stricte sur (ℝ ∩ [0, 1], <=) ?
- ne garantit pas l'arrêt, car on peut avoir une suite décroissante
infinie (avec des pas de plus en plus petits)

Propriétés intéressantes de ℕ : on a une borne, et la décroissance est
toujours significative


Décroissance stricte sur (P(ℕ), ⊆) ?
- si décroissance du cardinal, ok car aussi décroissance dans ℕ

Cas A ⊂ B (strict) avec cardinaux égaux
[4, +infini[ ⊂ [2, +infini[

Décroissance stricte sur (parties finies de ℕ, ⊆) ?
- ok


Lien ordre/ordre strict :
<= est un ordre
< est l'ordre strict associé à <=, qu'on peut définir comme
  a < b  ssi  a <= b ∧ a ≠ b


Ordre bien fondé : ordre qui permet de définir des variants

Définition 1/
Il n'existe pas de suite infinie strictement décroissante

Définition 2/
Toute partie non vide admet un élément minimal

Exemples : (ℕ, <=), (ensembles finis, ⊆)


Construire des ordres bien fondés (en combinant des ordres bien fondés
déjà connus)


Ordres produits

(1, 2) < (3, 4) ?

1 < 3 et 2 < 4, donc comparaison composante par composante

(1, 4) < (2, 3)

Cette fois on n'a pas 1 < 2 et 4 < 3 : pas composante par composante
Mais on peut dire (1, 4) < (2, 3) si on trie d'abord avec la première
composante.

Au moins deux manières de comparer des paires (x₁, y₁) et (x₂, y₂)

1/ (x₁, y₁) <= (x₂, y₂)  ssi  x₁ <=₁ x₂ et y₁ <=₂ y₂
(ordre produit cartésien)

2/ (x₁, y₁) <= (x₂, y₂)  ssi  x₁ <₁ x₂ ou (x₁ = x₂ et y₁ <=₂ y₂)
(ordre produit lexicographique)

Ces constructions fonctionnent sur A₁ x A₂ avec (A₁, <=₁) et (A₂, <=₂)
Si <=₁ et <=₂ sont des ordres bien fondés, les produits le sont aussi.