$Q(n)$: “$P(k)$ holds for all $k<n$”. Then why is $Q(0)$ clearly true? [duplicate]
$begingroup$
This question already has an answer here:
Strong induction and vacuous truth
2 answers
Strong Induction Requires No Base Case?
2 answers
Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?
6 answers
It is a principle and proof from Introduction to Set Theory, Hrbacek and Jech.
In the proof, line 1 and 2, I couldn't understand why $Q(0)$ is true.
$Q(0)$ means that "$P(k)$ holds for all $k<0$".
I understood there are no $k<0$.
And then I couldn't proceed.
induction proof-explanation
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
$endgroup$
marked as duplicate by Asaf Karagila♦ set-theory
Users with the set-theory badge can single-handedly close set-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:38
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Strong induction and vacuous truth
2 answers
Strong Induction Requires No Base Case?
2 answers
Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?
6 answers
It is a principle and proof from Introduction to Set Theory, Hrbacek and Jech.
In the proof, line 1 and 2, I couldn't understand why $Q(0)$ is true.
$Q(0)$ means that "$P(k)$ holds for all $k<0$".
I understood there are no $k<0$.
And then I couldn't proceed.
induction proof-explanation
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
$endgroup$
marked as duplicate by Asaf Karagila♦ set-theory
Users with the set-theory badge can single-handedly close set-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:38
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Vacuous truth
$endgroup$
– Wojowu
Jan 4 at 12:05
add a comment |
$begingroup$
This question already has an answer here:
Strong induction and vacuous truth
2 answers
Strong Induction Requires No Base Case?
2 answers
Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?
6 answers
It is a principle and proof from Introduction to Set Theory, Hrbacek and Jech.
In the proof, line 1 and 2, I couldn't understand why $Q(0)$ is true.
$Q(0)$ means that "$P(k)$ holds for all $k<0$".
I understood there are no $k<0$.
And then I couldn't proceed.
induction proof-explanation
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
$endgroup$
This question already has an answer here:
Strong induction and vacuous truth
2 answers
Strong Induction Requires No Base Case?
2 answers
Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?
6 answers
It is a principle and proof from Introduction to Set Theory, Hrbacek and Jech.
In the proof, line 1 and 2, I couldn't understand why $Q(0)$ is true.
$Q(0)$ means that "$P(k)$ holds for all $k<0$".
I understood there are no $k<0$.
And then I couldn't proceed.
This question already has an answer here:
Strong induction and vacuous truth
2 answers
Strong Induction Requires No Base Case?
2 answers
Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?
6 answers
induction proof-explanation
induction proof-explanation
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
edited Jan 4 at 17:54
Andrés E. Caicedo
65.3k8158247
65.3k8158247
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
asked Jan 4 at 12:02
Doyun NamDoyun Nam
66119
66119
marked as duplicate by Asaf Karagila♦ set-theory
Users with the set-theory badge can single-handedly close set-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:38
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Asaf Karagila♦ set-theory
Users with the set-theory badge can single-handedly close set-theory questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:38
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Vacuous truth
$endgroup$
– Wojowu
Jan 4 at 12:05
add a comment |
$begingroup$
Vacuous truth
$endgroup$
– Wojowu
Jan 4 at 12:05
$begingroup$
Vacuous truth
$endgroup$
– Wojowu
Jan 4 at 12:05
$begingroup$
Vacuous truth
$endgroup$
– Wojowu
Jan 4 at 12:05
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
$Q(n)$ is the predicate "$forall kin{Bbb N}_0 (k<nRightarrow P(k))$." Then $Q(0)$ is vacuously true, since the premise is false and so the implication is true.
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
$endgroup$
add a comment |
$begingroup$
A sentence like "for all $x$, if $x$ has the property $A$, then $x$ has the property $B$" is false if (and only if) there exists a counterexample, that is, if there exists some $x$ with the property $A$ but without the property $B$.
If there is no $x$ that has the property $A$, then there is no counterexample, so the sentence is true.
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$Q(n)$ is the predicate "$forall kin{Bbb N}_0 (k<nRightarrow P(k))$." Then $Q(0)$ is vacuously true, since the premise is false and so the implication is true.
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
$endgroup$
add a comment |
$begingroup$
$Q(n)$ is the predicate "$forall kin{Bbb N}_0 (k<nRightarrow P(k))$." Then $Q(0)$ is vacuously true, since the premise is false and so the implication is true.
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
$endgroup$
add a comment |
$begingroup$
$Q(n)$ is the predicate "$forall kin{Bbb N}_0 (k<nRightarrow P(k))$." Then $Q(0)$ is vacuously true, since the premise is false and so the implication is true.
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
$endgroup$
$Q(n)$ is the predicate "$forall kin{Bbb N}_0 (k<nRightarrow P(k))$." Then $Q(0)$ is vacuously true, since the premise is false and so the implication is true.
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
answered Jan 4 at 12:23
WuestenfuxWuestenfux
4,2871413
4,2871413
add a comment |
add a comment |
$begingroup$
A sentence like "for all $x$, if $x$ has the property $A$, then $x$ has the property $B$" is false if (and only if) there exists a counterexample, that is, if there exists some $x$ with the property $A$ but without the property $B$.
If there is no $x$ that has the property $A$, then there is no counterexample, so the sentence is true.
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
$endgroup$
add a comment |
$begingroup$
A sentence like "for all $x$, if $x$ has the property $A$, then $x$ has the property $B$" is false if (and only if) there exists a counterexample, that is, if there exists some $x$ with the property $A$ but without the property $B$.
If there is no $x$ that has the property $A$, then there is no counterexample, so the sentence is true.
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
$endgroup$
add a comment |
$begingroup$
A sentence like "for all $x$, if $x$ has the property $A$, then $x$ has the property $B$" is false if (and only if) there exists a counterexample, that is, if there exists some $x$ with the property $A$ but without the property $B$.
If there is no $x$ that has the property $A$, then there is no counterexample, so the sentence is true.
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
$endgroup$
A sentence like "for all $x$, if $x$ has the property $A$, then $x$ has the property $B$" is false if (and only if) there exists a counterexample, that is, if there exists some $x$ with the property $A$ but without the property $B$.
If there is no $x$ that has the property $A$, then there is no counterexample, so the sentence is true.
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
answered Jan 4 at 12:09
ajotatxeajotatxe
53.8k23890
53.8k23890
add a comment |
add a comment |
$begingroup$
Vacuous truth
$endgroup$
– Wojowu
Jan 4 at 12:05