These notes are derived from Richard Hammack’s textbook Book of Proof and course notes graciously given to me by Milos Savic. Much thanks to their creative, passionate work!

Chapter 1 - Sets

1.1 Introduction to Sets

What is a set?

A set is a collection of things.

What are the things? The things are called elements.

What is an element? Ok, an example is in order.

Example: $\{1,2,3,5,8\}$ is a set. Within braces, all elements of the set are listed. To save time, we could label/define our set: \[A = \{1,2,3,5,8\}\] Then, we can refer to our set as $A$ later on.
What are the elements of A?

Question 1: Create three different sets, with two of the three sets having objects different than whole numbers?

If there is a distinct pattern, ellipses ($...$) are used to denote a continuation of a pattern.

Which of the following sets are infinite? Which are finite?

$X = \{-2,-1,...,101,102\}$
$Y = \{-2,-1,0,1,...\}$
$\mathbb{Z} = \{...,-2,-1,0,1,2,...\}$
This is called the set of integers.
$\mathbb{N} = \{1,2,3,...\}$
This is called the set of natural numbers.

Question 2: Are each of your sets in Question 1 finite or infinite?

Notationally, we can say things:

$1 \in A$ to mean “1 is an element of the set A”. This saves time.
$\{1,2\} \subseteq A$ to mean “$\{1,2\}$ is a subset of A”, which means that all the elements of the set $\{1,2\}$ is contained in $A$.
$\{1,7\} \not\subseteq A$ to mean "$\{1,7\}$ is not a subset of $A$.
$|A| = 5$ to mean "the cardinality of the set is 5, which means the number of elements in the set is 5.
$A = B$ to mean “The set A is equal to the set B”, which means two sets are equal if they contain exactly the same elements.
$\emptyset = \{\}$ is called the empty set, the set with no elements.

Question 3: What are some elements of the sets that you created above? What are some subsets of the sets you created above? Please use the appropriate symbols when discussing elements.

Question 4: What should we call the cardinality of the set if the number of elements is not finite?

Set-builder notation is used to describe sets that would be difficult or too big to describe in braces:
Example: The even numbers: $\{2n:n \in \mathbb{Z} \}$
Example: The rational numbers: $\mathbb{Q} = \big\{\frac{p}{q} : p,q \in \mathbb{Z}, n \neq 0 \big\}$

Question 5: Use set-builder notation to describe the following sets expressed in interval notation:

$[1,2]$
$[-2,2]$ a $[1,\infty)$
$(-\infty,-1] \cup [1,\infty)$
The odd numbers greater than 5.
The odd numbers that are not divisible to 3.

Question 6: Form the textbook exercises, do at least 5 problems parts A-D each.

1.2 The Cartesian Product

An ordered pair is a list $(x,y)$ of two elements $x$ and $y$.

The Cartesian product of two sets $A$ and $B$ is $A \times B = \{(a,b): a \in A, b \in B \}$

Question 1: Sketch $\{x: x \in \mathbb{Z}, |x|<3\} \times \mathbb{Z}$.

Question 2: Sketch $\mathbb{N} \times \mathbb{Z}$.

Question 3: If $A$ and $B$ are sets, conjecture whether/how we can find $|A \times B |$? Prove your conjecture.

Question 4: From the textbook exercises, do A2-4 and B12-17.

1.3 Subsets

Recall:

If $A \subseteq B$, it is true that every element of A is an element of B. If such an element is called x, how would we write this using set notation?
If $A \not\subseteq B$, it is not true that every element of A is an element of B. Logically this means that there exists at least one element of A that is not an element of B. If such an element is called x, how would we write this using set notation?

Question 1: Are the following statements true or false? Justify/prove your results:

$A \subseteq A$ for any set A
$\emptyset \subseteq \emptyset$
$\emptyset \subseteq B$ for any set B

Comment: Authors that use “$\subseteq$” as we do here, may also use $A \subsetneq B$ or $A \subset B$ to mean “A is properly contained in B,” i.e. $A \subseteq B$ and there exists an $x \in B$ such that $x \notin A$.

Question 2: Make up your own examples $A$ and $B$ for each of the following cases:

$A \subset B$
$A \not\subset B$
$A \subseteq B$
$A \not\subseteq B$

Is it possible for any of these to occur simultaneously with the same sets?

Now brace yourselves: It is possible to make sets of sets.

Let $A = \{1,2,3\}$, $B = \{3,4\}$, and $C=\{5\}$. We could make
\[D = \{A,B,C\} = \big\{ \{1,2,3\}, \{3,4\}, \{5\} \big\}\] Question 3: By carefully using your definitions, find:

What are the elements of $D$?
What is $|D|$?
What are all the possible subsets of $D$?

