1
$\begingroup$

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?

  • 0
    Yes, you are totally right. Fixing that up.2012-08-28
  • 0
    You still have the problem that $\pi$ isn’t a partial order, and in any case $\gcd(0,0)$ is undefined.2012-08-28
  • 0
    @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$.2012-08-28
  • 0
    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.)2012-08-28
  • 0
    @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.2012-08-28
  • 0
    @BrianM.Scott I'm very sorry while copying my homework on screen, I must have messed up the definition of $\pi$, now it's fixed.2012-08-28
  • 0
    @Tobias: It depends on the definition that you’re using: it doesn’t work if you define $\gcd(a,b)$ to be, literally, the greatest (largest) common divisor.2012-08-28

1 Answers 1

1

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