Mixing
Spivak's Calculus Exercise 2-9
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
This is exercise 2-9 from Spivak's Calculus:
Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k + 1$ whenever it contains $k$, then $A$ contains all natural numbers $> n_0$.
Spivak's solution goes something like this: Let $B = l in mathbbN mid n_0 + l in A $. Clearly $0 in B$. Now suppose $l in B$. This means $n_0 + l in A$. By the property of $A$ it follows that $n_0 + l + 1 in A$ and thus $l+1 in B$. Therefore, $B = mathbbN$ and $A$ contains all $n ge n_0$.
My attempted solution, however, was more mechanical. I will readily admit that defining $B$ to be an inductive set in terms of $A$ is way more elegant, but I still wanted to run my proof by math.se to see if it has any flaws in its logical construction. This is my proof:
Let $P(n) := nge n_0 to nin A$. For the inductive hypothesis, suppose $P(n)$ is true, and suppose $n+1 ge n_0$. If $n+1 = n_0$ then clearly $n+1 in A$. If $n+1 > n_0$, then $n ge n_0$, so by assumption $n in A$. By the property of $A$ it also follows that $n+1in A$. Hence $P(n+1)$ is also true. For the base case, if $n_0 > 0$, then $P(0)$ is vacuously true. If $n_0 = 0$, then $0 in A$ and $P(0)$ is true as well. Therefore, $forall n ge n_0(nin A)$.
The interesting question is if this base case proof works correctly.
proof-verification logic induction first-order-logic
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
asked Jul 19 at 19:25
MuchToLearn
918
 |Â
