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

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

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.

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?

Updated December 01, 2017 08:20 AM

Updated April 30, 2019 21:20 PM

Updated January 02, 2018 19:20 PM

- Serverfault Query
- Superuser Query
- Ubuntu Query
- Webapps Query
- Webmasters Query
- Programmers Query
- Dba Query
- Drupal Query
- Wordpress Query
- Magento Query
- Joomla Query
- Android Query
- Apple Query
- Game Query
- Gaming Query
- Blender Query
- Ux Query
- Cooking Query
- Photo Query
- Stats Query
- Math Query
- Diy Query
- Gis Query
- Tex Query
- Meta Query
- Electronics Query
- Stackoverflow Query
- Bitcoin Query
- Ethereum Query