PG1.4 Negating a statement

Simulate

Check the claim with numbers

The negation of a statement $S$ is a statement that is true exactly when $S$ is false. Take $S$ : "the fund beats the index every year". Three sentences sound like its opposite, but at most one can be its negation.

The cell uses ten years of made-up annual returns, in percent, and tests $S$ and the three candidates. The fund beats the index in a year when its return is higher.

fund = [8.1, 12.4, -3.0, 22.9, 15.2, 25.1, -14.8, 21.7, 19.3, 13.0] index = [9.5, 10.8, -4.4, 20.6, 14.1, 23.0, -18.1, 22.3, 18.0, 11.2] beats = [f > i for f, i in zip(fund, index)] print("years the fund beats the index:", sum(beats), "of", len(beats)) print("S: beats it every year:", all(beats)) print("A: in some year it does not beat it:", any(not b for b in beats)) print("B: it never beats it:", all(not b for b in beats)) print("C: the index beats the fund every year:", all(i > f for f, i in zip(fund, index)))

⌘/Ctrl + Enter runs the cell

The fund wins 8 of the 10 years, so $S$ is false. Candidate A is true, but B and C are false, like $S$ . A negation must have the opposite truth value, so neither B nor C is one.

One record cannot settle A. The next cell tries 10,000 random three-year records, each year a win with probability 0.7.

import random random.seed(1) trials = 10_000 opposite = {"A": 0, "B": 0} for _ in range(trials): beats = [random.random() < 0.7 for _ in range(3)] S = all(beats) opposite["A"] += any(not b for b in beats) == (not S) opposite["B"] += all(not b for b in beats) == (not S) print(opposite)

⌘/Ctrl + Enter runs the cell

Candidate A has the opposite truth value to $S$ in all 10,000 records. Candidate B manages only 3,656.

Conjecture

A

Ten thousand records agree, but the claim is about every set and every sentence, which no simulation can cover. The proof below does.

The rules for negating

In words: "not every element passes" means "some element fails". Here $\neg$ is "not", $\wedge$ "and", $\vee$ "or" (lesson PG1.1), and $\Rightarrow$ "implies" (lesson PG1.2). Each rule below pushes a "not" one step inwards, until it sits on the simplest pieces.

Rule: Negation rules

\begin{gathered} \neg(\forall x,\ P(x)) \equiv \exists\, x : \neg P(x) \\ \neg(\exists\, x : P(x)) \equiv \forall x,\ \neg P(x) \\ \neg(P \wedge Q) \equiv \neg P \vee \neg Q \\ \neg(P \vee Q) \equiv \neg P \wedge \neg Q \\ \neg(P \Rightarrow Q) \equiv P \wedge \neg Q \end{gathered}

A "for every" becomes a "there exists" and the other way round. "And" and "or" swap, as in De Morgan's laws. The negation of an implication is not an implication: it says the hypothesis holds and the conclusion fails.

Lesson PG1.1 proved the two De Morgan laws. The first rule is proved below, and the second in Write it.

For the last rule, lesson PG1.2 showed that $P \Rightarrow Q$ is false exactly when $P$ is true and $Q$ is false. So $\neg(P \Rightarrow Q)$ is true exactly when $P \wedge \neg Q$ is.

Negating a comparison follows the same idea. The negation of $f > i$ is $f \le i$ , not $f < i$ : a tie is not a win, so "does not beat" includes a tie.

Format 1

Reorder the steps

Here is a proof of the first rule, with its lines shuffled. Put them in order. The name $x_0$ (read 'x nought') stands for one particular element of $A$ .

Suppose $\neg(\forall x \in A,\ P(x))$ is true, so it is not the case that every element of $A$ satisfies $P$ .
Each statement is true exactly when the other is, so they are equivalent.
Now suppose some $x_0 \in A$ has $\neg P(x_0)$ true, so $P(x_0)$ is false.
Then $x_0$ is a counterexample, so $\forall x \in A,\ P(x)$ is false, and its negation is true.
That $x_0$ has $\neg P(x_0)$ true, so $\exists\, x \in A : \neg P(x)$ is true.
Let $A$ be a set and $P(x)$ a sentence about each $x \in A$ . We show that the two statements are true in exactly the same cases.
Then at least one element fails: there is some $x_0 \in A$ with $P(x_0)$ false.

Simulate

Check a negation with an implication

A harder statement mixes a quantifier and an implication: "every year in which the market rose, the fund beat the index". The market rose in a year when the index return was positive. Here are four years in which the statement holds, and two attempts at its negation.

def implies(p, q): return (not p) or q index = [12.0, -6.5, 8.3, 15.1] fund = [13.2, -9.0, 9.1, 16.4] rose = [i > 0 for i in index] beat = [f > i for f, i in zip(fund, index)] print("statement:", all(implies(r, b) for r, b in zip(rose, beat))) print("some year: rose and did not beat:", any(r and not b for r, b in zip(rose, beat))) print("some year: if rose, then did not beat:", any(implies(r, not b) for r, b in zip(rose, beat)))

⌘/Ctrl + Enter runs the cell

The statement is true and the first attempt is false, as a negation must be. The second attempt is true as well, so it is not the negation. In the falling year, the second in the list, its "if … then" holds whatever the fund did.

Format 3

Find the error

This negates 'every year in which the market rose, the fund beat the index' step by step. One step breaks a rule. Select it, then say what is wrong.

Simulate

A claim of your own to prove

The second negation rule turns "no element passes" into "every element fails". The cell tests it on 10,000 random lists of four whole numbers from $-3$ to $3$ , with $P(v)$ the sentence " $v > 2$ ".

import random random.seed(2) trials, agree = 10_000, 0 for _ in range(trials): values = [random.randint(-3, 3) for _ in range(4)] left = not any(v > 2 for v in values) right = all(not v > 2 for v in values) agree += left == right print(agree, "of", trials)

⌘/Ctrl + Enter runs the cell

The two sides agree in all 10,000 lists.

Conjecture

A

Agreement in 10,000 lists is evidence. Prove it for every set and every sentence, then use the rules on a sentence about the fund.

Format 4

Write it

First prove the rule above: show that each side is true exactly when the other is. Then use the rules to negate 'in some year, the fund beat the index in every month', and say what the negation means.

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

S

Negating a statement

Check the claim with numbers

The rules for negating

Rule: Negation rules

Reorder the steps

Check a negation with an implication

Find the error

A claim of your own to prove

Write it

Summary card

Free further reading