The proof goes as follows:
Proof. Let $R$ be a partial order on a set, $A$. For any element, $a ∈ A$, let $g(a)$ be the set of elements “less than or equal to $a$”, that is, $g(a)::=R\{a\}\cup\{a\}$.
Now if $bRa$, then transitivity of $R$ implies that $g(b) ⊆ g(a)$. Also, if $bRa$ and $b \ne a$, then $a\notin g(b)$ since $R$ is antisymmetric, and so $g(b) ⊂ g(a)$. So if $a$ is not minimal, then there is some $b$ such that $g(b) ⊂ g(a)$. If $A$ is finite, this implies that $|g(b)| < |g(a)|$.
So if $A$ is finite, the Well Ordering Principle implies that there must be an $a_0$ such that $g(a_0)$ has minimum size. So no $g(b)$ can be smaller than $g(a_0)$, which means $a_0$ must be minimal.
I do not understand the relevance of the middle paragraph. I can intuit why a partial order on a non-empty finite set has a minimal element. But I thought that all you would need to show that some minimal element exists is the Well Ordering Principle. I do recognize that partial orders can have more than one minimal element (say in acyclic directed graphs)–is the paragraph in the middle meant to address that somehow?
One other question: why does transitivity of $R$ imply $g(b) \subseteq g(a)$?
Super confused and appreciate any help.
Thank you!
Best Answer
I’ll answer the second question first. Suppose that $b\mathrel{R}a$. If $x\in g(b)$, then either $x=b$, in which case $x\mathrel{R}a$ and hence $x\in g(a)$, or $x\mathrel{R}b$. But $b\mathrel{R}a$, so by transitivity $x\mathrel{R}a$, and hence again $x\in g(a)$. Thus, every member of $g(b)$ is a member of $g(a)$, i.e., $g(b)\subseteq g(a)$.
The point of the second paragraph is to arrange a situation in which the Well Ordering Principle actually applies. It says that any non-empty set of natural numbers has a smallest element, so in order to use it, we must have a non-empty set of natural numbers. This set is $\{|g(a)|:a\in A\}$, the set of sizes of the sets $g(a)$ for $a\in A$. Since $A$ is finite, and $a\in g(a)$ for each $a\in A$, each $|g(a)|$ is in fact a positive integer. The Well Ordering Principle now says that there is some $a_0\in A$ such that $|g(a_0)|\le|g(a)|$ for each $a\in A$: $|g(a_0)|$ is the smallest member of the set $\{|g(a)|:a\in A\}$ of positive integers.
Now suppose that $a_0$ is not minimal in $A$. Then there is some $b\in A$ such that $b\mathrel{R}a_0$ and $b\ne a_0$. But then $g(b)\subseteq g(a_0)$ and $a_0\in g(a_0)\setminus g(b)$, so $g(b)\subsetneqq g(a_0)$, and therefore $|g(b)|<|g(a_0)|$. This contradicts the minimality of $|g(a_0)|$, thereby showing that no such $b$ can exist and hence that $a_0$ is minimal in $A$.