how to list out the partial order

Question

Given the set $P=\mathbb{Z}\times\mathbb{Z}$ and the partial order $<$ on $P$ defined by $(a,b)<(c,d)$ iff $a$ less than $c$ and $b$ less than $d$.

Let $S=\mathbb{N}\times\mathbb{N}.$ Describe each of the following:

(a) the minimal elements of $S,$

(b) the maximal elements of $S,$

(c) the lower bounds of $S,$

(d) the upper bounds of $S,$

(e) the lub of $S,$

(f) the glb of $S.$

I know all the meaning of the questions (a), (b), (c), (d), (e), but I don't know how to list out the partial order of $S$ and $P.$ If I have the partial order of $S$ and $P,$ I am able to finish the rest of the question by myself.

Answer 1

It's unclear what you mean by "listing out" the partial order of $S$ and $P,$ but it sounds like you simply may not be understanding the definition. For example, $(-5,1)<(6,3),$ but $(-5,1)\not<(6,1)$ and $(8,1)\not<(6,3).$ Can you see why each of these holds? If not, let me know.

Added: Probably the easiest way to begin is to develop a visual understanding for how the partial order works. Let's imagine an ordered pair $(a,b)$ in $P$--that is, a point on the $xy$-plane, whose coordinates are both integers. The "greater" points $(c,d)$ are those with $a<c$ and $b<d.$ What does that mean about $(c,d)$ visually? Well, $a<c$ means that $(c,d)$ is somewhere to the right of $(a,b),$ and $b<d$ means that $(c,d)$ is somewhere above $(a,b).$ Thus, given any point $(a,b),$ the points greater than $(a,b)$ will be those above it and to the right. Similarly, the points less than $(a,b)$ will be those below it and to the left.

In our first picture, we see the point $(a,b)$ in red. The points in black are all greater than $(a,b).$ No points less than or incomparable to $(a,b)$ are shown.

In our second picture, we see the point $(a,b)$ in red again, but this time, the black points are those less than $(a,b).$ No points greater than or incomparable to $(a,b)$ are shown.

In our third picture, we once again see $(a,b)$ in red, but this time, the points in black are those incomparable to $(a,b).$

---

This is an exercise of applying definitions to justify our visual understanding. Let me show you how we might go about determine some of the answers visually (and sometimes logically). I will also outline a proof for one, and give a detailed proof for another.

---

The minimal elements of $S$ are elements $(a,b)$ of $S$ such that $(c,d)\not<(a,b)$ for all $(c,d)\in S.$ Visually, we need the the points in $S$ with no other points in $S$ below and to the left of them. But what are the points of $S$? Well, they are points in the $xy$-plane with non-negative integer coordinates. Put another way, they are the elements of $P$ lying either

1. at the origin,
2. on the positive $x$-axis,
3. on the positive $y$-axis, or
4. in the first quadrant (above the $x$-axis and to the right of the $y$-axis).

Every point satisfying 4 will have the origin below and to the left of it, so none of those can be minimal elements in $S.$ The points satisfying 1 and 2 have no points of $S$ below them, so will be minimal in $S$. The points satisfying 1 and 3 have no points of $S$ to the left of them, so will be minimal in $S$. Thus, the minimal points of $S$ will be those satisfying 1, 2, or 3.

Algebraically, this means we must show that the minimal points of $S$ are those $(a,b)\in S$ with $a=0$ and/or $b=0.$ I would let the proof follow my visual understanding, as follows:

• I would first note that for any $(a,b)\in S,$ we have $a\ge 0$ and $b\ge 0.$
• I would show that if $a>0$ and $b>0$--that is, if $(a,b)$ satisfies 4, as above--then $(0,0)<(a,b),$ so that $(a,b)$ is not minimal in $S$.
• I would show that if $b=0$--that is, if $(a,b)$ satisfies 1 or 2, as above--then in order to have $(c,d)<(a,b),$ we would have to have $d<b=0,$ and so $(c,d)\notin S.$ [Put visually, the only points of $P$ below $(a,b)$ are outside of $S.$] Thus, $(a,b)$ is minimal in $S,$ by definition.
• I would show that if $a=0$--that is, if $(a,b)$ satisfies 1 or 3, as above--then in order to have $(c,d)<(a,b),$ we would have to have $c<a=0,$ and so $(c,d)\notin S.$ [Put visually, the only points of $P$ to the left of $(a,b)$ are outside of $S.$] Noting how similar this is to the $b=0$ case, I would probably omit it from my final proof. Instead, I would include a remark such as: "If $(a,b)\in S$ with $a=0,$ then in a similar fashion to the $b=0$ case, we find that $(a,b)$ is minimal in $S$."

