Why am I getting that minimal elements are equivalent to the minimum?

104 Views Asked by At

I have these two definitions, about minimals and minimums in an order relation:

$b$ is minimal in $B<=>¬\exists:(x \in B \land x \prec b)$ and also equivalent to $ \forall x,[(x \in B \land x \preccurlyeq b)\implies x=b]$

$b$ is minimum in $B <=>(b \in B)\land \forall x,(x \in B \implies b\preccurlyeq x)$

Now I want to get the existential quantifier equivalent version of the minimum definition. So I do this:

$b$ is minimum in $B<=>(b \in B)\land \forall x,(x \in B \implies b \preccurlyeq x)$

$<=>(b\in B) \land ¬\exists x:[x\in B \land ¬(b \preccurlyeq x)]$ {Here I changed the quantifier, negate it, and also the predicate}

$<=>(b\in B) \land ¬\exists x:[x\in B \land b \succ x]$ {If b is not $\preccurlyeq$ to x, is not $\prec$ nor equal to x, so I suppose is $\succ$ to x}

$<=>(b\in B) \land ¬\exists x:[x\in B \land x \prec b]$

Well very close to the definition of minimal, if it weren't because of $(b\in B)$. But I re-read the statement that I have in my notes from my teacher that defines the minimal elements and start saying: "An element $b$ from $B$ it's said to be minimal in $B$, if there is no other element regarding the relation $\preccurlyeq$ that is strictly previous to it." That "element b from B" I understand he means $b \in B$. So I end up having the same thing in both definitions :

$b$ is minimal in $B<=>(b\in B) \land ¬\exists x:[x\in B \land x \prec b] <=> b $ is minimum in $B$

What it's wrong about this?

2

There are 2 best solutions below

0
On BEST ANSWER

You're assuming that the order you're dealing with is total. Otherwise $\neg(b\preccurlyeq x)$ is not the same as $b\succ x$.

For a total order a minimal element and a minimum are indeed the same concept.

If the order is partial this may not hold. For example, in the set of integers strictly larger than $1$ ordered by divisibility, every prime is a minimal element, but there is no minimum.

1
On

If the set $B$ is totally ordered then the two are the same. Otherwise the statement "If b is not ≼ to x, is not ≺ nor equal to x, so I suppose is ≻ to x" is false, as it is possible that $x$ and $b$ are incomparable, i.e. we have neither $b\leq x$ nor $b > x$.