Proving that if $A\leq_c B$ then $\chi(A)\leq_o \chi(B)$

56 Views Asked by At

By Hartog's Theorem we knoe that for every set $A$

There is a definite operation $\chi(A)$ which associates with each set $A$, a well ordered set $\chi(A) = (h(A),{\leq_{\chi(A)}}),$ such that $h(A) \nleq_c A$, i.e., there exists no injection $\pi: h(A)\longrightarrow A$. Moreover, for every well ordered set $W$, if $W \nleq_c A$, then $\chi(A) \leq_o W$.

By the proof of this theorem we know that $h(A)=\mathrm{WO}(A)/\thicksim$, where $\mathrm{WO}(A)$ is the set of all well ordered subset of $A$ and $U\thicksim V \Longleftrightarrow U\leq_o V \,\&\, V\leq_o U$.

I want to show this

If $A\leq_c B$ then $\chi(A)\leq_o \chi(B)$

I've tried different things.

First I tried to show that $h(B)\nleq_c A$ by contradiction.

Antoher aproach is show by contradicion that is imposible $\chi(B)\leq_o \chi(A)$. As thery are well ordered set this is equivalent to the existence of an orderpreserving injection $$i:\chi(B)\longleftrightarrow \chi(A).$$ But it is hard to me to find the contradiction.

What do you thing is the best aproach? Maybe there is something better?

Thank you for any help.

1

There are 1 best solutions below

3
On BEST ANSWER

First note that for initial ordinals (an initial ordinal is an ordinal which is not equipotent to any smaller ordinal, e.g. $\omega$ or $\omega_1$) being smaller as ordinals is the same as being smaller in cardinality.

You can't quite prove this statement if you don't add the requirement that $\chi(A)$ is an initial ordinal, which is the same as saying that it is the least ordinal with the wanted property. The reason is that you can choose for two countable sets different uncountable ordinals, and by symmetry arguments you get a contradiction.

So let's assume that we added the requirement that $\chi(A)$ is the least ordinal which does not inject into $A$.

Now if there was an injection from $\alpha$ into $A$, then there was one into $B$, by composing a fixed injection from $A$ into $B$. Now use the definition as "least ordinal such that ..." to conclude the wanted inequality.