2

I need to prove the following by contradiction:

"$$ and $$ are odd integers, then $$ is odd"

I'm sure this question isn't very hard to solve, however, my understanding of contraposition is very weak. I have only learned it recently and I do not feel like I am totally grasping the concept.

From my understanding, I am almost trying to prove this by saying the opposite statement. But I feel like this is oversimplifying it.

I know that based on previous proofs an even number is in a form like $=2$ an odd is the same as the even except plus 1: $=2+1$. Based on knowing this I assume I am able to use contraposition. But where do I start to use this?

Accelerator
  • 4,923
777
  • 21
  • 2
  • 1
    Contraposition is not the same as contradiction. The contraposition of an implication statement $P \implies Q$ is $\neg Q \implies \neg P$. Contradiction, on the other hand, is where you assume the negation of the given statement and then try to find a conflicting statement. To prove the given statement by contradiction, you assume $x,y$ are odd integers and $xy$ is even. You can find a contradiction by multiplying two odd integers together. – Accelerator Nov 21 '22 at 00:07
  • Be sure you have proved that "x is even" is the negation of "x is odd". – David P Nov 21 '22 at 01:43
  • A strange exercise ! If we , as desired , assume that $x,y$ are odd and $xy$ is even , then the "contradiction proof" includes calculating that $xy$ is odd (which is the contradiction) , but this is basically a direct proof. – Peter Nov 21 '22 at 06:08

3 Answers3

1

Contrapositive: Given a statement of the form $$\text{If $p$, then $q$}$$The contrapositive of this statement is $$\text{If not $q$, then not $p$}$$

If you prove the contrapositive, that is first you assume that $q$ is not true, and then prove that $p$ is not true, you have proven that if $p$ is true, then $q$ is true. As if $q$ was false, then $p$ would be false.

So, in your question, let $$p=\text{$x$ and $y$ are odd integers}$$ and $$q=\text{$xy$ is odd}$$

The statement you are trying to prove is $$\text{If $p$, then $q$}$$ which when written is words is $$\text{If $x$ and $y$ are odd integers, then $xy$ is odd}$$

The contrapositive of this statement would be $$\text{If $xy$ is not odd, then either $x$ or $y$ is not odd}$$

Contradiction: A proof by contradiction is very similar to a proof by contrapositive. As in, you start both proofs by assuming that $q$ is not true. But in a proof by contrapositive, you attempt to prove that if $q$ is not true, then $p$ is also not true. In a proof by contradiction, you try to reach a contradiction under the assumption that if $p$ is true and if $q$ is false, then we get some contradiction.

In a proof by contrapositive, you are not assuming that $p$ is true, whereas in a proof by contradiction, you are assuming that $p$ is true.

So, given a statement of the form $$\text{If $p$, then $q$}$$ A proof by contradiction would start with $$\text{Suppose that $p$ is true and suppose that $q$ is false}$$ and then proceed to arrive at a contradiction. This contradiction might very well be that $q$ being false implies that $p$ is false and in which case the proof by contradiction becomes a proof by contrapositive. This case is a bit subtle though.

So, if you want to prove the statement in question by a contradiction. Then you should start your proof like $$\text{Suppose that $x$ and $y$ are odd integers and also suppose that $xy$ is not odd}$$ and then proceed to find a contradiction.

Seeker
  • 3,594
1

Other responses have discussed proving the contrapositive.

The assertion can also be proven directly.

All even integers can be expressed as $(2n)$, where $n$ is some integer.

All odd integers can be expressed as $(2n + 1)$, where $n$ is some integer.

You are given that $x,y$ are both odd.

Therefore, there exist $n,m \in \Bbb{Z}$, such that $x = (2n + 1), y = (2m + 1).$

Set $A = 2mn + m + n \implies A \in \Bbb{Z}.$

Then,

$$xy = (2n + 1) \times (2m + 1) = 2A + 1 \implies (xy)~ \text{is odd}.$$

user2661923
  • 35,619
  • 3
  • 17
  • 39
0

Instead of using an explicit form for odd integers (that they are $2n+1$), I think that you rather should concentrate on the fact that all integers are either even or odd (in other words, an integer is odd if and only if it is not of the form $2n$ --- which means that it is not divisible by 2).

And if you need help with the contraposition of that statement, it is therefore:

"If $xy$ is even, then it is not true that $x$ and $y$ are both odd integers"

or

"If $xy$ is even, then at least one of $x$ and $y$ are even integers"

Ron Kaminsky
  • 726