mersenneforum.org Heights of Models of PA
 Register FAQ Search Today's Posts Mark Forums Read

 2017-06-01, 19:47 #1 jinydu     Dec 2003 Hopefully Near M48 110110111102 Posts 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 $M$ a countable model of $PA$, let $\text{height}(M)=\sup\{\alpha:\exists f:\alpha\rightarrow M\text{ order preserving embedding}\}$ Then - $\aleph_0\leq\text{height}(M)\leq\aleph_1$ with $\text{height}(M)=\aleph_0\leftrightarrow M=\mathbb{N}$ - By Compactness + Downward Loweinheim-Skolem, for every $\alpha<\aleph_1$ there is $M$ with $\text{height}(M)\geq\alpha$ Questions - Can we get $\text{height}(M)=\aleph_1$? - Can we get $\alpha<\text{height}(M)<\aleph_1$ for arbitrarily large countable $\alpha$? - Anything else interesting to say about $\{\text{height}(M):M\text{ countable model of }PA\}$?
 2017-06-02, 08:01 #2 Nick     Dec 2012 The Netherlands 31328 Posts Does PA stand for Peano Arithmetic here?
 2017-06-02, 19:41 #3 jinydu     Dec 2003 Hopefully Near M48 6DE16 Posts Yup
2017-06-03, 13:03   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

52×7×53 Posts

Quote:
 Originally Posted by jinydu Questions - Can we get $\text{height}(M)=\aleph_1$? - Can we get $\alpha<\text{height}(M)<\aleph_1$ for arbitrarily large countable $\alpha$? - Anything else interesting to say about $\{\text{height}(M):M\text{ countable model of }PA\}$?
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... Some guy like Cantor or Frankel may be able to tell more... hehe. For sure not me...

Last fiddled with by LaurV on 2017-06-03 at 13:05

2017-06-03, 16:15   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

25·331 Posts

Quote:
 Originally Posted by LaurV 2. is there anything "in between"? I don't know about that.
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.

Last fiddled with by xilman on 2017-06-03 at 16:15 Reason: Fix tag

 2017-06-03, 16:48 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 52·7·53 Posts 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...
 2017-06-03, 20:07 #7 jinydu     Dec 2003 Hopefully Near M48 2·3·293 Posts 1) Well $\mathbb{Q}$ (the set of rationals) has height $\aleph_1$, despite being countable. One can show by transfinite induction that every countable $\alpha$ embeds into $\mathbb{Q}$, and taking the $\sup$ of all such $\alpha$ yields $\aleph_1$. The only problem with this example? It's not a model of $PA$. 2) No question about $CH$ here, as this question is about $\aleph_1$. Last fiddled with by jinydu on 2017-06-03 at 20:09
2017-06-04, 02:13   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

52·7·53 Posts

Quote:
 Originally Posted by jinydu 1) Well $\mathbb{Q}$ (the set of rationals) has height $\aleph_1$, despite being countable.
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.

2017-06-04, 07:13   #9
CRGreathouse

Aug 2006

2×29×103 Posts

Quote:
 Originally Posted by jinydu 1) Well $\mathbb{Q}$ (the set of rationals) has height $\aleph_1$, despite being countable.
Quote:
 Originally Posted by LaurV 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.
I'm not sure what the model-theoretic definition of "height" is, but I don't think it's the same as cardinality.

2017-06-04, 09:57   #10
LaurV
Romulan Interpreter

Jun 2011
Thailand

52×7×53 Posts

Quote:
 Originally Posted by CRGreathouse I'm not sure what the model-theoretic definition of "height" is, but I don't think it's the same as cardinality.
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?

2017-06-04, 12:33   #11
uau

Jan 2017

1278 Posts

Quote:
 Originally Posted by LaurV 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?
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.