mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-06-01, 19:47   #1
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default 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\}?
jinydu is offline   Reply With Quote
Old 2017-06-02, 08:01   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5D916 Posts
Default

Does PA stand for Peano Arithmetic here?
Nick is online now   Reply With Quote
Old 2017-06-02, 19:41   #3
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

Yup
jinydu is offline   Reply With Quote
Old 2017-06-03, 13:03   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

Quote:
Originally Posted by jinydu View Post
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
LaurV is offline   Reply With Quote
Old 2017-06-03, 16:15   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

27D216 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
xilman is offline   Reply With Quote
Old 2017-06-03, 16:48   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

213448 Posts
Default

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...
LaurV is offline   Reply With Quote
Old 2017-06-03, 20:07   #7
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

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
jinydu is offline   Reply With Quote
Old 2017-06-04, 02:13   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

Quote:
Originally Posted by jinydu View Post
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.
LaurV is offline   Reply With Quote
Old 2017-06-04, 07:13   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by jinydu View Post
1) Well \mathbb{Q} (the set of rationals) has height \aleph_1, despite being countable.
Quote:
Originally Posted by LaurV View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-06-04, 09:57   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

213448 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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?
LaurV is offline   Reply With Quote
Old 2017-06-04, 12:33   #11
uau
 
Jan 2017

4F16 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
uau is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 19:18.

Wed Nov 25 19:18:49 UTC 2020 up 76 days, 16:29, 4 users, load averages: 1.55, 1.52, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.