Mdthbs

Withdrew when Jimmy met up with Heath

Is it okay for a ticket seller to grab a tip in the USA?

Can a fight scene, component-wise, be too complex and complicated?

A tool to replace all words with antonyms

Why isn’t SHA-3 in wider use?

Double redundancy for the Saturn V LVDC computer memory, how were disagreements resolved?

Three legged NOT gate? What is this symbol?

Why did Gandalf use a sword against the Balrog?

Question about "Approaching Zero and Limits" in the Intuitive Proof of the Derivative of Sine

What game uses dice with sides powers of 2?

Adding CSV file with lat/long to map in different CRS in QGIS

Understanding the point of a kölsche Witz

Shoud I use Kodak Vision 500T as 400 ISO or 800 ISO?

Different inverter (logic gate) symbols

During the Space Shuttle Columbia Disaster of 2003, Why Did The Flight Director Say, "Lock the doors."?

Write an interpreter for *

Why is transplanting a specific intact brain impossible if it is generally possible?

Is refreshing multiple times a test case for web applications?

What is my malfunctioning AI harvesting from humans?

How to mark beverage cans in a cooler for a blind person?

changing number of arguments to a function in secondary evaluation

AsyncDictionary - Can you break thread safety?

What does this double-treble double-bass staff mean?

Why are Gatwick's runways too close together?

$n$-types of the theory of natural numbers?

Question about the proof of consistency iff satisfiability of a theoryAn exercise on (isolated) typesAbout the proof of a test for quantifier elimination.$kappa$-saturated, $1$-types - $n$-typesComplete $n$-types for the theories of $( mathbb Z , s )$ and $( mathbb Z , s , < )$A test for quantifier eliuminationTypes realized in an atomic modelThe number of non isomorphic homogenous models of T

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}

4

1

$begingroup$

In David Marker's introduction to model theory, one corollary of theorem 4.2.11 is that, for $T$ a complete theory in a countable language, if $mid S_n(T)mid<2^{aleph_0}$, then $T$ has a prime model (where $S_n(T)$ is the set of complete $n$-types mutually satisfiable with $T$). At the end of the section he then comments:

We note that it is possible for there to be prime models even if $mid S_n(T)mid=2^{aleph_0}$. For example, $Th(mathbb{N}, +, cdot, <, 0, 1)$ and RCF have prime models.

