Welcome to MathOverflow

Question

1

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?

flag	asked Apr 1 2011 at 21:07 Eran 383●2●8

Richard Dore · Accepted Answer · 2011-04-01 21:18:04Z UTC

6

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.

answered Apr 1 2011 at 21:18

Richard Dore
2,395●2●16●29

1

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. – David Harris Apr 1 2011 at 22:13

- 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 $? – Eran Apr 2 2011 at 14:28

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$ – Richard Dore Apr 2 2011 at 16:06

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. – Richard Dore Apr 2 2011 at 16:06

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). – Eran Apr 2 2011 at 21:46

show 1 more comment

Omega_1 Categorical Theory

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.