Question 4: From the textbook exercises, do A-C. If you get stuck on any one of these, don’t stress! Just come to class ready to explain or discuss (1) what you tried and (2) where you got stuck.

1.4 Power Sets

The power set of a set A is the set of all the subsets of a set, denoted $\mathcal{P}(A)$. In symbols: \[\mathcal{P}(A) = \{X: X \subseteq A\}\]

Question 3: Make up your own sets for $A$ with 0, 1, 2, 3, and 4 elements. Then determine $\mathcal{P}(A)$ for each case.

Question 4: If is a finite set $A$ with $|A| =n$, determine a formula for $|\mathcal{P}(A)|$.

Question 5: From the textbook exercises, do A2,5-8,10-12 and B14-18,20.

1.5 Union, Intersection, Difference

Let A and B be sets. Then:

The union of A and B is the set: $A \cup B = \{x: x \in A \text{ or } x \in B \}$.
In words, the union $A \cup B$ is the set of all things that are in A or in B (or in both).

The intersection of A and B is the set: $A \cap B = \{x: x \in A \text{ and } x \in B \}$.
The intersection $A\cap B$ is the set of all things in both A and B.

The difference of A and B is the set: $A - B = \{x: x \in A \text{ and } x \not\in B \}$.
The difference $A-B$ is the set of all things that are in A but not in B.

Note: Another common notation for $A - B$ is $A \backslash B$

Question 1: Take two sets A, B, and C that are subsets of the integers, and consider the above operations with them. For example, what is the set $A \cap B$, $A \cup B$ or $(A \cup B) - C$ with your sets? Keep playing!

Question 2: Prove the following theorems.

Theorem 1: For sets A and B, if $A \cap B = A$, then $A \cup B=B$.

Theorem 2: For sets A,B, and C, if $A \subseteq B$ and $A \subseteq C$, then $A \subseteq B \cap C$.

Theorem 3: For sets A, B, and C, if $A \subseteq B$ then $C- B \subseteq C - A$.
Theorem 4: $A - (B \cup C) = (A - B) \cap (A - C)$.

Theorem 5: Let U be a set. For all subsets A and B of U, $A \cup B= \emptyset$ if and only if $A=\emptyset$ and $B=\emptyset$.

Theorem 6: For sets A,B, and C, if $A \cup B=C$ and $A \cap B=\emptyset$, then $B=C - A$.

Question 3: If you had four or more sets, give at least one theorem you could pose and prove that theorem.

Question 4: Let A and B be sets.
Is $P(A \cap B)=P(A) \cap P(B)$? If so, prove it.
Is $P(A \cup B)=P(A) \cup P(B)$? If so, prove it.

Question 5: From the textbook exercises, do #2-3, 6-7, 9-10

1.6 Complement

Often it is useful to talk about a set coming from an assumed set called the universal set. For example, the set of prime numbers comes from the natural numbers: $\mathbb{R}^2$. The set of points on the unit circle comes from the larger set of points in the real plane: $\mathbb{R}^2$.

Question 1: Think of two other example of sets and their universal set.

Let A be a set with a universal set U. The complement of A is $\bar{A} = U-A$.

Question 2: From the textbook exercises, do #1,4,5.

1.7 Venn Diagrams

Question 1: From the textbook exercises, pick 5 problems that you think look interesting to do.

1.8 Indexed Sets

Let $A_1, A_2, ... , A_n$ be sets. Then,

$\bigcup\limits_{i=1}^{n} A_i = A_1 \cup A_2 \cup ... \cup A_n = \{ x : x \in A_i \text{ for at least one set } A_i \text{, for } 1 \leq i \leq n \}$
$\bigcap\limits_{i=1}^{n} A_i = A_1 \cap A_2 \cap ... \cap A_n = \{ x : x \in A_i \text{ for every set } A_i \text{, for } 1 \leq i \leq n \}$

Question 1: From the textbook exercises, do #1.

Instead of using $i = 1,2,3,...n$, to index our series of unions, another way to describe this is with an index set, $I = \{1,2,...,n\}$:

$\bigcup\limits_{i\in I} A_i = \{ x : x \in A_i \text{ for at least one set } A_i \text{ with } i \in I \}$
$\bigcap\limits_{i \in I} A_i = \{ x : x \in A_i \text{ for every set } A_i \text{ with } i \in I \}$

Question 2: Let $I = [0,2]$ and $A_{\alpha} = [\alpha] \times [\alpha, 2]$. Find $\bigcup\limits_{\alpha \in I} A_{\alpha}$.

Question 3: From the textbook exercises, do #3-6, 10-14.

1.9 Russel’s Paragraph

See discussion in Canvas.

Chapter 2 - Logic

2.1 Statements

A statement is a mathematical expression that is either definitely true or definitely false.

