0.1 How to read a theorem

Every theorem is built from a few logical pieces (and, or, not, if-then, for every, there exists). Read them exactly, negate them correctly, and half of every proof is already done.

A theorem is a sentence. Before you can prove one, you have to know exactly what it says: what you may assume, what you must show, and for which objects. Most wrong proofs are not wrong in the algebra. They prove a slightly different sentence. This chapter is about reading sentences exactly. It reuses the logic from CS 240. The goal here is to read and write mathematics, not to fill in truth tables.

Before you start

Nothing beyond school algebra. If you took CS 240, much of this will be familiar; the quick checks tell you where to slow down.

Quick checkWhat is the negation of 'If

n

is odd, then

n^2

is odd'?

Quick check'Every student has a phone' and 'There is a phone that every student has'. Do they say the same thing?

The picture

Think of a theorem as a contract. “If $n$ is even, then $n^2$ is even” makes a promise about every number you could hand it. It does not promise anything about odd numbers. A proof is the argument that the promise is never broken. To break it, someone would need one number that is even but has an odd square. Knowing exactly what would break a promise is the key skill of this chapter. That is the negation, and it is how proofs by contradiction and counterexamples work.

Where this came from· Why mathematicians started writing logic down

For most of history, mathematicians reasoned in ordinary language. In the 1800s, analysis needed more care. Words like “approaches” and “infinitely small” were too loose to settle which statements about continuous functions and infinite sums were true. Augustin-Louis Cauchy (1821) defined limits in careful words. Karl Weierstrass and his students, around the middle of the century, turned them into the sentences with “for every” and “there exists” that you will meet as the epsilon-delta definitions of Unit 1. In the same century George Boole (1847) treated “and”, “or” and “not” as an algebra, and Gottlob Frege (1879) added quantifiers to the symbolic language. That symbolic logic is what CS 240 taught you. It exists because ordinary words were not precise enough for proofs.

Definitions and theorems

Statements and connectives

Definition B

Statement

A statement (or proposition) is a sentence that is either true or false. ” $7$ is prime” is a statement (true). " $2 + 2 = 5$ " is a statement (false). " $x > 3$ " is not a statement until you say what $x$ is: it is a predicate, a sentence with a variable, which becomes a statement once the variable is fixed or quantified (below).

In one lineA sentence that is either true or false, with no third option.

Why it existsOnly sentences with a definite truth value can be proved or disproved.

Quick checkWhich of these is a statement in the sense just defined?

Statements combine with three connectives. We write $P$ and $Q$ for statements.

Symbol	Read	True exactly when
$P \land Q$	P and Q	both are true
$P \lor Q$	P or Q	at least one is true (maths “or” includes “both”)
$\neg P$	not P	$P$ is false

If-then

Definition B

Implication

The implication $P \Rightarrow Q$ , read “if $P$ then $Q$ ” or ” $P$ implies $Q$ ”, is false when $P$ is true and $Q$ is false, and true in every other case. $P$ is the hypothesis and $Q$ the conclusion.

In one line'If P then Q' ( $P \Rightarrow Q$ ) is false in exactly one case: P true and Q false.

Why it existsIt is the shape of almost every theorem: hypotheses on the left, conclusion on the right.

$P$	$Q$	$P \Rightarrow Q$	The promise “if P then Q”
T	T	T	kept
T	F	F	broken
F	T	T	not tested
F	F	T	not tested

Your answerTake three statements

P, Q, R

. Their truth table has 8 rows. In how many rows is

(P \lor Q) \Rightarrow R

false?

Why· Why 'false implies anything' counts as true

The last two rows bother everyone. Think of a promise: “If it rains, I will bring an umbrella.” On a day it does not rain, you cannot accuse me of breaking the promise, whatever I carry. A promise is broken only when its condition happens and the result does not. Mathematics counts a promise that was never tested as kept. This is called vacuous truth.

It is not a trick. It is what makes theorems usable. “If $n$ is even then $n^2$ is even” should be a true theorem about all integers. When $n = 3$ , the hypothesis is false. If we called that case false, the theorem would be false because of $n = 3$ , which it never talked about.

Worked example

