checking Zorn's lemma on an example

Question

I have difficulty with Zorn's lemma.

Zorn's lemma. If $A$ is a partially ordered set such that every chain in $A$ has an upper bound, then $A$ contains a maximal element.

Let's check it for the following example:

$$ A=\left\{0,1, \ldots, 100 \right\} $$

with the partial order relation (is divisible):

$$ \forall a, b \in A \quad a|b \iff \exists k\in \mathbb N \quad b=ka, $$

so the following sets are chains in $A$.

$\begin{align} A_2=\left\{1,2,4,\ldots, 64\right\}=& \left\{2^n, n\in \mathbb N\right\}\cap A,\\ A_3=\left\{1,3,9,\ldots, 81\right\}=& \left\{3^n, n\in \mathbb N\right\}\cap A,\\ & \cdots \cdots \\ A_m= \left\{m^n, n\in \mathbb N\right\}\cap A,& m\in A. \end{align}$

Clearly, every sets $A_m, m\in A$ has a upper bound, then the set $A$ is inductive. By Zorn's Lemma, The set $A$ possesses a maximal element with respect to the partial order relation $|$ (is divisible by).

Question: What is the maximum element of $A$ with respect to the partial order relation?

I see that $100$ is the maximum element w.r.t the relation "less than or equal to", not w.r.t the relation $|$.

Thank you very much for your help.

Answer 1

Your misunderstanding is visible right in the question (emphasis by me):

What is the maximum element of A with respect to the partial order relation?

Zorn's lemma does not guarantee you a maximum, but only a maximal element. Those two are not equivalent: There can be only one maximum, but there can be many maximal elements.

Here are the relevant definitions:

• A maximum is an element $m$ such that for all other elements $n$ you have $n\le m$.

• A maximal element is an element $m$ such that there is no element $n$ with $m<n$.

While for total orders they are equivalent, for partial orders they are not. In particular, a set can have at most one maximum, but many maximal elements.

Now obviously a maximum is a maximal element, and if a maximum exists, it is the only maximal element. But a maximal element need not be a maximum, and in particular, if a set has more than one maximal element, it cannot have a maximum.

Now to your set $A=\{1,\ldots,100\}$ partially sorted by divisibility:

Theorem: An element $n\in A$ is a maximal element in the divisibility order if and only if $n>50$ in the standard order.

Proof:

Assume $n>50$. Then the smallest (in the standard order) number of which it is a proper divisor is $2n$, but $2n>100$ is not an element of $A$, nor is any number that is larger (in the standard order). Therefore in the divisibility order no element of $A$ is larger than $n$, that is, $n$ is a maximal element in the divisibility order.

Conversely, assume $n\le 50$. Then $2n\le 100$, therefore $2n\in A$, but $n|2n$ and therefore $n$ is not a maximal element in the divisibility order.

Edit:

I just noticed that you also included $0$ in your set $A$, which I previously missed.

In that case, $A$ has indeed a maximum in the divisibility order, and that maximum is $0$:

By the definition you gave, $n|0$ iff there exists a $k\in\mathbb N$ such that $0=kn$. Obviously there exists such a $k$ for any $n$, namely $k=0$. Therefore any number divides $0$, and thus $0$ is the maximum (and the unique maximal element) of $A$.

Answer 2

Let's denote your relation by $\preceq,$ i.e. $a \preceq b \iff a | b. $ A maximal element of $A$ is $100$ (assuming $0 \notin A$, otherwise $0$ is maximal). Assume $a \in A$ with $100 \preceq a,$ then $100 | a.$ But that means that $a=100,$ so there is no bigger element in $A$ with respect to that relation.