$Q(n)$: “$P(k)$ holds for all $k<n$”. Then why is $Q(0)$ clearly true? [duplicate]
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 10 hours ago
Andrés E. Caicedo
64.8k8158246
asked 16 hours ago
Doyun Nam
4169
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();
}
);
});
});
15 hours ago
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 |
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 10 hours ago
Andrés E. Caicedo
64.8k8158246
asked 16 hours ago
Doyun Nam
4169
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();
}
);
});
});
15 hours ago
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.
Vacuous truth
– Wojowu
16 hours ago
add a comment |
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 10 hours ago
Andrés E. Caicedo
64.8k8158246
asked 16 hours ago
Doyun Nam
4169
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 10 hours ago
Andrés E. Caicedo
64.8k8158246
asked 16 hours ago
Doyun Nam
4169
edited 10 hours ago
Andrés E. Caicedo
64.8k8158246
asked 16 hours ago
Doyun Nam
4169
edited 10 hours ago
Andrés E. Caicedo
64.8k8158246
edited 10 hours ago
Andrés E. Caicedo
64.8k8158246
edited 10 hours ago
Andrés E. Caicedo
64.8k8158246
64.8k8158246
asked 16 hours ago
Doyun Nam
4169
asked 16 hours ago
Doyun Nam
4169
asked 16 hours ago
Doyun Nam
4169
4169
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();
}
);
});
});
15 hours ago
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();
}
);
});
});
15 hours ago
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.
Vacuous truth
– Wojowu
16 hours ago
add a comment |
Vacuous truth
– Wojowu
16 hours ago
Vacuous truth
– Wojowu
16 hours ago
Vacuous truth
– Wojowu
16 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$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 15 hours ago
Wuestenfux
3,6041411
add a comment |
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 16 hours ago
ajotatxe
53.4k23890
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 15 hours ago
Wuestenfux
3,6041411
add a comment |
$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 15 hours ago
Wuestenfux
3,6041411
add a comment |
$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 15 hours ago
Wuestenfux
3,6041411
$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 15 hours ago
Wuestenfux
3,6041411
answered 15 hours ago
Wuestenfux
3,6041411
answered 15 hours ago
Wuestenfux
3,6041411
answered 15 hours ago
Wuestenfux
3,6041411
3,6041411
add a comment |
add a comment |
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 16 hours ago
ajotatxe
53.4k23890
add a comment |
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 16 hours ago
ajotatxe
53.4k23890
add a comment |
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 16 hours ago
ajotatxe
53.4k23890
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 16 hours ago
ajotatxe
53.4k23890
answered 16 hours ago
ajotatxe
53.4k23890
answered 16 hours ago
ajotatxe
53.4k23890
answered 16 hours ago
ajotatxe
53.4k23890
53.4k23890
add a comment |
add a comment |
Vacuous truth
– Wojowu
16 hours ago