essai 2, th 1
Contexte
É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.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.
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.