Question 1: Make up your own examples of 5 statements.

Sometimes it is useful to express statements with a letter, possibly with some kind of variable specifier. For example, the following are statements:

P: I am hungry.
P(x): Person x is hungry.
Q: I am hungry and thirsty.
Q(x): Person x is hungry and thirsty.

Some sentences are not statements. For example:

$P(x): x^2 > x$

Without knowing what x is, this may either be true or false. Such a statement is called an open sentence.

Question 2: Make up two more of your own open sentences.

Question 3: Modify P(x) above to make it a statement.

Sometimes there are mathematical statements that have not yet been proven true or false.

Question 4: What does the Goldback conjecture state? Is it a statement?

Question 5: From the textbook exercises, pick 5 problems that seem interesting to do.

2.2 And, OR, Not

If P and Q are statements, they can be combined in several ways:

$P \land Q$ means “P and Q” $P \lor Q$ means “P or Q”

Question 1: Consider all the logical possibilities of P and Q. E.g. “P true, Q true”, “P true, Q false”, etc. In which cases is are $P \land Q$ and $P \lor Q$ true?

If P is a statement, the negation of P is denoted ~P or $\neg P$.

Question 2: Make up your own statements P and Q. Based on this, find the following:

$\neg P$
$\neg Q$
$P \land \neg Q$
$\neg P \lor \neg Q$

What other ways can you combine P and Q to make statements?

Question 3: From the textbook exercises, do #1-6.

2.3 Conditional Statements

Review:

$\land$ = and
$\lor$ = or

Another useful symbol for making logic statements is: $\Rightarrow$ which means “implies.”

When used in a statement such as $P \Rightarrow Q$, this is read “P implies Q”, or “If P is true, then Q must also be true.” This is called a conditional statement because Q is true under the condition that P is true.

Question 1: Make up three conditional statements. (They may or may not be accurate or true all the time.)

Question 2: Consider the statement (You pass the exam) $\Rightarrow$ (You pass the course). Under which cases is this not true.

Question 3: Consider all the logical possibilities of P and Q. E.g. “P true, Q true”, “P true, Q false”, etc. In which cases is $P \Rightarrow Q$ true? (It may be helpful to use an example, like the one above.)

Question 4: Besides the ones mentioned above, there are many other grammatical forms of the conditional statement. Write down as many other possible ways you might see conditional statements in common language that are equivalent to $P \Rightarrow Q$.

If P, then Q
Q if P
Q occurs whenever P occurs

Two of the more subtle, but equivalent ways of stating the conditional (P implies Q) are as follows:

P is a sufficient condition for Q.
Q is a necessary condition for P.

These statements are notoriously difficult for inexperienced mathematicians to correcty interpret:

Think about sufficient this way. “P is a sufficient condition for Q” means that to guarantee/ensure that Q occurs, it is sufficient to have found that P has occurred.
Think about necessary this way: “Q is a necessary condition for P” means if P occurs, then Q MUST (necessarily) occur.

Question 5: From the textbook exercises, do #1-11.

2.4 Biconditional Statements

If we are considering the conditional statement $P \Rightarrow Q$, the converse of this statement is $Q \Rightarrow R$.

Question 1: Write the converse of each of your conditional statements from 2.3 Question 1.

Question 2: If $P \Rightarrow Q$ is true, is the converse $Q \Rightarrow P$ necessarily true?

Question 3: Consider all the logical possibilities of P and Q. E.g. “P true, Q true”, “P true, Q false”, etc. In which cases is $Q \Rightarrow P$ true?

In the cases when both $P \Rightarrow Q$ and $Q \Rightarrow P$ are true, we say \[P \Leftrightarrow Q\] Which is read “P if and only if Q.”

Question 4: Consider all the logical possibilities of P and Q. E.g. “P true, Q true”, “P true, Q false”, etc. In which cases is $Q \Leftrightarrow P$ true?

Question 5: From the textbook exercises, do #1-5.

2.5 Truth Tables for Statements

Review: What do each of the following symbols mean?

$\land$
$\lor$
$\not$
$\Rightarrow$
$\Leftrightarrow$

(By now you should have these memorized. If not, do so ASAP!)

Question 1: Use a true table to determine when $\\mathord{\sim} (P \land Q)$ is true.

Question 2: Use a true table to determine when $(P \lor Q) \land \mathord{\sim} (P \land Q)$ is true.

Question 3: Use a true table to determine when $P \Leftrightarrow (Q \land R)$ is true.

Question 4: From the textbook exercises, do #1-5.

2.6 Logical Equivalences

Two logic statements are logically equivalent when if they have the same truth table, i.e. their truth values match up line for line in a truth table.

Question 1: Show $(P \lor Q) \land \mathord{\sim} (P \land Q)$ is logically equivalent to $P \Leftrightarrow Q$.

