Take the 2-minute tour ×

What I am struggling the most these days is determining maximum, minimum, maximal and minimal elements of a poset. I realize I'm often misled by the definition of total order given by the well known $\leq$. What I am looking for is a general rule that will help in spotting the above mentioned elements, but let me give you an example of what I mean.

Let $(a,b) \in \mathbb Z \times \mathbb Z$ and $d(a,b) \in \mathbb N$ the only non-negative GCD of the pair. Let also $(\mathbb Z \times \mathbb Z, \pi)$ be defined as follows:

$$\begin{aligned} (a,b)\pi (c,t) \Leftrightarrow (a,b) = (c,t) \text{ or } d(a,b) < d(c,t)\end{aligned}$$

it's easy enough showing $(\mathbb Z \times \mathbb Z, \pi)$ is not a total order: let's take $(a,b) \neq (c,t) \in \mathbb Z \times \mathbb Z : d(a,b) = d(c,t)$ then $(a,b) \not{\pi} (c,t)$ and $(c,t) \not{\pi} (a,b)$, so these two elements are not comparable.

Now the question: what are the minimal and maximal elements? Is there a minimum or a maximum?

I have found that $d(a,b) = 0 \Leftrightarrow (a,b) = (0,0)$.

In order for $d(a,b)$ to be a minimal element does it have to be the GCD for the least number of $(a,b)$ elements or just the least value? As $(0,0)$ is the only element with a null GCD does it automatically make $(0,0)$ a minimum?

Similarly when we come to the maximal element/maximum are we looking for the greatest GCD value or the greatest number of elements with the same GCD?

As $\mathbb N$ is infinite I'd say there aren't maximal elements and in particular there's no maximum.

Will you please shed light on my confusion?

share|improve this question
Yes, you are totally right. Fixing that up. –  haunted85 Aug 28 '12 at 9:21
You still have the problem that $\pi$ isn’t a partial order, and in any case $\gcd(0,0)$ is undefined. –  Brian M. Scott Aug 28 '12 at 9:26
@BrianM.Scott why is $\pi$ not a partial order? And my textbook clearly states if $a = b = 0$ then the (only) $\gcd(a,b)=0$. –  haunted85 Aug 28 '12 at 9:32
Because a partial order is antisymmetric: if $a\,R\,b$ and $b\,R\,a$, then $a=b$. Your $\pi$, however, is not antisymmetric, as was already noted: $\langle 1,2\rangle\,\pi\,\langle 1,3\rangle$ and $\langle 1,3\rangle\,\pi\,\langle 1,2\rangle$, but $\langle 1,2\rangle\ne\langle 1,3\rangle$. (If your text actually defines $\gcd(0,0$, that’s fine, but it’s by no means a universal convention, so I didn’t expect it.) –  Brian M. Scott Aug 28 '12 at 9:38
@BrianM.Scott What is wrong with defining $gcd(0,0) = 0$? $0$ is the unique common divisor of $0$ and $0$ such that any common divisor of $0$ and $0$ divides it. –  Tobias Kildetoft Aug 28 '12 at 9:40

1 Answer 1

up vote 1 down vote accepted

The ordering is based directly on the GCD, so it’s the actual GCD that matters, not the number of pairs with a given GCD.

  • For any $\langle a,b\rangle\in\Bbb Z\times\Bbb Z$, $\langle 0,0\rangle\pi\langle a,b\rangle$: either $\langle a,b\rangle=\langle 0,0\rangle$, or $\gcd(a,b)>0=\gcd(0,0)$. This shows that $\langle 0,0\rangle$ is the minimum element of the poset (and hence if of course also minimal).

  • Let $\langle a,b\rangle\in\Bbb Z\times\Bbb Z$. If $n=|a|+|b|+1$, then $\gcd(a,b)<n=\gcd(n,n)$, so $\langle a,b\rangle\pi\langle n,n\rangle$. Clearly $\langle n,n\rangle\ne\langle a,b\rangle$, so $\langle n,n\rangle$ is strictly larger than $\langle a,b\rangle$ with respect to $\pi$. This shows that no element of $\Bbb Z\times\Bbb Z$ is maximal, which of course implies that the poset also has no maximum element. Note that it isn’t enough to know that $\Bbb N$ is infinite: to show that the poset has no maximal elements, you must show that there are pairs $\langle a,b\rangle$ with arbitrarily large GCDs.

share|improve this answer

Your Answer


