# Cardinality of a some linear ordering is at most that of a given cardinal?

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

-
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

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.

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

-

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

-