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?
On
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.
On
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.
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:
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:
This turns out to be a very deep problem in set theory; the biggest positive result is due to Justin Moore:
(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).