Heights of Models of PA

jinydu · 2017-06-01, 19:47

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\}$ ?

Nick · 2017-06-02, 08:01

Does PA stand for Peano Arithmetic here?

jinydu · 2017-06-02, 19:41

Yup

LaurV · 2017-06-03, 13:03

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...

xilman · 2017-06-03, 16:15

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.

LaurV · 2017-06-03, 16:48

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...

jinydu · 2017-06-03, 20:07

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$ .

LaurV · 2017-06-04, 02:13

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.

CRGreathouse · 2017-06-04, 07:13

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.

LaurV · 2017-06-04, 09:57

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?

uau · 2017-06-04, 12:33

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.

2017-06-01, 19:47	#1
jinydu Dec 2003 Hopefully Near M48 6DE₁₆ 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-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-02, 08:01	#2
Nick Dec 2012 The Netherlands 1,583 Posts	Does PA stand for Peano Arithmetic here?

2017-06-02, 19:41	#3
jinydu Dec 2003 Hopefully Near M48 2×3×293 Posts	Yup

2017-06-03, 16:48	#6
LaurV Romulan Interpreter Jun 2011 Thailand 3×43×71 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...