$R$ is a partial order on nonempty finite set $S$, does $S$ contain an element $b$ such that if $aRb$ implies $a = b$

49 Views Asked by At

I do not know how to start. I tried to use property of transitive and reflexive to get $bRa$, but i cannot connect those together. Any hint on how to prove this?

2

There are 2 best solutions below

6
On BEST ANSWER

After question edit

If $|S|=1$ the statement is obvious. Now let's do full induction.

Suppose the statement holds for every nonempty partially ordered set with less than $|S|$ elements.

Let $a\in S$ and consider $T=\{x\in S:xRa, x\ne a\}$. If $T$ is empty, you are done. Otherwise, $|T|<|S|$ and so the induction hypothesis apply.

Now finish up the argument.


Original answer

You are asking whether any infinite partially ordered set has a minimal element.

Since total orders are partial orders, the property would imply that every infinite totally ordered set has a minimum. Now, can you find a counterexample?

0
On

Try it out on order $(\mathbb R,\leq)$.

Then you will find that no such element $b\in\mathbb R$ exists.

Simply because $a:=b-1\leq b$ and $a\neq b$ for every $b\in\mathbb R$.