Are the natural numbers definable in the (2nd-order) theory of complete ordered fields?
$begingroup$
I read that the natural numbers are not definable in the theory of real closed fields (RCF), which captures the 1st-order properties of the real numbers. That's why RCF doesn't contradict Gödel's theorem.
But are the natural numbers definable in the 2nd-order theory of complete ordered fields (COF), which categorically captures the real numbers ?
Edit : Looks like the answer was simple, after some thinking. Since COF is a 2nd-order theory, we can quantify over subsets of $mathbb R$. Then expressing that $mathbb N$ is the smallest inductive subset of $mathbb R$ should do.
Essentially, for a subset $Ssubseteqmathbb R$, define the (meta-)property $I(S)$ of being inductive :
$$I(S) := (0in S wedge (forall xinmathbb R : xin Srightarrow x+1in S))$$
Define the (meta-)property $N(S)$ of being the smallest inductive set :
$$N(S) := (I(S) wedge (forall Tsubseteqmathbb R : I(T)rightarrow Ssubseteq T))$$
Then $mathbb N$ is the unique subset $S$ of $mathbb R$ such that $N(S)$.
I hope there is no mistake.
field-theory real-numbers natural-numbers
asked Nov 30 '18 at 9:28
SephiSephi
1056
$endgroup$
add a comment |
$begingroup$
I read that the natural numbers are not definable in the theory of real closed fields (RCF), which captures the 1st-order properties of the real numbers. That's why RCF doesn't contradict Gödel's theorem.
But are the natural numbers definable in the 2nd-order theory of complete ordered fields (COF), which categorically captures the real numbers ?
Edit : Looks like the answer was simple, after some thinking. Since COF is a 2nd-order theory, we can quantify over subsets of $mathbb R$. Then expressing that $mathbb N$ is the smallest inductive subset of $mathbb R$ should do.
Essentially, for a subset $Ssubseteqmathbb R$, define the (meta-)property $I(S)$ of being inductive :
$$I(S) := (0in S wedge (forall xinmathbb R : xin Srightarrow x+1in S))$$
Define the (meta-)property $N(S)$ of being the smallest inductive set :
$$N(S) := (I(S) wedge (forall Tsubseteqmathbb R : I(T)rightarrow Ssubseteq T))$$
Then $mathbb N$ is the unique subset $S$ of $mathbb R$ such that $N(S)$.
I hope there is no mistake.
field-theory real-numbers natural-numbers
asked Nov 30 '18 at 9:28
SephiSephi
1056
$endgroup$
$begingroup$
That looks like the way I've seen the natural numbers defined in textbooks that start from the axioms for a complete ordered field. Now sure what you mean by (meta-). By "meta-property" do you just mean a second order property? What's "meta" about that?
$endgroup$
– bof
Nov 30 '18 at 10:33
$begingroup$
It's just that the "predicates" $I$ and $N$ are not symbols of the language of COF, they are merely abbreviations. They are not predicates inside of COF. That's what I meant.
$endgroup$
– Sephi
Nov 30 '18 at 10:36
$begingroup$
So every defined notion, like $2$ or $-$ or $!$ or $exp$, is "meta"? All right.
$endgroup$
– bof
Nov 30 '18 at 10:40
$begingroup$
If you define 1st-order objects (terms, functions, relations), you can add them to the language. For example, add the term symbol "2" and the defining axiom "2=1+1", and "2" is now internal to the theory. But if you conceive a property about a subset (like $I(S)$ above, which is a property of the subset $S$), you can't add the symbol $I$ to the language since in a 2nd-order language, there are no such kind of symbols... at least, that I know of.
$endgroup$
– Sephi
Nov 30 '18 at 12:45
add a comment |
$begingroup$
I read that the natural numbers are not definable in the theory of real closed fields (RCF), which captures the 1st-order properties of the real numbers. That's why RCF doesn't contradict Gödel's theorem.
But are the natural numbers definable in the 2nd-order theory of complete ordered fields (COF), which categorically captures the real numbers ?
Edit : Looks like the answer was simple, after some thinking. Since COF is a 2nd-order theory, we can quantify over subsets of $mathbb R$. Then expressing that $mathbb N$ is the smallest inductive subset of $mathbb R$ should do.
Essentially, for a subset $Ssubseteqmathbb R$, define the (meta-)property $I(S)$ of being inductive :
$$I(S) := (0in S wedge (forall xinmathbb R : xin Srightarrow x+1in S))$$
Define the (meta-)property $N(S)$ of being the smallest inductive set :
$$N(S) := (I(S) wedge (forall Tsubseteqmathbb R : I(T)rightarrow Ssubseteq T))$$
Then $mathbb N$ is the unique subset $S$ of $mathbb R$ such that $N(S)$.
I hope there is no mistake.
field-theory real-numbers natural-numbers
asked Nov 30 '18 at 9:28
SephiSephi
1056
$endgroup$
I read that the natural numbers are not definable in the theory of real closed fields (RCF), which captures the 1st-order properties of the real numbers. That's why RCF doesn't contradict Gödel's theorem.
But are the natural numbers definable in the 2nd-order theory of complete ordered fields (COF), which categorically captures the real numbers ?
Edit : Looks like the answer was simple, after some thinking. Since COF is a 2nd-order theory, we can quantify over subsets of $mathbb R$. Then expressing that $mathbb N$ is the smallest inductive subset of $mathbb R$ should do.
Essentially, for a subset $Ssubseteqmathbb R$, define the (meta-)property $I(S)$ of being inductive :
$$I(S) := (0in S wedge (forall xinmathbb R : xin Srightarrow x+1in S))$$
Define the (meta-)property $N(S)$ of being the smallest inductive set :
$$N(S) := (I(S) wedge (forall Tsubseteqmathbb R : I(T)rightarrow Ssubseteq T))$$
Then $mathbb N$ is the unique subset $S$ of $mathbb R$ such that $N(S)$.
I hope there is no mistake.
field-theory real-numbers natural-numbers
field-theory real-numbers natural-numbers
asked Nov 30 '18 at 9:28
SephiSephi
1056
asked Nov 30 '18 at 9:28
SephiSephi
1056
edited Nov 30 '18 at 10:17
Sephi
asked Nov 30 '18 at 9:28
SephiSephi
1056
asked Nov 30 '18 at 9:28
SephiSephi
1056
asked Nov 30 '18 at 9:28
SephiSephi
1056
1056
$begingroup$
That looks like the way I've seen the natural numbers defined in textbooks that start from the axioms for a complete ordered field. Now sure what you mean by (meta-). By "meta-property" do you just mean a second order property? What's "meta" about that?
$endgroup$
– bof
Nov 30 '18 at 10:33
$begingroup$
It's just that the "predicates" $I$ and $N$ are not symbols of the language of COF, they are merely abbreviations. They are not predicates inside of COF. That's what I meant.
$endgroup$
– Sephi
Nov 30 '18 at 10:36
$begingroup$
So every defined notion, like $2$ or $-$ or $!$ or $exp$, is "meta"? All right.
$endgroup$
– bof
Nov 30 '18 at 10:40
$begingroup$
If you define 1st-order objects (terms, functions, relations), you can add them to the language. For example, add the term symbol "2" and the defining axiom "2=1+1", and "2" is now internal to the theory. But if you conceive a property about a subset (like $I(S)$ above, which is a property of the subset $S$), you can't add the symbol $I$ to the language since in a 2nd-order language, there are no such kind of symbols... at least, that I know of.
$endgroup$
– Sephi
Nov 30 '18 at 12:45
add a comment |
$begingroup$
That looks like the way I've seen the natural numbers defined in textbooks that start from the axioms for a complete ordered field. Now sure what you mean by (meta-). By "meta-property" do you just mean a second order property? What's "meta" about that?
$endgroup$
– bof
Nov 30 '18 at 10:33
$begingroup$
It's just that the "predicates" $I$ and $N$ are not symbols of the language of COF, they are merely abbreviations. They are not predicates inside of COF. That's what I meant.
$endgroup$
– Sephi
Nov 30 '18 at 10:36
$begingroup$
So every defined notion, like $2$ or $-$ or $!$ or $exp$, is "meta"? All right.
$endgroup$
– bof
Nov 30 '18 at 10:40
$begingroup$
If you define 1st-order objects (terms, functions, relations), you can add them to the language. For example, add the term symbol "2" and the defining axiom "2=1+1", and "2" is now internal to the theory. But if you conceive a property about a subset (like $I(S)$ above, which is a property of the subset $S$), you can't add the symbol $I$ to the language since in a 2nd-order language, there are no such kind of symbols... at least, that I know of.
$endgroup$
– Sephi
Nov 30 '18 at 12:45
$begingroup$
That looks like the way I've seen the natural numbers defined in textbooks that start from the axioms for a complete ordered field. Now sure what you mean by (meta-). By "meta-property" do you just mean a second order property? What's "meta" about that?
$endgroup$
– bof
Nov 30 '18 at 10:33
$begingroup$
That looks like the way I've seen the natural numbers defined in textbooks that start from the axioms for a complete ordered field. Now sure what you mean by (meta-). By "meta-property" do you just mean a second order property? What's "meta" about that?
$endgroup$
– bof
Nov 30 '18 at 10:33
$begingroup$
It's just that the "predicates" $I$ and $N$ are not symbols of the language of COF, they are merely abbreviations. They are not predicates inside of COF. That's what I meant.
$endgroup$
– Sephi
Nov 30 '18 at 10:36
$begingroup$
It's just that the "predicates" $I$ and $N$ are not symbols of the language of COF, they are merely abbreviations. They are not predicates inside of COF. That's what I meant.
$endgroup$
– Sephi
Nov 30 '18 at 10:36
$begingroup$
So every defined notion, like $2$ or $-$ or $!$ or $exp$, is "meta"? All right.
$endgroup$
– bof
Nov 30 '18 at 10:40
$begingroup$
So every defined notion, like $2$ or $-$ or $!$ or $exp$, is "meta"? All right.
$endgroup$
– bof
Nov 30 '18 at 10:40
$begingroup$
If you define 1st-order objects (terms, functions, relations), you can add them to the language. For example, add the term symbol "2" and the defining axiom "2=1+1", and "2" is now internal to the theory. But if you conceive a property about a subset (like $I(S)$ above, which is a property of the subset $S$), you can't add the symbol $I$ to the language since in a 2nd-order language, there are no such kind of symbols... at least, that I know of.
$endgroup$
– Sephi
Nov 30 '18 at 12:45
$begingroup$
If you define 1st-order objects (terms, functions, relations), you can add them to the language. For example, add the term symbol "2" and the defining axiom "2=1+1", and "2" is now internal to the theory. But if you conceive a property about a subset (like $I(S)$ above, which is a property of the subset $S$), you can't add the symbol $I$ to the language since in a 2nd-order language, there are no such kind of symbols... at least, that I know of.
$endgroup$
– Sephi
Nov 30 '18 at 12:45
add a comment |
0
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%2f3019873%2fare-the-natural-numbers-definable-in-the-2nd-order-theory-of-complete-ordered%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
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.
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%2f3019873%2fare-the-natural-numbers-definable-in-the-2nd-order-theory-of-complete-ordered%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
$begingroup$
That looks like the way I've seen the natural numbers defined in textbooks that start from the axioms for a complete ordered field. Now sure what you mean by (meta-). By "meta-property" do you just mean a second order property? What's "meta" about that?
$endgroup$
– bof
Nov 30 '18 at 10:33
$begingroup$
It's just that the "predicates" $I$ and $N$ are not symbols of the language of COF, they are merely abbreviations. They are not predicates inside of COF. That's what I meant.
$endgroup$
– Sephi
Nov 30 '18 at 10:36
$begingroup$
So every defined notion, like $2$ or $-$ or $!$ or $exp$, is "meta"? All right.
$endgroup$
– bof
Nov 30 '18 at 10:40
$begingroup$
If you define 1st-order objects (terms, functions, relations), you can add them to the language. For example, add the term symbol "2" and the defining axiom "2=1+1", and "2" is now internal to the theory. But if you conceive a property about a subset (like $I(S)$ above, which is a property of the subset $S$), you can't add the symbol $I$ to the language since in a 2nd-order language, there are no such kind of symbols... at least, that I know of.
$endgroup$
– Sephi
Nov 30 '18 at 12:45