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.

  • $\begingroup$ 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$? $\endgroup$ – Not Mike Feb 8 '18 at 0:34
  • $\begingroup$ @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.$ $\endgroup$ – bof Feb 8 '18 at 1:49
  • $\begingroup$ 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.$ $\endgroup$ – bof Feb 8 '18 at 1:54
  • $\begingroup$ @bof looking back I really don't know what I was trying to communicate. I'll just blame lack of coffee. $\endgroup$ – 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$.

  • $\begingroup$ $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. $\endgroup$ – bof Feb 8 '18 at 1:25
  • $\begingroup$ @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? $\endgroup$ – Prasun Biswas Feb 8 '18 at 1:42
  • $\begingroup$ 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. $\endgroup$ – bof Feb 8 '18 at 1:46
  • $\begingroup$ @bof, How would using a transfinite sequence help since $C\subseteq S$, so $C$ cannot have a cardinality greater than $|S|$, right? $\endgroup$ – Prasun Biswas Feb 8 '18 at 2:02
  • $\begingroup$ @bof, I guess using Zorn's lemma would be a better approach. Should I delete this answer then? $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Matt Dickau Feb 8 '18 at 2:49
  • $\begingroup$ 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. $\endgroup$ – 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.


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.