# Partially ordered set with no maximal element

If I have a partially-ordered set $S$ (of some infinite cardinality), where for every $x$ in $S$ there is a $y$ in $S$ such that $x<y$. Is there a totally-ordered subset $C$ of $S$ satisfying these conditions?

• For every $x$ in $C$ there is a $y$ in $C$ such that $x<y$
• There is no $x$ in $S$ which is greater than every element of $C$

It seems to me intuitively that this is the case, but I can't figure out how to prove it.

• When you say "...which is greater than every element of.." are you under the impression that each element in $S$ will be comparable with some member of $C$? – Not Mike Feb 8 '18 at 0:34
• @NotMike What makes you think the OP is under that impression? I think the statement is correct the way he stated it, and there is no reason to expect each element of $S$ will be comparable with some member of $C.$ – bof Feb 8 '18 at 1:49
• Are you familiar with Zorn's Lemma? It's an easy consequence of Zorn's Lemma that in every partially ordered set $S$ there is a totally ordered subset $C$ which is maximal with respect to set inclusion, that is, $C$ is not a proper subset of any totally ordered subset of $S.$ – bof Feb 8 '18 at 1:54
• @bof looking back I really don't know what I was trying to communicate. I'll just blame lack of coffee. – Not Mike Feb 8 '18 at 3:42

Since $S$ is of infinite cardinality, it is non-empty, so $\exists~x_0\in S$

Now, consider $x_1\in S$ such that $x_0\lt x_1$. Continuing with $x_k\in S$, we consider $x_{k+1}\in S$ such that $x_k\lt x_{k+1}$ ad infinitum.

Now, define $C:=\{x_i\}_{i\in I}$ where $I$ is an index set with cardinality $|S|$ (a proper subset $A\subset S$ exists such that $|A|=|S|$ since $S$ is infinite, we take $I$ to be the index set of $A$).

This is totally ordered since for any $x_i,x_j\in C$, we have $x_i\lt x_j$ for $i\leq j$

• The first condition is obviously satisfied, since for $x_n\in C$, we have $x_{n+1}\in C$ such that $x_n\lt x_{n+1}$

• For the second one, suppose there exists $y\in S$ such that $x\lt y~\forall~x\in C$. But, by the construction of $C$, it has no maximal element, a contradiction to the existence of $y$.

• $S=\mathbb R$ is an ordered set of infinite cardinality and has no maximal element. Following your instructions, I chose $x_0=0,x_1=1/2,x_2=2/3,\dots,x_n=n/(n+1),\dots.$ But $x_n\lt3$ for every element $x_n$ in my set $C=\{0/1,1/2,2/3,3/4,\dots\}.$ What did I do wrong. – bof Feb 8 '18 at 1:25
• @bof, You're correct. I suspected that a countable construction might fail. I think it should work if the index set is of cardinality $|S|$, no? – Prasun Biswas Feb 8 '18 at 1:42
• Change $\mathbb R$ to $\mathbb Q$ in my example; now $S$ is countable, but the same example works. I recomment that you use a transfinite* sequence (with transfinite ordinals as indices) or alternatively use Zorn's Lemma. – bof Feb 8 '18 at 1:46
• @bof, How would using a transfinite sequence help since $C\subseteq S$, so $C$ cannot have a cardinality greater than $|S|$, right? – Prasun Biswas Feb 8 '18 at 2:02
• @bof, I guess using Zorn's lemma would be a better approach. Should I delete this answer then? – Prasun Biswas Feb 8 '18 at 2:06

Partial answer. Assume that $S$ is a countable partially-ordered set with no maximal element. Say $S=\{s_0,s_1,s_2,\dots,s_n,\dots\}.$ Now define a sequence $c_0,c_1,c_2,\dots,c_n,\dots$ recursively, as follows. Start with any element $c_0\in S.$ Having defined $c_n,$ let $c_{n+1}=s_n$ if $s_n\gt c_n;$ otherwise, choose any $c_{n+1}\in S$ so that $c_{n+1}\gt c_n.$ Finally let $C=\{c_0,c_1,c_2,\dots,c_n,\dots\}.$ Since $c_0\lt c_1\lt c_2\lt\cdots,$ it follows that $C$ is totally ordered and satisfies your first condition. To see that the second condition is satisfied, consider any element $s\in S,$ and assume for a contradiction that $s$ is greater than every element of $C.$ Then $s=s_n$ for some $n.$ Since $s_n\gt c_n,$ it follows that $s_n=c_{n+1}\lt c_{n+2}\in C.$

That answers your question for countable sets. For the general case, you will need some form of the axiom of choice, such as Zorn's Lemma or the Well Ordering Theorem.

• For using Zorn's lemma: it states that if every totally ordered subset has an upper bound, then the poset has a maximal element. I think it is just the contrapositive that I am looking for? If the poset has no maximal element, then there is a totally ordered subset with no upper bound in the poset? – Matt Dickau Feb 8 '18 at 2:49
• Given any poset $S$ we can define another poset $P$; the elements of $P$ are the totally ordered subsets of $S,$ and the order relation in $P$ is $\subseteq.$ Zorn's lemma may not apply to $S$ but it does apply to $P,$ and so $P$ has a maximal element. A maximal element of $P$ is a maximal (with respect to set inclusion) totally ordered subset of $S,$ So Zorn's lemma implies that every partially ordered set has a maximal totally ordered subset (a.k.a. maximal chain). If $S$ has no maximal elements, then a maximal chain in $S$ satisfies your conditions. – bof Feb 8 '18 at 3:51

Any maximal chain C, will suffice for if C had a maximum,
then S would have a maximal element, which it does not.