1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

0
$\begingroup$

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$).

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – F. Zer
    Jun 7, 2020 at 21:41
  • $\begingroup$ What's a minorant ? $\endgroup$
    – F. Zer
    Jun 7, 2020 at 21:42
  • 1
    $\begingroup$ @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). $\endgroup$ Jun 7, 2020 at 21:50
  • $\begingroup$ I understand, now. Thank you ! $\endgroup$
    – F. Zer
    Jun 7, 2020 at 21:56
  • 1
    $\begingroup$ @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!). $\endgroup$ Jun 7, 2020 at 22:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .