Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
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 '11 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 '11 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 '11 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 '11 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 '11 at 21:46
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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