Suppose $R$ is a partial order on set $A$, and $B \subseteq A$. Prove theorems about the uniqueness of the smallest element

by Nelver   Last Updated October 18, 2019 09:20 AM

Suppose $R$ is a partial order on set $A$, and $B \subseteq A$. Prove

  1. If B has a smallest element, then this smallest element is unique. Thus, we can speak of the smallest element of B rather than a smallest element.

  2. Suppose b is the smallest element of B. Then b is also a minimal element of B, and it is the only minimal element.

My attempt:

1.

Suppose $x \in B$ and $x$ is smallest element. Suppose $x$ is not unique. Then there is one more smallest element, call it $y$, where $x≠y$.

Since $x$ is smallest element, $(x,y) \in R$

And since $y$ is smallest element, $(y,x) \in R$

Since $x ≠ y$, and $(x,y), (y,x)$ both in $R$, we conclude that $R$ is symmetric. But we know that $R$ is partial order, which implies it must antisymmetric. Hence we have a contradiction, which means $x$ must be unique.

2.

Suppose $b$ is the smallest element.

Suppose $b$ is not a minimal element. It means that there is some $x$, where $x ≠ b$ and $(x,b) \in R$. But since $(b,x) \in R $, it would imply that $R$ is symmetric, but we know it's not. Hence $b$ is a minimal element.

Suppose $b$ is not the only minimal element. Then there exists one more minimal element, say $x$, such that $x ≠ b$. It follows that neither $(x,b) \in R$ nor $(b,x) \in R$. But this is a contradiction, since we know that $b$ is a smallest element, and by definition of smallest element we have

$$\forall x \in B (bRx)$$

Which implies that $(b,x) \in R$. Hence $b$ is the only minimal element. $\Box$

Is it correct?



Related Questions


Updated December 05, 2016 08:08 AM

Updated April 30, 2019 21:20 PM

Updated July 11, 2016 09:08 AM