If $(A,\preccurlyeq)$ is a linear ordering such that $|\{y\in A\mid y\preccurlyeq x\}| < \aleph_\gamma$ for all $x\in A$, then $|A|\le\aleph_\gamma$

52 Views Asked by At

If $(A,\preccurlyeq)$ is a linear ordering such that $|\{y\in A\mid y\preccurlyeq x\}| \le \aleph_\gamma$ for all $x\in A$, then $|A|\le\aleph_\gamma$.

Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help!


My attempt:

Lemma: If $|S| \le \aleph_\gamma$ and, for all $A\in S$, $|A|\le \aleph_\gamma$, then $|\bigcup S|\le \aleph_\gamma$.

By Well-Ordering Principle, there is a well-ordering $\preccurlyeq'$ on $A$. Let $V$ be the class of all sets and $\rm Ord$ be the class of all ordinals. First, we define function $f:\mathcal{P}(A)\setminus\{\emptyset\} \to A$ by $f(X)=\min X$ (with regard to $\preccurlyeq'$).

Next, we define function $G:V \to V$ by $G(x)=f(\{a\in A \mid \forall t\in {\rm ran}(x):t \prec a\})$ if $x$ is a function and $\{a\in A \mid \forall t\in {\rm ran}(x):t \prec a\} \neq \emptyset$, and $G(x)=A$ otherwise. By Transfinite Recursion Theorem, there is a function $F: {\rm Ord} \to V$ such that $F(\alpha)=G(F \restriction \alpha)$ for all $\alpha \in {\rm Ord}$.

It is not hard to verify (by Hartogs number) that $F(\alpha)= A$ for some ordinal $\alpha$. Let $\lambda=\min\{\alpha \in {\rm Ord} \mid F(\alpha)= A\}$. Then $F \restriction \lambda$ is a strictly increasing function with ${\rm ran}(F \restriction \lambda)={\rm ran}(F )\setminus \{A\} \subseteq A$.

We have $F(\lambda)=A$, so $\{a\in A \mid \forall t\in {\rm ran}(F \restriction \lambda):t \prec a\} = \emptyset$. As $(A,\preccurlyeq)$ is linear ordering, it follows that, for every $a\in A$, there exists $\alpha < \lambda$ such that $a \preccurlyeq F(\alpha)$. Hence $S=\bigcup_{\alpha<\lambda}\{a \in A\mid a \preccurlyeq F(\alpha)\}$.

We have $|\{a \in A\mid a \preccurlyeq F(\alpha)\}| \le \aleph_\gamma$ for all $\alpha<\lambda$ by assumption. Moreover, $|\lambda| =|{\rm ran}(F \restriction \lambda)|=|{\rm ran}(F )\setminus \{A\}| \le |A|\le \aleph_\gamma$. Hence $|\bigcup S|=|\bigcup_{\alpha<\lambda}\{a \in A\mid a \preccurlyeq F(\alpha)\}| \le \aleph_\gamma$ by Lemma. This completes the proof.


Update: Thanks to @Asaf's answer, I figure out that the theorem is incorrectly stated. Instead, it should be

If $(A,\preccurlyeq)$ is a linear ordering such that $|\{y\in A\mid y\preccurlyeq x\}| < \aleph_\gamma$ for all $x\in A$, then $|A|\le\aleph_\gamma$.

My fix for the wrong part at the end:

We have $|\{a \in A\mid a \preccurlyeq F(\alpha)\}| \le \aleph_\gamma$ for all $\alpha<\lambda$ by assumption. Moreover, $\lambda \le \aleph_\gamma$. If not, $\aleph_\gamma < \lambda$. We have $\aleph_\gamma=|\omega_\gamma|=|{\rm ran}(F \restriction \omega_\gamma)|$ and ${\rm ran}(F \restriction \omega_\gamma) \subseteq \{y \in A \mid y \le F (\omega_\gamma)\}$. Thus $\aleph_\gamma \le |\{y \in A \mid y \le F (\omega_\gamma)\}|$. This contradicts our assumption. Hence $|\bigcup S|=|\bigcup_{\alpha<\lambda}\{a \in A\mid a \preccurlyeq F(\alpha)\}| \le \aleph_\gamma$ by Lemma. This completes the proof.

1

There are 1 best solutions below

1
On BEST ANSWER

The statement itself is wrong. $\omega_1$ itself is an example of a linear ordering where for every $x<\omega_1$, $|y\in\omega_1\mid y\leq x\}|\leq\aleph_0$, but $|\omega_1|=\aleph_1>\aleph_0$.

You can prove, however, that $\aleph_{\gamma+1}$ is the upper limit. To do this, first note that there is a well-ordered (under $\preccurlyeq$!) subset of $A$ which is not bounded from above. Then prove that this cannot have order type greater than $\omega_{\gamma+1}$. Now you can apply to your lemma and finish the proof.

Alternatively, you can replace $|\{y\in A\mid y\preccurlyeq x\}|\leq\aleph_\gamma$ by a strict inequality to obtain a true statement again.