Now, we could try to proceed entirely logically from the definitions, and never worry about a visual. We need the elements $(a,b)$ of $S$ such that $(c,d)\not<(a,b)$ for all $(c,d)\in S.$ Put another way, no matter what $c,d$ we choose from $\Bbb N,$ we'll have $c$ not less than $a$ or we'll have $d$ not less than $b$ (or we'll have both); this is simply by negating the definition of $<$. Since $\Bbb N$ is totally ordered, this means we'll have $a$ less than or equal to $c$ for all $c\in\Bbb N$ or we'll have $b$ less than or equal to $d$ for all $d\in\Bbb N$ (or we'll have both). Put more briefly, $a$ or $b$ (or both) must be a lower bound of $\Bbb N,$ but since $a,b\in\Bbb N,$ this means that $a$ or $b$ (or both) must be the least element of $\Bbb N.$ This means that $a=0$ and/or $b=0,$ which is exactly what our visual led us to conclude, so our proof from that point would proceed in much the same way.

---

The maximal elements of $S$ are elements $(a,b)$ of $S$ such that $(a,b)\not<(c,d)$ for all $(c,d)\in S.$ Visually, they would be points of $S$ with no points of $S$ above and to the right of them. But there are no such points! Given any point $(a,b)$ of $S,$ $(a+1,b+1)$ will be a point of $S$ that is above and to the right of $(a,b),$ so $(a,b)$ cannot be maximal in $S.$

Or, avoiding the visual, we can negate the definition of $(a,b)<(c,d)$, and reason in a similar fashion to the minimal elements question, concluding that we'd need $a$ or $b$ (or both) to be the greatest element of $\Bbb N.$ Since $\Bbb N$ has no greatest element, we conclude that $S$ has no maximal elements.

---

The lower bounds of $S$ are the elements $(a,b)$ of $P$ such that $(a,b)\leq(c,d)$ for all $(c,d)$ in $S$. Visually, $(a,b)$ is a point such that all elements of $S$ are either equal to $(a,b),$ or above and to the right of $(a,b).$ However, there is no point of $S$ with all other points of $S$ above and to the right of it, so the lower bounds of $S$ are those points of $P$ below and to the left of all points of $S.$ In order to be below all points of $S,$ it will need to be below the $x$-axis, and in order to be to the left of all points of $S,$ it must be to the left of the $y$-axis. Thus, the lower bounds of $S$ will be the points $(a,b)$ in $P$ with $a<0$ and $b<0.$

[I will prove this in more detail below.]

---

The upper bounds of $S$ are the elements $(a,b)$ of $P$ such that $(c,d)\leq(a,b)$ for all $(c,d)$ in $S$. Visually, $(a,b)$ is a point such that all elements of $S$ are either equal to $(a,b),$ or below and to the left of $(a,b).$ However, no point of $S$ has all other points of $S$ below and to the left of it--if there were such a point of $S,$ it would be maximal in $S,$ and we've already determined that $S$ has no maximal elements. On the other hand, if we pick a point $(a,b)$ of $P$ that isn't in $S,$ then $(a,b)$ will be to the left of the $y$-axis and/or below the $x$-axis, and thus can't have any elements of $S$ below and to the left of it, so can't be an upper bound of $S.$

---

Now, I will prove exactly what the lower bounds of $S$ are, and prove further that $S$ has no greatest lower bound.

I will insert some comments in areas where I think you may have confusion/questions.

Claim: Let $L$ be the set of lower bounds of $S$ in $P.$ We show that $$L=\bigl\{(x,y)\in P:x<0\text{ and }y<0\bigr\},$$ and that $L$ has no greatest element, meaning that $\operatorname{glb}(S)$ does not exist.

Proof: Suppose that $(x,y)$ is a lower bound of $S$ in $P.$ We show that $x$ and $y$ are both negative.

Since $(x,y)$ is a lower bound of $S$ in $P,$ then we know by definition that $$(x,y)\le(a,b)\tag{$\star$}$$ for all $(a,b)\in S.$

