Mathematical Induction: First vs. Second order Induction Axiom

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

The second-order variables in the second order Induction Axiom of (second order) Peano Arithmetic range over the set of all subsets of the natural numbers,
that is, it has uncountable cardinality. Does the induction scheme on first order Peano Arithmetic has also uncountable number of instances?

logic first-order-logic cardinals peano-axioms second-order-logic

share|cite|improve this question

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

asked Aug 6 at 14:13

George Chailos

91

add a comment | 

up vote
1
down vote

favorite

The second-order variables in the second order Induction Axiom of (second order) Peano Arithmetic range over the set of all subsets of the natural numbers,
that is, it has uncountable cardinality. Does the induction scheme on first order Peano Arithmetic has also uncountable number of instances?

logic first-order-logic cardinals peano-axioms second-order-logic

share|cite|improve this question

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

asked Aug 6 at 14:13

George Chailos

91

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

The second-order variables in the second order Induction Axiom of (second order) Peano Arithmetic range over the set of all subsets of the natural numbers,
that is, it has uncountable cardinality. Does the induction scheme on first order Peano Arithmetic has also uncountable number of instances?

logic first-order-logic cardinals peano-axioms second-order-logic

share|cite|improve this question

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

asked Aug 6 at 14:13

George Chailos

91

The second-order variables in the second order Induction Axiom of (second order) Peano Arithmetic range over the set of all subsets of the natural numbers,
that is, it has uncountable cardinality. Does the induction scheme on first order Peano Arithmetic has also uncountable number of instances?

logic first-order-logic cardinals peano-axioms second-order-logic

share|cite|improve this question

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

asked Aug 6 at 14:13

George Chailos

91

share|cite|improve this question

share|cite|improve this question

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

edited Aug 6 at 18:31

Taroccoesbrocco

3,48941431

3,48941431

asked Aug 6 at 14:13

George Chailos

91

asked Aug 6 at 14:13

George Chailos

91

asked Aug 6 at 14:13

George Chailos

91

91

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
4
down vote

No, it has countably many instances: the set of finite strings from a finite (or countable) alphabet is countable. In that sense, there are "fewer".

But note that there is only one second-order induction axiom: it just has a variable ranging over all subsets, but that does not make it uncountably many separate axioms any more than $forall n(S(n) neq 0)$ is infinitely many axioms.

share|cite|improve this answer

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
  – George Chailos
  Aug 6 at 14:24
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  While that is true, it does not follow from the "hence". The reason is deeper.
  – Mees de Vries
  Aug 6 at 14:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
  – George Chailos
  Aug 6 at 14:44
  

  
  
  
  

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873907%2fmathematical-induction-first-vs-second-order-induction-axiom%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
4
down vote

No, it has countably many instances: the set of finite strings from a finite (or countable) alphabet is countable. In that sense, there are "fewer".

But note that there is only one second-order induction axiom: it just has a variable ranging over all subsets, but that does not make it uncountably many separate axioms any more than $forall n(S(n) neq 0)$ is infinitely many axioms.

share|cite|improve this answer

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
  – George Chailos
  Aug 6 at 14:24
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  While that is true, it does not follow from the "hence". The reason is deeper.
  – Mees de Vries
  Aug 6 at 14:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
  – George Chailos
  Aug 6 at 14:44
  

  
  
  
  

add a comment | 

up vote
4
down vote

No, it has countably many instances: the set of finite strings from a finite (or countable) alphabet is countable. In that sense, there are "fewer".

But note that there is only one second-order induction axiom: it just has a variable ranging over all subsets, but that does not make it uncountably many separate axioms any more than $forall n(S(n) neq 0)$ is infinitely many axioms.

share|cite|improve this answer

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
  – George Chailos
  Aug 6 at 14:24
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  While that is true, it does not follow from the "hence". The reason is deeper.
  – Mees de Vries
  Aug 6 at 14:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
  – George Chailos
  Aug 6 at 14:44
  

  
  
  
  

add a comment | 

up vote
4
down vote

up vote
4
down vote

No, it has countably many instances: the set of finite strings from a finite (or countable) alphabet is countable. In that sense, there are "fewer".

But note that there is only one second-order induction axiom: it just has a variable ranging over all subsets, but that does not make it uncountably many separate axioms any more than $forall n(S(n) neq 0)$ is infinitely many axioms.

share|cite|improve this answer

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

No, it has countably many instances: the set of finite strings from a finite (or countable) alphabet is countable. In that sense, there are "fewer".

But note that there is only one second-order induction axiom: it just has a variable ranging over all subsets, but that does not make it uncountably many separate axioms any more than $forall n(S(n) neq 0)$ is infinitely many axioms.

share|cite|improve this answer

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

share|cite|improve this answer

share|cite|improve this answer

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

answered Aug 6 at 14:17

Mees de Vries

13.7k12345

13.7k12345

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
  – George Chailos
  Aug 6 at 14:24
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  While that is true, it does not follow from the "hence". The reason is deeper.
  – Mees de Vries
  Aug 6 at 14:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
  – George Chailos
  Aug 6 at 14:44
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
  – George Chailos
  Aug 6 at 14:24
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  While that is true, it does not follow from the "hence". The reason is deeper.
  – Mees de Vries
  Aug 6 at 14:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
  – George Chailos
  Aug 6 at 14:44
  

  
  
  
  

Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
– George Chailos
Aug 6 at 14:24

Thanks a lot! Hence, the (single) Second order Iinduction Axiom is strictly stronger than the first order induction schema (countably many axioms).
– George Chailos
Aug 6 at 14:24

2

2

While that is true, it does not follow from the "hence". The reason is deeper.
– Mees de Vries
Aug 6 at 14:26

While that is true, it does not follow from the "hence". The reason is deeper.
– Mees de Vries
Aug 6 at 14:26

Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
– George Chailos
Aug 6 at 14:44

Second-order arithmetic, as a second order theory, is categorical (in contrast with first order) and that is a real strength! (in my opinion). Above I concentrated in the range and the expressive power of the Induction Axiom
– George Chailos
Aug 6 at 14:44

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873907%2fmathematical-induction-first-vs-second-order-induction-axiom%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Name Email

Name Email

Name

Email

Name Email

Name

Email