Question 2: Show $\mathord{\sim} (P \land Q)$ is logically equivalent to $(\mathord{\sim} P) \lor (\mathord{\sim} Q)$

Question 3: Show $\mathord{\sim} (P \lor Q)$ is logically equivalent to $(\mathord{\sim} P) \land (\mathord{\sim} Q)$

Note: Questions 2 and 3 are used enough they have a name, DeMorgan’s Laws.

Another commonly used statement is the contrapostive statement: $(\mathord{\sim} Q) \Rightarrow (\mathord{\sim} P)$

Question 4: Show $P \Rightarrow Q$ is logically equivalent to the contrapostive statement.

Question 5: Explain in your own words why the commutative laws hold.

$P \land Q = Q \land P$
$P \lor Q = Q \lor P$

Question 6: Explain in your own words (or using a truth table) why the associative laws hold.

$P \land (Q \land R) = (P \land Q)\land R$
$P \lor (Q \lor R) = (P \lor Q) \lor R$

Extra Credit: Show the distributive laws hold by using truth tables.

$P \land (Q \lor R) = (P \land Q) \lor (P \land R)$
$P \lor (Q \land R) = (P \lor Q) \land (P \lor R)$

Question 7: From the textbook exercises, do #10-13.

2.7 Quantifiers

Do you have these symbols memorized?

$\land$
$\lor$
$\not$
$\Rightarrow$
$\Leftrightarrow$

Two more symbols are really useful:

$\exists$ means “there exists” or “there is.” This is called the existential quantifier.
$\forall$ means “for all” or “for every.” This is called the universal quantifier.

Question 1: Write the following statements using quantifier symbols.

For every $n\in \mathbb{Z}$, $2n+1$ is odd.
There exists a subset $X$ of $\mathbb{Z}$, such that $|X| = 8$.

Notice the above statements are true. Statements with quantifiers may or may not be true.

Question 2: Make up three statements with quantifiers that are not true. Explain why they are not true.

Question 3: From the textbook exercises, do #1-10. If the statement is false, provide a counterexample.

2.8 (Skip)

2.9 Translating English to Symbolic Logic

Remember Goldback’s conjecture: Every even integer greater than 2 is the sum of two primes.

Question 1: State Goldback’s conjecture using quantifiers.

Notice that the following statements say the same thing:

$\forall x \in X, Q(x)$
$(x \in X) \Rightarrow Q(x)$

This awareness can make it easier to translate/interpret statements sometimes.

Question 2: From the textbook exercises, do #1-6, 12-13.

2.10 Negating Statements

Question 1: Try negating the following statement involving “and” and “or”:

Statement 1: You can solve a quadratic equation by factoring or with the quadratic formula.
Statement 2: The numbers x and y are both odd.

What did you do to negate the above statements?
Did you notice you were using DeMorgan’s laws?

Question 2: Try negating the following statements involving the universal and existential quantifier.

Statement 1: For all $x \in \mathbb{Z}$, $x$ is a perfect square holds.
Statement 2: There exists $x \in \mathbb{Z}$ such that $x$ is irrational.

Notice you just demonstrated the following equivalent:

$~(\forall x \in X, P(X)) = \exists x \in X, ~P(x)$
$~(\exists x \in X, P(X)) = \forall x \in X, ~P(x)$

These two negations describe precises meaning that is very useful in proving. Though sometimes we can intuitively negate statements, as we begin proving more statements, it will be very helpful to identify symbolic logic and apply negations for considering alternative meanings in disproving and proving statements.

Question 2: In whatever way makes the most sense to you, do textbook exercises #1-7, 11-12.

2.11 Logical Inference

See discussion in Canvas.

2.12 (Skip)

Chapter 3 - Counting

3.4 Factorials and Permutations

Question 1: How many different ways are there to arrange the following sets in a non-repetitive list (order matters)?

{a,b,c}
{a,b,c,d}
{1,2,3,…,n}

Definition: If $n$ is a non-negative integer, then $n!$ is the number of lists of length $n$ that can be made from $n$ symbols.

$0! = 1$
$1! = 1$
If $n>1$, then $n! = n(n-1)(n-2) ... 3 \cdot 2\cdot 1$.

Definition: A permutation is an arrangements of the elements of a set in a row (a non-repetitive list of all the elements of a set). A k-permutaion is an arrangement of k elements of a set in a row (a non-repetitive list of k elements of a set).

Question 2: Find all the 2-permutations of the following sets?

{a,b,c}
{a,b,c,d}
{1,2,3,…,n}

Question 3: Ten contestants run a marathon. All finish, and there are no ties. How many different possible rankings are there for first-, second and third-place?

Question 4: Find for formula for the number of k-permutations of an n-element set?

