Mixing
Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even
$begingroup$
As the title says:
Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even.
From my understanding I can either choose not $P$ and prove $Q$ or not $Q$ and prove $P$.
So choosing either $m$ or $n$ as my $P$ or $Q$, I could prove using the definition of even and odd:
$mn$ = $(2k+1)(2i)$ where $m$ is not $P$?
Is this the correct approach?
elementary-number-theory
edited Jan 29 at 1:52
JMoravitz
48.7k43988
asked Jan 29 at 1:01
JohnJohn
446
$endgroup$
add a comment |
$begingroup$
As the title says:
Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even.
From my understanding I can either choose not $P$ and prove $Q$ or not $Q$ and prove $P$.
So choosing either $m$ or $n$ as my $P$ or $Q$, I could prove using the definition of even and odd:
$mn$ = $(2k+1)(2i)$ where $m$ is not $P$?
Is this the correct approach?
elementary-number-theory
edited Jan 29 at 1:52
JMoravitz
48.7k43988
asked Jan 29 at 1:01
JohnJohn
446
$endgroup$
add a comment |
$begingroup$
As the title says:
Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even.
From my understanding I can either choose not $P$ and prove $Q$ or not $Q$ and prove $P$.
So choosing either $m$ or $n$ as my $P$ or $Q$, I could prove using the definition of even and odd:
$mn$ = $(2k+1)(2i)$ where $m$ is not $P$?
Is this the correct approach?
elementary-number-theory
edited Jan 29 at 1:52
JMoravitz
48.7k43988
asked Jan 29 at 1:01
JohnJohn
446
$endgroup$
As the title says:
Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even.
From my understanding I can either choose not $P$ and prove $Q$ or not $Q$ and prove $P$.
So choosing either $m$ or $n$ as my $P$ or $Q$, I could prove using the definition of even and odd:
$mn$ = $(2k+1)(2i)$ where $m$ is not $P$?
Is this the correct approach?
elementary-number-theory
elementary-number-theory
edited Jan 29 at 1:52
JMoravitz
48.7k43988
asked Jan 29 at 1:01
JohnJohn
446
edited Jan 29 at 1:52
JMoravitz
48.7k43988
asked Jan 29 at 1:01
JohnJohn
446
edited Jan 29 at 1:52
JMoravitz
48.7k43988
edited Jan 29 at 1:52
JMoravitz
48.7k43988
edited Jan 29 at 1:52
JMoravitz
48.7k43988
48.7k43988
asked Jan 29 at 1:01
JohnJohn
446
asked Jan 29 at 1:01
JohnJohn
446
asked Jan 29 at 1:01
JohnJohn
446
446
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
You seem to be confusing yourself as to what $P$ and $Q$ might represent in this case.
Let $m$ and $n$ be integers. Let $P$ be the statement "$mn$ is even". Let $Q$ be the statement "$m$ is even or $n$ is even."
Proving $Qimplies P$ is trivial. Suppose without loss of generality that $m$ is even. Then we have some integer $k$ such that $m=2k$ and therefore $mn = (2k)n = 2(kn)$ is even as well. The problem doesn't actually ask us to prove this, but since it is true anyways it might as well be done so you can see more examples.
Now, proving that $Pimplies Q$ is easiest to do by contraposition rather than directly. That is to say, we instead prove that $neg Qimplies neg P$. So, suppose that neither $m$ nor $n$ is even. That is to say, both $m$ and $n$ are odd. Then there exist some integers $k$ and $ell$ such that $m=2k+1$ and $n=2ell + 1$. It follows then that $mn = dots$
$mn = (2k+1)(2ell+1) = 4kell + 2k + 2ell + 1 = 2(2kell + k + ell) + 1$ is odd.
Of course, it could also have been done directly if you know enough about prime numbers and Euclid's lemma. Suppose that $mn$ is even. Then $2mid mn$. It follows by Euclid's lemma that $2mid m$ or $2mid n$. Hence $m$ is even or $n$ is even. Given the nature of your question however, I expect that these properties have not yet been proven for you yet and so likely are not yet valid for you to use.
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
$endgroup$
add a comment |
$begingroup$
I am not sure what you mean by 'using disjunction prove' ... I see that there is a disjunction involved here, yes, but 'disjunction' is not a proof technique.
More importantly, you cannot treat $m$ and $n$, which are numbers as $P$ and $Q$, which are claims
What you can do, is to define $P$ as the claim that "$m$ is even", and $Q$ as "$n$ is even"
Now, since you have to prove that $P lor Q$, which is equivalent to both $neg P rightarrow Q$ and $neg Q rightarrow P$, you do indeed have a choice to either show that $Q$ is true if you assume that $P$ is false, or vice versa.
Now, I see that you are going for the assume $neg P$ route, i.e. assume that $m$ is not even, and thus odd. Ok, that's fine, but you now have to prove that $n$ is even ... rather than just assuming that, which is what you do. That is, you can assume that $m=2k+1$ for some whole number $k$, but you need to show that $n=2i$. And for that, you will need the fact that $mn$ is even, i.e. that $mn=2j$.
To sum up: you have that $m=2k+1$, and that $mn=2j$. Now you need to show that $n=2i$ for some whole number $i$. To do this, I would show that if $n$ is not even, you obtain a contradiction.
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
$endgroup$
add a comment |
$begingroup$
"If $mn$ is even, then $m$ is even or $n$ is even" is equivalent to the contrapositive:
"if not ($m$ is even or $n$ is even), then not ($mn$ is even)."
This is logically equivalent to the following:
"if $m$ is not even and $n$ is not even, then $mn$ is not even,"
i.e., the product of two odd numbers is odd, which is true because
$(2 times u+1)(2 times v+1) = 2 times (2times utimes v+u+v) + 1$ for integers $u$ and $v$.
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3091612%2fusing-disjunction-prove-that-for-all-integers-m-and-n-if-mn-is-even-then%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You seem to be confusing yourself as to what $P$ and $Q$ might represent in this case.
Let $m$ and $n$ be integers. Let $P$ be the statement "$mn$ is even". Let $Q$ be the statement "$m$ is even or $n$ is even."
Proving $Qimplies P$ is trivial. Suppose without loss of generality that $m$ is even. Then we have some integer $k$ such that $m=2k$ and therefore $mn = (2k)n = 2(kn)$ is even as well. The problem doesn't actually ask us to prove this, but since it is true anyways it might as well be done so you can see more examples.
Now, proving that $Pimplies Q$ is easiest to do by contraposition rather than directly. That is to say, we instead prove that $neg Qimplies neg P$. So, suppose that neither $m$ nor $n$ is even. That is to say, both $m$ and $n$ are odd. Then there exist some integers $k$ and $ell$ such that $m=2k+1$ and $n=2ell + 1$. It follows then that $mn = dots$
$mn = (2k+1)(2ell+1) = 4kell + 2k + 2ell + 1 = 2(2kell + k + ell) + 1$ is odd.
Of course, it could also have been done directly if you know enough about prime numbers and Euclid's lemma. Suppose that $mn$ is even. Then $2mid mn$. It follows by Euclid's lemma that $2mid m$ or $2mid n$. Hence $m$ is even or $n$ is even. Given the nature of your question however, I expect that these properties have not yet been proven for you yet and so likely are not yet valid for you to use.
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
$endgroup$
add a comment |
$begingroup$
You seem to be confusing yourself as to what $P$ and $Q$ might represent in this case.
Let $m$ and $n$ be integers. Let $P$ be the statement "$mn$ is even". Let $Q$ be the statement "$m$ is even or $n$ is even."
Proving $Qimplies P$ is trivial. Suppose without loss of generality that $m$ is even. Then we have some integer $k$ such that $m=2k$ and therefore $mn = (2k)n = 2(kn)$ is even as well. The problem doesn't actually ask us to prove this, but since it is true anyways it might as well be done so you can see more examples.
Now, proving that $Pimplies Q$ is easiest to do by contraposition rather than directly. That is to say, we instead prove that $neg Qimplies neg P$. So, suppose that neither $m$ nor $n$ is even. That is to say, both $m$ and $n$ are odd. Then there exist some integers $k$ and $ell$ such that $m=2k+1$ and $n=2ell + 1$. It follows then that $mn = dots$
$mn = (2k+1)(2ell+1) = 4kell + 2k + 2ell + 1 = 2(2kell + k + ell) + 1$ is odd.
Of course, it could also have been done directly if you know enough about prime numbers and Euclid's lemma. Suppose that $mn$ is even. Then $2mid mn$. It follows by Euclid's lemma that $2mid m$ or $2mid n$. Hence $m$ is even or $n$ is even. Given the nature of your question however, I expect that these properties have not yet been proven for you yet and so likely are not yet valid for you to use.
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
$endgroup$
add a comment |
$begingroup$
You seem to be confusing yourself as to what $P$ and $Q$ might represent in this case.
Let $m$ and $n$ be integers. Let $P$ be the statement "$mn$ is even". Let $Q$ be the statement "$m$ is even or $n$ is even."
Proving $Qimplies P$ is trivial. Suppose without loss of generality that $m$ is even. Then we have some integer $k$ such that $m=2k$ and therefore $mn = (2k)n = 2(kn)$ is even as well. The problem doesn't actually ask us to prove this, but since it is true anyways it might as well be done so you can see more examples.
Now, proving that $Pimplies Q$ is easiest to do by contraposition rather than directly. That is to say, we instead prove that $neg Qimplies neg P$. So, suppose that neither $m$ nor $n$ is even. That is to say, both $m$ and $n$ are odd. Then there exist some integers $k$ and $ell$ such that $m=2k+1$ and $n=2ell + 1$. It follows then that $mn = dots$
$mn = (2k+1)(2ell+1) = 4kell + 2k + 2ell + 1 = 2(2kell + k + ell) + 1$ is odd.
Of course, it could also have been done directly if you know enough about prime numbers and Euclid's lemma. Suppose that $mn$ is even. Then $2mid mn$. It follows by Euclid's lemma that $2mid m$ or $2mid n$. Hence $m$ is even or $n$ is even. Given the nature of your question however, I expect that these properties have not yet been proven for you yet and so likely are not yet valid for you to use.
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
$endgroup$
You seem to be confusing yourself as to what $P$ and $Q$ might represent in this case.
Let $m$ and $n$ be integers. Let $P$ be the statement "$mn$ is even". Let $Q$ be the statement "$m$ is even or $n$ is even."
Proving $Qimplies P$ is trivial. Suppose without loss of generality that $m$ is even. Then we have some integer $k$ such that $m=2k$ and therefore $mn = (2k)n = 2(kn)$ is even as well. The problem doesn't actually ask us to prove this, but since it is true anyways it might as well be done so you can see more examples.
Now, proving that $Pimplies Q$ is easiest to do by contraposition rather than directly. That is to say, we instead prove that $neg Qimplies neg P$. So, suppose that neither $m$ nor $n$ is even. That is to say, both $m$ and $n$ are odd. Then there exist some integers $k$ and $ell$ such that $m=2k+1$ and $n=2ell + 1$. It follows then that $mn = dots$
$mn = (2k+1)(2ell+1) = 4kell + 2k + 2ell + 1 = 2(2kell + k + ell) + 1$ is odd.
Of course, it could also have been done directly if you know enough about prime numbers and Euclid's lemma. Suppose that $mn$ is even. Then $2mid mn$. It follows by Euclid's lemma that $2mid m$ or $2mid n$. Hence $m$ is even or $n$ is even. Given the nature of your question however, I expect that these properties have not yet been proven for you yet and so likely are not yet valid for you to use.
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
answered Jan 29 at 1:50
JMoravitzJMoravitz
48.7k43988
48.7k43988
add a comment |
add a comment |
$begingroup$
I am not sure what you mean by 'using disjunction prove' ... I see that there is a disjunction involved here, yes, but 'disjunction' is not a proof technique.
More importantly, you cannot treat $m$ and $n$, which are numbers as $P$ and $Q$, which are claims
What you can do, is to define $P$ as the claim that "$m$ is even", and $Q$ as "$n$ is even"
Now, since you have to prove that $P lor Q$, which is equivalent to both $neg P rightarrow Q$ and $neg Q rightarrow P$, you do indeed have a choice to either show that $Q$ is true if you assume that $P$ is false, or vice versa.
Now, I see that you are going for the assume $neg P$ route, i.e. assume that $m$ is not even, and thus odd. Ok, that's fine, but you now have to prove that $n$ is even ... rather than just assuming that, which is what you do. That is, you can assume that $m=2k+1$ for some whole number $k$, but you need to show that $n=2i$. And for that, you will need the fact that $mn$ is even, i.e. that $mn=2j$.
To sum up: you have that $m=2k+1$, and that $mn=2j$. Now you need to show that $n=2i$ for some whole number $i$. To do this, I would show that if $n$ is not even, you obtain a contradiction.
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
$endgroup$
add a comment |
$begingroup$
I am not sure what you mean by 'using disjunction prove' ... I see that there is a disjunction involved here, yes, but 'disjunction' is not a proof technique.
More importantly, you cannot treat $m$ and $n$, which are numbers as $P$ and $Q$, which are claims
What you can do, is to define $P$ as the claim that "$m$ is even", and $Q$ as "$n$ is even"
Now, since you have to prove that $P lor Q$, which is equivalent to both $neg P rightarrow Q$ and $neg Q rightarrow P$, you do indeed have a choice to either show that $Q$ is true if you assume that $P$ is false, or vice versa.
Now, I see that you are going for the assume $neg P$ route, i.e. assume that $m$ is not even, and thus odd. Ok, that's fine, but you now have to prove that $n$ is even ... rather than just assuming that, which is what you do. That is, you can assume that $m=2k+1$ for some whole number $k$, but you need to show that $n=2i$. And for that, you will need the fact that $mn$ is even, i.e. that $mn=2j$.
To sum up: you have that $m=2k+1$, and that $mn=2j$. Now you need to show that $n=2i$ for some whole number $i$. To do this, I would show that if $n$ is not even, you obtain a contradiction.
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
$endgroup$
add a comment |
$begingroup$
I am not sure what you mean by 'using disjunction prove' ... I see that there is a disjunction involved here, yes, but 'disjunction' is not a proof technique.
More importantly, you cannot treat $m$ and $n$, which are numbers as $P$ and $Q$, which are claims
What you can do, is to define $P$ as the claim that "$m$ is even", and $Q$ as "$n$ is even"
Now, since you have to prove that $P lor Q$, which is equivalent to both $neg P rightarrow Q$ and $neg Q rightarrow P$, you do indeed have a choice to either show that $Q$ is true if you assume that $P$ is false, or vice versa.
Now, I see that you are going for the assume $neg P$ route, i.e. assume that $m$ is not even, and thus odd. Ok, that's fine, but you now have to prove that $n$ is even ... rather than just assuming that, which is what you do. That is, you can assume that $m=2k+1$ for some whole number $k$, but you need to show that $n=2i$. And for that, you will need the fact that $mn$ is even, i.e. that $mn=2j$.
To sum up: you have that $m=2k+1$, and that $mn=2j$. Now you need to show that $n=2i$ for some whole number $i$. To do this, I would show that if $n$ is not even, you obtain a contradiction.
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
$endgroup$
I am not sure what you mean by 'using disjunction prove' ... I see that there is a disjunction involved here, yes, but 'disjunction' is not a proof technique.
More importantly, you cannot treat $m$ and $n$, which are numbers as $P$ and $Q$, which are claims
What you can do, is to define $P$ as the claim that "$m$ is even", and $Q$ as "$n$ is even"
Now, since you have to prove that $P lor Q$, which is equivalent to both $neg P rightarrow Q$ and $neg Q rightarrow P$, you do indeed have a choice to either show that $Q$ is true if you assume that $P$ is false, or vice versa.
Now, I see that you are going for the assume $neg P$ route, i.e. assume that $m$ is not even, and thus odd. Ok, that's fine, but you now have to prove that $n$ is even ... rather than just assuming that, which is what you do. That is, you can assume that $m=2k+1$ for some whole number $k$, but you need to show that $n=2i$. And for that, you will need the fact that $mn$ is even, i.e. that $mn=2j$.
To sum up: you have that $m=2k+1$, and that $mn=2j$. Now you need to show that $n=2i$ for some whole number $i$. To do this, I would show that if $n$ is not even, you obtain a contradiction.
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
edited Jan 29 at 2:20
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
answered Jan 29 at 2:05
Bram28Bram28
63.9k44793
63.9k44793
add a comment |
add a comment |
$begingroup$
"If $mn$ is even, then $m$ is even or $n$ is even" is equivalent to the contrapositive:
"if not ($m$ is even or $n$ is even), then not ($mn$ is even)."
This is logically equivalent to the following:
"if $m$ is not even and $n$ is not even, then $mn$ is not even,"
i.e., the product of two odd numbers is odd, which is true because
$(2 times u+1)(2 times v+1) = 2 times (2times utimes v+u+v) + 1$ for integers $u$ and $v$.
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
$endgroup$
add a comment |
$begingroup$
"If $mn$ is even, then $m$ is even or $n$ is even" is equivalent to the contrapositive:
"if not ($m$ is even or $n$ is even), then not ($mn$ is even)."
This is logically equivalent to the following:
"if $m$ is not even and $n$ is not even, then $mn$ is not even,"
i.e., the product of two odd numbers is odd, which is true because
$(2 times u+1)(2 times v+1) = 2 times (2times utimes v+u+v) + 1$ for integers $u$ and $v$.
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
$endgroup$
add a comment |
$begingroup$
"If $mn$ is even, then $m$ is even or $n$ is even" is equivalent to the contrapositive:
"if not ($m$ is even or $n$ is even), then not ($mn$ is even)."
This is logically equivalent to the following:
"if $m$ is not even and $n$ is not even, then $mn$ is not even,"
i.e., the product of two odd numbers is odd, which is true because
$(2 times u+1)(2 times v+1) = 2 times (2times utimes v+u+v) + 1$ for integers $u$ and $v$.
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
$endgroup$
"If $mn$ is even, then $m$ is even or $n$ is even" is equivalent to the contrapositive:
"if not ($m$ is even or $n$ is even), then not ($mn$ is even)."
This is logically equivalent to the following:
"if $m$ is not even and $n$ is not even, then $mn$ is not even,"
i.e., the product of two odd numbers is odd, which is true because
$(2 times u+1)(2 times v+1) = 2 times (2times utimes v+u+v) + 1$ for integers $u$ and $v$.
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
answered Jan 29 at 1:49
J. W. TannerJ. W. Tanner
4,0611320
4,0611320
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3091612%2fusing-disjunction-prove-that-for-all-integers-m-and-n-if-mn-is-even-then%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
