Cantor-Bendixson rank of a tree over $\omega$ : possible values and more.

512 Views Asked by At

This is exercise 5.12 from Schimmerling's "A course on set theory", which states the following:

Prove by induction that, for every ordinal $\delta$ < $\omega_1$, there is a tree $\mathcal T$ on $\omega $ whose Cantor-Bendixson rank is $\delta$ and $\mathcal T^\delta$ = $\emptyset$.

It's the "and..." part that's been bugging me.

Take $\delta$ = $\omega$ and suppose $\mathcal T$ satisfies those conditions.

Then, for each $\mathcal n < \omega$, $$ \mathcal T^n \neq \emptyset, $$ otherwise we would have $ \mathcal T^{n+1} = (\mathcal T^n)' = \mathcal T^n.$

So each $\mathcal T^n \subseteq \omega ^{<\omega}$ is a non-empty tree, and thus $$<> \space \in \space \mathcal T^n, $$ where $<> $ denotes the empty sequence.

We get $$ <> \space \in \space \mathcal T^\omega, $$ since $ \mathcal T^\omega = \bigcap\limits_{\mathcal n < \omega} \mathcal T^n $ by definition, and we have a contradiction.

We could take any limit ordinal $\delta < \omega_1 $ and get the same contradiction.

What's wrong here?

Thanks.


edit: Some clarifications, all are straight from Ernst Schimmerling's book. If more are needed please ask.

For each $s \in \omega ^{<\omega}$, with $ k < \omega $ being the domain of $s $, define $$ N_s = \{ x \in \omega^{\omega} : x {\restriction_k} = s \}. $$

For a tree $ \mathcal T $ on $\omega $ define its set of infinite branches, $$ [\mathcal T] = \{ x \in \omega^{\omega} : x {\restriction_n} \in \mathcal T \space \forall n < \omega \}. $$

Then the Cantor-Bendixson derivative of $\mathcal T$ is $$ \mathcal T' := \{s \in \mathcal T : N_s \cap [\mathcal T] \space has \space at \space least \space two \space elements \}. $$

For a tree $ \mathcal T $ on $\omega $ we can define the following descending sequence: $$ \mathcal T^0 = \mathcal T, $$ $$ \mathcal T^{\alpha + 1} = \mathcal (T^\alpha)' $$ for any ordinal $\alpha$ and, for a limit ordinal $\beta$, $$ \mathcal T^\beta = \bigcap\limits_{\mathcal \alpha < \beta} \mathcal T^\alpha. $$

Those are all trees on $\omega$.

The Cantor-Bendixson rank of $\mathcal T $ is defined to be the least ordinal $\delta $ such that $$ \mathcal T^{\delta + 1} = \mathcal T^\delta. $$ One proves that the above equality is valid for some $\delta < \omega_1$, so the CB rank of $\mathcal T $ is a countable ordinal.

Sorry if i'm writing too much but this is the only context where i've studied these things (trees, CB rank etc...).

1

There are 1 best solutions below

1
On

(This is very late, and the OP hasn’t been around in several years, but I’d like to get the question off the unanswered list.)

You are correct in thinking that if $\alpha<\omega_1$ is a limit ordinal, there is no tree $\mathcal{T}$ of Cantor-Bendixson rank $\alpha$ such that $\mathcal{T}^\alpha=\varnothing$; the best that we can hope for is a tree $\mathcal{T}$ of Cantor-Bendixson rank $\alpha+1$ such that $\mathcal{T}^\alpha=\{\langle\rangle\}$. And in fact this is possible: for each $\alpha<\omega_1$ there is a tree $\mathcal{T}_\alpha$ such that $\mathcal{T}_\alpha^\alpha=\{\langle\rangle\}$. Of course this means that for each successor ordinal $\alpha+1<\omega_1$ the tree $\mathcal{T}_\alpha$ is of Cantor-Bendixson rank $\alpha+1$ and has empty $(\alpha+1)$-st Cantor-Bendixson derivative.

As one would expect, the trees $\mathcal{T}_\alpha$ can be constructed recursively, but some notation helps: for $\mathcal{S}\subseteq\omega^{<\omega}\setminus\{\langle\rangle\}$ and $p\in\omega^{<\omega}$ let $p^{\frown}\mathcal{S}=\{p^\frown s:s\in\mathcal{S}\}$.

Clearly $\mathcal{T}_0=\{\langle\rangle\}$. Given $\mathcal{T}_\alpha$ for some $\alpha<\omega_1$, let

$$\mathcal{T}_{\alpha+1}=\{\langle\rangle\}\cup\bigcup_{n\in\omega}\Big(\left(0^{n+1}\right)^{\frown}\mathcal{T}_\alpha\Big)\cup\bigcup_{n\in\omega}\Big(\left(1^{n+1}\right)^{\frown}\mathcal{T}_\alpha\Big)\,;$$

then

$$\mathcal{T}_{\alpha+1}^\alpha=\{\langle\rangle\}\cup\{0^{n+1}:n\in\omega\}\cup\{1^{n+1}:n\in\omega\}=\mathcal{T}_1\,,$$

so $\mathcal{T}_{\alpha+1}^{\alpha+1}=\{\langle\rangle\}$, as desired.

Now suppose that $\alpha<\omega_1$ is a limit ordinal and that we have constructed $\mathcal{T}_\xi$ for all $\xi<\alpha$. Let $\langle\alpha_n:n\in\omega\rangle$ be a strictly increasing sequence of ordinals whose limit is $\alpha$, and let

$$\mathcal{T}_\alpha=\{\langle\rangle\}\cup\bigcup_{n\in\omega}\big(\langle n\rangle^\frown\mathcal{T}_{\alpha_n}\big)\,;$$

clearly $\mathcal{T}_\alpha^\alpha=\{\langle\rangle\}$.

It’s not too hard to picture what’s going on here. $\mathcal{T}_1$ is just a pair of branches, $\{0^n:n\in\omega\}$ and $\{1^n:n\in\omega\}$, intersecting at the root $\langle\rangle$. $\mathcal{T}_{\alpha+1}$ is built by making each non-root node of $\mathcal{T}_1$ the root of a tree isomorphic to $\mathcal{T}_\alpha$. $\mathcal{T}_\alpha$ for limit $\alpha$ is built from the bush $\{s\in\omega^{<\omega}:|s|\le 1\}$ by making each node $\langle n\rangle$ the root of a tree isomorphic to $\mathcal{T}_{\alpha_n}$.