Decide whether each statement is true: (a) 'If

1 = 2

then

5 = 7

.' (b) 'If

2 + 2 = 4

then

5 = 7

.' (c) 'If

x

is a prime and

x

is even, then

x = 2

', for the particular number

x = 9

Solution.

Find the hypothesis and the conclusion of (a). Hypothesis: $1 = 2$ . Conclusion: $5 = 7$ . An implication is judged by the pair (hypothesis, conclusion), so name both first.
Decide the truth value of each part. $1 = 2$ is false, and $5 = 7$ is false. That is the row F, F of the table. The table needs the truth value of each part, never the meaning of the whole sentence.
Read the table. The row F, F gives true. The hypothesis never happened, so the promise was never tested and was never broken (vacuous truth).
Do (b). $2 + 2 = 4$ is true and $5 = 7$ is false: the row T, F. This is the only row that gives false.
Do (c). For $x = 9$ the hypothesis “9 is prime and even” is false (9 is not prime). The conclusion " $9 = 2$ " is also false. The row F, F gives true. Plugging in a number that fails the hypothesis cannot break the promise. Only a prime that is even and not 2 could, and there is none.

Answer. (a) true, (b) false, (c) true.

Why· Why $P \Rightarrow Q$ means the same as 'not P, or Q'

From the table, $P \Rightarrow Q$ is false only in the row ” $P$ true, $Q$ false”. So it is true exactly when that row does not happen: when $P$ is false, or $Q$ is true. That is $\neg P \lor Q$ . In words: “if it rains I bring an umbrella” says the same as “either it does not rain, or I bring an umbrella”. Both rule out exactly one situation: rain and no umbrella.

Mathematicians say $P \Rightarrow Q$ in several ways. All of these mean exactly the same statement.

Wording	Example with $P$ = ” $n$ is divisible by 4”, $Q$ = ” $n$ is even”
if $P$ , then $Q$	if $n$ is divisible by 4, then $n$ is even
$P$ implies $Q$	$n$ divisible by 4 implies $n$ even
$Q$ whenever $P$	$n$ is even whenever it is divisible by 4
$P$ only if $Q$	$n$ is divisible by 4 only if $n$ is even
$P$ is sufficient for $Q$	being divisible by 4 is enough to be even
$Q$ is necessary for $P$	being even is needed in order to be divisible by 4

The two to watch are “only if” and “necessary”. They can sound like they reverse $P$ and $Q$ . The thing after “only if” is the conclusion, and in ” $Q$ is necessary for $P$ ” the conclusion is the thing that is necessary, $Q$ .

Quick check'You pass the course only if you score at least 40.' Which statement does this say?

Three relatives of $P \Rightarrow Q$ appear constantly.

Definition B

Converse

The converse of $P \Rightarrow Q$ is $Q \Rightarrow P$ .

In one lineThe converse of $P \Rightarrow Q$ is $Q \Rightarrow P$ ; it is a different statement and can be false when the original is true.

Why it existsMixing up a statement with its converse is the most common logical error in proofs.

“If $n$ is divisible by 4, then $n$ is even” is true. Its converse, “if $n$ is even, then $n$ is divisible by 4”, is false, because $n = 6$ is even and not divisible by 4.

Your answerAmong the integers

1, 2, \dots, 20

, for how many

n

does the converse of 'if

n

is divisible by 4 then

n

is even' fail? (It fails at

n

when

n

is even but not divisible by 4.)

Definition B

Contrapositive

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ : swap the two sides and negate both.

In one lineThe contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ ; it always has the same truth value as the original.

Why it existsSometimes 'not Q' is easier to start from than P, so proving the contrapositive is a legitimate shortcut.

The fourth relative is the inverse, $\neg P \Rightarrow \neg Q$ : negate both sides and keep the order. It is the contrapositive of the converse, so it is equivalent to the converse and not to the original.

Worked example

Write the converse, the contrapositive and the inverse of 'If a number is divisible by 6, then it is divisible by 3.' Decide which are true.

Solution.

Name the two parts. $P$ : “the number is divisible by 6”. $Q$ : “the number is divisible by 3”. All four statements are built from the same $P$ and $Q$ .
Converse ( $Q \Rightarrow P$ ). “If a number is divisible by 3, then it is divisible by 6.” Swap the sides.
Contrapositive ( $\neg Q \Rightarrow \neg P$ ). “If a number is not divisible by 3, then it is not divisible by 6.” Swap the sides and negate both.
Inverse ( $\neg P \Rightarrow \neg Q$ ). “If a number is not divisible by 6, then it is not divisible by 3.” Negate both and keep the order.
Decide the original. True: $n = 6k = 3(2k)$ . Unfold divisibility and exhibit the multiple.
Decide the other three with one example each. The contrapositive is true, because it is equivalent to the original. The converse is false: $n = 9$ is divisible by 3 and not by 6. The inverse is false for the same reason, because it is equivalent to the converse (again $n = 9$ : not divisible by 6, yet divisible by 3). A single number making the hypothesis true and the conclusion false kills an implication. The contrapositive needs no check, since it always has the truth value of the original.

Answer. Original and contrapositive are true. Converse and inverse are false.

Theorem B

An implication equals its contrapositive

For any statements $P$ and $Q$ , $P \Rightarrow Q$ and $\neg Q \Rightarrow \neg P$ have the same truth value.

In one line $P \Rightarrow Q$ and $\neg Q \Rightarrow \neg P$ are true in exactly the same situations.

Why it is trueBoth are false in exactly one case: P true and Q false.

Proofstandard

The idea: An implication is false in exactly one case. Find that case for each statement and see that it is the same case.

P \Rightarrow Q

is false exactly when

P

is true and

Q

is false.

By the definition of implication: false only when the hypothesis holds and the conclusion fails.

\neg Q \Rightarrow \neg P

is false exactly when

Q

is false and

P

is true.

Here the hypothesis is

\neg Q

and the conclusion is

\neg P

. It is false only when

\neg Q

is true and

\neg P

is false.

So the two statements always have the same truth value.

The two descriptions are the same situation, so the statements are false together and true together.

Proof workshopRebuild the proof that an implication equals its contrapositive

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Watch out· Proving the contrapositive IS proving the theorem

A student’s common question: “if I use the contrapositive, do I still need to show the original is true?” Showing the contrapositive true is the whole proof. Because the two statements are always true together, proving " $\neg Q \Rightarrow \neg P$ " proves " $P \Rightarrow Q$ ". You do not prove the original separately. You choose whichever of the two is easier to start from.

Definition B

If and only if

$P \Leftrightarrow Q$ , read ” $P$ if and only if $Q$ ” (written iff), means $P \Rightarrow Q$ and $Q \Rightarrow P$ . It is true when $P$ and $Q$ have the same truth value. To prove it, you prove both directions, often labelled ( $\Rightarrow$ ) and ( $\Leftarrow$ ), as in the subspace test of 2.1.

In one line'P if and only if Q' ( $P \Leftrightarrow Q$ ) means both $P \Rightarrow Q$ and $Q \Rightarrow P$ .

Why it existsDefinitions and characterisations ('a matrix is invertible iff its determinant is non-zero') say two things are the same condition, and need proofs in both directions.

Worked example

Prove: an integer

n

is odd if and only if

n + 1

is even.

Solution. An integer is even if it equals $2k$ for some integer $k$ , and odd if it equals $2k + 1$ for some integer $k$ . We prove the two directions separately.

Direction ( $\Rightarrow$ ): assume $n$ is odd. Then $n = 2k + 1$ for some integer $k$ . This direction is “odd implies $n + 1$ even”, so the hypothesis is “odd” and we unfold it.
Reach the conclusion. $n + 1 = 2k + 2 = 2(k + 1)$ , and $k + 1$ is an integer, so $n + 1$ is even. The conclusion “even” needs the form $2(\text{integer})$ .
Direction ( $\Leftarrow$ ): assume $n + 1$ is even. Then $n + 1 = 2m$ for some integer $m$ . This is the converse direction. It is a different statement, so it needs its own proof.
Reach the conclusion. $n = 2m - 1 = 2(m - 1) + 1$ , and $m - 1$ is an integer, so $n$ is odd. The conclusion “odd” needs the form $2(\text{integer}) + 1$ .

