Mixing
What is the difference between “for some $k inmathbb{R}$” and “$forall: k inmathbb{R}$”?
up vote
-1
down vote
favorite
When proving by induction, in the IH you're supposed to write something like "suppose $a_k < a_{k+1} < 15$ for some $k in Bbb R$. If I instead write for all $k in Bbb R$ is that considered wrong?
abstract-algebra
edited yesterday
Hirak
2,54911336
asked yesterday
ming
321
add a comment |
up vote
-1
down vote
favorite
When proving by induction, in the IH you're supposed to write something like "suppose $a_k < a_{k+1} < 15$ for some $k in Bbb R$. If I instead write for all $k in Bbb R$ is that considered wrong?
abstract-algebra
edited yesterday
Hirak
2,54911336
asked yesterday
ming
321
3
Are you sure you don't mean $kinBbb N$?
– J.G.
yesterday
In general, in a proof by induction we have to prove that $P(k)$ holds for every $k$.
– Mauro ALLEGRANZA
yesterday
The proof runs as follows : (i) Prove that $P(0)$ holds. (ii) prove that, provided that $P(k)$ holds, also $P(k+1)$ holds, i.e. that $P(k) to P(k+1)$ holds, for every $k$.
– Mauro ALLEGRANZA
yesterday
In general, when you do a proof by induction, you work in a countable set, most often $mathbb{N}$, and not $mathbb{R}$. So can you provide more details? Why do you want to do induction in $mathbb{R}$?
– Todor Markov
yesterday
Oh I just had to prove that a recursive sequence is non-decreasing so I just said suppose $a_k < a_{k+1} < 15$ for all $k epsilon Bbb R$ but I got marks taken off for saying "all" instead of "some"
– ming
yesterday
add a comment |
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
When proving by induction, in the IH you're supposed to write something like "suppose $a_k < a_{k+1} < 15$ for some $k in Bbb R$. If I instead write for all $k in Bbb R$ is that considered wrong?
abstract-algebra
edited yesterday
Hirak
2,54911336
asked yesterday
ming
321
When proving by induction, in the IH you're supposed to write something like "suppose $a_k < a_{k+1} < 15$ for some $k in Bbb R$. If I instead write for all $k in Bbb R$ is that considered wrong?
abstract-algebra
abstract-algebra
edited yesterday
Hirak
2,54911336
asked yesterday
ming
321
edited yesterday
Hirak
2,54911336
asked yesterday
ming
321
edited yesterday
Hirak
2,54911336
edited yesterday
Hirak
2,54911336
edited yesterday
Hirak
2,54911336
2,54911336
asked yesterday
ming
321
asked yesterday
ming
321
asked yesterday
ming
321
321
3
Are you sure you don't mean $kinBbb N$?
– J.G.
yesterday
In general, in a proof by induction we have to prove that $P(k)$ holds for every $k$.
– Mauro ALLEGRANZA
yesterday
The proof runs as follows : (i) Prove that $P(0)$ holds. (ii) prove that, provided that $P(k)$ holds, also $P(k+1)$ holds, i.e. that $P(k) to P(k+1)$ holds, for every $k$.
– Mauro ALLEGRANZA
yesterday
In general, when you do a proof by induction, you work in a countable set, most often $mathbb{N}$, and not $mathbb{R}$. So can you provide more details? Why do you want to do induction in $mathbb{R}$?
– Todor Markov
yesterday
Oh I just had to prove that a recursive sequence is non-decreasing so I just said suppose $a_k < a_{k+1} < 15$ for all $k epsilon Bbb R$ but I got marks taken off for saying "all" instead of "some"
– ming
yesterday
add a comment |
3
Are you sure you don't mean $kinBbb N$?
– J.G.
yesterday
In general, in a proof by induction we have to prove that $P(k)$ holds for every $k$.
– Mauro ALLEGRANZA
yesterday
The proof runs as follows : (i) Prove that $P(0)$ holds. (ii) prove that, provided that $P(k)$ holds, also $P(k+1)$ holds, i.e. that $P(k) to P(k+1)$ holds, for every $k$.
– Mauro ALLEGRANZA
yesterday
In general, when you do a proof by induction, you work in a countable set, most often $mathbb{N}$, and not $mathbb{R}$. So can you provide more details? Why do you want to do induction in $mathbb{R}$?
– Todor Markov
yesterday
Oh I just had to prove that a recursive sequence is non-decreasing so I just said suppose $a_k < a_{k+1} < 15$ for all $k epsilon Bbb R$ but I got marks taken off for saying "all" instead of "some"
– ming
yesterday
3
3
Are you sure you don't mean $kinBbb N$?
– J.G.
yesterday
Are you sure you don't mean $kinBbb N$?
– J.G.
yesterday
In general, in a proof by induction we have to prove that $P(k)$ holds for every $k$.
– Mauro ALLEGRANZA
yesterday
In general, in a proof by induction we have to prove that $P(k)$ holds for every $k$.
– Mauro ALLEGRANZA
yesterday
The proof runs as follows : (i) Prove that $P(0)$ holds. (ii) prove that, provided that $P(k)$ holds, also $P(k+1)$ holds, i.e. that $P(k) to P(k+1)$ holds, for every $k$.
– Mauro ALLEGRANZA
yesterday
The proof runs as follows : (i) Prove that $P(0)$ holds. (ii) prove that, provided that $P(k)$ holds, also $P(k+1)$ holds, i.e. that $P(k) to P(k+1)$ holds, for every $k$.
– Mauro ALLEGRANZA
yesterday
In general, when you do a proof by induction, you work in a countable set, most often $mathbb{N}$, and not $mathbb{R}$. So can you provide more details? Why do you want to do induction in $mathbb{R}$?
– Todor Markov
yesterday
In general, when you do a proof by induction, you work in a countable set, most often $mathbb{N}$, and not $mathbb{R}$. So can you provide more details? Why do you want to do induction in $mathbb{R}$?
– Todor Markov
yesterday
Oh I just had to prove that a recursive sequence is non-decreasing so I just said suppose $a_k < a_{k+1} < 15$ for all $k epsilon Bbb R$ but I got marks taken off for saying "all" instead of "some"
– ming
yesterday
Oh I just had to prove that a recursive sequence is non-decreasing so I just said suppose $a_k < a_{k+1} < 15$ for all $k epsilon Bbb R$ but I got marks taken off for saying "all" instead of "some"
– ming
yesterday
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Consider the following situation: For every $ninmathbb{N}$ you have a statement $P(n)$, which is either true or false.
The induction principle says the following. You first explicitly show that $P(1)$ is true. Then you show that $P(n)implies P(n+1)$ for all $ngeq 1$. Now you get this nice domino effect: Since $P(1)$ is true and $P(1)implies P(2)$, $P(2)$ is true as well. Since $P(2)$ is true and $P(2)implies P(3)$, $P(3)$ is true. You can easily see that we now showed that $P(n)$ is true for all $n$.
Sometimes it is more convenient to show that $(P(1) wedge dots wedge P(n))implies P(n+1)$. In that case the left part is sometimes written as, $P(k)$ for all $kleq n$. You can show that a base step together with the above rule will also show that all $P(n)$ are true.
What you never should write is the following: $(forall nin mathbb{N}:P(n))implies P(n+1)$. This doesn't make sense for two reasons:
- You want to show $forall nin mathbb{N}:P(n)$, so why would it be your induction hypothesis? If you assume this, then obviously what you want to prove is correct, but what if it is false?
- the variable $n+1$ is not defined on the right side of the implication $(forall nin mathbb{N}:P(n))implies P(n+1)$. This is just bad mathematics.
answered yesterday
Mathematician 42
8,50111438
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Consider the following situation: For every $ninmathbb{N}$ you have a statement $P(n)$, which is either true or false.
The induction principle says the following. You first explicitly show that $P(1)$ is true. Then you show that $P(n)implies P(n+1)$ for all $ngeq 1$. Now you get this nice domino effect: Since $P(1)$ is true and $P(1)implies P(2)$, $P(2)$ is true as well. Since $P(2)$ is true and $P(2)implies P(3)$, $P(3)$ is true. You can easily see that we now showed that $P(n)$ is true for all $n$.
Sometimes it is more convenient to show that $(P(1) wedge dots wedge P(n))implies P(n+1)$. In that case the left part is sometimes written as, $P(k)$ for all $kleq n$. You can show that a base step together with the above rule will also show that all $P(n)$ are true.
What you never should write is the following: $(forall nin mathbb{N}:P(n))implies P(n+1)$. This doesn't make sense for two reasons:
- You want to show $forall nin mathbb{N}:P(n)$, so why would it be your induction hypothesis? If you assume this, then obviously what you want to prove is correct, but what if it is false?
- the variable $n+1$ is not defined on the right side of the implication $(forall nin mathbb{N}:P(n))implies P(n+1)$. This is just bad mathematics.
answered yesterday
Mathematician 42
8,50111438
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours ago
add a comment |
up vote
0
down vote
Consider the following situation: For every $ninmathbb{N}$ you have a statement $P(n)$, which is either true or false.
The induction principle says the following. You first explicitly show that $P(1)$ is true. Then you show that $P(n)implies P(n+1)$ for all $ngeq 1$. Now you get this nice domino effect: Since $P(1)$ is true and $P(1)implies P(2)$, $P(2)$ is true as well. Since $P(2)$ is true and $P(2)implies P(3)$, $P(3)$ is true. You can easily see that we now showed that $P(n)$ is true for all $n$.
Sometimes it is more convenient to show that $(P(1) wedge dots wedge P(n))implies P(n+1)$. In that case the left part is sometimes written as, $P(k)$ for all $kleq n$. You can show that a base step together with the above rule will also show that all $P(n)$ are true.
What you never should write is the following: $(forall nin mathbb{N}:P(n))implies P(n+1)$. This doesn't make sense for two reasons:
- You want to show $forall nin mathbb{N}:P(n)$, so why would it be your induction hypothesis? If you assume this, then obviously what you want to prove is correct, but what if it is false?
- the variable $n+1$ is not defined on the right side of the implication $(forall nin mathbb{N}:P(n))implies P(n+1)$. This is just bad mathematics.
answered yesterday
Mathematician 42
8,50111438
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours ago
add a comment |
up vote
0
down vote
up vote
0
down vote
Consider the following situation: For every $ninmathbb{N}$ you have a statement $P(n)$, which is either true or false.
The induction principle says the following. You first explicitly show that $P(1)$ is true. Then you show that $P(n)implies P(n+1)$ for all $ngeq 1$. Now you get this nice domino effect: Since $P(1)$ is true and $P(1)implies P(2)$, $P(2)$ is true as well. Since $P(2)$ is true and $P(2)implies P(3)$, $P(3)$ is true. You can easily see that we now showed that $P(n)$ is true for all $n$.
Sometimes it is more convenient to show that $(P(1) wedge dots wedge P(n))implies P(n+1)$. In that case the left part is sometimes written as, $P(k)$ for all $kleq n$. You can show that a base step together with the above rule will also show that all $P(n)$ are true.
What you never should write is the following: $(forall nin mathbb{N}:P(n))implies P(n+1)$. This doesn't make sense for two reasons:
- You want to show $forall nin mathbb{N}:P(n)$, so why would it be your induction hypothesis? If you assume this, then obviously what you want to prove is correct, but what if it is false?
- the variable $n+1$ is not defined on the right side of the implication $(forall nin mathbb{N}:P(n))implies P(n+1)$. This is just bad mathematics.
answered yesterday
Mathematician 42
8,50111438
Consider the following situation: For every $ninmathbb{N}$ you have a statement $P(n)$, which is either true or false.
The induction principle says the following. You first explicitly show that $P(1)$ is true. Then you show that $P(n)implies P(n+1)$ for all $ngeq 1$. Now you get this nice domino effect: Since $P(1)$ is true and $P(1)implies P(2)$, $P(2)$ is true as well. Since $P(2)$ is true and $P(2)implies P(3)$, $P(3)$ is true. You can easily see that we now showed that $P(n)$ is true for all $n$.
Sometimes it is more convenient to show that $(P(1) wedge dots wedge P(n))implies P(n+1)$. In that case the left part is sometimes written as, $P(k)$ for all $kleq n$. You can show that a base step together with the above rule will also show that all $P(n)$ are true.
What you never should write is the following: $(forall nin mathbb{N}:P(n))implies P(n+1)$. This doesn't make sense for two reasons:
- You want to show $forall nin mathbb{N}:P(n)$, so why would it be your induction hypothesis? If you assume this, then obviously what you want to prove is correct, but what if it is false?
- the variable $n+1$ is not defined on the right side of the implication $(forall nin mathbb{N}:P(n))implies P(n+1)$. This is just bad mathematics.
answered yesterday
Mathematician 42
8,50111438
answered yesterday
Mathematician 42
8,50111438
answered yesterday
Mathematician 42
8,50111438
answered yesterday
Mathematician 42
8,50111438
8,50111438
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours ago
add a comment |
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours ago
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
Ohh so the reason I can't write for all k is we can't actually assume that it works for every k, we're just saying it works for "some" k, which is true because we proved the base case, and obviously if it works for one case, we know it actually works for AT LEAST 1 k, hence we can write "some"?
– ming
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
You definitely can't assume that it works for all $k$ as that is what you want to show. Usually when working with induction, you want to show that if $P(n)$ holds, so does $P(n+1)$.
– Mathematician 42
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
@ming, That comment is true, but there's a bit more to it. "Some" in your case refers to one number $k$, not a set of them. This is important, because only if you're talking about a specific $k$ you have a "next one" ($k + 1$). However, while it denotes a single number, it is not specified which. That is, you want to be able to substitute $k$ for any number, and get a true statement.
– Todor Markov
yesterday
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours ago
So.. then is it saying basically "we proved that ONE k works so far, the base case. Now let's prove that it works for k+1, k+2, k+3, etc.." And that one case is just denoted by "some"??
– ming
15 hours 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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004635%2fwhat-is-the-difference-between-for-some-k-in-mathbbr-and-forall-k-i%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
3
Are you sure you don't mean $kinBbb N$?
– J.G.
yesterday
In general, in a proof by induction we have to prove that $P(k)$ holds for every $k$.
– Mauro ALLEGRANZA
yesterday
The proof runs as follows : (i) Prove that $P(0)$ holds. (ii) prove that, provided that $P(k)$ holds, also $P(k+1)$ holds, i.e. that $P(k) to P(k+1)$ holds, for every $k$.
– Mauro ALLEGRANZA
yesterday
In general, when you do a proof by induction, you work in a countable set, most often $mathbb{N}$, and not $mathbb{R}$. So can you provide more details? Why do you want to do induction in $mathbb{R}$?
– Todor Markov
yesterday
Oh I just had to prove that a recursive sequence is non-decreasing so I just said suppose $a_k < a_{k+1} < 15$ for all $k epsilon Bbb R$ but I got marks taken off for saying "all" instead of "some"
– ming
yesterday