0
$\begingroup$

Let $(A,\sqsubseteq)$ be a partially ordered set and $\emptyset\neq B\subset A$ a finite subset. Does $B$ have a minimal element (with repect to to $\sqsubseteq$)?

I want to prove this by induction, but I get stuck at the induction hypotheses. Is this the easiest ways to prove this, or is there another way?

$\endgroup$
1
$\begingroup$

If there's one element, then you're done: it is a minimal element.

Suppose the proposition holds for $n \geq 1$ elements.

Given a finite subset of $n+1$ elements, first order any $n$ of them to find a minimal element, i.e., apply the Induction Hypothesis to $n$ of them. Then compare the element you've found to the last element in the subset of $n+1$ elements; this will give you a minimal element, though you may wish to write out a few more details in this regard.

Then the proposition holds for any finite subset by the Principle of Mathematical Induction.

$\endgroup$
  • $\begingroup$ You do not necessarily have a smallest element (that is, an element smaller than all the others), all you can claim is that there are minimal elements (that is, with no elements strictly smaller). To fix the argument: Given $n+1$ elements, pick $n$. By induction, that set has a minimal element (not necessarily a smallest). Now consider the set consisting of that minimal element $a$, and the remaining ($n+1$-st) element. If either is smaller than the other, it is then minimal for the whole set of $n+1$ elements. If neither is smaller than the other, then $a$ is minimal. $\endgroup$ – Andrés E. Caicedo Sep 28 '13 at 17:30
  • $\begingroup$ Right: I will change the word "smallest" to "minimal"; thanks for pointing out the distinction. $\endgroup$ – Benjamin Dickman Sep 28 '13 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.