Answer. Both $P \Rightarrow Q$ and $Q \Rightarrow P$ hold, so $n$ is odd if and only if $n + 1$ is even. $\blacksquare$

Quick checkA theorem says 'If

A

is invertible, then

\det A \ne 0

.' Which statement is guaranteed to be true as well?

Quantifiers

Definition B

Quantifier

The universal quantifier $\forall x$ reads “for every $x$ ”. The existential quantifier $\exists x$ reads “there exists (at least one) $x$ ”. Putting a quantifier in front of a predicate turns it into a statement. " $\forall x \in \mathbb R,\ x^2 \ge 0$ " is true. " $\exists x \in \mathbb R,\ x^2 = -1$ " is false.

In one line'For every' ( $\forall$ ) and 'there exists' ( $\exists$ ): they say how many objects a predicate is claimed for.

Why it existsEvery theorem is about a whole class of objects, and the quantifiers say which and how many.

Watch out· Hidden quantifiers

Theorems often hide their “for every”. “If $n$ is even then $n^2$ is even” means “for every integer $n$ : if $n$ is even, then $n^2$ is even”. A proof must work for an arbitrary $n$ , not for $n = 4$ . Before proving anything, rewrite the statement with every quantifier visible.

Quick checkDoes '

\forall x \in \mathbb R,\ x^2 > 0

' hold?

The order of quantifiers matters. The cleanest example uses $x$ and $y$ ranging over the real numbers.

Worked example

Compare

\forall x\ \exists y:\ y > x

with

\exists y\ \forall x:\ y > x

Solution.

Read the first one as a game. “For every $x$ , there is a $y$ with $y > x$ .” You name any $x$ ; I then get to choose $y$ , knowing your $x$ . The variable that comes later may depend on the ones before it.
Decide it. Whatever $x$ you name, I answer $y = x + 1$ . So it is true. My $y$ is allowed to depend on your $x$ .
Read the second one. “There is a $y$ such that for every $x$ , $y > x$ .” Now I must commit to one $y$ first, and then it has to beat every $x$ you could name. Here $y$ comes first, so it cannot depend on $x$ .
Decide it. Whatever $y$ I pick, you name $x = y + 1$ , and $y > x$ fails. So it is false: no real number is bigger than all real numbers. One counter-move is enough to defeat an ‘exists’.

Answer. The first is true and the second is false. Swapping $\forall$ and $\exists$ changed which player moves first, and so changed the meaning.

Your answerLet

x

and

y

range over

\{1, 2, 3, 4, 5, 6\}

. For how many values of

x

is the statement '

\forall y:\ xy \le 12

' true?

Worked example

Does '

\exists x:\ (x \text{ is even and } x \text{ is odd})

' say the same as '

(\exists x:\ x \text{ is even}) \land (\exists x:\ x \text{ is odd})

'? Let

x

range over the integers.

Solution.

Read the first sentence. It asks for ONE integer that is both even and odd. One quantifier covers the whole bracket, so a single $x$ must satisfy both parts.
Decide it. No integer is both even and odd, so it is false. An integer leaves remainder 0 or 1 on division by 2, never both.
Read the second sentence. It has two separate quantifiers. The first $x$ is even and the second may be a different integer that is odd. Each $\exists$ introduces its own $x$ , and the two do not have to agree.
Decide it. $x = 2$ is even and $x = 3$ is odd, so it is true. Exhibiting examples proves an ‘exists’.

Answer. They are different: the first is false and the second is true. An $\exists$ cannot be split across an “and” when the same $x$ must serve both parts. (The mirror case, with $\forall$ and “or”, is one of the problems below.)

A preview· Preview: the limit definition is this game

" $a_n \to L$ " means: $\forall \varepsilon > 0\ \exists N\ \forall n > N:\ |a_n - L| < \varepsilon$ . You (the sceptic) pick $\varepsilon$ ; the prover answers with $N$ , which may depend on $\varepsilon$ . Chapter 1.2 plays this game with a visualizer. Reading quantifier order is most of what analysis asks of you.

Negation

