Notes

Proofs

A proof is a valid argument that establishes the truth of a statement.

In Math and CS, we mostly use informal proofs.

Why proofs in CS?

• To prove your program to be correct
• Dijkstra “Testing shows the presence of bugs, not its absence”
• To establish your OS is secure
• To prove your algorithm gives you the correct answer
• To show your system specifications are consistent

Tools in our “Proof” Toolbox

• The Rules of Inference allow us to preserve truth.
• We must begin with the truth
• We must start with premises that are true.
• To prove a mathematical statement, we will need the following tools
  • Definitions
  • Theorem - A statement that can be shown to be true
  • axioms - Statements we assume to be true
  • lemma - A helping theorem or result which is needed to prove a theorem
  • proof - A valid argument that establishes the truth of a theorem
  • corollary - A theorem that can be established directly from a theorem
  • conjecture - A statement that is proposed to be true, usually on the basis of some partial evidence or intuition of an expert. When proof is found, the conjecture becomes a theorem.

Types of Proofs

• Exhaustive Proof
• Direct Proof
• Direct Proof by Contraposition
• Proof by Contradiction
• Uniqueness Proof
• Vacuous Proof
• Proof by Cases
• Trivial Proof
• Existence Proof

Link to original

Theorems

A theorem is a statement that can be shown to be true.

How are theorems stated?

• Many theorem assert that a property holds for all elements in the domain.
• We may have a universal quantifier, but it may not be explicitly stated.
  • Ex: If $x>y$, where $x$ and $y$ are positive real numbers, then $x^2>y^2$
  • What that really means is $(\forall x|x\in \mathbb{R}\wedge x>0:(\forall y|y\in \mathbb{R}\wedge y>0:x^2>y^2))$

Theorems that are Biconditional Statements

These are theorems that have the form $p\leftrightarrow q$.

We know that $p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$

We can prove biconditional by proving both $p\to q$ and $q\to p$.

Ex: For all integers $n$, $n$ is odd if and only if $n^2$ is odd.

Link to original

Definitions

Definitions of Numbers

Even Number

$De{f}^n$: An integer $n$ is said to be even if there exists an integer $k$ such that $n=2k$

Odd Number

$De{f}^n$: An integer $n$ is said to be odd if there exists an integer $k$ such that $n=2k+1$

Rational Number

$De{f}^n$: A real number $r$ is rational if there exists integers $p$ and $q$, where $q\ne 0$, $r=\frac{p}{q}$

Irrational Number

$De{f}^n$: A real number $r$ is irrational if there exists integers $p$ and $q$, where $q\ne 0$, $r=\frac{p}{q}$, and $p$ and $q$ have no common factors

Absolute Value

$De{f}^n$: $|a|$ is the absolute value of $a$ and it equals $a$ when $a\ge 0$, and equals $-a$ when $a\le 0$.

Definitions of Sets

Natural Numbers

$De{f}^n$: The set of natural numbers is defined to be

$\mathbb{N}=\{0,1,2,3,\dots \}$

Note that $0$ exists in this set. This is debated heavily, but for the purposes of this class, we assume it is a natural number.

Integers

$De{f}^n$: The set of integer numbers is defined to be

$Z=\{\dots ,-2,-1,0,1,2,\dots \}$

Rationals

$De{f}^n$: The set of rational numbers is defined to be $Q=\{\frac{p}{q}|p\in z\wedge q\in z\wedge q\ne 0\}$

Real

$\mathbb{R}$

Empty Set/Null Set

Is simply $\{\}$ or $\varnothing$

Singleton Set

A set with exactly one element.

$\{\varnothing \}$: singleton (we are saying that we have a Set with a null set within it)

U: Universal

Refers to all the elements that are in the currently referenced scope.

Ordered $n$-tuple

$De{f}^n$: $(a_1,a_2,\dots ,a_n)$ is an ordered collection of $n$ objects.

Note that there are parentheses instead of curly brackets. When this is the case, order does matter.

$(a_1,a_2,\dots ,a_n)=(b_1,b_2,\dots ,b_n)$ as long as