I suspect that your confusion stems from $(\star).$ Given the way that $<$ was defined, it is tempting to say that $(x,y)\le(a,b)$ iff $x$ is less than or equal to $a$ and $y$ is less than or equal to $b.$ However, this is not the case, as our visual understanding made clear (and as the proof will show momentarily).

On the other hand, suppose we defined $\preceq$ on $P$ by $(a,b)\preceq(c,d)$ iff $a\le b$ and $c\le d,$ then defined $\prec$ by $(a,b)\prec(c,d)$ iff $(a,b)\preceq(c,d)$ and $(a,b)\neq(c,d).$ Put visually, $(a,b)\prec(c,d)$ if $(c,d)$ is either (i) directly above $(a,b),$ (ii) directly to the right of $(a,b),$ or (iii) above and to the right of $(a,b).$ Considering $P$ as a partial order under $\prec,$ we would have that $(0,0)\preceq(a,b)$ for all $(a,b)\in S,$ making $(0,0)$ the least element (and so greatest lower bound) of $S$ in $P$ under that different partial order.

Since $(x,y)\le(a,b)$ iff $(x,y)<(a,b)$ or $(x,y)=(a,b),$ then $(\star)$ is equivalent to saying that one of the following holds: $$x\text{ is less than }a\text{ and }y\text{ is less than }b.\tag{1}$$ $$x=a\text{ and }y=b.\tag{2}$$

Note that $(2)$ can only occur if $(x,y)\in S,$ but this is impossible. If it were possible to have $(x,y)\in S,$ then by definition of $S,$ we would have $x\ge 0$ and $y\ge 0,$ but then $(1)$ can't hold for $(a,b)=(0,0).$ Since $(x,y)$ is a lower bound of $S$ in $P$, then $(\star)$ holds for $(a,b)=(0,0),$ so since $(1)$ doesn't hold in that case, then $(2)$ has to hold, meaning that $(x,y)=(0,0).$ However, then neither $(1)$ nor $(2)$ can hold for $(a,b)=(1,0),$ so $(x,y)\not\le(1,0),$ which contradicts our choice of $(x,y)$ as a lower bound of $S$ in $P.$

The short version, here, is that none of the elements of $S$ can be a lower bound of $S.$ This isn't always the case. Considering $D=\{(n,n):n\in\Bbb N\},$ then we have that $(0,0)$ is the least element (and so greatest lower bound) of $D$ in $P.$ And as mentioned above, in the different partial order $\preceq$, $(0,0)$ is the least element (and greatest lower bound) of $S$ in $P.$

Having obtained a contradiction from assuming that $(2)$ holds for some $(a,b)\in S,$ we conclude that in order for $(\star)$ to hold for all $(a,b)\in S,$ we must have that $(1)$ holds for all $(a,b)\in S,$ meaning that $$(x,y)<(a,b)\tag{$\heartsuit$}$$ holds for all $(a,b)\in S.$ In particular, $(x,y)<(0,0),$ and so both $x$ and $y$ are negative, as desired.

On the other hand, take any $(x,y)\in P$ with $x$ and $y$ both negative. Given any $(a,b)\in S,$ we then have $x<0\le a$ and $y<0\le b$ by definition of $S$ and by choice of $(x,y),$ so that $(x,y)<(a,b).$ Since $(a,b)\in S$ was arbitrary, then $(x,y)$ is a lower bound of $S$ in $P,$ as desired.

At this point, we've proved that $(x,y)$ is a lower bound of $S$ in $P$ iff both $x$ and $y$ are negative integers, having proved the implication in both directions.

We now show that $L$ has no greatest element. By way of contradiction, suppose that $(a,b)$ is the greatest element of $L.$ Since $(-2,-2)<(-1,-1),$ then we can't have $(-2,-2)=(a,b),$ but since $(a,b)$ is the greatest element of $L,$ then we must have $(-2,-2)\le(a,b).$ Therefore, we have $(-2,-2)<(a,b),$ so that $-2<a$ and $-2<b.$ By the work above, though, $a$ and $b$ are both negative integers, so we must have $(a,b)=(-1,-1).$ But then neither $(-1,-2)<(a,b)$ nor $(-1,-2)=(a,b),$ so $(-1,-2)\not\le(a,b),$ contradicting our assumption that $(a,b)$ was the greatest element of $L.$ $\Box$