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 ∣ a^{2}$ then $4 ∣ a$ ", which is false: $4 ∣ 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 ∣ a^{2}$ then $4 ∣ a$ ", which is false: $4 ∣ 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 ∣ a^{2}$ then $4 ∣ a$ ", which is false: $4 ∣ 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} \dots p_{k} + 1$ has a prime divisor not among $p_{1}, \dots, 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

10.[2p]
Euclid's lemma says that if a prime $p$ divides $a b$ , then $p$ divides $a$ or $b$ . Which of these show that it fails when $p$ is replaced by a composite number?

Select all that apply

$6 ∣ 4 \times 9$ , but $6$ divides neither $4$ nor $9$

Correct

$4 ∣ 2 \times 6$ , but $4$ divides neither $2$ nor $6$

Correct

$5 ∣ 10 \times 3$ , and $5 ∣ 10$

The answer is: $6 ∣ 4 \times 9$ , but $6$ divides neither $4$ nor $9$ , $4 ∣ 2 \times 6$ , but $4$ divides neither $2$ nor $6$

$9 ∣ 3 \times 6$ , and $9 ∣ 18$

The answer is: $6 ∣ 4 \times 9$ , but $6$ divides neither $4$ nor $9$ , $4 ∣ 2 \times 6$ , but $4$ divides neither $2$ nor $6$

11.[2p]
The proof that there are infinitely many primes of the form $4 k + 3$ lists them all as $p_{1}, \dots, p_{k}$ and considers which number?

$4 p_{1} p_{2} \dots p_{k} - 1$

Correct

$p_{1} p_{2} \dots p_{k} + 1$

The answer is: $4 p_{1} p_{2} \dots p_{k} - 1$

$4 p_{1} p_{2} \dots p_{k} + 1$

The answer is: $4 p_{1} p_{2} \dots p_{k} - 1$

$p_{1} p_{2} \dots p_{k} + 3$

The answer is: $4 p_{1} p_{2} \dots p_{k} - 1$

12.[2p]
A proof by contradiction of "for every integer $n$ , $n^{2} + n$ is even" should begin by assuming what?

There is an integer $n$ with $n^{2} + n$ odd

Correct

For every integer $n$ , $n^{2} + n$ is odd

The answer is: There is an integer $n$ with $n^{2} + n$ odd

There is an integer $n$ with $n^{2} + n$ even

The answer is: There is an integer $n$ with $n^{2} + n$ odd

$n^{2} + n$ is odd when $n = 1$

The answer is: There is an integer $n$ with $n^{2} + n$ odd

13.[1p]
A hundred people are in a room. By the generalised pigeonhole principle, at least how many of them must have been born in the same month?

CorrectNot quite: 9

14.[2p]
Why can Euclid's argument not be copied directly to prove that there are infinitely many primes of the form $4 k + 1$ ?

A product of two numbers of the form $4 k + 3$ has the form $4 k + 1$ , so a number of the form $4 k + 1$ need not have a prime divisor of that form

Correct

There are only finitely many primes of the form $4 k + 1$

The answer is: A product of two numbers of the form $4 k + 3$ has the form $4 k + 1$ , so a number of the form $4 k + 1$ need not have a prime divisor of that form

Numbers of the form $4 k + 1$ are always prime

The answer is: A product of two numbers of the form $4 k + 3$ has the form $4 k + 1$ , so a number of the form $4 k + 1$ need not have a prime divisor of that form

The well-ordering principle does not apply to numbers of the form $4 k + 1$

The answer is: A product of two numbers of the form $4 k + 3$ has the form $4 k + 1$ , so a number of the form $4 k + 1$ need not have a prime divisor of that form

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?

10.[2p] Euclid's lemma says that if a prime p divides ab, then p divides a or b. Which of these show that it fails when p is replaced by a composite number?

11.[2p] The proof that there are infinitely many primes of the form 4k+3 lists them all as p1,…,pk and considers which number?

12.[2p] A proof by contradiction of "for every integer n, n2+n is even" should begin by assuming what?

13.[1p] A hundred people are in a room. By the generalised pigeonhole principle, at least how many of them must have been born in the same month?

14.[2p] Why can Euclid's argument not be copied directly to prove that there are infinitely many primes of the form 4k+1?

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?

10.[2p]
Euclid's lemma says that if a prime $p$ divides $a b$ , then $p$ divides $a$ or $b$ . Which of these show that it fails when $p$ is replaced by a composite number?

11.[2p]
The proof that there are infinitely many primes of the form $4 k + 3$ lists them all as $p_{1}, \dots, p_{k}$ and considers which number?

12.[2p]
A proof by contradiction of "for every integer $n$ , $n^{2} + n$ is even" should begin by assuming what?

13.[1p]
A hundred people are in a room. By the generalised pigeonhole principle, at least how many of them must have been born in the same month?

14.[2p]
Why can Euclid's argument not be copied directly to prove that there are infinitely many primes of the form $4 k + 1$ ?