Heights of Models of PA
 

This question is inspired by an incomplete solution of mine to a final exam problem a few years back.

For [tex]M[/tex] a countable model of [tex]PA[/tex], let [tex]\text{height}(M)=\sup\{\alpha:\exists f:\alpha\rightarrow M\text{ order preserving embedding}\}[/tex]

Then
- [tex]\aleph_0\leq\text{height}(M)\leq\aleph_1[/tex] with [tex]\text{height}(M)=\aleph_0\leftrightarrow M=\mathbb{N}[/tex]
- By Compactness + Downward Loweinheim-Skolem, for every [tex]\alpha<\aleph_1[/tex] there is [tex]M[/tex] with [tex]\text{height}(M)\geq\alpha[/tex]

Questions
- Can we get [tex]\text{height}(M)=\aleph_1[/tex]?
- Can we get [tex]\alpha<\text{height}(M)<\aleph_1[/tex] for arbitrarily large countable [tex]\alpha[/tex]?
- Anything else interesting to say about [tex]\{\text{height}(M):M\text{ countable model of }PA\}[/tex]?

Does PA stand for Peano Arithmetic here?

Yup

[QUOTE=jinydu;460260]
Questions
- Can we get [tex]\text{height}(M)=\aleph_1[/tex]?
- Can we get [tex]\alpha<\text{height}(M)<\aleph_1[/tex] for arbitrarily large countable [tex]\alpha[/tex]?
- Anything else interesting to say about [tex]\{\text{height}(M):M\text{ countable model of }PA\}[/tex]?[/QUOTE]
1. I don't think so, as alef1 is not countable. For any n no matter how big, but finite, combinations like n*alef0, or alef0^n is still countable. But n^alef0 (even 2^alef0) is not.
2. is there anything "in between"? I don't know about that.
3. yes, it is cute... :razz: Some guy like Cantor or Frankel may be able to tell more... hehe. For sure not me...

[QUOTE=LaurV;460409]
2. is there anything "in between"? I don't know about that. [/QUOTE]Which would you prefer to have? Choose one and run with it.

The "continuum hypothesis", that there is nothing in between, has been shown to be undecidable in ZFC. You can add it as an axiom, if you wish, or you can add its negation and each choice will lead to a consistent system.

Hmm.. we have to google for this and read the "news" about... First, we don't know the English terms, and then we have a lot of lacunes (why is this red? is it lacunas? or lacunae?) in the math itself. We were once good at these things (set theory) but we feel like few milenia passed since...

1) Well [tex]\mathbb{Q}[/tex] (the set of rationals) has height [tex]\aleph_1[/tex], despite being countable. One can show by transfinite induction that every countable [tex]\alpha[/tex] embeds into [tex]\mathbb{Q}[/tex], and taking the [tex]\sup[/tex] of all such [tex]\alpha[/tex] yields [tex]\aleph_1[/tex].

The only problem with this example? It's not a model of [tex]PA[/tex].

2) No question about [tex]CH[/tex] here, as this question is about [tex]\aleph_1[/tex].

[QUOTE=jinydu;460445]1) Well [tex]\mathbb{Q}[/tex] (the set of rationals) has height [tex]\aleph_1[/tex], despite being countable.[/QUOTE]
That is new for me, and I think is false. According with my (old) memory, countable means \(\aleph_0\). There is a bijection between Q and N, and I still remember my high school teacher, Mrs. Diaconu, paining that diagonal-counting matrix on the blackboard.

[QUOTE=jinydu;460445]1) Well [tex]\mathbb{Q}[/tex] (the set of rationals) has height [tex]\aleph_1[/tex], despite being countable.[/QUOTE]

[QUOTE=LaurV;460481]That is new for me, and I think is false. According with my (old) memory, countable means \(\aleph_0\). There is a bijection between Q and N, and I still remember my high school teacher, Mrs. Diaconu, paining that diagonal-counting matrix on the blackboard.[/QUOTE]

I'm not sure what the model-theoretic definition of "height" is, but I don't think it's the same as cardinality.

[QUOTE=CRGreathouse;460490]I'm not sure what the model-theoretic definition of "height" is, but I don't think it's the same as cardinality.[/QUOTE]
Well, the height, as I understand it, is the cardinal of the longest chain that preserves the order. I may be totally wrong here, but I can't see how I can make a chain in Q that preserves the order and yet, have more elements than Q itself. What I am missing?

[QUOTE=LaurV;460491]Well, the height, as I understand it, is the cardinal of the longest chain that preserves the order. I may be totally wrong here, but I can't see how I can make a chain in Q that preserves the order and yet, have more elements than Q itself. What I am missing?[/QUOTE]

Height (as defined in the first post in this thread) is the sup of all the embeddable ordinals. You can't embed a larger cardinality, but you can embed all countable ordinals. Thus the sup is the first ordinal that is NOT countable.