ordre partiel - ensemble fini - élément minimal

Question

prouver par induction .Chaque d'ordre partiel sur unfini non vide ensemble au moins un élément minimal.

Comment I résoudre cette question?

Answer 1

Si l'ordre partiel a la taille 1, c'est évident. Supposons que cela soit vrai pour les ordres partiels <n, puis que la commande partielle (P,<) ait la taille n.

Sélectionnez x dans P. Laisser P(<x) = { y in P : y<x }

Si P(<x) est vide, alors x est un élément minimal.

Sinon, P(<x) est strictement inférieur à P, car x n'est pas dans P(<x). Donc le poset (P(<x),<) doit avoir un élément minimal, y.

Ce y doit être un élément minimal de P puisque, si z<y dans P, puis z<x, et donc z serait en P(<x) et plus petit que y, ce qui contredit l'hypothèse selon laquelle y était minime dans P(<x).

Answer 2

Il est trivialement vrai s'il n'y a qu'un seul élément dans le poset. Supposons maintenant que cela soit vrai pour tous les ensembles de taille < n. Comparez le nième élément à l'élément minimal du poset (n-1), que nous savons exister. Ce sera soit le nouveau minimal ou pas ou incomparable. Cela n'a pas d'importance. (Pourquoi?)