Can every infinite set be partially ordered in a way that does not have maximal elements?

Question

I hope this isn't a dumb question: I'm no mathematician.

Let $S$ be a an infinite set in the sense that it is nonempty and there is no natural number $n$ such that $S$ can be put in 1-1 correspondence with $\{1, \dots, n\}$.

Can it be proven that there exists some partial order $\leq$ on $S$ having no maximal elements, i.e., such that for every $a \in S$, there is some $b$ where $a \leq b$?

(Of course, not every partial order on $S$ will lack maximal elements; e.g., for the infinite set of the closed internal [0, 1], 1 will be maximal, but of course the same set could be partially ordered with a different relation, i.e., putting 1 before all the other members, and then there is no maximal element. The question is whether there must be at least one such ordering.)

I'm fairly sure this can be proven if you assume the axiom of choice, but can it be proven without it?

Answer 1

The answer given by quasi is correct - if we assume the axiom of choice. Without choice, things get more complicated: there can be infinite sets which don't admit injections from $\mathbb{N}$ (that is, such that we can't in fact "pick distinct $x_1,x_2, ...$" to set up the situation in quasi's answer).

In fact, it turns out to be consistent with ZF (= set theory without choice) that there are infinite sets which cannot be partially ordered without maximal elements. The proof of this is via forcing, which is unfortunately too complicated to get into here.

---

EDIT: In particular, any amorphous set has this property.

Suppose $A$ is amorphous and $<_A$ is a partial ordering of $A$ with no maximal element. Then for each $a\in A$, the set $\{x\in A: a<_Ax\}$ is infinite, hence cofinite since $A$ is amorphous.

Think about the function $d$ sending each $a\in A$ to $d(a)=\vert\{x\in A: a\not<_Ax\}\vert$. By the above, $d:A\rightarrow\mathbb{N}$, and it's clear that the range of $d$ is unbounded (if $x<_Ay$ then $d(x)<d(y)$). If we partition the range of $d$ into two infinite pieces (this can be done, since the range is infinite and well-orderable), then pulling this partition back along $d$ gives a partition of $A$ into two disjoint infinite sets, contradicting the amorphousness of $A$.

Answer 2

Yes, just let $$x_1 < x_2 < x_3 < \cdots$$ and let all the other elements (if any) be less than $x_1$, but not comparable with each other.

Note:$\;$As Noah Schweber points out in a comment, to guarantee that we can select a countably infinite sequence $x_1,x_2,x_3,...$ of distinct elements of $S$, we do need some form of the Axiom of Choice.