discrete mathematics chapter 3 method of proof

Proof: showing that an assertion is true by sequence of statements that follow from other true statements (axioms and theorems).

Quantified Statement: Statements can be formed from open sentences by what is called a quantifier. There are two types of quantifiers: universal and existential.

Universal Quantifier: $forall$, “for all”, “for every”, “for each”.

Universal Quantified Statement: $forall x in S, P(x):$ for all $ x in S, P(x)$.

Existential Quantifier: $exists$, “there exists”, “there is”, “for some”, “for at least one”.

Existential Quantifier Statement: $exists x in S, Q(x):$ there exists $x in S$ such that $Q(x)$.

Negations of Quantified Statements:

• For an open sentence $R(x)$ over a domain $S$,

$$
begin{equation}
¬ (forall x in S, R(x)) ⇔ exists x in S, ¬R(x) \
¬ (exists x in S, R(x)) ⇔ forall x in S, ¬R(x)
end{equation}
$$

• For an open sentence $R(x, y)$ containing variables $x$ and $y$, where the domain of $x$ is $S$ and the domain of $y$ is $T$:

$$
begin{equation}
¬(forall x in S, exists y in T, R(x, y)) ⇔ exists x in S, forall y in T, ¬R(x,y) \
¬(exists x in S), forall y in T, R(x, y)) ⇔ forall x in S, exists y in T, ¬R(x,y)
end{equation}
$$

Direct Proof: finding a proof by moving forward from assumptions towards the target statement. Such that to prove $A ⇒ B$, assume $A$ is true and derive $B$.

• For example: If $n$ is odd then $5n + 3$ is even:

$$
begin{align}
Proof: &\
& n ; is ; any ; odd ; number; ⇒ n(mod ; 1) = 1 ; or ; n = 2k + 1 ; for ; some ; k \
& ⇒ 5n + 3 = 5(2k + 1) + 3 = 10k + 8 = 2(5k + 4), which ; is ; even. □
end{align}
$$

Proof by contrapositive: proving $¬ Q ⇒ ¬ P$ instead of $P ⇒ Q$. In this type of proof, we assume that $Q$ is false for and show that $P$ is false.

• For example: $3n + 8$ is odd if and only if $n$ is odd:

$$
begin{align}
Proof ; by ; contra&positive:\
&n:even; ⇒ ; n = 2k ; for ; some ; k \
&⇒ ; 3n + 8 = 3 times 2k + 8 = 2(2k + 4): even. □
end{align}
$$

Proof by case: dividing the target association into cases and proving them individually.

• For example: If $n$ is an integer then $n^2 - n$ is even:

$$
begin{align}
Proof; by; cases&: \
&case; 1: n ; is ; even:n = 2k ; for ; some ; k; \
&quad⇒ n^2 - n = (2k)^2 - k = 2(2k^2 - 1): even. □ \
&case; 2: n ; is ; odd: n = 2k + 1 ; for ; some ; k; \
&quad⇒ n^2 - n = (2k+1)^2 -(2k+1) = 2(2k^2 + k): even.□
end{align}
$$

Proof by counterexample: disproving $forall x; P(x) ⇒ Q(x)$ which is false, that is, $P(x)$ is true and $Q(x)$ is false: $¬forall x ; P(x) ⇔ exists x ; ¬P(x)$.

• For example: If $4n + 5$ is odd then $n$ is even:

$$
begin{align}
Disprove;:& \
&Pick; n = 1 ; as; counter-example,; then; 4n + 5 = 9:; odd; but; n; is; not; even. □
end{align}
$$

Existence Proof: in an existence proof of $exists x in S, P(x) ⇒ Q(x)$, we show that there is an element $a in S$ for which $R(a)$ is true.

• For example: $exists n ; (2-n^2 > 0)$:

$$
begin{align}
Proof:&\
& Pick; n = 0,; then; 2 - n^2 = 2 > 0. □
end{align}
$$

Proof by contradiction: proving an assertion by assuming that it is false and deriving a contradiction.

• For example: There is no smallest real number:

$$
begin{align}
Proof:& (by; contradiction) \
&Suppose; not,; for; instance,; there; is; a; smallest; real; number,; say; r < 0,; \
&then; r/2; is; a; real; number; which; is; smaller; than; 1,; a; contradiction.; \
&So;, the; assumption; that; there; is; a; smallest; real; number > 0; is; wrong.; □
end{align}
$$