Proof: It is not true that if a partially ordered set has exactly one minimal element, then it must be the smallest element.

85 Views Asked by At

$Proof$. Let $A=\mathbb{Z}\cup\{a\}$, where $\mathbb{Z}$ is ordered in the usual strict linear order, and $a\notin\mathbb{Z}$. Then we have a partial order on $A$. Now since there is no $x\in A$ such that $x<a$, $a$ is minimal, and since for any $x\in\mathbb{Z}$, $x-1<x$, $a$ is the only minimal. Finally, since $a<x$ is undefined for any $x\in\mathbb{Z}$, $a$ is not the smallest element.

What does $x<a$ even mean? Since we are talking about the partial order on $A$, i think it means that $x$ and $y$ are elements of $A$. Im confused because someone told me that by definition $x<y$ tells that $x,y\in\mathbb{Z}$, but can't the $<$ symbol be used for other relations aswell?

Or is it because for $x\in\mathbb{Z}$, $x<y$ is only valid if $y\in\mathbb{Z}$, e.g you cannot compare an integer with some other type of object.

In general, is $x<y$ only valid if $x$ and $y$ are elements of the same set?

2

There are 2 best solutions below

0
On

There is no unwritten rule or convention you are missing. The partial order in the proof is just not explained explicitly and clearly.

What’s intended is that, for $x,y\in A$, $x<_A y$ if and only if $x,y\in\mathbb Z$ and $x<_{\mathbb Z} y$, where $<_{\mathbb Z}$ is the standard order on $\mathbb Z$. (I call the partial order we’re defining on $A$$<_A$“ just to avoid ambiguity.)

With that definition, you can show $<_A$ is a partial order on $A$, and that $a$ is uniquely minimal, but not least in $(A,<_A)$.

0
On

We choose to define a particular strict partial order $<$ on $A:=\Bbb Z\cup\{a\}$ (for some fixed $a\notin\Bbb Z$) by:

$(\forall x,y\in A),$ $x<y$ iff $x,y\in\Bbb Z$ and $x$ is strictly less than $y$ in the usual sense.

For this order, there is no $x\in A$ satisfying $x<a,$ which means that $a$ is minimal. And $a$ is not a least element: it is not even comparable with any other element of $A.$

But all this is a matter of choice, not of "type of objects". We could as well have chosen some other order on $A$ (which would then not be the counterexample we want) by (for instance): $x<y$ iff: either same as before, or $x=a$ and $y\in\Bbb Z.$ For this order, $a$ is the least element of $A.$