Mixing
Difference between first and second order induction?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Can anyone explain the difference between induction as it's stated in first order logic and that from second order logic? I don't understand the difference as it pertains to things like Peano axioms.
logic induction definition peano-axioms
asked 3 hours ago
user525966
1,943821
add a comment |Â
up vote
2
down vote
favorite
Can anyone explain the difference between induction as it's stated in first order logic and that from second order logic? I don't understand the difference as it pertains to things like Peano axioms.
logic induction definition peano-axioms
asked 3 hours ago
user525966
1,943821
3
Second-order induction is an axiom which applies to any set $Xsubseteq mathbbN$: if $0in X$ and $forall n(n in X rightarrow n+1in X)$, then $X=mathbbN$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $phi$, i.e., sets of the form $X= nin mathbbN: phi(n) mathrmis true$.
– realdonaldtrump
3 hours ago
@realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" includes the formula "$n in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme.
– Carl Mummert
14 secs ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Can anyone explain the difference between induction as it's stated in first order logic and that from second order logic? I don't understand the difference as it pertains to things like Peano axioms.
logic induction definition peano-axioms
asked 3 hours ago
user525966
1,943821
Can anyone explain the difference between induction as it's stated in first order logic and that from second order logic? I don't understand the difference as it pertains to things like Peano axioms.
logic induction definition peano-axioms
logic induction definition peano-axioms
asked 3 hours ago
user525966
1,943821
asked 3 hours ago
user525966
1,943821
asked 3 hours ago
user525966
1,943821
asked 3 hours ago
user525966
1,943821
asked 3 hours ago
user525966
1,943821
1,943821
3
Second-order induction is an axiom which applies to any set $Xsubseteq mathbbN$: if $0in X$ and $forall n(n in X rightarrow n+1in X)$, then $X=mathbbN$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $phi$, i.e., sets of the form $X= nin mathbbN: phi(n) mathrmis true$.
– realdonaldtrump
3 hours ago
@realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" includes the formula "$n in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme.
– Carl Mummert
14 secs ago
add a comment |Â
3
Second-order induction is an axiom which applies to any set $Xsubseteq mathbbN$: if $0in X$ and $forall n(n in X rightarrow n+1in X)$, then $X=mathbbN$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $phi$, i.e., sets of the form $X= nin mathbbN: phi(n) mathrmis true$.
– realdonaldtrump
3 hours ago
@realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" includes the formula "$n in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme.
– Carl Mummert
14 secs ago
3
3
Second-order induction is an axiom which applies to any set $Xsubseteq mathbbN$: if $0in X$ and $forall n(n in X rightarrow n+1in X)$, then $X=mathbbN$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $phi$, i.e., sets of the form $X= nin mathbbN: phi(n) mathrmis true$.
– realdonaldtrump
3 hours ago
Second-order induction is an axiom which applies to any set $Xsubseteq mathbbN$: if $0in X$ and $forall n(n in X rightarrow n+1in X)$, then $X=mathbbN$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $phi$, i.e., sets of the form $X= nin mathbbN: phi(n) mathrmis true$.
– realdonaldtrump
3 hours ago
@realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" includes the formula "$n in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme.
– Carl Mummert
14 secs ago
@realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" includes the formula "$n in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme.
– Carl Mummert
14 secs ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
The informal statement of induction is:
For any property $P$ of natural numbers, if $P(0)$ holds, and $P(n)$ implies $P(n+1)$ for all $n$, then $P(n)$ holds for all $n$.
Of course, this raises the question: What exactly do we mean by a "property of natural numbers"?
One natural interpretation is to identify properties of natural numbers with sets of natural numbers. That is, for any property $P$, we can form the set of all natural numbers satisfying that property. And for any set of natural numbers $X$, we can consider the property of being in $X$. For example, the property of being a prime number corresponds to the set $nin mathbbNmid ntext is prime$
Another natural interpretation is to identify properties of natural numbers with formulas in one free variable in some logic (in this discussion, let's just talk about first-order logic in the language of arithemetic). Here the syntax of the logic gives us a language for writing down properties of natural numbers. For example, the property of being a prime number corresponds to the formula $lnot (x= 1)land forall y, (exists z, (ycdot z = x) rightarrow (y = 1 lor y = x))$.
Induction under the interpretation "properties are sets" can be formalized as follows:
$forall Psubseteq mathbbN: ((0in Pland forall nin mathbbN: (nin P rightarrow (n+1)in P))rightarrow forall nin mathbbN: nin P)$
This is a sentence of second-order logic, since it involves a quantification $forall Psubseteq mathbbN$ over subsets of $mathbbN$.
The interpretation "properties are formulas" leads to the following formalization of induction:
$(varphi(0)land forall n, (varphi(n)rightarrow varphi(n+1)) rightarrow forall n,varphi(n)$
Here we have an infinite schema of sentences of first-order logic, one for each first-order formula $varphi(x)$. It's first-order because the quantifiers only range over elements of $mathbbN$, not subsets, and the formulas $varphi(x)$ are themselves first-order.
It's worth noting that second-order induction is much stronger than first-order induction. Second-order induction applies to all subsets, while first-order induction only applies to those which can be defined by some first-order formula (and since there are are $2^aleph_0$-many subsets of $mathbbN$ and only $aleph_0$-many first-order formulas, there are many subsets which are not definable).
The second-order Peano axioms (which consist of some basic rules of arithmetic, together with the second-order induction axiom above) suffice to pin down $mathbbN$ up to isomorphism.
The first-order Peano axioms (which consist of some basic rules of arithmetic, together with the first-order induction axiom schema above) cannot hope to pin down $mathbbN$ up to isomorphism (thanks to the Löwenheim-Skolem theorems). That is, there are "non-standard models" of the first-order Peano axioms, which satisfy induction for all first-order definable properties, but not for arbitrary subsets.
answered 2 hours ago
Alex Kruckman
25.3k22455
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
The informal statement of induction is:
For any property $P$ of natural numbers, if $P(0)$ holds, and $P(n)$ implies $P(n+1)$ for all $n$, then $P(n)$ holds for all $n$.
Of course, this raises the question: What exactly do we mean by a "property of natural numbers"?
One natural interpretation is to identify properties of natural numbers with sets of natural numbers. That is, for any property $P$, we can form the set of all natural numbers satisfying that property. And for any set of natural numbers $X$, we can consider the property of being in $X$. For example, the property of being a prime number corresponds to the set $nin mathbbNmid ntext is prime$
Another natural interpretation is to identify properties of natural numbers with formulas in one free variable in some logic (in this discussion, let's just talk about first-order logic in the language of arithemetic). Here the syntax of the logic gives us a language for writing down properties of natural numbers. For example, the property of being a prime number corresponds to the formula $lnot (x= 1)land forall y, (exists z, (ycdot z = x) rightarrow (y = 1 lor y = x))$.
Induction under the interpretation "properties are sets" can be formalized as follows:
$forall Psubseteq mathbbN: ((0in Pland forall nin mathbbN: (nin P rightarrow (n+1)in P))rightarrow forall nin mathbbN: nin P)$
This is a sentence of second-order logic, since it involves a quantification $forall Psubseteq mathbbN$ over subsets of $mathbbN$.
The interpretation "properties are formulas" leads to the following formalization of induction:
$(varphi(0)land forall n, (varphi(n)rightarrow varphi(n+1)) rightarrow forall n,varphi(n)$
Here we have an infinite schema of sentences of first-order logic, one for each first-order formula $varphi(x)$. It's first-order because the quantifiers only range over elements of $mathbbN$, not subsets, and the formulas $varphi(x)$ are themselves first-order.
It's worth noting that second-order induction is much stronger than first-order induction. Second-order induction applies to all subsets, while first-order induction only applies to those which can be defined by some first-order formula (and since there are are $2^aleph_0$-many subsets of $mathbbN$ and only $aleph_0$-many first-order formulas, there are many subsets which are not definable).
The second-order Peano axioms (which consist of some basic rules of arithmetic, together with the second-order induction axiom above) suffice to pin down $mathbbN$ up to isomorphism.
The first-order Peano axioms (which consist of some basic rules of arithmetic, together with the first-order induction axiom schema above) cannot hope to pin down $mathbbN$ up to isomorphism (thanks to the Löwenheim-Skolem theorems). That is, there are "non-standard models" of the first-order Peano axioms, which satisfy induction for all first-order definable properties, but not for arbitrary subsets.
answered 2 hours ago
Alex Kruckman
25.3k22455
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
add a comment |Â
up vote
4
down vote
The informal statement of induction is:
For any property $P$ of natural numbers, if $P(0)$ holds, and $P(n)$ implies $P(n+1)$ for all $n$, then $P(n)$ holds for all $n$.
Of course, this raises the question: What exactly do we mean by a "property of natural numbers"?
One natural interpretation is to identify properties of natural numbers with sets of natural numbers. That is, for any property $P$, we can form the set of all natural numbers satisfying that property. And for any set of natural numbers $X$, we can consider the property of being in $X$. For example, the property of being a prime number corresponds to the set $nin mathbbNmid ntext is prime$
Another natural interpretation is to identify properties of natural numbers with formulas in one free variable in some logic (in this discussion, let's just talk about first-order logic in the language of arithemetic). Here the syntax of the logic gives us a language for writing down properties of natural numbers. For example, the property of being a prime number corresponds to the formula $lnot (x= 1)land forall y, (exists z, (ycdot z = x) rightarrow (y = 1 lor y = x))$.
Induction under the interpretation "properties are sets" can be formalized as follows:
$forall Psubseteq mathbbN: ((0in Pland forall nin mathbbN: (nin P rightarrow (n+1)in P))rightarrow forall nin mathbbN: nin P)$
This is a sentence of second-order logic, since it involves a quantification $forall Psubseteq mathbbN$ over subsets of $mathbbN$.
The interpretation "properties are formulas" leads to the following formalization of induction:
$(varphi(0)land forall n, (varphi(n)rightarrow varphi(n+1)) rightarrow forall n,varphi(n)$
Here we have an infinite schema of sentences of first-order logic, one for each first-order formula $varphi(x)$. It's first-order because the quantifiers only range over elements of $mathbbN$, not subsets, and the formulas $varphi(x)$ are themselves first-order.
It's worth noting that second-order induction is much stronger than first-order induction. Second-order induction applies to all subsets, while first-order induction only applies to those which can be defined by some first-order formula (and since there are are $2^aleph_0$-many subsets of $mathbbN$ and only $aleph_0$-many first-order formulas, there are many subsets which are not definable).
The second-order Peano axioms (which consist of some basic rules of arithmetic, together with the second-order induction axiom above) suffice to pin down $mathbbN$ up to isomorphism.
The first-order Peano axioms (which consist of some basic rules of arithmetic, together with the first-order induction axiom schema above) cannot hope to pin down $mathbbN$ up to isomorphism (thanks to the Löwenheim-Skolem theorems). That is, there are "non-standard models" of the first-order Peano axioms, which satisfy induction for all first-order definable properties, but not for arbitrary subsets.
answered 2 hours ago
Alex Kruckman
25.3k22455
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
The informal statement of induction is:
For any property $P$ of natural numbers, if $P(0)$ holds, and $P(n)$ implies $P(n+1)$ for all $n$, then $P(n)$ holds for all $n$.
Of course, this raises the question: What exactly do we mean by a "property of natural numbers"?
One natural interpretation is to identify properties of natural numbers with sets of natural numbers. That is, for any property $P$, we can form the set of all natural numbers satisfying that property. And for any set of natural numbers $X$, we can consider the property of being in $X$. For example, the property of being a prime number corresponds to the set $nin mathbbNmid ntext is prime$
Another natural interpretation is to identify properties of natural numbers with formulas in one free variable in some logic (in this discussion, let's just talk about first-order logic in the language of arithemetic). Here the syntax of the logic gives us a language for writing down properties of natural numbers. For example, the property of being a prime number corresponds to the formula $lnot (x= 1)land forall y, (exists z, (ycdot z = x) rightarrow (y = 1 lor y = x))$.
Induction under the interpretation "properties are sets" can be formalized as follows:
$forall Psubseteq mathbbN: ((0in Pland forall nin mathbbN: (nin P rightarrow (n+1)in P))rightarrow forall nin mathbbN: nin P)$
This is a sentence of second-order logic, since it involves a quantification $forall Psubseteq mathbbN$ over subsets of $mathbbN$.
The interpretation "properties are formulas" leads to the following formalization of induction:
$(varphi(0)land forall n, (varphi(n)rightarrow varphi(n+1)) rightarrow forall n,varphi(n)$
Here we have an infinite schema of sentences of first-order logic, one for each first-order formula $varphi(x)$. It's first-order because the quantifiers only range over elements of $mathbbN$, not subsets, and the formulas $varphi(x)$ are themselves first-order.
It's worth noting that second-order induction is much stronger than first-order induction. Second-order induction applies to all subsets, while first-order induction only applies to those which can be defined by some first-order formula (and since there are are $2^aleph_0$-many subsets of $mathbbN$ and only $aleph_0$-many first-order formulas, there are many subsets which are not definable).
The second-order Peano axioms (which consist of some basic rules of arithmetic, together with the second-order induction axiom above) suffice to pin down $mathbbN$ up to isomorphism.
The first-order Peano axioms (which consist of some basic rules of arithmetic, together with the first-order induction axiom schema above) cannot hope to pin down $mathbbN$ up to isomorphism (thanks to the Löwenheim-Skolem theorems). That is, there are "non-standard models" of the first-order Peano axioms, which satisfy induction for all first-order definable properties, but not for arbitrary subsets.
answered 2 hours ago
Alex Kruckman
25.3k22455
The informal statement of induction is:
For any property $P$ of natural numbers, if $P(0)$ holds, and $P(n)$ implies $P(n+1)$ for all $n$, then $P(n)$ holds for all $n$.
Of course, this raises the question: What exactly do we mean by a "property of natural numbers"?
One natural interpretation is to identify properties of natural numbers with sets of natural numbers. That is, for any property $P$, we can form the set of all natural numbers satisfying that property. And for any set of natural numbers $X$, we can consider the property of being in $X$. For example, the property of being a prime number corresponds to the set $nin mathbbNmid ntext is prime$
Another natural interpretation is to identify properties of natural numbers with formulas in one free variable in some logic (in this discussion, let's just talk about first-order logic in the language of arithemetic). Here the syntax of the logic gives us a language for writing down properties of natural numbers. For example, the property of being a prime number corresponds to the formula $lnot (x= 1)land forall y, (exists z, (ycdot z = x) rightarrow (y = 1 lor y = x))$.
Induction under the interpretation "properties are sets" can be formalized as follows:
$forall Psubseteq mathbbN: ((0in Pland forall nin mathbbN: (nin P rightarrow (n+1)in P))rightarrow forall nin mathbbN: nin P)$
This is a sentence of second-order logic, since it involves a quantification $forall Psubseteq mathbbN$ over subsets of $mathbbN$.
The interpretation "properties are formulas" leads to the following formalization of induction:
$(varphi(0)land forall n, (varphi(n)rightarrow varphi(n+1)) rightarrow forall n,varphi(n)$
Here we have an infinite schema of sentences of first-order logic, one for each first-order formula $varphi(x)$. It's first-order because the quantifiers only range over elements of $mathbbN$, not subsets, and the formulas $varphi(x)$ are themselves first-order.
It's worth noting that second-order induction is much stronger than first-order induction. Second-order induction applies to all subsets, while first-order induction only applies to those which can be defined by some first-order formula (and since there are are $2^aleph_0$-many subsets of $mathbbN$ and only $aleph_0$-many first-order formulas, there are many subsets which are not definable).
The second-order Peano axioms (which consist of some basic rules of arithmetic, together with the second-order induction axiom above) suffice to pin down $mathbbN$ up to isomorphism.
The first-order Peano axioms (which consist of some basic rules of arithmetic, together with the first-order induction axiom schema above) cannot hope to pin down $mathbbN$ up to isomorphism (thanks to the Löwenheim-Skolem theorems). That is, there are "non-standard models" of the first-order Peano axioms, which satisfy induction for all first-order definable properties, but not for arbitrary subsets.
answered 2 hours ago
Alex Kruckman
25.3k22455
edited 2 hours ago
answered 2 hours ago
Alex Kruckman
25.3k22455
answered 2 hours ago
Alex Kruckman
25.3k22455
answered 2 hours ago
Alex Kruckman
25.3k22455
25.3k22455
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
add a comment |Â
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom.
– Carl Mummert
13 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex.
– Carl Mummert
9 mins ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2984410%2fdifference-between-first-and-second-order-induction%23new-answer', 'question_page');
);
Post as a guest
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
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
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
3
Second-order induction is an axiom which applies to any set $Xsubseteq mathbbN$: if $0in X$ and $forall n(n in X rightarrow n+1in X)$, then $X=mathbbN$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $phi$, i.e., sets of the form $X= nin mathbbN: phi(n) mathrmis true$.
– realdonaldtrump
3 hours ago
@realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" includes the formula "$n in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme.
– Carl Mummert
14 secs ago