Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is an intuitive idea that I've used for a while, but don't know how to explain formally.

Suppose $(A,\prec)$ is some linear ordering, and each initial segment of $A$ has cardinality strictly smaller than $\kappa$ for some cardinal $\kappa$. Then $|A|\leq\kappa$.

This makes sense, since you can just take bigger and bigger initial segments whose cardinalities "approach" $\kappa$. But more formally, why is $|A|\leq\kappa$?

share|cite|improve this question
As mean downvoters said, my answer is wrong but I knew that to begin with and I even mentioned it in my answer that I wasn't sure I was right. Although I assumed that the segments had cardinality not strictly smaller than $\kappa$. I am wondering : does the result still hold if we replace strictly by not strictly? – Patrick Da Silva Dec 9 '11 at 20:33
@PatrickDaSilva: I'm not mean, I also undid my downvote after your edit. I disagree with you on whether or not the answer should stay, but that's irrelevant. To your question, consider $\omega_1$. Every initial segment is countable but the whole order is uncountable. – Asaf Karagila Dec 9 '11 at 20:39
up vote 5 down vote accepted

The statement is true. Suppose $(A,\lt)$ is a linear ordering and every proper initial segment of $A$ has size less than a cardinal $\kappa$. Then it follows that $|A|\leq\kappa$.

To see this, notice first that we may assume $A$ is infinite. Let $\gamma$ be the smallest cardinal such that there is a cofinal subset $B\subset A$ of order type $\gamma$. This is called the cofinality of the order $(A,\lt)$, and it follows that $\gamma$ is a regular cardinal. Note that $\gamma\leq\kappa$, since if $\gamma\gt\kappa$, then $\gamma$ would have a $\kappa^{\rm th}$ element, and so $A$ would have an initial segment with at least $\kappa$ many predecessors, contrary to assumption. Now simply observe that $A$ is the union of $\gamma$ many sets, each of size less than $\kappa$, namely, the predecessors of the elements of $B$. It follows that $A$ has size at most $\kappa^2=\kappa$, as desired.

share|cite|improve this answer
Thanks all${}$. – Saint Louie Dec 9 '11 at 22:49

A subset $Y \subseteq X$ of a linear ordering is cofinal if for any element $x\in X$ there exists $y\in Y$ such that $y \geq x$.

1) Suppose there is a set of cardinality at most $\kappa$ which is cofinal in $X$. In this case, you can write $X$ as union of at most $\kappa$ invervals, each of cardinality at most $\kappa$, since $\kappa \cdot \kappa = \kappa$, the result follows.

2) Suppose there is no such set. By some well-known theorem (by Hausdorff I think) there is a well ordered cofinal subset $A$ (proof), and it must have cardinality $\lambda > \kappa$. Take the $\kappa+1$-th element of $A$, its initial segment has at least $\kappa$ elements, contradiction.

share|cite|improve this answer

The statement is true.

Suppose that $|A|>\kappa$. For each $x\in A$, $A$ is the disjoint union of $(\leftarrow,x)$, $\{x\}$, and $(x,\to)$, and $|\{x\}|,|(\leftarrow,x)|<\kappa$, so $|(x,\to)|>\kappa$. In other words, every ‘tail’ of $A$ has cardinality greater than $\kappa$. I’ll use this to construct a strictly increasing function $\varphi:\kappa^+\to A$.

Let $\varphi(0)\in A$ be arbitrary. Suppose that $\eta<\kappa^+$, and I’ve already chosen $\varphi(\xi)\in A$ for each $\xi<\eta$ in such a way that $\varphi\upharpoonright\eta$ is strictly increasing. Let $$P_\eta=\bigcup_{\xi<\eta}\big(\leftarrow,\varphi(\xi)\big)\;;$$ by hypothesis $\left|\big(\leftarrow,\varphi(\xi)\big)\right|<\kappa$ for each $\xi<\eta$, and $|\eta|\le\kappa$, so $|P_\eta|\le\kappa$. Thus, $A\setminus P_\eta\ne\varnothing$, and we can choose $\varphi(\eta)\in A\setminus P_\eta$. Clearly $\varphi(\eta)>\varphi(\xi)$ for $\xi<\eta$, so the induction goes through to $\kappa^+$.

But this is impossible, because $\varphi(\kappa)$ has at least $\kappa$ predecessors in $\langle A,\prec\rangle$, namely, $\{\varphi(\xi):\xi<\kappa\}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.