Does “every” first-order theory have a finitely axiomatizable conservative extension? The Next CEO of Stack OverflowA *finite* first order theory whose finite models are exactly the $Bbb F_p$?$mathsfZF$ is not finitely axiomatizableAre there axiomatizations of first order logic or set theory defined in first order logic or set theory?complete, finitely axiomatizable, theory with 3 countable modelsIs there a 'nice' axiomatization in the language of arithmetic of the statements ZF proves about the natural numbers?Finitely axiomatized second-order theory without a model, which is consistent for reasonable deductive systemsInfinitely many axioms of ZFC vs. finitely many axioms of NBG$X+negtextCon(X)$ for finitely axiomatizable theoriesDoes every first order theory have a pointwise definable model?Which second-order theories have a model?
Mathematica command that allows it to read my intentions
The sum of any ten consecutive numbers from a fibonacci sequence is divisible by 11
Find a path from s to t using as few red nodes as possible
Compilation of a 2d array and a 1d array
Is it reasonable to ask other researchers to send me their previous grant applications?
Calculate the Mean mean of two numbers
Planeswalker Ability and Death Timing
Calculating discount not working
How does a dynamic QR code work?
Are British MPs missing the point, with these 'Indicative Votes'?
Incomplete cube
Early programmable calculators with RS-232
Strange use of "whether ... than ..." in official text
How seriously should I take size and weight limits of hand luggage?
Can a PhD from a non-TU9 German university become a professor in a TU9 university?
Is a distribution that is normal, but highly skewed, considered Gaussian?
Why does freezing point matter when picking cooler ice packs?
Is this a new Fibonacci Identity?
How do I secure a TV wall mount?
Can I cast Thunderwave and be at the center of its bottom face, but not be affected by it?
Simplify trigonometric expression using trigonometric identities
Is it a bad idea to plug the other end of ESD strap to wall ground?
pgfplots: How to draw a tangent graph below two others?
How do I keep Mac Emacs from trapping M-`?
Does “every” first-order theory have a finitely axiomatizable conservative extension?
The Next CEO of Stack OverflowA *finite* first order theory whose finite models are exactly the $Bbb F_p$?$mathsfZF$ is not finitely axiomatizableAre there axiomatizations of first order logic or set theory defined in first order logic or set theory?complete, finitely axiomatizable, theory with 3 countable modelsIs there a 'nice' axiomatization in the language of arithmetic of the statements ZF proves about the natural numbers?Finitely axiomatized second-order theory without a model, which is consistent for reasonable deductive systemsInfinitely many axioms of ZFC vs. finitely many axioms of NBG$X+negtextCon(X)$ for finitely axiomatizable theoriesDoes every first order theory have a pointwise definable model?Which second-order theories have a model?
$begingroup$
I've now asked this question on mathoverflow here.
There's a famous theorem (due to Montague) that states that if $sf ZFC$ is consistent then it cannot be finitely axiomatized. However $sf NBG$ set theory is a conservative extension of $sf ZFC$ that can be finitely axiomatized.
Similarly, if $sf PA$ is consistent then it is not finitely axiomatizable (Ryll-Nardzewski) but it has a conservative extension, $sf ACA_0$, which is finitely axiomatizable. (Usually $sf ACA_0$ is considered a second-order theory, but my understanding is that there isn't really a difference between first and second-order from the syntactic point of view.)
I'm wondering if this happens in general. At first I thought it might be that every theory had a finitely axiomatizable conservative extension. But then I realised that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable. So we shouldn't hope for theories to have finitely axiomatizable conservative extensions unless they're already effectively axiomatizable. Similarly if we add countably many logical constants to the language and demand that they're all true then that's effectively axiomatizable but doesn't have a finitely axiomatizable conservative extension, so we should restrict our attention to finite languages.
Does every effectively axiomatizable first-order theory over a finite language have a finitely axiomatizable conservative extension?
logic set-theory first-order-logic computability second-order-logic
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
$endgroup$
add a comment |
$begingroup$
I've now asked this question on mathoverflow here.
There's a famous theorem (due to Montague) that states that if $sf ZFC$ is consistent then it cannot be finitely axiomatized. However $sf NBG$ set theory is a conservative extension of $sf ZFC$ that can be finitely axiomatized.
Similarly, if $sf PA$ is consistent then it is not finitely axiomatizable (Ryll-Nardzewski) but it has a conservative extension, $sf ACA_0$, which is finitely axiomatizable. (Usually $sf ACA_0$ is considered a second-order theory, but my understanding is that there isn't really a difference between first and second-order from the syntactic point of view.)
I'm wondering if this happens in general. At first I thought it might be that every theory had a finitely axiomatizable conservative extension. But then I realised that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable. So we shouldn't hope for theories to have finitely axiomatizable conservative extensions unless they're already effectively axiomatizable. Similarly if we add countably many logical constants to the language and demand that they're all true then that's effectively axiomatizable but doesn't have a finitely axiomatizable conservative extension, so we should restrict our attention to finite languages.
Does every effectively axiomatizable first-order theory over a finite language have a finitely axiomatizable conservative extension?
logic set-theory first-order-logic computability second-order-logic
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
$endgroup$
$begingroup$
Good question. As an aside, does your statement that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable have a more informative proof than arguing that the extended theory is r.e., hence the set of theorems in the unextended theory is r.e. and gives an r.e. axiomatization of itself, but r.e. axiomatizablility is equivalent to effectively axiomatizability?
$endgroup$
– Rob Arthan
Mar 20 at 21:01
$begingroup$
@RobArthan The proof I had in mind was exactly the one you gave.
$endgroup$
– Oscar Cunningham
Mar 20 at 21:31
$begingroup$
I asked this on mathoverflow here.
$endgroup$
– Oscar Cunningham
Mar 27 at 11:10
add a comment |
$begingroup$
I've now asked this question on mathoverflow here.
There's a famous theorem (due to Montague) that states that if $sf ZFC$ is consistent then it cannot be finitely axiomatized. However $sf NBG$ set theory is a conservative extension of $sf ZFC$ that can be finitely axiomatized.
Similarly, if $sf PA$ is consistent then it is not finitely axiomatizable (Ryll-Nardzewski) but it has a conservative extension, $sf ACA_0$, which is finitely axiomatizable. (Usually $sf ACA_0$ is considered a second-order theory, but my understanding is that there isn't really a difference between first and second-order from the syntactic point of view.)
I'm wondering if this happens in general. At first I thought it might be that every theory had a finitely axiomatizable conservative extension. But then I realised that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable. So we shouldn't hope for theories to have finitely axiomatizable conservative extensions unless they're already effectively axiomatizable. Similarly if we add countably many logical constants to the language and demand that they're all true then that's effectively axiomatizable but doesn't have a finitely axiomatizable conservative extension, so we should restrict our attention to finite languages.
Does every effectively axiomatizable first-order theory over a finite language have a finitely axiomatizable conservative extension?
logic set-theory first-order-logic computability second-order-logic
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
$endgroup$
I've now asked this question on mathoverflow here.
There's a famous theorem (due to Montague) that states that if $sf ZFC$ is consistent then it cannot be finitely axiomatized. However $sf NBG$ set theory is a conservative extension of $sf ZFC$ that can be finitely axiomatized.
Similarly, if $sf PA$ is consistent then it is not finitely axiomatizable (Ryll-Nardzewski) but it has a conservative extension, $sf ACA_0$, which is finitely axiomatizable. (Usually $sf ACA_0$ is considered a second-order theory, but my understanding is that there isn't really a difference between first and second-order from the syntactic point of view.)
I'm wondering if this happens in general. At first I thought it might be that every theory had a finitely axiomatizable conservative extension. But then I realised that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable. So we shouldn't hope for theories to have finitely axiomatizable conservative extensions unless they're already effectively axiomatizable. Similarly if we add countably many logical constants to the language and demand that they're all true then that's effectively axiomatizable but doesn't have a finitely axiomatizable conservative extension, so we should restrict our attention to finite languages.
Does every effectively axiomatizable first-order theory over a finite language have a finitely axiomatizable conservative extension?
logic set-theory first-order-logic computability second-order-logic
logic set-theory first-order-logic computability second-order-logic
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
edited Mar 27 at 11:10
Oscar Cunningham
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
asked Mar 20 at 9:25
Oscar CunninghamOscar Cunningham
10.3k23061
10.3k23061
$begingroup$
Good question. As an aside, does your statement that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable have a more informative proof than arguing that the extended theory is r.e., hence the set of theorems in the unextended theory is r.e. and gives an r.e. axiomatization of itself, but r.e. axiomatizablility is equivalent to effectively axiomatizability?
$endgroup$
– Rob Arthan
Mar 20 at 21:01
$begingroup$
@RobArthan The proof I had in mind was exactly the one you gave.
$endgroup$
– Oscar Cunningham
Mar 20 at 21:31
$begingroup$
I asked this on mathoverflow here.
$endgroup$
– Oscar Cunningham
Mar 27 at 11:10
add a comment |
$begingroup$
Good question. As an aside, does your statement that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable have a more informative proof than arguing that the extended theory is r.e., hence the set of theorems in the unextended theory is r.e. and gives an r.e. axiomatization of itself, but r.e. axiomatizablility is equivalent to effectively axiomatizability?
$endgroup$
– Rob Arthan
Mar 20 at 21:01
$begingroup$
@RobArthan The proof I had in mind was exactly the one you gave.
$endgroup$
– Oscar Cunningham
Mar 20 at 21:31
$begingroup$
I asked this on mathoverflow here.
$endgroup$
– Oscar Cunningham
Mar 27 at 11:10
$begingroup$
Good question. As an aside, does your statement that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable have a more informative proof than arguing that the extended theory is r.e., hence the set of theorems in the unextended theory is r.e. and gives an r.e. axiomatization of itself, but r.e. axiomatizablility is equivalent to effectively axiomatizability?
$endgroup$
– Rob Arthan
Mar 20 at 21:01
$begingroup$
Good question. As an aside, does your statement that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable have a more informative proof than arguing that the extended theory is r.e., hence the set of theorems in the unextended theory is r.e. and gives an r.e. axiomatization of itself, but r.e. axiomatizablility is equivalent to effectively axiomatizability?
$endgroup$
– Rob Arthan
Mar 20 at 21:01
$begingroup$
@RobArthan The proof I had in mind was exactly the one you gave.
$endgroup$
– Oscar Cunningham
Mar 20 at 21:31
$begingroup$
@RobArthan The proof I had in mind was exactly the one you gave.
$endgroup$
– Oscar Cunningham
Mar 20 at 21:31
$begingroup$
I asked this on mathoverflow here.
$endgroup$
– Oscar Cunningham
Mar 27 at 11:10
$begingroup$
I asked this on mathoverflow here.
$endgroup$
– Oscar Cunningham
Mar 27 at 11:10
add a comment |
0
active
oldest
votes
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%2f3155201%2fdoes-every-first-order-theory-have-a-finitely-axiomatizable-conservative-exten%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%2f3155201%2fdoes-every-first-order-theory-have-a-finitely-axiomatizable-conservative-exten%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$
Good question. As an aside, does your statement that every theory with a finitely axiomatized conservative extension must be effectively axiomatizable have a more informative proof than arguing that the extended theory is r.e., hence the set of theorems in the unextended theory is r.e. and gives an r.e. axiomatization of itself, but r.e. axiomatizablility is equivalent to effectively axiomatizability?
$endgroup$
– Rob Arthan
Mar 20 at 21:01
$begingroup$
@RobArthan The proof I had in mind was exactly the one you gave.
$endgroup$
– Oscar Cunningham
Mar 20 at 21:31
$begingroup$
I asked this on mathoverflow here.
$endgroup$
– Oscar Cunningham
Mar 27 at 11:10