show 2 more comments
up vote
1
down vote
favorite
This is exercise 2-9 from Spivak's Calculus:
Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k + 1$ whenever it contains $k$, then $A$ contains all natural numbers $> n_0$.
Spivak's solution goes something like this: Let $B = l in mathbbN mid n_0 + l in A $. Clearly $0 in B$. Now suppose $l in B$. This means $n_0 + l in A$. By the property of $A$ it follows that $n_0 + l + 1 in A$ and thus $l+1 in B$. Therefore, $B = mathbbN$ and $A$ contains all $n ge n_0$.
My attempted solution, however, was more mechanical. I will readily admit that defining $B$ to be an inductive set in terms of $A$ is way more elegant, but I still wanted to run my proof by math.se to see if it has any flaws in its logical construction. This is my proof:
Let $P(n) := nge n_0 to nin A$. For the inductive hypothesis, suppose $P(n)$ is true, and suppose $n+1 ge n_0$. If $n+1 = n_0$ then clearly $n+1 in A$. If $n+1 > n_0$, then $n ge n_0$, so by assumption $n in A$. By the property of $A$ it also follows that $n+1in A$. Hence $P(n+1)$ is also true. For the base case, if $n_0 > 0$, then $P(0)$ is vacuously true. If $n_0 = 0$, then $0 in A$ and $P(0)$ is true as well. Therefore, $forall n ge n_0(nin A)$.
The interesting question is if this base case proof works correctly.
proof-verification logic induction first-order-logic
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
asked Jul 19 at 19:25
MuchToLearn
918
If $P(n)$ is true, then $n geq n_0$ and it immediately follows that $n+1 > n_0$. So you do not need to suppose $n+1 geq n_0$ and the $n+1 = n_0$ is unnecessary.
– gd1035
Jul 19 at 19:33
1
I disagree. Assuming $P(n)$ tells you nothing about the precise value of $n$. It tells that if it is greater than $n_0$, then it is in $A$, but you don't know that it is greater than $n_0$.
– MuchToLearn
Jul 19 at 19:46
True, but if $n geq n_0$ then it must be true that $n+1 > n_0$
– gd1035
Jul 19 at 19:49
If $n+1 = n_0$, then $n = n_0 - 1$ and so $n < n_0$, but this can't happen under your assumption that $P(n)$ is true
– gd1035
Jul 19 at 19:50
But you don't know $n ge n_0$, you are given $n + 1 ge n_0$. After all, it may very well be the case that $n + 1 = n_0$, in which case $n < n_0$ so you can't use the assumption of $P(n)$ at all.
– MuchToLearn
Jul 19 at 19:59
 |Â
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This is exercise 2-9 from Spivak's Calculus:
Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k + 1$ whenever it contains $k$, then $A$ contains all natural numbers $> n_0$.
Spivak's solution goes something like this: Let $B = l in mathbbN mid n_0 + l in A $. Clearly $0 in B$. Now suppose $l in B$. This means $n_0 + l in A$. By the property of $A$ it follows that $n_0 + l + 1 in A$ and thus $l+1 in B$. Therefore, $B = mathbbN$ and $A$ contains all $n ge n_0$.
My attempted solution, however, was more mechanical. I will readily admit that defining $B$ to be an inductive set in terms of $A$ is way more elegant, but I still wanted to run my proof by math.se to see if it has any flaws in its logical construction. This is my proof:
Let $P(n) := nge n_0 to nin A$. For the inductive hypothesis, suppose $P(n)$ is true, and suppose $n+1 ge n_0$. If $n+1 = n_0$ then clearly $n+1 in A$. If $n+1 > n_0$, then $n ge n_0$, so by assumption $n in A$. By the property of $A$ it also follows that $n+1in A$. Hence $P(n+1)$ is also true. For the base case, if $n_0 > 0$, then $P(0)$ is vacuously true. If $n_0 = 0$, then $0 in A$ and $P(0)$ is true as well. Therefore, $forall n ge n_0(nin A)$.
The interesting question is if this base case proof works correctly.
proof-verification logic induction first-order-logic
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
asked Jul 19 at 19:25
MuchToLearn
918
This is exercise 2-9 from Spivak's Calculus:
Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k + 1$ whenever it contains $k$, then $A$ contains all natural numbers $> n_0$.
Spivak's solution goes something like this: Let $B = l in mathbbN mid n_0 + l in A $. Clearly $0 in B$. Now suppose $l in B$. This means $n_0 + l in A$. By the property of $A$ it follows that $n_0 + l + 1 in A$ and thus $l+1 in B$. Therefore, $B = mathbbN$ and $A$ contains all $n ge n_0$.
My attempted solution, however, was more mechanical. I will readily admit that defining $B$ to be an inductive set in terms of $A$ is way more elegant, but I still wanted to run my proof by math.se to see if it has any flaws in its logical construction. This is my proof:
Let $P(n) := nge n_0 to nin A$. For the inductive hypothesis, suppose $P(n)$ is true, and suppose $n+1 ge n_0$. If $n+1 = n_0$ then clearly $n+1 in A$. If $n+1 > n_0$, then $n ge n_0$, so by assumption $n in A$. By the property of $A$ it also follows that $n+1in A$. Hence $P(n+1)$ is also true. For the base case, if $n_0 > 0$, then $P(0)$ is vacuously true. If $n_0 = 0$, then $0 in A$ and $P(0)$ is true as well. Therefore, $forall n ge n_0(nin A)$.
The interesting question is if this base case proof works correctly.
proof-verification logic induction first-order-logic
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
asked Jul 19 at 19:25
MuchToLearn
918
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
edited Jul 29 at 20:36
Taroccoesbrocco
3,48941431
3,48941431
asked Jul 19 at 19:25
MuchToLearn
918
asked Jul 19 at 19:25
MuchToLearn
918
asked Jul 19 at 19:25
MuchToLearn
918
918
If $P(n)$ is true, then $n geq n_0$ and it immediately follows that $n+1 > n_0$. So you do not need to suppose $n+1 geq n_0$ and the $n+1 = n_0$ is unnecessary.
– gd1035
Jul 19 at 19:33
1
I disagree. Assuming $P(n)$ tells you nothing about the precise value of $n$. It tells that if it is greater than $n_0$, then it is in $A$, but you don't know that it is greater than $n_0$.
– MuchToLearn
Jul 19 at 19:46
True, but if $n geq n_0$ then it must be true that $n+1 > n_0$
– gd1035
Jul 19 at 19:49
If $n+1 = n_0$, then $n = n_0 - 1$ and so $n < n_0$, but this can't happen under your assumption that $P(n)$ is true
– gd1035
Jul 19 at 19:50
But you don't know $n ge n_0$, you are given $n + 1 ge n_0$. After all, it may very well be the case that $n + 1 = n_0$, in which case $n < n_0$ so you can't use the assumption of $P(n)$ at all.
– MuchToLearn
Jul 19 at 19:59
 |Â
