# Suppose $b$ is the smallest element of $B$. Then $b$ is also a minimal element of $B$.

Working on the book: Daniel J. Velleman. "HOW TO PROVE IT: A Structured Approach, Second Edition" (p. 206)

Suppose $$R$$ is a partial order on a set $$A$$, and $$B \subseteq A$$. Suppose $$b$$ is the smallest element of $$B$$. Then $$b$$ is also a minimal element of $$B$$, and it is the only minimal element.

In this post, Suppose $b$ is the smallest element of $B$. Then $b$ is also a minimal element of $B$, and it is the only minimal element., I showed that the minimal element is unique. Now, I will prove premise two of that proof (that $$b$$ is also a minimal element of $$B$$).

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \def\Ae#1{\qquad\mathbf{\forall E} \: #1 \\} \def\Ai#1{\qquad\mathbf{\forall I} \: #1 \\} \def\Ee#1{\qquad\mathbf{\exists E} \: #1 \\} \def\Ei#1{\qquad\mathbf{\exists I} \: #1 \\} \def\R#1{\qquad\mathbf{R} \: #1 \\} \def\ci#1{\qquad\mathbf{\land I} \: #1 \\} \def\ce#1{\qquad\mathbf{\land E} \: #1 \\} \def\oi#1{\qquad\mathbf{\lor I} \: #1 \\} \def\oe#1{\qquad\mathbf{\lor E} \: #1 \\} \def\ii#1{\qquad\mathbf{\to I} \: #1 \\} \def\ie#1{\qquad\mathbf{\to E} \: #1 \\} \def\be#1{\qquad\mathbf{\leftrightarrow E} \: #1 \\} \def\bi#1{\qquad\mathbf{\leftrightarrow I} \: #1 \\} \def\qi#1{\qquad\mathbf{=I}\\} \def\qe#1{\qquad\mathbf{=E} \: #1 \\} \def\ne#1{\qquad\mathbf{\neg E} \: #1 \\} \def\ni#1{\qquad\mathbf{\neg I} \: #1 \\} \def\IP#1{\qquad\mathbf{IP} \: #1 \\} \def\x#1{\qquad\mathbf{X} \: #1 \\} \def\DNE#1{\qquad\mathbf{DNE} \: #1 \\}$$

$$\fitch{ 1.\, \forall x\forall y((xRy \land yRx) \to x=y)\\ 2.\, b \in B \land \forall x(x \in B \to bRx) }{ \fitch{3.\, \exists x(x \in B \land xRb \land x \neq b)}{ \fitch{4.\, a \in B \land aRb \land a \neq b}{ 5.\,\forall x(x \in B \to bRx) \ce{2} 6.\,a \in B \to bRa \Ae{5} 7.\,a \in B \ce{4} 8.\,bRa \ie{6,7} 9.\,(aRb \land bRa) \to a = b \Ae{1} 10.\,aRb \ce{4} 11.\,aRb \land bRa \ci{10,8} 12.\,a=b \ie{9,11} 13.\,a \neq b \ce{4} 14.\,\bot \ne{12,13} }\\ 15.\,\bot \Ee{3,4-14} }\\ 16.\,\neg \exists x(x \in B \land xRb \land x \neq b) \ni{3-15} 17.\,b \in B \ce{2} 18.\,b \in B \land \neg \exists x(x \in B \land xRb \land x \neq b) \ci{17,16} }$$

Why do I need to add "$$x \in B$$" in the symbolisation of "$$b$$ is a minimal element of B" in order to accomplish the proof ?

Is this proof correct ?

Your derivation is correct. Note that you only need that $$R$$ is antisymmetric to prove that the smallest element of $$B$$ is a minimal element of $$B$$.

The formula $$\tag{1}\lnot \exists x (xRb \land x \neq b)$$ means that $$b$$ is a minimal element for the domain of quantification, that is the set $$A$$ and not the subset $$B$$. Indeed, $$\lnot \exists x$$ means that there is no $$x$$ in the domain.

The fact that $$b$$ is the smallest element of $$B \subseteq A$$ does not imply that $$b$$ is a minimal element of $$A$$. For instance, if $$A = \{0,1\}$$ and $$B = \{1\}$$ with the usual order, then $$B \subseteq A$$, and $$1$$ is the smallest element of $$B$$ but is not a minimal element of $$A$$.

This is the reason why it is important to add $$x \in B$$ to $$(1)$$ and get $$\tag{2} \lnot \exists x (x \in B \land xRb \land x \neq b)$$ which actually means that there is no element in $$B$$ smaller than $$b$$. According to $$(2)$$, possibly $$b \in A \smallsetminus B$$, so formula $$(2)$$ alone does not mean that $$b$$ is a minimal element of $$B$$. But formula $$(2)$$ in conjunction with $$b \in B$$ means that $$b$$ is a minimal element of $$B$$.

From a technical point of view, in your derivation you can easily see the need for adding $$x \in B$$ to $$(1)$$. Suppose that your line $$3$$ were $$\exists x (xRb \land x \neq b)$$, which means that $$b$$ is not a minimal element of $$A$$. As in line $$3$$ there would not be $$x \in B$$, you cannot infer $$a \in B$$ in line $$7$$ and hence you cannot derive $$bRa$$ in line $$8$$ (which is essential to use antisymmetry and conclude that $$a = b$$ in line 12, so that you get a contradiction and thus derive that $$b$$ is a minimal element of $$B$$).

• Thank you very much, @Taroccoesbrocco ! One question: in the formula, $$\lnot \exists x (xRb \land x \neq b)$$ I see $b$ belongs to $A$, but for that reason, isn't it necessary to add $b \in B$ to that formula? The addition of $x \in B$, specifies which set $x$ belongs, but still $b$ could belong to $A$. Perhaps, I am confused about it. Jun 7, 2020 at 21:41
• What's a minorant ? Jun 7, 2020 at 21:42
• @F.Zer - A minorant of $B \subseteq A$ is a element $b \in A$ smaller than all the elements of $B$. I've just reworded the sentence without using "minorant" to avoid too many concepts (moreover the previous version was slightly inaccurate). Jun 7, 2020 at 21:50
• I understand, now. Thank you ! Jun 7, 2020 at 21:56
• @F.Zer - The formula $\lnot \exists x (x \in B \land x R b \land x \neq b)$ means that $b$ is an element of $A$ such that there is no element in $B$ smaller than $b$. It doesn't mean that $b$ is a minimal element of $B$, because maybe $b \notin B$. I reworded the sentence to make it clearer (I hope!). Jun 7, 2020 at 22:04