I'm struggling with the first example in this statement; it's not at all clear to me why the set of complete $n$-types mutually satisfiable with $Th(mathbb{N}, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:

What do the complete $n$-types of $Th(mathbb{N}, +, cdot, <, 0, 1)$ look like?

First I'm trying to ascertain if $T=Th(mathbb{N}, +, cdot, <, 0, 1)$ has quantifier elimination (just arguing by the test in corollary 3.1.12). If it does, then wouldn't the definable subsets of any model of $T$ just be finite boolean combinations of intervals and finite sets? In which case any complete $n$-type would have to be uniquely determined by such a boolean combination, and so the set of $n$-types would be countable.

Clearly there's something wrong in that argument, but I don't know where; can anyone give me some insight here?

edit: On second thought I don't think $T$ has quantifier elimination; for instance, it's clear that $phi(v):=exists xspace v=2cdot x$ defines an infinite and coinfinite subset of $mathbb{N}$, which would contradict quantifier elimination.

logic model-theory universal-algebra

share|cite|improve this question

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

$endgroup$

add a comment | 

4

1

$begingroup$

In David Marker's introduction to model theory, one corollary of theorem 4.2.11 is that, for $T$ a complete theory in a countable language, if $mid S_n(T)mid<2^{aleph_0}$, then $T$ has a prime model (where $S_n(T)$ is the set of complete $n$-types mutually satisfiable with $T$). At the end of the section he then comments:

We note that it is possible for there to be prime models even if $mid S_n(T)mid=2^{aleph_0}$. For example, $Th(mathbb{N}, +, cdot, <, 0, 1)$ and RCF have prime models.

I'm struggling with the first example in this statement; it's not at all clear to me why the set of complete $n$-types mutually satisfiable with $Th(mathbb{N}, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:

What do the complete $n$-types of $Th(mathbb{N}, +, cdot, <, 0, 1)$ look like?

First I'm trying to ascertain if $T=Th(mathbb{N}, +, cdot, <, 0, 1)$ has quantifier elimination (just arguing by the test in corollary 3.1.12). If it does, then wouldn't the definable subsets of any model of $T$ just be finite boolean combinations of intervals and finite sets? In which case any complete $n$-type would have to be uniquely determined by such a boolean combination, and so the set of $n$-types would be countable.

Clearly there's something wrong in that argument, but I don't know where; can anyone give me some insight here?

edit: On second thought I don't think $T$ has quantifier elimination; for instance, it's clear that $phi(v):=exists xspace v=2cdot x$ defines an infinite and coinfinite subset of $mathbb{N}$, which would contradict quantifier elimination.

logic model-theory universal-algebra

share|cite|improve this question

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

$endgroup$

add a comment | 

$begingroup$

In David Marker's introduction to model theory, one corollary of theorem 4.2.11 is that, for $T$ a complete theory in a countable language, if $mid S_n(T)mid<2^{aleph_0}$, then $T$ has a prime model (where $S_n(T)$ is the set of complete $n$-types mutually satisfiable with $T$). At the end of the section he then comments:

We note that it is possible for there to be prime models even if $mid S_n(T)mid=2^{aleph_0}$. For example, $Th(mathbb{N}, +, cdot, <, 0, 1)$ and RCF have prime models.

I'm struggling with the first example in this statement; it's not at all clear to me why the set of complete $n$-types mutually satisfiable with $Th(mathbb{N}, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:

What do the complete $n$-types of $Th(mathbb{N}, +, cdot, <, 0, 1)$ look like?

First I'm trying to ascertain if $T=Th(mathbb{N}, +, cdot, <, 0, 1)$ has quantifier elimination (just arguing by the test in corollary 3.1.12). If it does, then wouldn't the definable subsets of any model of $T$ just be finite boolean combinations of intervals and finite sets? In which case any complete $n$-type would have to be uniquely determined by such a boolean combination, and so the set of $n$-types would be countable.

Clearly there's something wrong in that argument, but I don't know where; can anyone give me some insight here?

edit: On second thought I don't think $T$ has quantifier elimination; for instance, it's clear that $phi(v):=exists xspace v=2cdot x$ defines an infinite and coinfinite subset of $mathbb{N}$, which would contradict quantifier elimination.

logic model-theory universal-algebra

share|cite|improve this question

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

$endgroup$

share|cite|improve this question

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

share|cite|improve this question

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

edited 14 mins ago

Asaf Karagila♦

315k3434 gold badges453453 silver badges787787 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

asked 10 hours ago

Atticus StonestromAtticus Stonestrom

7966 bronze badges

1 Answer
1

active

oldest

votes

5

$begingroup$

I don't think there's any nice description of the complete $n$-types: $Th(mathbb{N}, +, cdot, <, 0, 1)$ is a very complicated theory. It's easy to show there are uncountably many for any $ngeq 1$, though. Just note that if $S$ is any set of primes, there is a (not necessarily complete) $1$-type which says $x$ is divisible by each element of $S$ but not divisible by any prime not in $S$. These $1$-types for different values of $S$ are all incompatible, so they can be extended to distinct complete $1$-types (or $n$-types for any $ngeq 1$). Since there are $2^{aleph_0}$ different sets of primes, this gives $2^{aleph_0}$ different complete $1$-types.

share|cite|improve this answer

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbb{N}, +, cdot, <, 0, 1)$ does not admit quantifier elimination correct? Obviously need to fill in details/casework but would an argument along those lines work?
  $endgroup$
  – Atticus Stonestrom
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah. Any quantifier-free formula is just a Boolean combination of polynomial inequalities. With one variable, it's easy to show that the set of elements of $mathbb{N}$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
  $endgroup$
  – Eric Wofsey
  9 hours ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3320419%2fn-types-of-the-theory-of-natural-numbers%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

I don't think there's any nice description of the complete $n$-types: $Th(mathbb{N}, +, cdot, <, 0, 1)$ is a very complicated theory. It's easy to show there are uncountably many for any $ngeq 1$, though. Just note that if $S$ is any set of primes, there is a (not necessarily complete) $1$-type which says $x$ is divisible by each element of $S$ but not divisible by any prime not in $S$. These $1$-types for different values of $S$ are all incompatible, so they can be extended to distinct complete $1$-types (or $n$-types for any $ngeq 1$). Since there are $2^{aleph_0}$ different sets of primes, this gives $2^{aleph_0}$ different complete $1$-types.

share|cite|improve this answer

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbb{N}, +, cdot, <, 0, 1)$ does not admit quantifier elimination correct? Obviously need to fill in details/casework but would an argument along those lines work?
  $endgroup$
  – Atticus Stonestrom
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah. Any quantifier-free formula is just a Boolean combination of polynomial inequalities. With one variable, it's easy to show that the set of elements of $mathbb{N}$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
  $endgroup$
  – Eric Wofsey
  9 hours ago
  

  
  
  
  

add a comment | 

5

$begingroup$

I don't think there's any nice description of the complete $n$-types: $Th(mathbb{N}, +, cdot, <, 0, 1)$ is a very complicated theory. It's easy to show there are uncountably many for any $ngeq 1$, though. Just note that if $S$ is any set of primes, there is a (not necessarily complete) $1$-type which says $x$ is divisible by each element of $S$ but not divisible by any prime not in $S$. These $1$-types for different values of $S$ are all incompatible, so they can be extended to distinct complete $1$-types (or $n$-types for any $ngeq 1$). Since there are $2^{aleph_0}$ different sets of primes, this gives $2^{aleph_0}$ different complete $1$-types.

share|cite|improve this answer

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbb{N}, +, cdot, <, 0, 1)$ does not admit quantifier elimination correct? Obviously need to fill in details/casework but would an argument along those lines work?
  $endgroup$
  – Atticus Stonestrom
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah. Any quantifier-free formula is just a Boolean combination of polynomial inequalities. With one variable, it's easy to show that the set of elements of $mathbb{N}$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
  $endgroup$
  – Eric Wofsey
  9 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

I don't think there's any nice description of the complete $n$-types: $Th(mathbb{N}, +, cdot, <, 0, 1)$ is a very complicated theory. It's easy to show there are uncountably many for any $ngeq 1$, though. Just note that if $S$ is any set of primes, there is a (not necessarily complete) $1$-type which says $x$ is divisible by each element of $S$ but not divisible by any prime not in $S$. These $1$-types for different values of $S$ are all incompatible, so they can be extended to distinct complete $1$-types (or $n$-types for any $ngeq 1$). Since there are $2^{aleph_0}$ different sets of primes, this gives $2^{aleph_0}$ different complete $1$-types.

share|cite|improve this answer

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges

$endgroup$

share|cite|improve this answer

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges

answered 9 hours ago

Eric WofseyEric Wofsey

208k1414 gold badges245245 silver badges376376 bronze badges