Prove by induction. Every partial order on a nonempty finite set has at least one minimal element.
How can I solve that question ?
[Math] Question related with partial order – finite set – minimal element
elementary-set-theoryinductionorder-theory
Related Solutions
To show that there is an $n$ such that $T_{n+1} = \emptyset$, just note that $\min ( T_k ) \geq k$ (actually, $T_k \cap A_{k-1} = \emptyset$; an easy proof by induction), and so $T_{m+1}$ must be empty (if $T \subseteq A_m$).
I would personally proceed in a different fashion, and not bother so much in trying to exhibit a bijection. Instead, by induction show that for each $m$ every nonempty $T \subseteq A_m$ is finite. The base case $m = 1$ is trivial. Suppose it is known for $m$, and let $T \subseteq A_{m+1}$ be nonempty. There are three cases:
- If $T = A_{m+1}$, then we're done.
- If $m+1 \notin T$, then actually $T \subseteq A_m$, and we're done by hypothesis.
- If $T \neq A_{m+1}$ and $m+1 \in T$, we can swap $m+1 \in T$ out for something not in $T$ to get a subset $S \subseteq A_m$ equipotent with $T$. (And so $T$ is equipotent with a finite set.)
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$.
Best Answer
One proof method (by induction) is on the size of your set.
The basis, a singleton. There is only one element so clearly it is minimal. Assume the claim is true for sets of size $n$, now prove for $n+1$:
Choose any element of $A$, denote it by $a$ now restrict your partial order to $A\setminus\{a\}$. By the induction hypothesis there is a minimal element there, $b$. Now look at the original order - if $a<b$ show that $a$ is minimal, otherwise $b$ is still minimal.
Either way, you found a minimal element in $A$ and your partial order.