This continues a discussion begun at checking Zorn's lemma on an example where an example was offered to help understand maximal elements and Zorn's lemma. That example used the set {1,…,100} with partial order "is divided by."
That has problems, especially when applied to my textbook, "Topology", 2nd ed., Munkres. In Munkres' description of Zorn's Lemma, the "is divided by" partial order would not work, I don't think. Munkres uses the term "strict partial order" in Zorn's Lemma and defines it as a two-part test. (see image below) One test is being nonreflexive, i.e. a ≺ a never holds. Almost the opposite of the test for partial order in Wolfram Mathworld and in the Oxford Dictionary of Mathematics. So for Munkres, "is divisible by" would not be a strict partial order.
That problem would be fixed by changing it to "is divisible by with quotient greater than 1". But there is another problem in that the dividend precedes the divisor. Also, I'm not sure but that might make some of the answers given in the earlier discussion wrong. I think some answers assumed the reverse.
For Munkres' description of Zorn's Lemma, the question becomes easier for me to understand if the relation is "divides with quotient greater than 1" so that the smaller integer precedes the larger one.
Another problem is that I don't think the earlier question correctly describes the family of total ordered subsets correctly. For example, {3,6,12,24,48,96} is missing, I think. To simplify the question further, use the smaller superset {1,…,16}. Then I think a complete list of subsets would be: {1, 2, 10}, {1, 3, 9}, {1, 4, 12}, {1, 5, 10}, {1, 7, 14}, {1, 2, 6, 12}, {1, 3, 6, 12}, {1, 2, 4, 8, 16}.
That said, I don't think I know the answer to the earlier question or to my revision of it. I'd like to since it would give me an easy example to the maximal concept. Can someone try to put the answer in simple terms? How would I go about identifying all the maximal elements in the set {1,…,16} with the slightly changed relation?
Best Answer
There are two ways to define a partially ordered set:
These two definitions are sort of equivalent. If $(X,<)$ is a strict poset, then we can define a non-strict "$\leq$" relation on $X$ via: $x\leq y$ if $x<y$ or $x=y$. On the other hand if $(X,\leq)$ is a non-strict poset, then we can define strict "$<$" via $x<y$ if $x\leq y$ and $x\neq y$. Then we can pass freely between strict and non-strict variants, and this correspondence behaves like a one-to-one function.
And so a strict order differs from non-strict order only by considering equal or non-equal elements. And thus the Zorn's lemma applies to both variants.
With that, if $X$ is a subset of naturals $\mathbb{N}$ then we can define a non-strict ordering on $X$ via: $x\leq y$ if $x$ divides $y$. Then the corresponding strict ordering is: $x< y$ if $x$ divides $y$ and $x\neq y$.
Recall that if $X$ is a poset (strict or not) then a subset $C\subseteq X$ is called a chain, if given two elements $x,y\in C$, $x\neq y$ we get that either $x<y$ or $y<x$. Then a chain $C\subseteq X$ is called a maximal chain if $C$ is not a proper subset of any other chain.
With these definitions it can be shown that an element $x\in X$ is maximal if and only if there is a maximal chain $C\subseteq X$ such that $x\in C$ and $x$ is greatest* in $C$
Let's have a look an example. I will use $X=\{1,2,3,4,5,6,7,8\}$ to simplify it even more. With respect to "divisible by" ordering of course. Then maximal chains are:
$$\{1,2,4,8\}$$ $$\{1,3,6\}$$ $$\{1,5\}$$ $$\{1,7\}$$
And so $\{5,6,7,8\}$ are all maximal in $X$.
In fact, if $X=\{1,2,\ldots,n\}$ for some natural $n$ then any $x\in X$ such that $x$ is greater than $n/2$ (with respect to the standard number ordering) is maximal in our "divisible by" ordering. Because the next multiple of any $x$ is $2\cdot x$ which doesn't belong to our $X$. On the other hand if $x$ is smaller or equal to $n/2$ (with respect to the standard number ordering) than $2\cdot x$ belongs to $X$ and so there is a greater (with respect to "divisible by" ordering) element in $X$. Meaning $x$ is not maximal.
All in all: given $X=\{1,2,\ldots,n\}$ with the "divisible by" ordering we get that $x\in X$ is maximal if and only if $x>n/2$ (with respect to the standard number ordering).
*: the terms "maximal" and "greatest" are not the same, but they coincide for chains.