2
$\begingroup$

Hi,

In Chang & Keisler "Model Theory" it is claimed that the theory of a one-to-one function of A onto A with no finite cycles is $\omega_1$- categorical (page 140). Why is that, and is there a reference for this?

$\endgroup$

1 Answer 1

7
$\begingroup$

Let $A$ and $B$ be two models of size $\omega_1$. In both A and B, being in the same cycle is an equivalence relation. Each equivalence class has size $\omega$. So there are $\omega_1$ many equivalence classes in both A and B. Fix a bijection between the equivalence classes in A and B. You can use this to make an isomorphism between A and B because every single equivalence class in either A and B is isomorphic to every other.

$\endgroup$
6
  • 1
    $\begingroup$ You left out important detail: because $f$ is onto, these equivalence classes are all doubly infinite paths. So they are all isomorphic to each other. $\endgroup$ Apr 1, 2011 at 22:13
  • $\begingroup$ - What do you mean by doubly infinite paths? aren't they isomorphic since all of them of size $ \omega $ ? - Can't we have in f_1 a cycle of size $ \omega_1 $ while in f_2 all cycles are of size $ \omega $? $\endgroup$
    – Eran
    Apr 2, 2011 at 14:28
  • $\begingroup$ David's point is just that cycle keeps going in the direction of repeated applications of f: $f(x), f(f(x)), f(f(f(x))), \ldots$ and in the direction of repeated applications of $f^{-1}$: $f^{-1}(x), f^{-1}(f^{-1}(x)), f^{-1}(f^{-1}(f^{-1}(x))), \ldots$ $\endgroup$ Apr 2, 2011 at 16:06
  • $\begingroup$ You can't have an uncountable cycle. Let f be your function, and x some point in your cycle. Then the cycle is exactly $\{ f^n (x) : n \in \mathbb{Z}\}$, which is a countable set. $\endgroup$ Apr 2, 2011 at 16:06
  • $\begingroup$ Do we need $f$ to be onto? if $f^{i}(x)$ is the i'st element in the cycle for i limit, then $f^{-1}(f^{i}(x))$ is an $f^{j}(x)$ for some j<i which is a contradiction since $f(f^{j}(x))$ is another element in between (so we can't have i limit). $\endgroup$
    – Eran
    Apr 2, 2011 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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