Lesson test: Contrapositive and contradiction

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Contrapositive and contradiction

1.[1p]
A proof by contrapositive that "if $n^{2}$ is even then $n$ is even" should begin with which line?

Let $n$ be an integer that is not even, so $n$ is odd.

Correct

Let $n$ be an integer with $n^{2}$ even.

The answer is: Let $n$ be an integer that is not even, so $n$ is odd.

Let $n$ be an even integer.

The answer is: Let $n$ be an integer that is not even, so $n$ is odd.

Suppose $n^{2}$ is even and $n$ is even.

The answer is: Let $n$ be an integer that is not even, so $n$ is odd.

2.[1p]
To prove $P \Rightarrow Q$ by contradiction, you assume both $P$ and $\neg Q$ .

True

Correct

False

The answer is: True

3.[2p]
Put the lines of the proof that $\sqrt{2}$ is irrational in order.

Then $4 c^{2} = 2 b^{2}$ , so $b^{2} = 2 c^{2}$ and $b^{2}$ is even.
So $b$ is even, and $a$ and $b$ are both even, contradicting the choice of $a$ and $b$ .
Since $a^{2}$ is even, $a$ is even, so $a = 2 c$ for some integer $c$ .
Hence $\sqrt{2}$ is irrational.
Squaring and multiplying by $b^{2}$ gives $a^{2} = 2 b^{2}$ , so $a^{2}$ is even.
Suppose, for contradiction, that $\sqrt{2} = \frac{a}{b}$ for integers $a$ and $b$ with $b \neq 0$ , not both even.

Show the answer

a, b, c, d, e, f

4.[2p]
The same argument, run with $4$ in place of $2$ , would "prove" $\sqrt{4}$ irrational. Where does it break?

It needs "if $4 ∣ a^{2}$ then $4 ∣ a$ ", which is false: $4 ∣ 36$ but $4$ does not divide $6$

Correct

It needs $a$ and $b$ not both even, which cannot be arranged for $\sqrt{4}$

The answer is: It needs "if $4 \mid a^2$ then $4 \mid a$", which is false: $4 \mid 36$ but $4$ does not divide $6$

Squaring $\sqrt{4} = \frac{a}{b}$ does not give an equation in integers

The answer is: It needs "if $4 \mid a^2$ then $4 \mid a$", which is false: $4 \mid 36$ but $4$ does not divide $6$

It breaks nowhere, since the argument never used anything special about $2$

The answer is: It needs "if $4 \mid a^2$ then $4 \mid a$", which is false: $4 \mid 36$ but $4$ does not divide $6$

5.[1p]
$2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1$ is prime.

True

The answer is: False

False

Correct

6.[3p]
Which of these are true of Euclid's proof that there are infinitely many primes?

Select all that apply

It shows that $p_{1} p_{2} \dots p_{k} + 1$ has a prime divisor not among $p_{1}, \dots, p_{k}$

Correct

It shows that $p_{1} p_{2} \dots p_{k} + 1$ is always prime

The answer is: It shows that $p_1 p_2 \cdots p_k + 1$ has a prime divisor not among $p_1, \ldots, p_k$, It uses the fact that a number dividing two integers divides their difference, It relies on every integer greater than $1$ having a prime divisor

It uses the fact that a number dividing two integers divides their difference

Correct

It relies on every integer greater than $1$ having a prime divisor

Correct

The argument only works when the list contains every prime

7.[3p]
Match each statement to what a proof of it by contradiction assumes.

$\sqrt{3}$ is irrational
There are infinitely many primes
If $n^{2}$ is even then $n$ is even
For every $n$ there is a prime greater than $n$

Some $n$ has no prime greater than it
$n^{2}$ is even and $n$ is odd
There are only finitely many primes
$\sqrt{3} = \frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$

Show the answer

$\sqrt{3}$ is irrational: $\sqrt{3} = \frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ There are infinitely many primes: There are only finitely many primes If $n^{2}$ is even then $n$ is even: $n^{2}$ is even and $n$ is odd For every $n$ there is a prime greater than $n$ : Some $n$ has no prime greater than it

8.[2p]
"Suppose, for contradiction, that the sum of odd integers $a$ and $b$ is odd. Write $a = 2 k + 1$ and $b = 2 m + 1$ . Then $a + b = 2 (k + m + 1)$ , which is even, a contradiction." What is this really?

A direct proof wrapped in an assumption it never uses

Correct

A proof by contrapositive

The answer is: A direct proof wrapped in an assumption it never uses

A proof by cases

The answer is: A direct proof wrapped in an assumption it never uses

An invalid proof, since the contradiction is with the assumption itself

The answer is: A direct proof wrapped in an assumption it never uses

9.[2p]
When a statement can be proved either by contrapositive or by contradiction, why does the lesson prefer the contrapositive?

Its target is fixed in advance, so a mistake usually shows as a failure to arrive

Correct

A proof by contradiction is not valid in classical mathematics

The answer is: Its target is fixed in advance, so a mistake usually shows as a failure to arrive

The contrapositive proves a stronger statement than the original

The answer is: Its target is fixed in advance, so a mistake usually shows as a failure to arrive

A proof by contradiction cannot be used on a conditional

The answer is: Its target is fixed in advance, so a mistake usually shows as a failure to arrive

1.[1p] A proof by contrapositive that "if n2 is even then n is even" should begin with which line?

2.[1p] To prove P⇒Q by contradiction, you assume both P and ¬Q.

3.[2p] Put the lines of the proof that 2 is irrational in order.

4.[2p] The same argument, run with 4 in place of 2, would "prove" 4 irrational. Where does it break?

5.[1p] 2×3×5×7×11×13+1 is prime.

6.[3p] Which of these are true of Euclid's proof that there are infinitely many primes?

7.[3p] Match each statement to what a proof of it by contradiction assumes.

8.[2p] "Suppose, for contradiction, that the sum of odd integers a and b is odd. Write a=2k+1 and b=2m+1. Then a+b=2(k+m+1), which is even, a contradiction." What is this really?

9.[2p] When a statement can be proved either by contrapositive or by contradiction, why does the lesson prefer the contrapositive?

1.[1p]
A proof by contrapositive that "if $n^{2}$ is even then $n$ is even" should begin with which line?

2.[1p]
To prove $P \Rightarrow Q$ by contradiction, you assume both $P$ and $\neg Q$ .

3.[2p]
Put the lines of the proof that $\sqrt{2}$ is irrational in order.

4.[2p]
The same argument, run with $4$ in place of $2$ , would "prove" $\sqrt{4}$ irrational. Where does it break?

5.[1p]
$2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1$ is prime.

6.[3p]
Which of these are true of Euclid's proof that there are infinitely many primes?

7.[3p]
Match each statement to what a proof of it by contradiction assumes.

8.[2p]
"Suppose, for contradiction, that the sum of odd integers $a$ and $b$ is odd. Write $a = 2 k + 1$ and $b = 2 m + 1$ . Then $a + b = 2 (k + m + 1)$ , which is even, a contradiction." What is this really?

9.[2p]
When a statement can be proved either by contrapositive or by contradiction, why does the lesson prefer the contrapositive?