Fdtxjr

Term for the "extreme-extension" version of a straw man fallacy?

How to make a variable always equal to the result of some calculations?

WOW air has ceased operation, can I get my tickets refunded?

What does this shorthand mean?

Why did we only see the N-1 starfighters in one film?

Trouble understanding the speech of overseas colleagues

What do "high sea" and "carry" mean in this sentence?

How to write the block matrix in LaTex?

Why do remote companies require working in the US?

What is meant by a M next to a roman numeral?

How can I get through very long and very dry, but also very useful technical documents when learning a new tool?

Should I tutor a student who I know has cheated on their homework?

Was a professor correct to chastise me for writing "Prof. X" rather than "Professor X"?

Why doesn't a table tennis ball float on the surface? How do we calculate buoyancy here?

What does "Its cash flow is deeply negative" mean?

Is it my responsibility to learn a new technology in my own time my employer wants to implement?

Why does C# sound extremely flat when saxophone is tuned to G?

Science fiction (dystopian) short story set after WWIII

What is the purpose of the Evocation wizard's Potent Cantrip feature?

What happens if you roll doubles 3 times then land on "Go to jail?"

Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis

Whats the best way to handle refactoring a big file?

How to get regions to plot as graphics

How can I quit an app using Terminal?

Peano axioms and first-order logic with $exists^infty$

1

$begingroup$