a_1=b_1 \\ a_2=b_2 \\ \vdots \\ a_n=b_n \end{align}$$ If $n=2$, then we have an **ordered pair.** ### Union $$A\cup{B}$$ is defined as $$x\in A \vee x\in B$$ ### Intersection $$A\cap B$$ is defined as $$x\in A\wedge x\in B$$ ### Difference $$ A - B $$ is defined as $$x\in A \wedge \neg x\in B$$ ### Complement $$\overline{A}\; \text{or}\; A^\complement $$ is defined as $$x\in U\wedge \neg x\in A$$ Complement of $B$ with respect to $A$ is the difference ### Set Identities ### Cardinality of Combined Sets (Principle of Inclusion-Exclusion) $|A\cup B| = |A| + |B| - |A\cap B|$ $|A\cup B\cup C| = |A|+|B|+|C|-|A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$ $$|A\cup B\cup C\cup D| = |A|+|B|+|C|+|D|-|A\cap B| - |B\cap C| - |C\cap D| - |C\cap D| - |A\cap B| - |A\cap C| + |A\cap B\cap C| + |A\cap C\cap D|+|B\cap C\cap D|+|A\cap B\cap D|-|A\cap B\cap C\cap D|$$ $A_1\cup A_2$ $\bigcup\limits_{i=1}^{n}A_i$ ## Functions ### Increasing/Decreasing Functions if $x<y$ then $f(x)\leq f(y)$ this is increasing $f(x)<f(y)$ this is strictly increasing if $x>y$ then $f(x)\geq f(y)$ this is decreasing if $x>y$ then $f(x)>f(y)$ this is strictly decreasingLink to original

Direct Proof

Definition

A direct proof of a conditional statement $p\to q$ is constructed by

• Assume $p$ is true
• Use rules of inferences, axioms, and logical (basic) equivalences to show that $q$ must follow

Note: In some cases, you may want to use direct proof by contraposition

Example 1: Give a direct proof of the theorem “If $n$ is an odd integer, then $n^2$ is odd.”

$De{f}^n$: An integer $n$ is said to be even if there exists an integer $k$ such that $n=2k$

$De{f}^n$: An integer $n$ is said to be odd if there exists an integer $k$ such that $n=2k+1$

For direct proof, we will assume the hypothesis is true.

Proof:

Assume $n$ is odd, then we have $n=2k+1$, for some integer $k$ (this is essentially a universal instantiation)

Squaring $n$, $n^2$, we get $n^2=2t+1$ where $t$ is an integer

\begin{flalign} n^2 \\ \equiv\, <\mathrm{substitution}> \\ (2k+1)^2 \\ \equiv\, <\mathrm{algebra}> \\ 4k^2+4k+1 \\ \equiv\, <\mathrm{algebra}> \\ 2(2k^2+2k)+1 \\ \equiv\, <\mathrm{substitution}> \\ 2r+1 \end{flalign}

What if we skip the last substitution? We can do this instead:

$$\mathrm{let}r=2k^2+2k$$

Since $k$ is an integer, $r=2k^2+2k$ is also an integer. $\therefore n^2$ can be written as $2r+1\therefore$ by the definition of odd integers, $n^2$ is odd.

Example 2: Give a direct proof of the theorem “The sum of two real rational numbers is rational”

Remember the definition of a rational number:

Rational Number

$De{f}^n$: A real number $r$ is rational if there exists integers $p$ and $q$, where $q\ne 0$, $r=\frac{p}{q}$

Link to original

Proof:

Arbitrarily pick 2 rational numbers. $\mathrm{let}r$ and $s$ be two real rational numbers. $\therefore$ there exist integers $p,q,t,u$ ($q\ne 0$ and $u\ne 0$ such that $r=\frac{p}{q}$ and $s=\frac{t}{u}$).

Now,

$$\begin{array}{r}r+s\\ \equiv <subt>\\ \frac{p}{q}+\frac{t}{u}\\ \equiv <algebra>\\ \frac{pu+tq}{qu}\end{array}$$

Let $u$ = $pu+tq$ and $w=qu$. Since $p,q,t,u$ are integers & $q\ne 0$ and $u\ne 0$, $u$ and $w$ are integers and $w\ne 0$. $\therefore$ by definition of rational numbers, $r+s$ is rational.

Link to original

Direct Proof by Contraposition

Definition

$p\to q\equiv \neg q\to \neg p$ If we can prove that the negation

