1
$\begingroup$

I was reading over some lecture notes from a combinatorics class at Harvard here, in particular Lemma 7 (bold emphasis mine):

Let $A$ be a finite partially ordered set. If $A$ is nonempty, then $A$ has at least one minimal element.

Proof. Since $A$ is nonempty, we can choose an element $a_{0} \in A$. If $A$ is minimal, then we are done. Otherwise, there exists an element $a_{1}$ such that $a_{1} \leq a_{0}$ and $a_{1} \neq a_{0}$. If $a_{1}$ is minimal, then we are done. Otherwise, we can choose an element $a_{2}$ such that $a_{2} \leq a_{1}$ and $a_{2} \neq a_{1}$. Proceeding in this way, we produce a sequence $$ a_{0} \geq a_{1} \geq a_{2} \geq \cdots $$ Since ${A}$ is finite, this sequence must have some repeated terms: that is, we must have $a_{i} = a_{j}$ for some $j \neq i$. WLOG we may assume that $j > i$. Then $a_{i} = a_{j} \leq a_{i+1}$ and $a_{i+1} \leq a_{i}$. Using antisymmetry, we deduce that $a_{i+1} = a_{i}$, which contradicts our choice of $a_{i+1}$. $$ \square$$

What I've marked in bold is the part of the proof I don't understand in particular. It is clear to me how the sequence $a_{0} \geq a_{1} \geq a_{2} \geq \cdots$ is formed as well as the motivation behind it, but I cannot understand what the purpose is (or how even it follows) that this sequence shall have some repeated terms. Furthermore, assuming that we know our sequence has some repeated terms, what is the contradiction afterwards proving? (I can understand how the contradiction is constructed)

It may just be a nuance or wording but I'm having a really hard time following the last few lines here.

$\endgroup$
  • $\begingroup$ Well, there can't be an infinite number of distinct terms, if the set is finite, right? $\endgroup$ – fleablood Oct 8 '16 at 2:24
  • $\begingroup$ @fleablood Silly question- how does it follow that our generated sequence is infinite, though? $\endgroup$ – Eric Hansen Oct 8 '16 at 2:28
  • $\begingroup$ The contradiction is transitivity mean a_0 > a_1 > ... so we have both a_i = a_j and a_i > a_j. $\endgroup$ – fleablood Oct 8 '16 at 2:29
  • $\begingroup$ My first thought is that if there are repeated elements, they must be consecutive. $\endgroup$ – Joseph Wood Oct 8 '16 at 2:29
  • $\begingroup$ If it is finite, the last term is minimal, and we are done. If it's infinite we get the contradiction so it can't be infinite. But we must show the contradiction occurs. $\endgroup$ – fleablood Oct 8 '16 at 2:31
1
$\begingroup$

I think the best answer is what fleablood wrote in your comment box. I'll just add that if it's infinite, transitivity will make there exist two elements a,b in the chain with a$\leq$b and b$\leq$a, which implies that a=b.

Here is a simpler way to think about it though: If the decreasing chain never ends, then the cardinality of the chain will quickly exceed the cardinality of the poset, which is not possible.

You could also use the minimals version of zorn's lemma which would be cool, but almost pointless, because in proving that every chain is bounded below, you essentially use the exact same argument as they did in your proof; that any chain must be finite, because any infinitely decreasing sequence in P collapses into a finite chain since two elements will be bound to repeat because P is finite (you can also use the cardinality argument to do it though, if that's easier for you).

$\endgroup$
0
$\begingroup$

You could prove this by induction on the cardinality of the set. The claim is true if your set has exactly one element. Suppose the claim is true for a set of $N$ elements, and consider one with $N+1$ elements. Pick an element in your set, say $p$. If $p$ is not comparable to any element of your poset, then you can remove it, and by inductive hypothesis there is a minimal element in the remaining poset. If $p$ is comparable to some other $q$, you either have $p>q$ or $p<q$. In the first case, remove $p$, and apply the inductive hypothesis, in the second case remove $q$, and do the same.

$\endgroup$

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.