Question 5: From the textbook exercises, do #1-7.

3.5 Counting Subsets

Question 1: How many different 2-element subsets be made from the following sets?

{a,b,c}
{a,b,c,d}
{1,2,3,…,n}

Question 2: How many different 3-element subsets be made from the following sets?

{a,b,c}
{a,b,c,d}
{1,2,3,…,n}

Definition: If $n$ and $k$ are integers, then $n \choose k$ or $C(n,k)$ is the number of subsets that can be made by choosing $k$ elements from an $n$-element set.

Question 3: Find the formula for $n \choose k$.

Question 4: How many of subsets of {1,2,3,4,5,6,7,8,9} are there with size 4.

Question 5: How many subsets of a set with size $n$ are there with size $k$ for:

$k = 0$
$k = -1$
$k < 0$
$k = n+1$
$k > n$

Question 6: From the textbook exercises, do #2-7, 9-11, and 18-19.

3.6 Pascal’s Triangle and the Binomial Theorem

Question 1: Prove ${n+1 \choose k} = {n \choose k-1} + {n \choose k}$.

Question 2: Use this to draw Pascal’s Triangle (down to 6 rows).

Question 3: Prove ${n \choose k} = {n \choose n-k}$ for $0 \leq k \leq n$.

THe Binomial Theorem: If $n$ is a non-negative integer, then \[ (x+y)^n = \sum_{i=1}^n {n \choose 0}x^{n-i}y^i\] Question 4: Use the binomial theorem to expand $(x+2)^5$.

Question 5: From the textbook exercises, do #3-5, 7.

choose(13,5)*2^5

## [1] 41184

3.9 The Division and Pigeonhole Principles

Definitions:

The floor of x, or $\lfloor {x} \rfloor$, is x rounded down to the nearest integer.
The ceiling of x, or $\lceil {x} \rceil$, is x rounded up to the nearest integer.

Question 1: If $\lfloor \frac{x}{4} \rfloor=3$, what are the possible integer values of x?

Question 2: If $\lceil \frac{x}{4} \rceil=3$, what are the possible integer values of x?

Question 3: Prove the Division Principle:

Suppose $n$ objects are placed into $k$ boxes. Then,

at least one box contains $\lceil \frac{n}{k} \rceil$ or more objects, and
at least one box contains $\lfloor \frac{n}{k} \rfloor$ or fewer objects.

Question 4: A store has a gumball machine containing a large number of red, green, blue and white gumballs. You get one gumball for each nickel you put into the machine. The store offers the following deal: You agree to buy some number of gumballs, and if 13 or more of them have the same color you get $5. What is the fewest number of gumballs you need to buy to be 100% certain that you will make money on the deal?

Question 5: State the Division Principle in the cases of both $n>k$ and $n<k$

Fact: (Pigeonhole Principle) Suppose $n$ objects are placed into $k$ boxes. Then,

If $n>k$, then at least one box contains more than one object.
If $n<k$, then at least one box is empty.

Question 6: How many people would need to be choosen in order for at least two of them to have the same birth month?

Question 5: From the textbook exercises, do #2-4.

3.10 Combinatorial Proof

Combinatorial proof is a method of proving two different expressions are equal by showing that they are both answers to the same counting question.

Question 1: Use combinatorial proof to show that ${n \choose k} = {n \choose n-k}$.

Question 2: Use combinatorial proof to show that $\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}$.

Question 3: From the textbook exercises, do #2,3.

Chapter 4 - Direct Proof

4.1 & 4.2 Theorems & Definitions

Which of the following terms have you seen used before?

Theorem:
Proof:
Conjecture:
Definition:
Proposition:
Lemma:

Definitions:

An integer $n$ is even if $n=2a$ for some $a\in \mathbb{Z}$.
An integer $n$ is odd if $n=2a+1$ for some $a\in \mathbb{Z}$.
Two integers have the same parity if they are both odd or both even. Otherwise they have the opposite parity.

Question 1: Prove the following propositions:

Prop 1: If $x$ is an even number, then $x^2 - 6x + 5$ is odd.
Prop 2: IF $x$ is an odd integer, then $x^3+1$ is even.

More definitions:

If $a$ and $b$ are integers, we say a divides b, or $a \mid b$, if $b = ac$ for some $c \in \mathbb{Z}$.
An number $n \in \mathbb{N}$ is prime if it has exactly two positive divisors, $1$ and $n$. Numbers that are not prime are called composite.

Question 2: Show that a number is composite if and only if $n = ab$ such that $1<a<n$ and $1<b<n$

Definition: The greatest common divisor of integers $a$ and $b$, denoted $gcd(a,b)$ is the largest divisor of both $a$ and $b$

Question 3: Find the following:

$gcd(18,24)$
$gcd(7,7)$
$gcd(24,-8)$
$gcd(2,7)$
$gcd(a,b)$ when $a$ and $b$ are distinct primes.

Facts:

The sum, difference, and product of integers are also integers.
(Division algorithm) Given integers $a$ and $b$ with $b>0$, there exists unique integers $q$ and $r$ for which $a = qb+r$ and $0 \leq r \leq b$.
Every natural number greater than 1 has a unique factorization into primes. In other words, for $n \in \mathbb{Z}$, there exists exactly one set of prime numbers $p_1 < p_2 < ... < p_k$ and natural numbers $n_1, n_2, ..., n_k$ whereby:

\[n = p_1 ^{n_1} \cdot p_2^{n_2} \cdot ... \cdot p_k^{n_k}\] For example, $2200 = 2^3 \cdot 5^2 \cdot 11$ ($p_1 = 2, n_1 = 3, p_2 = 5, n_2=2, p_3 = 11, n_3 = 1$).

Question 4: Pick three distinct composite numbers. Find the prime factorization of each.

For your reference, here are some good definitions of the terms from the beginning of this chapter.

Theorem: a mathematical statement that is true and can (and has been) be verified as true
Proof: written verification that shows a theorem is unequivocally true.
Conjecture: a mathematical statement that is not known to be true or false.
Definition: exact unambiguous explanation of a mathematical word or phrase.
Proposition: a mathematical statement that is true, but not significant as a theorem
Lemma: a theorem whose main purpose is to help prove another theorem
Corollary: a result or immediate consequence of a theorem or proposition.

4.3 Direct Proof

This is the outline for proving a conditional statement directly.

Proposition: If P, then Q.
Proof: Suppose P.
$\vdots$
Therefore Q.

Remember: First line (Suppose P), last line (Therefore Q), unpacking ($\vdots$)."

Question 1: Use the proof outline above to prove the following propositions:

Proposition A: If x is odd, then $x^2$ is odd.

Proposition B: If $a \mid b$ and $b \mid c$, then $a \mid c$.

Proposition C: If $x$ and $y$ are positive real numbers, then \[\sqrt{xy} \leq \frac{x+y}{2}\]

Question 2: In a direct proof, why don’t we consider the situation in which P is false?

Question 3: From the textbook exercises at the end of Chapter 4, do #3-8, 10-11.

4.4 Using Cases

Sometimes in a direct proof, it is helpful to consider multiple subproofs of specific cases.

Question 1: Use cases to prove the following propositions:

Proposition D: If $n\in \mathbb{N}$, then $1+(-1)^n(2n-1)$ is a multiple of 4.

Proposition E: If two integers have the opposite parity, then their sum is odd.

In the above propositions, both cases are identical. In this case, we can state “without loss of generality” (WLOG), to state that we are treating one of several nearly identical cases.

Question 2: From the textbook exercises for chapter 4, do #14-20, 26.

Chapter 5 - Contrapostive Proof

5.1 Contrapostive Proof

This is the outline for proving a conditional statement using the contrapostive.

Proposition: If P, then Q.
Proof: Suppose ~Q.
$\vdots$
Therefore ~P.

Question 1: Use the contrapostive to prove the following propositions:

Proposition A: Suppose $x \in \mathbb{Z}$. If $7x+9$ is even, then $x$ is odd.

Proposition B: Suppose $x \in \mathbb{Z}$. If $x^2-6x+5$ is even, then $x$ is odd.

Proposition C: Suppose $x,y \in \mathbb{R}$. If $y^3 + yx^2 \leq x^3 + xy^2$, then $y \leq x$.

Question 2: From the textbook exercises for chapter 5, do #1-4, 9, 12.

5.2 Congruence of Integers

Definition: Given $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, we say that $a$ and $b$ are congruent modulo n if $n | (a-b)$, written as: \[a \equiv b \;(\bmod\; n)\]

If $a$ and $b$ are not congruent modulo $n$, we write: \[a \not\equiv b \;(\bmod\; n)\]

Example: $6 \equiv 10 (\text{mod } 4)$ because $4$ divides $(6-10)$.

Example: $7 \not\equiv 10 (\text{mod } 4)$ because $4$ does not divide $(7-10)$.

Question 1: Let $X$ be the set of all numbers that are congruent to $1$ modulo $4$. Find $X$.

Question 2: Prove the following proposition using direct proof.

Let $a,b \in \mathbb{Z}$ and $n\in\mathbb{N}$. If $a \equiv b (\text{mod } n)$, then $a^2 \equiv b^2 (\text{mod } n)$.

Question 3: Prove the following propositions using contrapositive proof.

Let $a,b \in \mathbb{Z}$ and $n\in\mathbb{N}$. If $12a \equiv 12b (\text{mod } n)$, then $n$ does not divide 12.