To disprove a statement, or to set up a proof by contradiction, you need its exact negation. These rules give it mechanically.

Definition B

Negation

The negation $\neg S$ of a statement $S$ is true exactly when $S$ is false.

In one lineThe negation of a statement is the statement that is true exactly when the original is false.

Why it existsProof by contradiction starts from the negation, and a counterexample is a witness for the negation.

Fact B

Rules for negating

$\neg(P \land Q)$ is $\neg P \lor \neg Q$ . (De Morgan)
$\neg(P \lor Q)$ is $\neg P \land \neg Q$ . (De Morgan)
$\neg(P \Rightarrow Q)$ is $P \land \neg Q$ .
$\neg(\forall x\ P(x))$ is $\exists x\ \neg P(x)$ .
$\neg(\exists x\ P(x))$ is $\forall x\ \neg P(x)$ .

In one lineNot(and) is or-of-nots; not(or) is and-of-nots; not(if P then Q) is P and not Q; not(for all) is exists-not; not(exists) is for-all-not.

Why it is trueEach rule describes exactly the situations in which the original is false.

Proofstandard

The idea: For each rule, describe exactly when the original statement is false; that description is the rule's right side.

Rule 1:

P \land Q

is false exactly when

P

is false or

Q

is false.

'P and Q' needs both. It fails as soon as one of them fails.

Rule 2:

P \lor Q

is false exactly when

P

is false and

Q

is false.

'P or Q' needs at least one. It fails only when both fail.

Rule 3:

P \Rightarrow Q

is false exactly when

P

is true and

Q

is false.

From the truth table of implication: the only false row is P true, Q false.This is the rule missed on CS 240 Exam 1. The negation of an if-then is an AND, never another if-then.

Rule 4:

\forall x\ P(x)

is false exactly when some

x

has

P(x)

false.

'Every x works' fails as soon as one x does not work.

Rule 5:

\exists x\ P(x)

is false exactly when every

x

has

P(x)

false.

'Some x works' fails only when no x works, that is, every x fails.

A truth table is a second way to check any rule about connectives. It lists every possible combination of true and false for the letters and compares the two sides row by row.

Worked example

Use a truth table to show

\neg(P \land Q)

and

\neg P \lor \neg Q

always agree (De Morgan, rule 1).

Solution.

List the rows. Two letters give $2 \times 2 = 4$ rows: $(P, Q)$ = TT, TF, FT, FF. Every combination must appear once, or the check could miss a case.
Fill the left side $\neg(P \land Q)$ . First $P \land Q$ is T, F, F, F. Negating gives F, T, T, T. $P \land Q$ is true only in row TT, and the ‘not’ flips each entry.
Fill the right side $\neg P \lor \neg Q$ . $\neg P$ is F, F, T, T and $\neg Q$ is F, T, F, T. ‘Or’ of the two is F, T, T, T. An ‘or’ is true as soon as one side is true, and false only in the row where both are false (row TT).
Compare the columns. F, T, T, T on both sides. Same value in every row means the two statements are equivalent.

Answer. The columns agree in all four rows, so $\neg(P \land Q)$ and $\neg P \lor \neg Q$ always have the same truth value.

To negate a long sentence, move the “not” from left to right one symbol at a time, flipping each $\forall$ to $\exists$ and each $\exists$ to $\forall$ , and using rule 3 when you reach an if-then.

Worked example CS 240 Exam 1

Negate: 'If

3n + 4

is odd, then

n - 3

is even' (for every integer

n

Solution.

Make the hidden quantifier visible. The statement is $\forall n \in \mathbb Z:\ (3n + 4 \text{ odd}) \Rightarrow (n - 3 \text{ even})$ . Theorems about integers speak about every integer unless they say otherwise.
Negate the quantifier. $\exists n \in \mathbb Z:\ \neg\big((3n + 4 \text{ odd}) \Rightarrow (n - 3 \text{ even})\big)$ . Rule 4.
Negate the implication. $\exists n \in \mathbb Z:\ (3n + 4 \text{ odd}) \land (n - 3 \text{ odd})$ . Rule 3: the negation of if-then is AND. Note ‘not even’ is ‘odd’ for integers.