All Peano axioms except the induction axiom are statements in first-order logic.
The induction axiom is written as $forall X(0 in X land forall n(n in mathbbN rightarrow (n in X land n' in X)) rightarrow mathbbN subseteq X$, where $n'$ is the successor of $n$.

Now I want to look at an extension of first-order logic. I also allow $exists^infty$ [exists infinity many]. My notes states that the induction axiom can be rewritten only using this extension of first-order logic.

My question is: How?

Since I look at first-order logic I am not allowed to have a set $X$. Here I am allready stuck, because I think I can not just say $exists^infty x$ to have something like a set ...
I think the solution requires two steps: First get rid of the set and then use $exists^infty$ to make it well-defined in my case.

logic first-order-logic peano-axioms

share|cite|improve this question

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

asked Mar 18 at 10:49

SqyuliSqyuli

344111

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  It's kinda weird talking about Peano and first-order while quantifying over subsets (second-order) and referring to $Bbb N$ in the formula.
  $endgroup$
  – Asaf Karagila♦
  Mar 18 at 11:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @AsafKaragila Well he did say all the axioms "expect" the induction axiom - if you assume "expect" was a typo for "except" it makes sense....
  $endgroup$
  – David C. Ullrich
  Mar 18 at 14:45
  

  
  
  
  

add a comment | 

1

$begingroup$

All Peano axioms except the induction axiom are statements in first-order logic.
The induction axiom is written as $forall X(0 in X land forall n(n in mathbbN rightarrow (n in X land n' in X)) rightarrow mathbbN subseteq X$, where $n'$ is the successor of $n$.

Now I want to look at an extension of first-order logic. I also allow $exists^infty$ [exists infinity many]. My notes states that the induction axiom can be rewritten only using this extension of first-order logic.

My question is: How?

Since I look at first-order logic I am not allowed to have a set $X$. Here I am allready stuck, because I think I can not just say $exists^infty x$ to have something like a set ...
I think the solution requires two steps: First get rid of the set and then use $exists^infty$ to make it well-defined in my case.

logic first-order-logic peano-axioms

share|cite|improve this question

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

asked Mar 18 at 10:49

SqyuliSqyuli

344111

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  It's kinda weird talking about Peano and first-order while quantifying over subsets (second-order) and referring to $Bbb N$ in the formula.
  $endgroup$
  – Asaf Karagila♦
  Mar 18 at 11:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @AsafKaragila Well he did say all the axioms "expect" the induction axiom - if you assume "expect" was a typo for "except" it makes sense....
  $endgroup$
  – David C. Ullrich
  Mar 18 at 14:45
  

  
  
  
  

add a comment | 

$begingroup$

All Peano axioms except the induction axiom are statements in first-order logic.
The induction axiom is written as $forall X(0 in X land forall n(n in mathbbN rightarrow (n in X land n' in X)) rightarrow mathbbN subseteq X$, where $n'$ is the successor of $n$.

Now I want to look at an extension of first-order logic. I also allow $exists^infty$ [exists infinity many]. My notes states that the induction axiom can be rewritten only using this extension of first-order logic.

My question is: How?

Since I look at first-order logic I am not allowed to have a set $X$. Here I am allready stuck, because I think I can not just say $exists^infty x$ to have something like a set ...
I think the solution requires two steps: First get rid of the set and then use $exists^infty$ to make it well-defined in my case.

logic first-order-logic peano-axioms

share|cite|improve this question

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

asked Mar 18 at 10:49

SqyuliSqyuli

344111

$endgroup$

share|cite|improve this question

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

asked Mar 18 at 10:49

SqyuliSqyuli

344111

share|cite|improve this question

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

asked Mar 18 at 10:49

SqyuliSqyuli

344111

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

edited Mar 18 at 14:43

David C. Ullrich

61.6k43995

asked Mar 18 at 10:49

SqyuliSqyuli

344111

asked Mar 18 at 10:49

SqyuliSqyuli

344111

1 Answer
1

active

oldest

votes

3

$begingroup$

Note that induction is equivalent to well-ordering (more generally to well-foundedness). Namely, removing the induction axiom, a model of $sf PA$ is well-ordered if and only if it satisfies the (second-order) induction axiom.

But well-ordering is equivalent to "there is no infinite decreasing chain". Finally, since in $sf PA$ every non-zero element has a predecessor, this means that well-ordering is equivalent to stating that no element has infinitely many elements smaller than itself.

And this should be fairly straightforward to state using $exists^infty$.

share|cite|improve this answer

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771

$endgroup$

add a comment | 

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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152639%2fpeano-axioms-and-first-order-logic-with-exists-infty%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

Note that induction is equivalent to well-ordering (more generally to well-foundedness). Namely, removing the induction axiom, a model of $sf PA$ is well-ordered if and only if it satisfies the (second-order) induction axiom.

But well-ordering is equivalent to "there is no infinite decreasing chain". Finally, since in $sf PA$ every non-zero element has a predecessor, this means that well-ordering is equivalent to stating that no element has infinitely many elements smaller than itself.

And this should be fairly straightforward to state using $exists^infty$.

share|cite|improve this answer

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771

$endgroup$

add a comment | 

3

$begingroup$

Note that induction is equivalent to well-ordering (more generally to well-foundedness). Namely, removing the induction axiom, a model of $sf PA$ is well-ordered if and only if it satisfies the (second-order) induction axiom.

But well-ordering is equivalent to "there is no infinite decreasing chain". Finally, since in $sf PA$ every non-zero element has a predecessor, this means that well-ordering is equivalent to stating that no element has infinitely many elements smaller than itself.

And this should be fairly straightforward to state using $exists^infty$.

share|cite|improve this answer

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771

$endgroup$

add a comment | 

$begingroup$

Note that induction is equivalent to well-ordering (more generally to well-foundedness). Namely, removing the induction axiom, a model of $sf PA$ is well-ordered if and only if it satisfies the (second-order) induction axiom.

But well-ordering is equivalent to "there is no infinite decreasing chain". Finally, since in $sf PA$ every non-zero element has a predecessor, this means that well-ordering is equivalent to stating that no element has infinitely many elements smaller than itself.

And this should be fairly straightforward to state using $exists^infty$.

share|cite|improve this answer

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771

$endgroup$

share|cite|improve this answer

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771

answered Mar 18 at 11:19

Asaf Karagila♦Asaf Karagila

307k33439771