Lazi

essai 2, th 1

Contexte

Voir Essai 2

Énoncé

Définition locale

Soit R la relation définie sur les formules : R x y ssi on a la disjonction :

  • x et y sont calculables et ont le même résultat de calcul.
  • x et y sont incalculables.

Conclusion

R est une relation d'équivalence

Preuve

Réflexivité

Soit x une formule.
Si x est calculable, il a un résultat de calcul, donc la première condition de la disjonction est vérifiée donc R x x.
Si x est incalculable alors la deuxième condition de la disjonction est vérifiée donc R x x.

Symétrie

Toutes les conditions de la disjonction sont symétriques, donc R est symétrique.

Transitivité

Soit x,y et z tq R x y et R y z.

Si x est incalculable.

Alors y est incalculable, donc z est incalculable.
Par la symétrie, on déduit que si x, y ou z est incalculable alors x, y et z sont incalculable. Donc si x,y ou z est calculable alors x,y et z sont calculable.
Si x est calculable.
Alors x,y et z sont calculable (voir plus haut) et x et y ont le même résultat de calcul ainsi que y et z. Donc x et z ont le même résultat de calcul, donc R x z.