mathdiscrete-mathematicsposet

partial order - finite set - minimal element

Prove by induction.Every partial order on a nonempty finite set at least one minimal element.

How can I solve that question ?

Solution

  • If the partial order has size 1, it is obvious.

    Assume it is true for partial orders <n, and then take a partial order (P,<) has size n.

    Pick x in P. Let P(<x) = { y in P : y<x }

    If P(<x) is empty, then x is a minimal element.

    Otherwise, P(<x) is strictly smaller than P, since x is not in P(<x). So the poset (P(<x),<) must have a minimal element, y.

    This y must be a minimal element of P since, if z<y in P, then z<x, and hence z would be in P(<x) and smaller than y, which contradicts the assumption that y was minimal in P(<x).