Question 4: From the textbook exercises for chapter 5, do #20-25.

5.3 Mathematical Writing

See Discussion in Canvas.

Chapter 6 - Proof by Contradiction

6.1 Proving Statements using Contradiction

This is the outline for proving a statement using contradiction.

Proposition: $P$
Proof: Suppose $\mathord{\sim} P$.
$\vdots$
Therefore $C \land \mathord{\sim} C$.

Question 1: Prove the following using proof by contradiction.

Proposition: If $a,b \in \mathbb{Z}$, then $a^2-4b \neq1$.

Proposition: The number $\sqrt{2}$ is irrational.

Proposition: There are infinitely many primes.

6.2 Proving Conditional Statements using Contradiction

Recall: What is the negation of the conditional statement, P implies Q?

This gives the following outline for proving a conditional statement using contradiction.

Proposition: $P$ implies $Q$
Proof: Suppose $P$ and $\mathord{\sim} Q$.
$\vdots$
Therefore $C \land \mathord{\sim} C$.

Question 2: Prove the following conditional statement using proof by contradiction.

Proposition: If $a,b \in \mathbb{Z}$ and $a \geq 2$, then $a \nmid b$ or $a \nmid (b+1)$.

6.4 Which is simpler, contradiction or contrapositive?

Question 3: Give two proofs the following statements - one using proof by contradiction and one using proof by contrapositive. Which is simpler?

Proposition: If $a^2$ is even, $a$ is even.

Question 4: Do the exercises at the end of chapter 6: #2-3,5-6,8-10,16-18.

Chapter 7 - Proving Non-Conditional Statements

7.1 Biconditional Statements

Question 1: Prove the following statements:

Proposition - An integer $n$ is odd if and only $n^2$ is odd.

Proposition - Suppose $a$ and $b$ are integers. Then $a \equiv b \;(\bmod\; 6)$ if and only if $a \equiv b \;(\bmod\; 2)$ and $a \equiv b \;(\bmod\; 3)$

7.2 Equivalence

Question 2: Suppose we need to prove statements P, Q, R, and S are all equivalent: \[P \iff Q \iff R \iff S\] Outline various ways to prove this.

7.3 Existence

Question 3: Prove the following statements:

Proposition - There exists an even prime number.

Proposition 7.1 (pg. 152) - If $a,b \in \mathbb{N}$, then there exists $k,l \in \mathbb{Z}$ for which $gcd(a,b) = ak + bl$.

7.4 Constructive vs. Non-Constructive Proofs

Proposition - There exists irrational numbers $x$ and $y$ for which $x^y$ is rational.

Question 4: Prove the above proposition using a non-constructive proof. (Let $x = \sqrt{2}^{\sqrt{2}}$ and $y = \sqrt{2}$.)

Question 5: Prove the above proposition using a constructive proof. (Let $x = \sqrt{2}$ and $y = \log_2{9}$.)

Question 6: Do the exercises at the end of chapter 7: #4-7, 10-12, 21, 29-30.

Chapter 8 - Proof Involving Sets

How to prove $a \in A$

To show $a \in \{x \in S : P(x) \}$:

Verify $a \in S$.
Show $P(a)$ is true.

Question 1: Let $C = \{3x^3+2: x \in \mathbb{Z}\}$. Show $-22 \in C$ but $22 \not\in C$.

Question 2: Let $A = \{(x,y)\in \mathbb{Z} \times \mathbb{Z}: x \equiv y \;(\bmod\; 8) \}$. Find 2 elements that are in A and 2 elements that are not.

How to prove $A \subseteq B$

To show $A \subseteq B$ directly,

Suppose $a \in A$.
Show $a \in B$.

This proves $a \in A$ implies $a \in B$, so $A \subseteq B$.

To show $A \subseteq B$ using the contrapostive,

Suppose $b \not\in B$.
Show $b \not\in A$.

This proves $b \not\in B$ implies $b \not\in A$, so $A \subseteq B$.

Question 3: Let $A = \{x^4: x \in \mathbb{Z}\}$ and $B = \{x^2: x \in \mathbb{Z}\}$ Show $A \subseteq B$.

Question 4: Show $\{ x \in \mathbb{Z}: 18|x \} \subseteq \{ x \in \mathbb{Z} : 6|x \}$.

Question 5: Prove $\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$.

How to prove $A = B$

To prove $A = B$,

Prove $A \subseteq B$.
Prove $B \subseteq A$.

Question 6: Prove $\{ n \in \mathbb{Z}: 15|n \} = \{ n \in \mathbb{Z} : 3|n \} \cap \{ x \in \mathbb{Z} : 5|n \}$.