Answer. “There is an integer $n$ with $3n + 4$ odd and $n - 3$ odd.” A proof by contradiction assumes exactly this and derives something impossible. The wrong version, “if $3n + 4$ is odd then $n - 3$ is odd”, is another if-then statement, and assuming it leads nowhere.

Worked example

Disprove: 'For every real

x

, if

x^2 > 4

then

x > 2

Solution.

Write the negation. $\exists x \in \mathbb R:\ x^2 > 4 \land x \le 2$ . Rules 4 and 3. To disprove a ‘for every’, exhibit one $x$ for which the negation holds.
Find a witness. $x = -3$ : $x^2 = 9 > 4$ and $-3 \le 2$ . Negative numbers have large squares but are small.

Answer. The statement is false, and $x = -3$ is a counterexample: an object that makes the negation true.

Your answerFor how many integers

n

from

1

10

is the statement 'if

n

is prime, then

n

is odd' false?

Worked example

A function

f

is increasing if

\forall x\ \forall y:\ x < y \Rightarrow f(x) < f(y)

. Write what 'not increasing' means, and show

f(x) = x^2

\mathbb R

is not increasing.

Solution.

Write the definition with every quantifier visible. $\forall x\ \forall y:\ (x < y) \Rightarrow (f(x) < f(y))$ . Start from the full sentence so that nothing is hidden.
Negate the two $\forall$ ‘s. $\exists x\ \exists y:\ \neg\big((x < y) \Rightarrow (f(x) < f(y))\big)$ . Rule 4, applied twice. Each $\forall$ becomes $\exists$ and the ‘not’ moves right.
Negate the implication. $\exists x\ \exists y:\ x < y \land f(x) \ge f(y)$ . Rule 3: the negation of if-then is AND. Also, ‘not less than’ is ‘greater than or equal’.
Read the negation in words. There are two inputs, one smaller than the other, whose outputs are in the wrong order or equal. This tells us exactly what object to hunt for.
Find a witness for $f(x) = x^2$ . Take $x = -2$ and $y = -1$ . Then $x < y$ , and $f(x) = 4 \ge 1 = f(y)$ . The square of a negative number gets bigger as the number moves away from 0.

Answer. ‘Not increasing’ means: there are $x < y$ with $f(x) \ge f(y)$ . The pair $(-2, -1)$ shows $x^2$ is not increasing on $\mathbb R$ .

Quick checkWhich is the negation of 'Every vector space has a basis with 3 elements'?

Quick checkWhich is the negation of 'Some student passed every exam'?

Proof workshopGive the reason for each step of this negation

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

$\neg\big(\forall x\ \exists y:\ x + y = 0\big)$
$\exists x\ \neg\big(\exists y:\ x + y = 0\big)$
$\exists x\ \forall y:\ \neg(x + y = 0)$
$\exists x\ \forall y:\ x + y \ne 0$

Reading a theorem, step by step

Before proving any theorem, do these four things. They take a minute and prevent most wrong proofs.

Name the objects and their types: integers, real numbers, vectors, functions.
Write every quantifier, including hidden ones, in order.
Split hypothesis from conclusion. What may you assume? What must you show?
Write the negation of the conclusion (for contradiction) and of the whole statement (to look for counterexamples).

Worked example Apostol Thm 1.5; 2.2

Read the statement behind Apostol's Theorem 1.5: 'If

k

vectors span a space, then any

k + 1

vectors in that space are linearly dependent.'

Solution. Linear dependence is defined in 2.2. Here we only use its shape: a set is dependent when some combination of its vectors, with coefficients not all zero, equals the zero vector $O$ .

