$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
Is “I am getting married with my sister” ambiguous?
Sci fi film similar to Village of the Damned
Does travel insurance for short flight delays exist?
What are some interesting features that are common cross-linguistically but don't exist in English?
Pythagorean triple with hypotenuse a power of 2
Which note goes on which side of the stem?
Why did they avoid parodying Martian Manhunter?
Dealing with an extrovert co-worker
Disambiguation of "nobis vobis" and "nobis nobis"
Confirming resignation after resignation letter ripped up
Nothing like a good ol' game of ModTen
How should I face my manager if I make a mistake because a senior coworker explained something incorrectly to me?
Is there any music source code for sound chips?
Compelling story with the world as a villain
Why in most German places is the church the tallest building?
Irish Snap: Variant Rules
Shouldn't the "credit score" prevent Americans from going deeper and deeper into personal debt?
Couple of slangs I've heard when watching anime
Is it possible to perform a regression where you have an unknown / unknowable feature variable?
Which household object drew this pattern?
Can't stopover at Sapporo when going from Asahikawa to Chitose airport?
Mathematical uses of string theory
Why did this happen to Thanos's ships at the end of "Avengers: Endgame"?
Avoiding racist tropes in fantasy
$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;
$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(mathbbN, +, 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(mathbbN, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:
What do the complete $n$-types of $Th(mathbbN, +, cdot, <, 0, 1)$ look like?
First I'm trying to ascertain if $T=Th(mathbbN, +, 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 $mathbbN$, which would contradict quantifier elimination.
logic model-theory universal-algebra
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 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(mathbbN, +, 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(mathbbN, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:
What do the complete $n$-types of $Th(mathbbN, +, cdot, <, 0, 1)$ look like?
First I'm trying to ascertain if $T=Th(mathbbN, +, 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 $mathbbN$, which would contradict quantifier elimination.
logic model-theory universal-algebra
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 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(mathbbN, +, 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(mathbbN, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:
What do the complete $n$-types of $Th(mathbbN, +, cdot, <, 0, 1)$ look like?
First I'm trying to ascertain if $T=Th(mathbbN, +, 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 $mathbbN$, which would contradict quantifier elimination.
logic model-theory universal-algebra
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 bronze badges
$endgroup$
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(mathbbN, +, 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(mathbbN, +, cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:
What do the complete $n$-types of $Th(mathbbN, +, cdot, <, 0, 1)$ look like?
First I'm trying to ascertain if $T=Th(mathbbN, +, 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 $mathbbN$, which would contradict quantifier elimination.
logic model-theory universal-algebra
logic model-theory universal-algebra
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 bronze badges
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 bronze badges
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
edited Aug 12 at 6:32
Asaf Karagila♦
316k35 gold badges454 silver badges789 bronze badges
316k35 gold badges454 silver badges789 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 bronze badges
asked Aug 11 at 20:44
Atticus StonestromAtticus Stonestrom
796 bronze badges
796 bronze badges
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I don't think there's any nice description of the complete $n$-types: $Th(mathbbN, +, 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.
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
$endgroup$
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
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
);
);
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
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
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I don't think there's any nice description of the complete $n$-types: $Th(mathbbN, +, 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.
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
$endgroup$
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
add a comment |
$begingroup$
I don't think there's any nice description of the complete $n$-types: $Th(mathbbN, +, 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.
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
$endgroup$
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
add a comment |
$begingroup$
I don't think there's any nice description of the complete $n$-types: $Th(mathbbN, +, 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.
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
$endgroup$
I don't think there's any nice description of the complete $n$-types: $Th(mathbbN, +, 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.
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
answered Aug 11 at 21:12
Eric WofseyEric Wofsey
210k15 gold badges246 silver badges378 bronze badges
210k15 gold badges246 silver badges378 bronze badges
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
add a comment |
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
$begingroup$
Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(mathbbN, +, 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
Aug 11 at 21:23
1
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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
$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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
Aug 11 at 21:27
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
