Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.