Name the objects. A vector space $V$ ; vectors $x_1, \dots, x_k$ in $V$ that span $V$ ; vectors $y_1, \dots, y_{k+1}$ in $V$ . Know what each letter is before reading further.
Write the quantifiers. For every $V$ , every $k \ge 1$ , every $x_1, \dots, x_k$ that span $V$ , and every list $y_1, \dots, y_{k+1}$ in $V$ : the $y$ ‘s are dependent. ‘Any $k + 1$ vectors’ is a hidden ‘for every’.
Split hypothesis from conclusion. Hypothesis: the $x$ ‘s span $V$ (so each $y_i$ is a combination of the $x$ ‘s). Conclusion: there exist $c_1, \dots, c_{k+1}$ , not all zero, with $\sum c_i y_i = O$ . Unfolding ‘dependent’ gives a conclusion containing an ‘exists’.
Say what a proof must do. Take arbitrary $x$ ‘s and $y$ ‘s satisfying the hypothesis and construct the $c_i$ . An ‘exists’ in the conclusion means the proof must produce something. The proof cannot just argue that none is impossible.
Write the negation, to know what a counterexample would be. $k$ vectors that span $V$ and $k + 1$ vectors in $V$ that are independent. Rule 3 for the whole statement. If the theorem is true, no such pair exists.

Answer. Unfolding the definitions shows the shape of the proof before you start: build the coefficients $c_i$ . The proof in 2.2 builds them by induction.

Where it is used

Used inside maths· Inside maths: every definition is a quantified sentence

A function $f$ is continuous at $a$ if $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x:\ |x - a| < \delta \Rightarrow |f(x) - f(a)| < \varepsilon$ . Reading that line correctly (who picks first, what depends on what, what the negation says) is the whole of Unit 1, and of MATH 521.

Used in the real world· Computer science: specifications and databases

Program specifications are quantified implications. A sorting routine’s contract is “for every input list, the output is a permutation of it and for all $i$ , output $[i] \le$ output $[i+1]$ ”. Testing checks a few inputs. Proving the contract, as the proof assistant Coq and the program verifier Dafny do, covers the ‘for every’. A database query “find customers who bought every product in category X” has a $\forall$ over products. SQL has no ‘for all’, so it is written as “there is no product in category X that the customer did not buy”, a double ‘NOT EXISTS’. That is rules 4 and 5 read backwards: $\forall$ is the same as “not exists not”.

Traps

Watch out· The negation of if-then is AND

$\neg(P \Rightarrow Q)$ is $P \land \neg Q$ . It is never " $P \Rightarrow \neg Q$ ". Proof by contradiction of “if P then Q” assumes P and not-Q together.

Watch out· A converse is a different theorem

Proving $Q \Rightarrow P$ does not prove $P \Rightarrow Q$ . When a proof seems to work too easily, check that you did not prove the converse.

Watch out· 'Or' includes both

In mathematics ” $P$ or $Q$ ” is true when both hold. ” $n$ is even or $n$ is divisible by 3” is true for $n = 6$ .

Watch out· An example is not a proof of 'for every'

Checking $n = 1, 2, 3$ proves nothing about all $n$ . But one counterexample DOES disprove a ‘for every’, and one example DOES prove a ‘there exists’.

Problems

check

Write the converse and the contrapositive of “If a matrix has two equal rows, then its determinant is 0.” Which of the three is guaranteed to be true?

Solution

Converse: if $\det A = 0$ , then $A$ has two equal rows (false: $\begin{bmatrix}1&2\\2&4\end{bmatrix}$ ). Contrapositive: if $\det A \ne 0$ , then $A$ has no two equal rows (true, since it is equivalent to the original, which is true).

check

Is “If $1 = 2$ , then the moon is made of cheese” true or false?

Solution

True. The hypothesis is false, so the implication is vacuously true: its promise is never tested.

check

Negate: “There is an integer $n$ such that $n^2 = 2$ .”

Solution

“For every integer $n$ , $n^2 \ne 2$ .” (Rule 5.) This negation is the true one.

use

Negate, and decide which version is true: “For every real $x > 0$ there is a real $y > 0$ with $y < x$ .”

Solution

Negation: there is a real $x > 0$ such that for every real $y > 0$ , $y \ge x$ . The original is true: given $x > 0$ , take $y = x/2$ . So the negation is false.

use

Write the definition “the vectors $x_1, \dots, x_k$ are linearly independent” with explicit quantifiers, then negate it. What familiar definition do you get?

Solution

