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?

$\endgroup$
7
  • $\begingroup$ Yes, you are totally right. Fixing that up. $\endgroup$ Commented Aug 28, 2012 at 9:21
  • $\begingroup$ You still have the problem that $\pi$ isn’t a partial order, and in any case $\gcd(0,0)$ is undefined. $\endgroup$ Commented Aug 28, 2012 at 9:26
  • $\begingroup$ @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$. $\endgroup$ Commented Aug 28, 2012 at 9:32
  • $\begingroup$ 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.) $\endgroup$ Commented Aug 28, 2012 at 9:38
  • $\begingroup$ @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. $\endgroup$ Commented Aug 28, 2012 at 9:40

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.