Example: Prove that for any integer $n$ if $3n+2$ is odd, then $n$ is odd.

This theorem is of the form $p\to q$. What is $p$ and $q$?

$p$: $3n+2$ is odd. $q$: $n$ is odd.

Contrapositive $\neg q\to \neg p$

$\neg q$: $n$ is even. $\neg p$: $3n+2$ is even.

Proof: Assume $n$ is even. Therefore, $n=2k$, where $k$ is an integer. Now,

$$\begin{array}{r}3n+2\\ \equiv <substitution>\\ 3(2k)+2\\ \equiv <algebra>\\ 6k+2\\ \equiv <algebra>\\ 2(3k+1)\\ \equiv <substitution>\\ 2j\end{array}$$

Since $j$ is an integer, $3n+2$ is even. Therefore, $\neg q\to \neg p$. Therefore $p\to q$.

Link to original

Trivial Proof

Definition

If we can show that $q$ is always true then we can say $p\to q$ is true.

Example: Let $P(n)$ be “if $a$ and $b$ are non-negative integers and $a\ge b$, then $a^n\ge b^n$. Show that $P(0)$ is true.

• What is the domain? Non-negative integers (includes zero)
• We need to show $P(0)$ is true, in other words, “if $a$ and $b$ are non-negative integers and $a\ge b$, then $a^0\ge b^0$.”

Let’s do an equivalence style proof:

$$\begin{array}{r}{a}^0\ge b^0\\ \equiv <algebra>\\ 1\ge 1\\ \equiv <algebra>\\ T\end{array}$$

The conclusion is always true regardless of what the values of a and b are. Therefore, P(0) is always true.

Link to original

Vacuous Proof

Definition

If we can show that $p$ is always false, then $p\to q$ is always true.

Example: Prove $P(n)$ where $P(n)$ is “If $n$ is an integer with $10\le n\le 15$, which is a perfect square then $n$ is a perfect cube.”

Proof:

$n$ is both $10\le n\le 15$ There are no perfect squares between 10 and 15 $\therefore$ the statement that $n$ is an integer with $10\le n\le 15$, which is a perfect square, then $n$ is false for all integers $n$. $\therefore P(n)$ is true for all integers $n$.

note: this one lowkey explained mad weirdly, i’d recommend just watching a youtube video on it: Vacuous Proofs

Link to original

Proof by Contradiction

Transclude of Basic-Equivalences#law-of-excluded-middle

Definition

For any statement $p$, either it is true or false. There is nothing in the middle.

So, if i want to prove $p$, I can start by assuming $\neg p$ is true.

Suppose from that I derive $F$ or any contradiction.

Basically, proof by contradiction relies on you making an assumption (a negation of part of the statement) and then proving that the statement is false when that assumption is made, then you can say that the original is true.

Example: Prove that $\sqrt{2}$ is irrational.

Assume $\sqrt{2}$ is rational. $\therefore$ There exists integers $a,b$ ($b\ne 0$) such that $\sqrt{2}=\frac{a}{b}$ and $a$ and $b$ have no common factors.

Now,

$$\begin{array}{r}\sqrt{2}=\frac{a}{b}\\ \therefore <sq.both\mathrm{sides}>\\ 2=\frac{a^2}{b^2}\\ \therefore <algebra>\\ 2b^2=a^2\end{array}$$

Since $b$ is an integer, $a^2$ is an even integer.

$\therefore$ Using result, $a$ is even.

$\therefore$ there exists an integer $k$ such that $a=2k$

$$\begin{array}{r}a=2k\\ \therefore <algebra>\\ 2b^2=(2k{)}^2\\ \therefore <algebra>\\ 2b^2=4k^2\\ \therefore <algebra>\\ b^2=2k^2\end{array}$$

Since $k^2$ is an integer, $b^2$ is even. $\therefore$ b is even.

Since $a$ and $b$ are even, and $b$ and $a$ have a common factor of 2.

This contradicts the fact that the $a$ and $b$ are co-prime and have no common factors. Therefore, the opposite must be true, and $\sqrt{2}$ is irrational.

Example 2: Prove a claim of the form $p\to q$ using proof by contradiction

We assume the negation $\neg (p\to q)$ and derive a contradiction.

Assume that both $p\wedge \neg q$. Derive a contradiction. We can resolve the contradiction by giving up p, but p is our premises, we will stick with $p$. Therefore, $q$ must be true. Therefore, $p\to q$.

Example 3: Prove “for any integer $n$, if $3n+2$ is odd, then $n$ is odd”

For the negation, we assume that $n$ is even and $3n+2$ is odd.

Since $n$ is even, there exists an integer $k$ such that $n=2k$.

Now,

$$\begin{array}{r}3n+2\\ \equiv <substitution>\\ 3(2k)+2\\ \equiv <algebra>\\ 6k+2\\ \equiv <algebra>\\ 2(3k+1)\end{array}$$

Since $3k+1$ is an integer, $3n+2$ is even, this contradicts the fact that $3n+2$ is odd.

$\therefore n$ must be odd.

$\therefore$ by contradiction, if $3n+2$ is odd, then $n$ is odd.

Link to original

Proof by Cases

Definition

$(p_1\vee p_2\vee \dots \vee p_n)\to q\equiv (p_1\to q)\wedge (p_2\to q)\wedge \dots (p_n\to q)$

the original conditional statement wtih a hypothesis made up of a disjunction of propositions $p_1,p_2,\dots ,p_n$ can be proved by proving each of the $n$ conditional statements $p_i\to q$ individually.

To prove $p\to q$, we can find $p_1\vee p_2\vee \dots \vee p_n\equiv p$ and then individually prove every case.

Common Errors

• Drawing incorrect conclusions from examples
• No matter how many cases we cover in our own proof, we cannot prove the theorem to be true unless we prove every case

Example: if $x$ is a real number, then $x^2$ is a positive real number.

Proof: Let us consider two cases:

1. $x$ is positive, since a positive number times a positive number is positive, $x^2$ must be positive.
2. $x$ is negative, since a negative number times a negative number is positive, $x^2$ must be positive This “completes” the proof (no it doesn’t. the proof is wrong)

Why? $So{l}^n$: we missed the case where $x=0$

Example: Use proof by cases to prove that $|xy|=|x||y|$, where $x$ and $y$ are real numbers.

First, we need the definition of absolute value.

Transclude of Definitions#absolute-value

Proof: We will consider four cases.

1. $x\ge 0,y\ge 0$
2. $x\le 0,y\ge 0$
3. $x\ge 0,y\le 0$
4. $x\le 0,y\le 0$

Case 1: $x\ge 0,y\ge 0$.

Therefore, we have $|x|=x$ and $|y|=y$. Also, $xy\ge 0$. Therefore,

$$\begin{array}{r}|xy|\\ \equiv <definition>\\ x\ast y\\ \equiv <substitution>\\ |x||y|\end{array}$$

$\therefore$ for $x\ge 0,y\ge 0$, $|xy|=|x||y|$

Case 2: $x\le 0,y\ge 0$.

Therefore, we have $|x|=-x$ and $|y|=y$. Also, $xy\le 0$. Therefore,

$$\begin{array}{r}|xy|\\ \equiv <definition>\\ (-x)\ast y\\ \equiv <substitution>\\ |x||y|\end{array}$$

$\therefore$ for $x\le 0,y\ge 0$, we have $|xy|=|x||y|$

Case 3: $x\ge 0,y\le 0$.

Therefore, we have $|x|=x$ and $|y|=-y$. Also, $xy\le 0$. Therefore,

$$\begin{array}{r}|xy|\\ \equiv <definition>\\ x\ast (-y)\\ \equiv <substitution>\\ |x||y|\end{array}$$

$\therefore$ for $x\ge 0,y\le 0$, we have $|xy|=|x||y|$

Case 4: $x\le 0,y\le 0$.

Therefore, we have $|x|=-x$ and $|y|=-y$. Also, $xy\ge 0$. Therefore,

$$\begin{array}{r}|xy|\\ \equiv <definition>\\ (-x)\ast (-y)\\ \equiv <substitution>\\ |x||y|\end{array}$$

$\therefore$ for $x\le 0,y\le 0$, we have $|xy|=|x||y|$

$\therefore$ for all real numbers, $x$, $y$: $|xy|=|x||y|$

Without loss of generality (WLOG)

• in the last example, we dismissed case 3 because it was the same as case 2 with reversed roles
• to shorten the proofs, we could have proved cases 2 and 3 together because both are completely arbitrary, and whichever one is positive and whichever one is even does not matter

Example: Show that if $x$ and $y$ are integers and both $xy$ and $x+y$ are even, then both $x$ and $y$ are even.

Techniques Employed:

• Direct Proof by Contraposition
• Without loss of Generality (WLOG)
• Proof by cases

Proof: Using proof by contrapositive, we will show that if $x$ is odd or $y$ is odd, $x+y$ is odd or $xy$ is odd.

Without loss of generality, assume $x$ is odd.

$\therefore$ there exists and integer $m$ such that $x=2m+1$

Now, all we have to analyze is when $y$ is odd and $y$ is even.

$\therefore$ we must consider two cases, $y$ is odd or $y$ is even

Cases:

1. $y$ is odd
2. $y$ is even

Case 1: $y$ is odd.

$\therefore$ there exists integer $n$, $y=2n+1$

Now \begin{align} xy\\ \equiv<substitution>\\ (2m+1)(2n+1)\\ \equiv<algebra>\\ 4mn+2m+2n+1\\ \equiv<algebra>\\ 2(2mn+m+n)+1\\ \end{align} Since $m$ and $n$ are integers, $2mn+m+n$ is also an integer. $\therefore$ $xy$ is odd.

Case 2: $y$ is even.

$\therefore$ there exists integer $n$ such that y=$2n$

Now, $$\begin{align} x+y\ \equiv\ 2m+1+2n\ \equiv\ 2(m+n)+1 \end{align}$$$m, n$areintegers.$\thereforem+n$ is an integer.

$\therefore x+y$ is odd.

$\therefore$ By contraposition, if $xy$ and $x+y$ are even, then both $x$ and $y$ are even.

Link to original

Exhaustive Proof

Definition

This is a type of Proof by Cases

Definition

$(p_1\vee p_2\vee \dots \vee p_n)\to q\equiv (p_1\to q)\wedge (p_2\to q)\wedge \dots (p_n\to q)$

the original conditional statement wtih a hypothesis made up of a disjunction of propositions $p_1,p_2,\dots ,p_n$ can be proved by proving each of the $n$ conditional statements $p_i\to q$ individually.

To prove $p\to q$, we can find $p_1\vee p_2\vee \dots \vee p_n\equiv p$ and then individually prove every case.

Link to original

• Some theorems can be proved by examining a small number of examples
• We call this exhaustive proofs
• Better for computers, but even those have limits

Common Errors

Common Errors

• Drawing incorrect conclusions from examples
• No matter how many cases we cover in our own proof, we cannot prove the theorem to be true unless we prove every case

Example: if $x$ is a real number, then $x^2$ is a positive real number.

Proof: Let us consider two cases:

1. $x$ is positive, since a positive number times a positive number is positive, $x^2$ must be positive.
2. $x$ is negative, since a negative number times a negative number is positive, $x^2$ must be positive This “completes” the proof (no it doesn’t. the proof is wrong)

Why? $So{l}^n$: we missed the case where $x=0$

Link to original

Example: It is true that every non-negative integer is the sum of 18 fourth power integers.

$So{l}^n$: To determine if a non-negative integer can $n$ can be written as a sum of 18 fourth powers, we might begin to examine whether $n$ is the sum of 18 fourth power integers for the smallest non-negative integers.

Fourth power integers: $0,1,16,81$.

We can show that non-negative integers add up to ?? can be written as a sum of 18 fourth powers.

One might conclude it is possible based on this example, but 79 cannot be written as a sum of 18 fourth powers.

Example: Prove that $(n+1{)}^3\ge 3^n$ if $n$ is a positive integer such that $n\le 4$

Proof:

$n$ is a positive integer where $n\le 4$. Therefore, $n=1,2,3\text{or}4$

For $n=1$

$$\begin{array}{r}{3}^1\\ \equiv <arithmetic>\\ 3\end{array}$$

And

$$\begin{array}{r}(1+1{)}^3\\ \equiv <arithmetic>\\ 2^3\\ \equiv <arithmetic>\\ 8\end{array}$$

Since, $8\ge 3$, therefore, for $n=1$, $(n+1{)}^3\ge 3^n$. Repeat this line of reasoning for $n=2,3,4$

Link to original