2
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ What? Of course there are sets which cannot be partially ordered without a maximum and a re not amorphous. The disjoint union of two copies of an amorphous set, for example. $\endgroup$
    – Asaf Karagila
    Commented May 11, 2018 at 22:46
  • $\begingroup$ @AsafKaragila Yeah I just deleted that part; not sure what came over me. :P $\endgroup$ Commented May 11, 2018 at 22:46
  • $\begingroup$ I think it would still be useful to mention amorphous sets somewhere in the answer. At least from my point of view, I cannot really follow forcing arguments, but I think I might be able to prove that an amorphous set, if one exists, cannot be ordered without a maximal element. So giving that hint (which I found in the history) would at least allow me to delineate my ignorance. $\endgroup$ Commented May 11, 2018 at 23:01
  • $\begingroup$ @HenningMakholm I've added the proof that amorphous sets are "self-maximizing." $\endgroup$ Commented May 11, 2018 at 23:46
  • $\begingroup$ @NoahSchweber: Thanks! Simple in hindsight ... $\endgroup$ Commented May 12, 2018 at 0:17
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Maybe you should make a comment that one can always have a countably infinite proper subset of any infinite set. (so that there are any other elements). $\endgroup$
    – fleablood
    Commented May 11, 2018 at 22:03
  • 1
    $\begingroup$ It need not be proper. We just need a countably infinite subset. $\endgroup$
    – quasi
    Commented May 11, 2018 at 22:08
  • $\begingroup$ But you need "all the other elements". If it isn't proper then there aren't any other elements.... and ... oh, we don't need any other elements. Well, okay. But maybe a comment that you can always take a countably infinite subset. This does not require axiom of choice but just inductive nature of the naturals. $\endgroup$
    – fleablood
    Commented May 11, 2018 at 22:37
  • $\begingroup$ @fleablood Actually, that does require the axiom of choice: without choice, we can have infinite sets which are Dedekind-finite (or even amorphous sets). $\endgroup$ Commented May 11, 2018 at 22:43
  • $\begingroup$ And with the axiom of choice, you can even construct a well-ordering with no maximal element on the set: just take $\kappa$ to be the von Neumann ordinal corresponding to the cardinality (which as an infinite cardinal is not a successor ordinal) and then choose a bijection $X \to \kappa$, then transfer the well-ordering on $\kappa$ back to $X$. $\endgroup$ Commented May 11, 2018 at 23:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .