# Every finite partially ordered set has a minimal element - proof explanation

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.

• Well, there can't be an infinite number of distinct terms, if the set is finite, right? – fleablood Oct 8 '16 at 2:24
• @fleablood Silly question- how does it follow that our generated sequence is infinite, though? – Eric Hansen Oct 8 '16 at 2:28
• The contradiction is transitivity mean a_0 > a_1 > ... so we have both a_i = a_j and a_i > a_j. – fleablood Oct 8 '16 at 2:29
• My first thought is that if there are repeated elements, they must be consecutive. – Joseph Wood Oct 8 '16 at 2:29
• 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. – fleablood Oct 8 '16 at 2:31

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