What do sentences in the theory of the structure $A=(Q,<,n)_{n in N}$ look like?
I'm working on a problem from Kees Doets, and he mentions the following structures:
$X=(Q,<,n)_{n in N}$
$Y=(Q,<,frac{-1}{n+1})_{n in N}$
$Z=(Q,<,q_n)_{n in N}$ where ${q_n}_{n in N}$ is an ascending sequence of rationals converging to some irrational.
The problem asks to show that up to isomorphism $Y$ and $Z$ are the only other countable models of $Th(X)$. Also asks to show which one is saturated and which one is prime. But for now I have a much more basic question:
What does a sentence in $Th(X)$ look like? I am confused by the symbols $n in N$ added to the language. Can a sentence $phi in Th(X)$ for example be $phi=forall q in Q, exists n in N: q<n$
This is true in the rationals, but is a sentence allowed to quantify over the constant symbols in its language, or is quantification reserved only for variables which will be interpreted in the model? Assuming of course that the interpretation of the symbols $n$ in the model is actually the natural numbers.
first-order-logic model-theory formal-languages
asked Dec 10 '18 at 0:45
Mike
684414
|
show 5 more comments
I'm working on a problem from Kees Doets, and he mentions the following structures:
$X=(Q,<,n)_{n in N}$
$Y=(Q,<,frac{-1}{n+1})_{n in N}$
$Z=(Q,<,q_n)_{n in N}$ where ${q_n}_{n in N}$ is an ascending sequence of rationals converging to some irrational.
The problem asks to show that up to isomorphism $Y$ and $Z$ are the only other countable models of $Th(X)$. Also asks to show which one is saturated and which one is prime. But for now I have a much more basic question:
What does a sentence in $Th(X)$ look like? I am confused by the symbols $n in N$ added to the language. Can a sentence $phi in Th(X)$ for example be $phi=forall q in Q, exists n in N: q<n$
This is true in the rationals, but is a sentence allowed to quantify over the constant symbols in its language, or is quantification reserved only for variables which will be interpreted in the model? Assuming of course that the interpretation of the symbols $n$ in the model is actually the natural numbers.
first-order-logic model-theory formal-languages
asked Dec 10 '18 at 0:45
Mike
684414
1
"Is a sentence allowed to quantify over the constant symbols in its language?" No. "Is quantification reserved only for variables which will be interpreted in the model?" Yes. That's how quantifiers work in first-order logic.
– Alex Kruckman
Dec 10 '18 at 0:50
1
Correct, it's not even a well-formed sentence. (And if it were, $Y$ and $Z$ wouldn't be models of $text{Th}(X)$!)
– Alex Kruckman
Dec 10 '18 at 0:52
1
Quantifiers in first-order logic usually are just written $forall x$ or $exists x$, not $forall xin Q$. The exception is when you're working with multi-sorted first-order logic, where you may see quantifiers that look like $(forall xin S)$. But here $S$ is required to be a sort symbol in the vocabulary (and the set of constant symbols is not a sort symbol). Of course, different authors may use different notational conventions. I'm not familiar with the book by Kees Doets that you're reading.
– Alex Kruckman
Dec 10 '18 at 1:01
1
Yep, now that's a sentence!
– Alex Kruckman
Dec 10 '18 at 1:02
1
The idea is that the language is the same for all three structures, namely the 2 place relation symbol < and an infinite list of constant symbols, say a1, a2, a3, ... The 3 structures are all models of the complete theory consisting of Dense Linear Ordering axioms plus the infinite list a1 < a2, a2 < a3, .... and so they are elementarily equivalent but not isomorphic, which is the point of the example. So the sentences of the language don't include names for specific rational numbers or integers but rather the common constant symbols which are interpreted differently in the three models.
– Ned
Dec 10 '18 at 2:57
|
show 5 more comments
I'm working on a problem from Kees Doets, and he mentions the following structures:
$X=(Q,<,n)_{n in N}$
$Y=(Q,<,frac{-1}{n+1})_{n in N}$
$Z=(Q,<,q_n)_{n in N}$ where ${q_n}_{n in N}$ is an ascending sequence of rationals converging to some irrational.
The problem asks to show that up to isomorphism $Y$ and $Z$ are the only other countable models of $Th(X)$. Also asks to show which one is saturated and which one is prime. But for now I have a much more basic question:
What does a sentence in $Th(X)$ look like? I am confused by the symbols $n in N$ added to the language. Can a sentence $phi in Th(X)$ for example be $phi=forall q in Q, exists n in N: q<n$
This is true in the rationals, but is a sentence allowed to quantify over the constant symbols in its language, or is quantification reserved only for variables which will be interpreted in the model? Assuming of course that the interpretation of the symbols $n$ in the model is actually the natural numbers.
first-order-logic model-theory formal-languages
asked Dec 10 '18 at 0:45
Mike
684414
I'm working on a problem from Kees Doets, and he mentions the following structures:
$X=(Q,<,n)_{n in N}$
$Y=(Q,<,frac{-1}{n+1})_{n in N}$
$Z=(Q,<,q_n)_{n in N}$ where ${q_n}_{n in N}$ is an ascending sequence of rationals converging to some irrational.
The problem asks to show that up to isomorphism $Y$ and $Z$ are the only other countable models of $Th(X)$. Also asks to show which one is saturated and which one is prime. But for now I have a much more basic question:
What does a sentence in $Th(X)$ look like? I am confused by the symbols $n in N$ added to the language. Can a sentence $phi in Th(X)$ for example be $phi=forall q in Q, exists n in N: q<n$
This is true in the rationals, but is a sentence allowed to quantify over the constant symbols in its language, or is quantification reserved only for variables which will be interpreted in the model? Assuming of course that the interpretation of the symbols $n$ in the model is actually the natural numbers.
first-order-logic model-theory formal-languages
first-order-logic model-theory formal-languages
asked Dec 10 '18 at 0:45
Mike
684414
asked Dec 10 '18 at 0:45
Mike
684414
asked Dec 10 '18 at 0:45
Mike
684414
asked Dec 10 '18 at 0:45
Mike
684414
asked Dec 10 '18 at 0:45
Mike
684414
684414
1
"Is a sentence allowed to quantify over the constant symbols in its language?" No. "Is quantification reserved only for variables which will be interpreted in the model?" Yes. That's how quantifiers work in first-order logic.
– Alex Kruckman
Dec 10 '18 at 0:50
1
Correct, it's not even a well-formed sentence. (And if it were, $Y$ and $Z$ wouldn't be models of $text{Th}(X)$!)
– Alex Kruckman
Dec 10 '18 at 0:52
1
Quantifiers in first-order logic usually are just written $forall x$ or $exists x$, not $forall xin Q$. The exception is when you're working with multi-sorted first-order logic, where you may see quantifiers that look like $(forall xin S)$. But here $S$ is required to be a sort symbol in the vocabulary (and the set of constant symbols is not a sort symbol). Of course, different authors may use different notational conventions. I'm not familiar with the book by Kees Doets that you're reading.
– Alex Kruckman
Dec 10 '18 at 1:01
1
Yep, now that's a sentence!
– Alex Kruckman
Dec 10 '18 at 1:02
1
The idea is that the language is the same for all three structures, namely the 2 place relation symbol < and an infinite list of constant symbols, say a1, a2, a3, ... The 3 structures are all models of the complete theory consisting of Dense Linear Ordering axioms plus the infinite list a1 < a2, a2 < a3, .... and so they are elementarily equivalent but not isomorphic, which is the point of the example. So the sentences of the language don't include names for specific rational numbers or integers but rather the common constant symbols which are interpreted differently in the three models.
– Ned
Dec 10 '18 at 2:57
|
show 5 more comments
1
"Is a sentence allowed to quantify over the constant symbols in its language?" No. "Is quantification reserved only for variables which will be interpreted in the model?" Yes. That's how quantifiers work in first-order logic.
– Alex Kruckman
Dec 10 '18 at 0:50
1
Correct, it's not even a well-formed sentence. (And if it were, $Y$ and $Z$ wouldn't be models of $text{Th}(X)$!)
– Alex Kruckman
Dec 10 '18 at 0:52
1
Quantifiers in first-order logic usually are just written $forall x$ or $exists x$, not $forall xin Q$. The exception is when you're working with multi-sorted first-order logic, where you may see quantifiers that look like $(forall xin S)$. But here $S$ is required to be a sort symbol in the vocabulary (and the set of constant symbols is not a sort symbol). Of course, different authors may use different notational conventions. I'm not familiar with the book by Kees Doets that you're reading.
– Alex Kruckman
Dec 10 '18 at 1:01
1
Yep, now that's a sentence!
– Alex Kruckman
Dec 10 '18 at 1:02
1
The idea is that the language is the same for all three structures, namely the 2 place relation symbol < and an infinite list of constant symbols, say a1, a2, a3, ... The 3 structures are all models of the complete theory consisting of Dense Linear Ordering axioms plus the infinite list a1 < a2, a2 < a3, .... and so they are elementarily equivalent but not isomorphic, which is the point of the example. So the sentences of the language don't include names for specific rational numbers or integers but rather the common constant symbols which are interpreted differently in the three models.
– Ned
Dec 10 '18 at 2:57
1
1
"Is a sentence allowed to quantify over the constant symbols in its language?" No. "Is quantification reserved only for variables which will be interpreted in the model?" Yes. That's how quantifiers work in first-order logic.
– Alex Kruckman
Dec 10 '18 at 0:50
"Is a sentence allowed to quantify over the constant symbols in its language?" No. "Is quantification reserved only for variables which will be interpreted in the model?" Yes. That's how quantifiers work in first-order logic.
– Alex Kruckman
Dec 10 '18 at 0:50
1
1
Correct, it's not even a well-formed sentence. (And if it were, $Y$ and $Z$ wouldn't be models of $text{Th}(X)$!)
– Alex Kruckman
Dec 10 '18 at 0:52
Correct, it's not even a well-formed sentence. (And if it were, $Y$ and $Z$ wouldn't be models of $text{Th}(X)$!)
– Alex Kruckman
Dec 10 '18 at 0:52
1
1
Quantifiers in first-order logic usually are just written $forall x$ or $exists x$, not $forall xin Q$. The exception is when you're working with multi-sorted first-order logic, where you may see quantifiers that look like $(forall xin S)$. But here $S$ is required to be a sort symbol in the vocabulary (and the set of constant symbols is not a sort symbol). Of course, different authors may use different notational conventions. I'm not familiar with the book by Kees Doets that you're reading.
– Alex Kruckman
Dec 10 '18 at 1:01
Quantifiers in first-order logic usually are just written $forall x$ or $exists x$, not $forall xin Q$. The exception is when you're working with multi-sorted first-order logic, where you may see quantifiers that look like $(forall xin S)$. But here $S$ is required to be a sort symbol in the vocabulary (and the set of constant symbols is not a sort symbol). Of course, different authors may use different notational conventions. I'm not familiar with the book by Kees Doets that you're reading.
– Alex Kruckman
Dec 10 '18 at 1:01
1
1
Yep, now that's a sentence!
– Alex Kruckman
Dec 10 '18 at 1:02
Yep, now that's a sentence!
– Alex Kruckman
Dec 10 '18 at 1:02
1
1
The idea is that the language is the same for all three structures, namely the 2 place relation symbol < and an infinite list of constant symbols, say a1, a2, a3, ... The 3 structures are all models of the complete theory consisting of Dense Linear Ordering axioms plus the infinite list a1 < a2, a2 < a3, .... and so they are elementarily equivalent but not isomorphic, which is the point of the example. So the sentences of the language don't include names for specific rational numbers or integers but rather the common constant symbols which are interpreted differently in the three models.
– Ned
Dec 10 '18 at 2:57
The idea is that the language is the same for all three structures, namely the 2 place relation symbol < and an infinite list of constant symbols, say a1, a2, a3, ... The 3 structures are all models of the complete theory consisting of Dense Linear Ordering axioms plus the infinite list a1 < a2, a2 < a3, .... and so they are elementarily equivalent but not isomorphic, which is the point of the example. So the sentences of the language don't include names for specific rational numbers or integers but rather the common constant symbols which are interpreted differently in the three models.
– Ned
Dec 10 '18 at 2:57
|
show 5 more comments
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3033263%2fwhat-do-sentences-in-the-theory-of-the-structure-a-q-n-n-in-n-look-like%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3033263%2fwhat-do-sentences-in-the-theory-of-the-structure-a-q-n-n-in-n-look-like%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
1
"Is a sentence allowed to quantify over the constant symbols in its language?" No. "Is quantification reserved only for variables which will be interpreted in the model?" Yes. That's how quantifiers work in first-order logic.
– Alex Kruckman
Dec 10 '18 at 0:50
1
Correct, it's not even a well-formed sentence. (And if it were, $Y$ and $Z$ wouldn't be models of $text{Th}(X)$!)
– Alex Kruckman
Dec 10 '18 at 0:52
1
Quantifiers in first-order logic usually are just written $forall x$ or $exists x$, not $forall xin Q$. The exception is when you're working with multi-sorted first-order logic, where you may see quantifiers that look like $(forall xin S)$. But here $S$ is required to be a sort symbol in the vocabulary (and the set of constant symbols is not a sort symbol). Of course, different authors may use different notational conventions. I'm not familiar with the book by Kees Doets that you're reading.
– Alex Kruckman
Dec 10 '18 at 1:01
1
Yep, now that's a sentence!
– Alex Kruckman
Dec 10 '18 at 1:02
1
The idea is that the language is the same for all three structures, namely the 2 place relation symbol < and an infinite list of constant symbols, say a1, a2, a3, ... The 3 structures are all models of the complete theory consisting of Dense Linear Ordering axioms plus the infinite list a1 < a2, a2 < a3, .... and so they are elementarily equivalent but not isomorphic, which is the point of the example. So the sentences of the language don't include names for specific rational numbers or integers but rather the common constant symbols which are interpreted differently in the three models.
– Ned
Dec 10 '18 at 2:57