5
$\begingroup$

I'm wondering if there are any infinite sets which can be totally ordered in such a way that all non-empty subsets contain a maximal and minimal element.

It is clear to me that this is impossible in discrete orderings and in the standard bounded dense orderings like $[0,1]$, but is it known that this is impossible in general?

$\endgroup$
12
$\begingroup$

This is indeed impossible. This is because any linear order $L$ has either an infinite increasing sequence or an infinite decreasing sequence (or both), and either provides a counterexample.


Technically, the observation above requires choice (think about a Dedekind-finite infinite set of reals). However, we do not in fact need choice for this problem:

Suppose $L$ is a linear order. Let

$$D=\{x\in L: \text{ there are finitely many points } <x\}$$

If $D$ has a maximal element $y$, then $\{z\in L: y<z\}$ is infinite (since $L$ is infinite) and has no least element, so $D$ can't have a maximal element. If $D$ is nonempty, then $D$ is a counterexample to the desired property.

So $D=\emptyset$. But then $L$ doesn't have a minimal element, so $L$ itself is a counterexample.

Concisely:

Suppose $L$ is a linear order. If $L$ has a least element, then the set of elements with finitely many smaller elements has no maximum.

Similarly, if $L$ has a greatest element, then the set of elements with finitely many bigger elements has no minimum.


Incidentally, going back to the observation at the top of the answer: while this isn't the best way to solve this problem since it requires choice, it leads to a really interesting question. Namely, the set $\{\omega, \omega^*\}$ (where $L^*$ denotes the reverse of $L$) is a basis for the infinite linear orders: a linear order is infinite iff it contains a copy of $\omega$ or of $\omega^*$. Moreover, this is clearly the smallest basis for the infinite linear orderings. So we can ask:

What about, say, uncountable linear orderings?

This turns out to be a very deep problem in set theory; the biggest positive result is due to Justin Moore:

Suppose the Proper Forcing Axiom (PFA) holds. Then $\{\omega_1,\omega_1^*,S, C,C^*\}$ is a basis for the uncountable linear orders whenever $C$ is an arbitrary Countryman line and $S$ is an $\aleph_1$-dense set of real numbers.

(Here a Countryman line is a linear order of cardinality $\aleph_1$ whose square is a countable union of chains; the existence of such an object is not immediate, but provable in ZFC alone.)

Interestingly, the choice of Countryman line is meaningful - different Countryman lines can be non-isomorphic - but the choice of $S$ turns out not to be: assuming PFA, any two $\aleph_1$-dense sets of reals without endpoints are isomorphic (this follows from work of Baumgartner, I'm not sure where it was first explicitly stated).

$\endgroup$
  • $\begingroup$ This is very cool, thank you. $\endgroup$ – Alec Rhea Dec 9 '17 at 0:07
  • 1
    $\begingroup$ What is a Countryman line, and who is Countryman? $\endgroup$ – bof Dec 9 '17 at 0:08
  • 1
    $\begingroup$ @bof : Is Wikipedia blocked where you are? en.wikipedia.org/wiki/Countryman_line $\endgroup$ – Eric Towers Dec 9 '17 at 7:45
  • 1
    $\begingroup$ @EricTowers No problem with access to Wikipedia, but thanks for your concern. I just didn't feel like looking up Countryman on Wikipedia; instead, I felt like posting a comment. By the way, do you know who this Countryman fellow is? $\endgroup$ – bof Dec 9 '17 at 9:57
  • $\begingroup$ Roger S. Countryman, Jr., working at the University of Minnesota and Arizona State University in the late 60s. His paper on the Countryman line was circulating but unpublished in 1970. Shelah's 1976 proof that it existed (linked from Wikipedia, its first reference is the paper above). Math Genealogy page: genealogy.math.ndsu.nodak.edu/id.php?id=1974 $\endgroup$ – Eric Towers Dec 10 '17 at 16:43
7
$\begingroup$

Here is a quick proof that this is impossible. Suppose $X$ is an infinite totally ordered set such that every nonempty subset has a least element and a greatest element. In particular, $X$ itself has a least element; call it $x_0$. Now $X\setminus\{x_0\}$ is nonempty, so it has a least element; call it $x_1$. Similarly, $X\setminus\{x_0,x_1\}$ has a least element, which we call $x_2$. Continuing inductively, we get a sequence of element $x_n$ such that $x_0<x_1<x_2<\dots$. (We can continue this over all natural numbers since $X$ is infinite so $X\setminus\{x_0,\dots,x_{n-1}\}$ will always be nonempty and we can define $x_n$.)

But now consider the set $A=\{x_n:n\in\mathbb{N}\}$. It has no greatest element, since for any $x_n$, $x_{n+1}$ is a greater element of $A$. This is a contradiction.

$\endgroup$
5
$\begingroup$

If an infinite set is linearly ordered in such a way that every nonempty subset has a least element (and you omitted "nonempty") then it has an initial segment that is order-isomorphic to $\{\,0,1,2,3,\ldots\,\}.$ That initial segment has no greatest element.

$\endgroup$
0
$\begingroup$

Prove that a partial order with a top and bottom, for which
every not empty subset contains the top and the bottom, has
exactly one point.

$\endgroup$
  • $\begingroup$ Maybe I'm missing something, but how is this relevant? $\endgroup$ – Noah Schweber Dec 10 '17 at 21:15
  • $\begingroup$ It is revalent because it shows the impossibility of OP's idea and fully describes the orders for which the property presented holds. @NoahSchweber $\endgroup$ – William Elliot Dec 11 '17 at 0:56
  • $\begingroup$ But that's not the property the OP is talking about. They're asking about subsets which themselves have maximal/minimal elements; for example, $\omega+\omega^*$ is a linear order where every nonempty subset has either a maximal or minimal element ("all non-empty subsets contain a maximal and minimal element" emph. mine). They're not asking about subsets which contain the maximal/minimal element of the order, which is of course trivial. $\endgroup$ – Noah Schweber Dec 11 '17 at 0:58
  • $\begingroup$ @NoahSchweber. Ok Noah, I accept your point. $\endgroup$ – William Elliot Dec 11 '17 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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