n-types of the theory of natural numbers?Question about the proof of consistency iff satisfiability of a theoryComplete n-types of the theory of atomless Boolean algebrasAbout 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
function evaluation - I don't get it
What does this double-treble double-bass staff mean?
How to take the beginning and end parts of a list with simpler syntax?
Is there a way to unplug the Raspberry pi safely without shutting down
Different inverter (logic gate) symbols
Does this Foo machine halt?
On Math Looking Obvious in Retrospect
Am I overreacting to my team leader's unethical requests?
During the Space Shuttle Columbia Disaster of 2003, Why Did The Flight Director Say, "Lock the doors."?
(11 of 11: Meta) What is Pyramid Cult's All-Time Favorite?
What is the difference between 型 and 形?
As a 16 year old, how can I keep my money safe from my mother?
How many different ways are there to checkmate in the early game?
What happen to those who died but not from the snap?
What should I call bands of armed men in Medieval Times?
How are you supposed to know the strumming pattern for a song from the "chord sheet music"?
What are the conventions for transcribing Semitic languages into Greek?
Continuous vertical line using booktabs in tabularx table?
Generate Brainfuck for the numbers 1–255
Acceptable to cut steak before searing?
Email address etiquette - Which address should I use to contact professors?
constant evaluation when using differential equations.
Plausibility of Ice Eaters in the Arctic
Bitcoin successfully deducted on sender wallet but did not reach receiver wallet
n-types of the theory of natural numbers?
Question about the proof of consistency iff satisfiability of a theoryComplete n-types of the theory of atomless Boolean algebrasAbout 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
asked 9 hours ago
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
asked 9 hours ago
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
asked 9 hours ago
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
asked 9 hours ago
Atticus StonestromAtticus Stonestrom
796 bronze badges
asked 9 hours ago
Atticus StonestromAtticus Stonestrom
796 bronze badges
edited 8 hours ago
Atticus Stonestrom
asked 9 hours ago
Atticus StonestromAtticus Stonestrom
796 bronze badges
asked 9 hours ago
Atticus StonestromAtticus Stonestrom
796 bronze badges
asked 9 hours ago
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 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 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
8 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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
8 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
);
);
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 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 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
8 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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
8 hours ago
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 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 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
8 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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
8 hours ago
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 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 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 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 bronze badges
answered 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 bronze badges
answered 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 bronze badges
answered 8 hours ago
Eric WofseyEric Wofsey
208k14 gold badges245 silver badges376 bronze badges
208k14 gold badges245 silver badges376 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
8 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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
8 hours ago
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
8 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 $mathbbN$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers.
$endgroup$
– Eric Wofsey
8 hours ago
$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
8 hours ago
$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
8 hours ago
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
8 hours ago
$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
8 hours ago
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