show 2 more comments
If $P(n)$ is true, then $n geq n_0$ and it immediately follows that $n+1 > n_0$. So you do not need to suppose $n+1 geq n_0$ and the $n+1 = n_0$ is unnecessary.
– gd1035
Jul 19 at 19:33
1
I disagree. Assuming $P(n)$ tells you nothing about the precise value of $n$. It tells that if it is greater than $n_0$, then it is in $A$, but you don't know that it is greater than $n_0$.
– MuchToLearn
Jul 19 at 19:46
True, but if $n geq n_0$ then it must be true that $n+1 > n_0$
– gd1035
Jul 19 at 19:49
If $n+1 = n_0$, then $n = n_0 - 1$ and so $n < n_0$, but this can't happen under your assumption that $P(n)$ is true
– gd1035
Jul 19 at 19:50
But you don't know $n ge n_0$, you are given $n + 1 ge n_0$. After all, it may very well be the case that $n + 1 = n_0$, in which case $n < n_0$ so you can't use the assumption of $P(n)$ at all.
– MuchToLearn
Jul 19 at 19:59
If $P(n)$ is true, then $n geq n_0$ and it immediately follows that $n+1 > n_0$. So you do not need to suppose $n+1 geq n_0$ and the $n+1 = n_0$ is unnecessary.
– gd1035
Jul 19 at 19:33
If $P(n)$ is true, then $n geq n_0$ and it immediately follows that $n+1 > n_0$. So you do not need to suppose $n+1 geq n_0$ and the $n+1 = n_0$ is unnecessary.
– gd1035
Jul 19 at 19:33
1
1
I disagree. Assuming $P(n)$ tells you nothing about the precise value of $n$. It tells that if it is greater than $n_0$, then it is in $A$, but you don't know that it is greater than $n_0$.
– MuchToLearn
Jul 19 at 19:46
I disagree. Assuming $P(n)$ tells you nothing about the precise value of $n$. It tells that if it is greater than $n_0$, then it is in $A$, but you don't know that it is greater than $n_0$.
– MuchToLearn
Jul 19 at 19:46
True, but if $n geq n_0$ then it must be true that $n+1 > n_0$
– gd1035
Jul 19 at 19:49
True, but if $n geq n_0$ then it must be true that $n+1 > n_0$
– gd1035
Jul 19 at 19:49
If $n+1 = n_0$, then $n = n_0 - 1$ and so $n < n_0$, but this can't happen under your assumption that $P(n)$ is true
– gd1035
Jul 19 at 19:50
If $n+1 = n_0$, then $n = n_0 - 1$ and so $n < n_0$, but this can't happen under your assumption that $P(n)$ is true
– gd1035
Jul 19 at 19:50
But you don't know $n ge n_0$, you are given $n + 1 ge n_0$. After all, it may very well be the case that $n + 1 = n_0$, in which case $n < n_0$ so you can't use the assumption of $P(n)$ at all.
– MuchToLearn
Jul 19 at 19:59
But you don't know $n ge n_0$, you are given $n + 1 ge n_0$. After all, it may very well be the case that $n + 1 = n_0$, in which case $n < n_0$ so you can't use the assumption of $P(n)$ at all.
– MuchToLearn
Jul 19 at 19:59
 |Â
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2856982%2fspivaks-calculus-exercise-2-9%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
If $P(n)$ is true, then $n geq n_0$ and it immediately follows that $n+1 > n_0$. So you do not need to suppose $n+1 geq n_0$ and the $n+1 = n_0$ is unnecessary.
– gd1035
Jul 19 at 19:33
1
I disagree. Assuming $P(n)$ tells you nothing about the precise value of $n$. It tells that if it is greater than $n_0$, then it is in $A$, but you don't know that it is greater than $n_0$.
– MuchToLearn
Jul 19 at 19:46
True, but if $n geq n_0$ then it must be true that $n+1 > n_0$
– gd1035
Jul 19 at 19:49
If $n+1 = n_0$, then $n = n_0 - 1$ and so $n < n_0$, but this can't happen under your assumption that $P(n)$ is true
– gd1035
Jul 19 at 19:50
But you don't know $n ge n_0$, you are given $n + 1 ge n_0$. After all, it may very well be the case that $n + 1 = n_0$, in which case $n < n_0$ so you can't use the assumption of $P(n)$ at all.
– MuchToLearn
Jul 19 at 19:59