Independent: for all scalars $c_1, \dots, c_k$ , if $\sum c_i x_i = O$ then every $c_i = 0$ . Negation: there exist $c_1, \dots, c_k$ with $\sum c_i x_i = O$ and not every $c_i = 0$ (rules 4 and 3). That is exactly the definition of linearly dependent in 2.2.

use

$f$ is called bounded if $\exists M\ \forall x:\ |f(x)| \le M$ . Write what ” $f$ is not bounded” means, and show $f(x) = x$ on $\mathbb R$ is not bounded.

Solution

Not bounded: $\forall M\ \exists x:\ |f(x)| > M$ . For $f(x) = x$ : given any $M$ , take $x = |M| + 1$ ; then $|f(x)| = |M| + 1 > M$ .

prove

Prove with a truth table, then explain in words, that $P \Rightarrow Q$ and $\neg P \lor Q$ are equivalent.

Solution

Rows (P, Q): (T,T): both true. (T,F): $P \Rightarrow Q$ false; $\neg P \lor Q$ = F or F = false. (F,T): both true. (F,F): both true. They agree in every row. In words: each is false in exactly one situation, P true and Q false.

prove

Prove that $P \Leftrightarrow Q$ is equivalent to $(P \Rightarrow Q) \land (\neg P \Rightarrow \neg Q)$ . Why does this give a second way to prove an “if and only if”?

Solution

$\neg P \Rightarrow \neg Q$ is the contrapositive of $Q \Rightarrow P$ , so it has the same truth value. Hence the right side has the same truth value as $(P \Rightarrow Q) \land (Q \Rightarrow P)$ , which is the definition of $P \Leftrightarrow Q$ . So to prove an iff you may prove “P implies Q” and “not P implies not Q”.

prove

Explain why " $\forall x\ (P(x) \land Q(x))$ " is equivalent to " $(\forall x\ P(x)) \land (\forall x\ Q(x))$ ", but " $\forall x\ (P(x) \lor Q(x))$ " is NOT equivalent to " $(\forall x\ P(x)) \lor (\forall x\ Q(x))$ ". Give a counterexample for the second.

Solution

First: both sides say every $x$ satisfies both properties. Second: take $x$ ranging over integers, $P(x)$ = ” $x$ is even”, $Q(x)$ = ” $x$ is odd”. Every integer is even or odd, so the left side is true. But not every integer is even, and not every integer is odd, so the right side is false.

stretch

$f$ is uniformly continuous if $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x\ \forall y:\ |x - y| < \delta \Rightarrow |f(x) - f(y)| < \varepsilon$ . Compare with continuity at every point: $\forall a\ \forall \varepsilon > 0\ \exists \delta > 0\ \forall x:\ |x - a| < \delta \Rightarrow |f(x) - f(a)| < \varepsilon$ . Which quantifiers moved, and what does that change? Write the negation of uniform continuity.

Solution

In continuity the point $a$ comes before $\delta$ , so $\delta$ may depend on $a$ . In uniform continuity $\delta$ comes before $x$ and $y$ , so one $\delta$ must work everywhere at once. Negation: $\exists \varepsilon > 0\ \forall \delta > 0\ \exists x, y:\ |x - y| < \delta \land |f(x) - f(y)| \ge \varepsilon$ . (Chapter 1.3 shows $f(x) = x^2$ on $\mathbb R$ is continuous but not uniformly continuous.)

Summary

A theorem is a sentence; read it exactly before proving it.
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false. It means the same as $\neg P \lor Q$ and as its contrapositive $\neg Q \Rightarrow \neg P$ ; it does NOT mean the same as its converse $Q \Rightarrow P$ .
Proving the contrapositive proves the theorem.
Quantifier order matters: a later variable may depend on earlier ones.
Negation rules: not-and = or-of-nots, not-or = and-of-nots, not(if P then Q) = P and not Q, not-for-every = exists-not, not-exists = for-every-not.
Before a proof: name the objects, write every quantifier, split hypothesis from conclusion, write the negation.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture

Definitions and theorems

Statements and connectives

Statement

If-then

Implication

Converse

Contrapositive

An implication equals its contrapositive

If and only if

Quantifiers

Quantifier

Negation

Negation

Rules for negating

Reading a theorem, step by step

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere