Proofs

2.1 Mathematical Definitions

An integer $x$ is even if there is an integer $k$ such that $x=2k$. An integer $x$ is odd if there is an integer $k$ such that $x=2k+1$.

The parity is whether the number is odd or even. If two numbers are both are even or odd, then the two numbers have the "same parity", otherwise they have "opposite parity."

A number $r$ is rational if there exists integers $x$ and $y$ such that $y \neq 0$ and $r=x/y$.

An integer $x$ divides an integer $y$ if and only if $x \neq 0$ and $y=kx$, for some integer $k$. The fact that $x$ divides $y$ is denoted as $x|y$. If $x$ does not divide $y$, then the fact is denoted $x|y$. If $x$ divides $y$, then $y$ is said to be a multiple of $x$, and $x$ is a factor or divisor of y.

An integer $n$ is prime if and only if $n>1$. and the only positive integers that divide $n$ are $1$ and $n$.

• Note that $1$ is not a prime number because $n$ must be greater than $1$.

An integer $n$ is composite if and only if $n>1$, and there is an integer $m$ such that $1<m<n$ and $m$ divides $n$.

An integer $n$ that is $n>1$ must be either prime or composite. Proof: Suppose $n$ is not prime, then there exists a positive integer $m$ such that $m\neq 1 \neq n$. Therefore, $1 < m < n$, and since $m$ divides $n$, then $n$ must be composite.

A real number $x$ is positive iff $x>0$ and a real number $x$ is negative iff $x<0$. A real number $x$ is non-negative iff $x\geq 0$ and non-positive iff $x \leq 0$.

Introduction to Proofs

A theorem is a statement that can be proven to be true. A proof consists of a series of steps, each of which that follows logically from assumptions or previously proven statements, whose final step should result in the statement of the theorem being proven. The proof of a theorem may use axioms which are statements assumed to be true.

• proofs are important to establish that a program works as expected, show that a crypto system is secure, or validating a set of inferences in AI.
• proof reasoning is stated in complete sentences and ends with a end of proof symbol ($\blacksquare$).

Most theorems are an assertion about all the elements in a set (universal statements) but can also assert that a number or object with certain properties exists (existential statements).

Proofs by exhaustion proves the statement by checking each element individual. Only use if the domain is small.

Proofs that use universal generation to prove a universal statement names an arbitrary object in the domain and proves the statement for that object. "Arbitrary" means that nothing is assumed about the object. Here's an example:

• Theorem: every positive integer is less than or equal to its square
• Proof: let $x$ be an integer such that $x>0$. [steps showing that $x \leq x^2$]

A counterexample is an assignment of values to variables that shows that a universal statement is false.

• A counterexample for a conditional statement must satisfy all the hypotheses and contradict the conclusion.

An existence proof is a proof that shows that an existential statement is true. It asserts that there is at least one element in the domain that has some particular properties.

• A common existence proof is a constructive proof of existence, which gives a specific example of an element in the domain or a set of directions to construct an element in the domain that has the required properties.
• A nonconstructive proof of existence proves that an element with the required properties exists without giving a specific example. A common method is to show that the non-existence of an element with the required properties leads to a contradiction.

To disprove an existential statement, you must argue that every single element of the domain does not have the required properties.

2.3 Best proof practices and common errors

It's best first practice to provide detailed arguments at each steps. Provide clear references when using outside facts. The assumptions that can be made for proofs in this course are:

• the rules of algebra
• the set of integer is closed under addition, multiplication, and subtraction. (e.g., sums of integers are also integers)
• every integer is either even or odd
• if $x$ is an integer, there are no other integer between $x$ and $x+1$.
• the relative order of any two real numbers
• the square of any real number is greater than or equal to $0$.

Language of proofs: Every step in a proof requires justification. Some common phrases are used to explain the reasoning in a proof:

• "thus" and "therefore": a statement that follows from the previous statement(s).
• "let": introduce new variables.
• "suppose": introduce a new variable or assumption.
• "since": reminds the reader of a fact that appeared earlier in the proof or assumption.
• "we will prove/show": give readers an indication of where the proof is leading.
• "by definition": known fact
• "by assumption": a fact that is known because of an assumption
• "in other words": rephrase a statement in a specific way
• "gives" and "yields": a proof is clearer if an algebraic step is justified, so use these words to say that one equation/inequality follows from another.

Other best practices:

• indicate when proofs start and end with "proof:" and $\blacksquare$.
• write proofs in complete sentences
• give readers a road map of what's been shown, what's been assumed, and where the proof is going
• introduce each variable when used for the first time
• blocks of equations should be introduced with english text and each step that does not follow from algebra should be justified.

Existential instantiation is a law of logic that says if an object is known to exist, then the object can be given a name, as long as it's not being used to denote something else.

Common mistakes:

• generalizing from examples. If a fact holds for some particular elements in a set it does not imply that the fact holds for all the elements in a set.
• skipping steps: don't assume a fact to be true without providing a reason.
• circular reason: do not use a fact to be proven in the proof itself.
• don't assume facts that have not been proven.

2.4 Writing direct proofs

Theorems of this kind can be expressed as $p \rightarrow c$ where $p$ is a proposition which asserts that a set of hypotheses are true and $c$ is the conclusion. In a direct proof, the hypotheses $p$ is assumed to be true and conclusion $c$ is proven as a direct result of the assumption.

2.5 Proof by contrapositive

A proof by contrapositive proves a conditional theorem of the form $p \rightarrow c$ by showing that the contrapositive $\lnot c \rightarrow \lnot p$ is true. In other words, $\lnot c$ is assumed to be true and $\lnot p$ is proven as a result of $\lnot c$

When deciding between a direct proof or a proof by contrapositive, choose the whether the hypothesis or negation of the conclusion provides a more useful assumption to work with.

An irrational number is a number that is not rational. If $x$ is a real number that is not irrational, then $x$ is rational.

Sometimes conditional statements have more than one hypothesis. In a proof by contrapositive it is only necessary to show that one of the hypotheses is false, assuming that the rest of the hypotheses are true and the conclusion is false.

2.6 Proof by contradiction

A proof by contradiction starts by assuming that the theorem is false and then it shows that by some logical inconsistency arises as a result of that assumption. The reasoning behind this is that if the assumption that the theorem is false leads to a conclusion that cannot be true, then the theorem must be true. This is also sometimes called the indirect proof.

The proof by contrapositive is a special case of a proof by contradiction, used only for conditional statements. It can be recasted as a proof by contradiction:

• assume $\lnot(p \rightarrow q)$, which is equivalent to $p \land \lnot q$
• use the assumption that $\lnot q$ is true to derive $\lnot p$ followed by the reasoning in the proof by contrapositive
• arrive at the contradiction $p$ (from the assumption) and $\lnot p$

2.7 Proof by cases

Proof by cases of a universal statement such as $\forall x P(x)$ breaks the domain for the variable $x$ into different classes and gives a different proof for each class (called a case). Every value in the domain must be included in at least one class. The cases are numbered, and each case begins with "Case $n$:" where $n$ is the number of that case. Each number is followed by a statement of assumptions for that case.

• a number can be included in more than one case as long as every integer is included in at least one case.

The absolute value of a real number $x$ is defined to be $|x| = -x$ if $x<0$, and $|x|=x$ if $x \geq 0$.

Two cases can be merged into one case. The term without loss of generality (WLOG) is used to narrow the scope of a proof to one special case in situations when the proof can easily be adapted to apply to the general case.

• this works when the two cases are identical