CODEWITHSUNDEEP
mathdiscrete-mathematicsposet
user478571
user478571

Reputation:

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 ?

Upvotes: 0

Views: 1635

Answers (2)

Thomas Andrews
Thomas Andrews

Reputation: 1597

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).

Upvotes: 0

Xodarap
Xodarap

Reputation: 11849

It is trivially true if there is only one element in the poset. Now suppose it is true for all sets of size < n. Compare the nth element to the minimal element of the (n-1) poset, which we know to exist. It will either be the new minimal or not or incomparable. It doesn't matter either way. (Why?)

Upvotes: 2

Related Questions