7 - Contrapositive Proof

What is a contrapositive?

The contrapositive of $P⟹Q$ is $\mathrm{\neg }Q⟹\mathrm{\neg }P$. The two statements are logically equivalent.

This is useful when the original direct proof is difficult to prove than the contrapositive proof.

Division

We can turn $a|b$ into the statement $b=ac$ for some $c\in \mathbb{Z}$.

In class practice

$\mathrm{\forall }x\in \mathbb{Z}$, if $3x-7$ is even, then $x$ is odd.

$\mathrm{\forall }x\in \mathbb{Z}$, if $x$ is even, then $3x-7$ is odd.

Proposition. Given $x\in \mathbb{Z}$, if $3x-7$ is even, then $x$ is odd.

Proof. Let $x\in \mathbb{Z}$. We work contrapositively. Assume that $x$ is even.
Thus $x=2k$ for some $k\in \mathbb{Z}$. We find

is odd.
Since $3k-4$ is an integer, $3x-7$ is odd. $◻$

Direct Proof
Let $x\in \mathbb{Z}$. We work directly. Assume that $3x-7$ is even. Then $3x-7=2j$ for some $j\in \mathbb{Z}$. Then $x=2j+7-2x=2(j-x+3)+1$. Since $j-x+3$

Proposition. Let $x\in \mathbb{Z}$. If $x^2-6x+7$ is odd, then $x$ is even.

Proof. Let $x\in \mathbb{Z}$. We work contrapositively. Assume that $x$ is odd. Thus $x=2k+1$ for some $k\in \mathbb{Z}$. Hence,

Since $2k^2-4k+1$ is an integer, $x^2-6x+7$ is even. $◻$

Proposition. Let $a,b\in \mathbb{Z}$. If $a\mid b$, then $a\mid 2b$.

Proof. Let $a,b\in \mathbb{Z}$. We work directly. Assume that $a\mid b$.
Thus there exists $c\in \mathbb{Z}$ such that $b=ac$.
Thus $2b=2ac=a(2c)$. Since $2c$ is an integer, $a\mid 2b$. $◻$

Proposition. Given $x\in \mathbb{Z}$, if $2\nmid x$, then $x$ is odd.

Proof. Let $x\in \mathbb{Z}$. We work contrapositively. Assume that $x$ is even. Thus $x=2k$ for some $k\in \mathbb{Z}$. Thus $2\mid x$.

HW 7

Ben Finch

E 7.1
Proposition. Let $a\in \mathbb{Z}$. If $a^2+3$ is odd, then $a$ is even.

Proof.
Let $a\in \mathbb{Z}$. We work contraposititvely. Assume $a$ is odd. Thus $a=2k+1$ for some $k\in \mathbb{Z}$. We find

is even. $◻$

E 7.2
Proposition. Let $x,y\in \mathbb{Z}$. If $xy+y^2$ is even, then $x$ is odd or $y$ is even.

Proof. Let $x,y\in \mathbb{Z}$. We work contrapositively. Assume $x$ is even and $y$ is odd. Thus $x=2k$ for some $k\in \mathbb{Z}$ and $y=2n+1$ for some $n\in \mathbb{Z}$.
We find

is an odd integer. $◻$

E 7.3
Proposition. Let $s\in \mathbb{Z}$. $s$ is odd if and only if $s^3$ is odd.

Proof. Let $s\in \mathbb{Z}$. We first prove that $s^3$ is odd if $s$ is odd. We work directly. Assume $s$ is odd, thus $s=2k+1$ for some $k\in \mathbb{Z}$. We find that

is an odd integer.

We now prove that $s$ is odd if $s^3$ is odd. We work contrapositively. Assume $s$ is even, thus $s=2k$ for some $k\in \mathbb{Z}$. We find that

is an even integer. $◻$

E 7.4
In the student's proof, they use the converse instead of the contrapositive. The correct contrapositive would be:
If $x$ is odd, then $2\nmid x$.

Proof. Assume, contrapositively, that $x$ is odd. Thus, $x=2k+1$ for some $k\in Z,$ which means $2$ does not divide $x$. $◻$

E 7.5

Proposition: Let $a,b,c,d\in \mathbb{Z}$. If $a|c$ and $b|d$, then $ab|cd$.

Proof: Let $a,b,c,d\in \mathbb{Z}$. We work directly. Assume $a|c$ and $b|d$. Thus $c=ax$ and $d=by$ for some $x,y\in \mathbb{Z}$.

Now, $cd=(ax)(by)=ab(xy)$. Since $xy\in \mathbb{Z}$, we have $ab|cd$. $◻$

E 7.6
If $ab\nmid cd$, then $a\nmid c$ or $b\nmid d$.

E 7.7
Proposition. Let $a\in \mathbb{Z}$. If $4\nmid a^2$, then $a$ is odd.

Proof. Let $a\in \mathbb{Z}$. We work contrapositively. The logically equivalent contrapositive is if $a$ is even, then $4\mid a^2$.
Assume $a$ is even. Thus $a=2k$ for some $k\in \mathbb{Z}$. We find

Which is a multiple of four. In other words, 4 is a divisor of 4 times some integer $k^2$. Thus $4\mid a^2.$ $◻$

E 7.8
Proposition. Given $x\in \mathbb{Z}$, then $5x-1$ is even only if $x$ is odd.

Direct Proof.
Let $x\in \mathbb{Z}$.
We work directly.
Assume $x$ is even. Thus $x=2k$ for some $k\in \mathbb{Z}$ We find

is odd. $◻$

Contrapositive Proof.
Let $x\in Z$.
We work contrapositively.
Assume $5x-1$ is odd. Thus $5x-1=2k+1$ for some $k\in \mathbb{Z}$. We find

is even. $◻$