Question 7: Do the exercises at the end of chapter 8: #2-6, 10, 19-20, 24, 28.

Chapter 9 - Disproof

To disprove $P$, prove $\mathord{\sim} P$.

Disproving Universal Statements

Question 1: How do we disprove $\forall \ x \in S, P(x)$?

Question 2: How do we disprove $P(x) \implies Q(x)$?

Question 3: Disprove the conjecture:
For every $n \in \mathbb{Z}$, $f(n) = n^2-n+11$ is prime.

Question 4: Disprove the conjecture:
If $n \in \mathbb{Z}$, $n^3-n$ is even.

Disproving Existential Statements

Question 5: How do we disprove $\exists \ x \in S, P(x)$?

Question 6: Disprove the following conjecture:
There is a real number for which $x^4 < x < x^2$.

Question 7: Prove or disprove the following conjecture:
There is a real number for which $x^4 \leq x \leq x^2$.

Disproof by contradiction

To disprove $P$ by contradiction:

Assume P is true.
Then deduce a contradiction.

Question 8: Disprove the following conjecture:
There is a prime numbers $p$ and $q$ for which $p-q = 61$.

Question 9: Do the exercises at the end of chapter 8: #10-12, 18-20, 24.

Chapter 10 - Mathematical Induction

10.1 Proof by Induction

Outline of Proof by Induction:

Proposition: The statements $S_1, S_2, S_3, ...$ are all true.
Proof: (1) Prove $S_1$ is true.
(2) Assume for any $k\geq 1$, $S_k \Rightarrow S_{k+1}$ is true.
It follows that every $S_k$ is true.

Question 1: Prove if $n \in \mathbb{N}$, $1+3+5+7 ++ (2n-1) = n^2$.

Question 2: Prove if $n \in \mathbb{N}$, $n\geq 2$, $1+2+3+n = \frac{n(n-1)}{2}$.

Question 3: Prove if $n \in \mathbb{N}$, $5 | (n^5-n)$.

Question 4: Prove if $n \in \mathbb{N}$, then $\sum_{i=0}^n i\cdot i! = (n+1)! - 1$.

Question 5: From the textbook exercises at the end of Chapter 10, do #2-6.

10.2 Proof by Strong Induction

Sometimes using proof by induction is a bit easier if we make a stronger assumption at the inductive step. Instead of showing $S_k \Rightarrow S_{k+1}$, we could get to the same conclusion by showing $(S_1 \land S_2 \land ... \land S_k) \Rightarrow S_{k+1}$. This technique is called strong induction:

Proposition: Statements $S_1, S_2, S_3, … $ are all true.
Proof: (Strong induction)
(1) Show that $S_1$ is true. (Or the first several S_n if this helps.) (2) Given any integer $k \geq 1$, prove $(S_1 \land S_2 \land ... \land S_k) \Rightarrow S_{k+1}$.

Question 6: Use strong induction to prove the following:
Any postage stamp of 8 cents or more is possible to make using 3 and 5 cent stamps.

Question 7: Use strong induction to prove the following: If $n \in \mathbb{n}$, then $12 | (n^4 - n^2)$.

A graph is a configuration of points (vertices) and line (edges). A graph has a cycle if it has way you can travel along edges from one point back to itself.

Question 8: Draw a graph with a cycle and another graph with two cycles

A graph is called a tree if it has no cycles.

Question 9: Draw your graphs from the previous question, but with enough removed edges to make it a tree!

Question 10: Use strong induction to prove that:
If a tree has $n$ vertices, then it has $n-1$

10.3 Proof by Smallest Counterexample

Another proof technique, proof by smallest counter example, is a hybrid of induction and proof by contradiction. Here is the outline:

Proposition: Statements $S_1, S_2, S_3, … $ are all true.
Proof: (Smallest counterexample)
(1) Show that $S_1$ is true.
(2) For the sake of contradiction, suppose that not every $S_n$ is true.
(2) Let $k>1$ be the smallest integer for which $S_k$ is false.
(4) Then $S_{k-1}$ must be true. Use this to derive a contradiction.

Question 11: Use proof by smallest counterexample to prove:
If $n \in \mathbb{Z}$, then $4 | (5^n-1)$.

10.4 Fundamental Theorem of Arithmetic

Question 12: Use induction to prove the Fundamental Theorem of Arithmetic:

Any integer $n>1$ has a unique prime factorization.

10.4 Fibonacci Numbers

Question 13: Use Google to find out: what is the Fibonacci sequence. How does it relate to the Golden Ratio?

Question 14: Use induction to prove that the Fibonacci sequence obeys: \[F^2_{n+1} - F_{n+1}F_n - F^2_n = (-1)^n\]

MATH 3253 - Foundation of Mathematics

Course Notes - Fall 2021

Paul Regier