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}, q \neq 0 \big\}$

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

$[1,2]$
$[-2,2] \cap [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 finite 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 1: Make up your own sets for $A$ with 0, 1, 2, 3, and 4 elements. Then determine $\mathcal{P}(A)$ for each case.

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

Question 3: 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: Using Venn Diagrams, illustrate 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: Find $\bigcup\limits_{i=1}^{4} A_i$ and $\bigcap\limits_{i=1}^{4} A_i$ when:

$A_1 = \{a,b,d,e,g,f\}$,
$A_2 = \{a,b,c,d,\}$,
$A_3 = \{b,d,a\}$, and
$A_4 = \{a,b,h\}$.

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 Sets that are Number Systems

(Skip)

1.10 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$ is not a statement.
Without knowing what x is, this may either be true or false. Such a statement is called an open sentence.

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

Question 3: Make up two of your own open sentences.

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

Question 4: The Goldback conjecture states that every even natural number greater than 2 is the sum of two prime numbers. Many brilliant mathematicians have tried and failed to prove it. Is Goldback conjecture a statement? Or an open sentence?

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 $\mathord{\sim}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 studied for the exam) $\Rightarrow$ (You will pass the exam). 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$ false? (It may be helpful to use an example, like the one above.)

Use this to fill in the blank: $\mathord{\sim} (P \Rightarrow Q)=$_________________

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-4, 7-10.

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 \land Q) \lor \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$

Question 7: 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 8: 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 More on Conditional Statements

Notice $P \Rightarrow Q$ is equivalent to “for all $p \in P$, $p \in Q$”. Negate the latter statement.

Question 1: Practice translating the following into statements involving quantifiers.

If $x$ is even, $x$ is a multiple of 6.
If $x \in \mathbb{R}$, $x^2 \geq 0$.

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.

Question 2 How did you do to negate the above statements?

Question 3: Try negating the following statements involving the universal quantifier.

Statement A: For all $x \in \mathbb{Z}$, $x$ is a perfect square.
Statement B: For all $x \in \mathbb{Z}$, $x^2$ is a non-negative.
Statement C: There exists $x \in \mathbb{Z}$ such that $x$ is irrational.
Statement D: There exists $x \in \mathbb{R}$ such that $x^2$ is odd.

Question 4: Which of the above statements are true?

These negations demonstrate the following equivalencies:

$\mathord{\sim} (\forall x \in X, P(X)) = \exists x \in X, \sim P(x)$
$\mathord{\sim} (\exists x \in X, P(X)) = \forall x \in X, \mathord{\sim}P(x)$

These two negations describe precise 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 5: Recall frm 2.8 that $P \Rightarrow Q$ is equivalent to “for all $p \in P$, $p \in Q$”. Negate the latter statement.

Question 6: Use the above to negate the following statements. Which version of each statement (the original or negation) is true?

Statement E: If $a$ is odd, $a^2$ is odd.
Statement F: If $p$ is prime, $p$ is odd.
Statement G: If $a>0$, $a^3-a>0$.

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

2.11-12 Logical Inference

See discussion in Canvas.

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: How many the 2-permutations are there for each 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=0}^n {n \choose i}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-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.
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 (each greater than 50). Find the prime factorization of each.

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$.

Question 5: Use the division algorithm to find $gcd(132, 132)$.

Question 6: Use the division algorithm to find $gcd(315,168)$.

Question 7: Choose $a,b \in \mathbb{Z}, a>100, b>100$. Use the division algorithm to find $gcd(a,b)$.

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.

Question 3: From the textbook, do 4.26: Prove “Every odd integer is a difference of two squares.”

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 $\mathord{\sim}Q$
$\vdots$
Therefore $\mathord{\sim}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 \not\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 \neq 2$.

Definition: A real number x is rational if $x = frac{a}{b}$ for some $a,b \in \mathbb{Z}$. Also, x is irrational if it is not rational, that is if $x \neq \frac{a}{b}$ for every $a,b \in\mathbb{Z}$.

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)$.

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

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

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

6.3-4 Which is simpler, contradiction or contrapositive?

Question 1: 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.

See discussion in Canvas.

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$.

Question 4: Use the division algorithm to find $gcd(132,56)$. Then use back-substitution to find $k,l\in\mathbb{Z}$ such that $gcd(132,56)=132k+56l$.

Question 5: Use the division algorithm to find $gcd(483,315)$. Then use back-substitution to find $k,l\in\mathbb{Z}$ such that $gcd(483,315)=483k+315$.

7.4 Constructive vs. Non-Constructive Proofs

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

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

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

Question 8: 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}$, $2n-n^2$ 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$.

Question 8: Prove or disprove the following conjecture:
There exists distinct $x,y,z \in \mathbb{N}$ such that $x^y = y^z$.

Disproof by contradiction

To disprove $P$ by contradiction:

Assume P is true.
Then deduce a contradiction.

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

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

Chapter 10 - Mathematical Induction

10.1 Proof by Induction

Proposition: Statements $S_1$, $S_2$, $S_3$, $...$ are all true. ($S_i$ is true for all $i \in \mathbb{N}$)
Proof: (Induction)
(1) Show that $S_1$ is true.
(2) Given any integer $k>1$, prove $S_k \Rightarrow S_{k+1}$.
Then it follows by mathematical induction that $S_{i}$ must be true for all $i \in \mathbb{N}$.

Question 1: How can the above be used to show $S_i$ is true for all $i \in \mathbb{Z}$?

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

Question 3: Show $1+2+3+4+...+n = \frac{n(n+1)}{2}$ for $n \in \mathbb{N}$.

Question 4: Show $5|(n^5-n)$ for $n \in \mathbb{N}$.

Question 5: Prove if $n \in \mathbb{N}$, $(1+x)^n \geq 1+nx$ for all $x \in \mathbb{R}$ with $x>-1$.

Question 6: 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 7: 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 8: 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 9: Draw a graph with a cycle.

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

Question 10: Draw your graph from Question 3, but with enough removed edges to make it a tree!

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

Question 12: From the textbook exercises, do #10-12, 16.

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 13: Use proof by smallest counterexample to prove:
If $n \in \mathbb{Z}$, then $4 | (5^n-1)$.

10.4 Fundamental Theorem of Arithmetic

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

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

Step 1: Prove n has prime factorization.
Step 2: Prove if n has prime factorization, that is is unique.

10.5 Fibonacci Numbers

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

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

Question 17: From the textbook exercises, do #19-21, 25, 29, 42.

Chapter 11 - Relations

11.1 Relations

Definition - A relation on a set $A$ is a subset $R \subseteq A \times A$. We often abreviate the statement $(x,y) \in R$ as $x R y$. The statement $(x,y)\not\in R$ is abbreviated as $x \not R y$.

Question 1: Make up a relation on the set $A = \{a,b,c,d\}$.

Question 2: Make up another relation on the set $A = \{a,b,c,d\}$, different from that in Question 1.

Another way a relation $R$ on $A$ can be depicted is by drawing dots for the elements of $A$ and drawing $(x,y) \in R$ as directed arrows from $x$ to $y$.

Question 3: Draw a picture of the relations from Questions 1 and 2.

Question 4: Draw all possible relations on $A = {0,1}$. How many are there?

Note that relations may not have any apparent meaning. The following relations, though, have a meaning we are familiar with. What is it?

$R_1 = \{(x,y) \in \mathbb{R} \times \mathbb{R}, x-y>0 \}$
$R_2 = \{(x,y) \in \mathbb{R} \times \mathbb{R}, x-y \leq 0 \}$
$R_3 = \{(x,y) \in \mathbb{R} \times \mathbb{R}, x-y=0 \}$
$R_4 = \{(x,y) \in \mathbb{R} \times \mathbb{R}, x-y\neq0 \}$

Question 5: From the textbook exercises, do #2-3,12-15.

11.2 Properties of Relations

Definition: Suppose $R$ is a relation on a set $A$.

Relation $R$ is reflexive if $xRx$ for every $x \in A$.
Relation $R$ is symmetric if $xRy$ implies $yRx$ for all $x, y \in A$.
Relation $R$ is transitive if whenever $xRy$ and $yRz$, then also $xRz$.

Question 6: Create relations on $A = (1,2,3)$ that are:

reflexive
symmetric
transitive

Question 7: Can you find a relation on $A = (1,2,3)$ that is transitive but not symmetric?

Question 8: Can you find a relation on $A = (1,2,3)$ that is symmetric but not transitive?

Question 9: For each of the following well-known relations on $\mathbb{R}$ determine if they are reflexives, symmteric, or transitive. (Make a table.)

$=$
$\neq$
$\leq$
$<$
$|$
$\not |$

Question 10: Prove is the relation $(a,b) \in R$ when $a \equiv b \;(\bmod\; 3)$ is reflexive, symmetric, and transitive.

Question 11: From the textbook exercises, do #7-10, 15-16.

11.3 Equivalence Relations

Definition: A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric and transitive.

Question 12: Make up and draw your own equivalence relation on $A = \{a,b,c,d\}$

Question 13: Show “has the same parity” is equivalence relation on $\mathbb{Z}$.

Question 14: Show “has the same absolute value” is equivalence relation on $\mathbb{Z}$.

Definition: Suppose $R$ is an equivalence relation on a set $A$. Given any element $a \in A$, the equivalence class containing $a$ is the subset $\{ x \in A : xRa \}$ of A consisting of all the elements of A that relate to a. This set is denoted as $[a]$:

\[[a]=\{x \in A : xRa \}\]

Question 15: Find the equivalence classes of the relations in Questions 12-14.

Question 16: From the textbook exercises, do #1-2, 6-8

11.4 Equivalence Classes and Partitions

Question 17: Prove the following theorem.

Theorem: Suppose $R$ is an equivalence relation on a set $A$. Suppose $a,b, \in A$. Then $[a]=[b]$ if an only if $aRb$

Definition A partition of a set $A$ is a set of non-empty subsets of $A$, such that the union of all the subsets equals $A$, and the intersection of any two different subsets is empty.

Question 18: Find the partitions of the relation $(a,b) \in R$ when $a \equiv b \;(\bmod\; 3)$

Question 19: Find all possible partitions of $A = \{a,b,c,d\}$.

Question 20: Prove the following theorem.

Theorem: Suppose $R$ is an equivalence relation on a set $A$. Then the set $\{[a] : a \in A\}$ of equivalence classes of R forms a partition of $A$.

Question 21: From the textbook exercise, do #2.

11.5 Integers Modulo n

Definition: Let $n \in \mathbb{N}$. The equivalence classes of the equivalence relation $(a,b) \in R$ when $a \equiv b \;(\bmod\; n)$ are $[0], [1], [2], ... , [n-1]$. The integers modulo n is the set $\mathbb{Z}_n = \{[0], [1], [2], ... , [n-1]\}$. Elements in $\mathbb{Z}_n$ can be added and multiplied by the rules:

$[a] + [b] = [a+b]$
$[a] \cdot [b] = [ab]$

Question 22: Write the addition and multiplication tables for $\mathbb{Z}_3$.

Question 23: Write the addition and multiplication tables for $\mathbb{Z}_4$.

Question 24: Verify the commutative and distributive laws for addition and multiplication over $\mathbb{Z}_n$.

Question 25: Is multiplication over $\mathbb{Z}_n$ independent of choice of the number representing equivalence classes? That is, if $[a],[b] \in \mathbb{Z}_n$, $[a]=[a']$, and $[b]=[b']$, does $[a]\cdot[b]=[a']\cdot[b']$?

Question 27: Is addition over $\mathbb{Z}_n$ independent of choice of the number representing equivalence classes? That is, if $[a],[b] \in \mathbb{Z}_n$, $[a]=[a']$, and $[b]=[b']$, does $[a]+[b]=[a']+[b']$?

11.6 Equivalence Classes and Partitions

Definition: A relation from a set $A$ to a set $B$ is a subset $R \subseteq A \times B$. We often abbreviate the statement $(x, y) \in R$ as $xRy$ and $(x, y) \not\in R$ as $x \not R y$.

Question 28: Make up your own relation from $A = \{1,2,3,4\}$ to $B = \{2,4,6,8,10\}$.

Chapter 12 - Functions

12.1 Functions

Definition: Suppose $A$ and $B$ are sets. A function $f$ from $A$ to $B$ (denoted as $f : A \rightarrow B$) is a relation $f \subseteq A \times B$ from $A$ to $B$, satisfying the property that for each a $a \in A$, the relation $f$ contains exactly one ordered pair of form $(a,b)$.

The statement $(a,b) \in f$ is abbreviated $f (a) = b$.

Question 1: Make up a relation from $A = \{a,b,c,d,e\}$ to $B = \{x,y\}$ that is a function.

Question 2: Make up a relation from $A = \{a,b,c,d,e\}$ to $B = \{x,y\}$ that is NOT a function.

Question 3: Define a relation $f$ from $\mathbb{R}$ to $\mathbb{R}$ that is a function.

Question 4: Define relation from $\mathbb{R}$ to $\mathbb{Z}$ that is a function.

Definition: For a function $f : A \to B$,

the set $A$ is called the domain of $f$ .
the set $B$ is called the codomain of $f$ .
the set $\{f(a): a \in A\}$ or $\{b: (a,b) \in f \}$ is called the range of $f$.

Which of these terms describes the set of “all possible input values” for f?
Which of these terms describes the set of “all possible output values” for f?

Question 5: Find the domain, codomain, and range of your functions in questions 1,3, and 4.

Definition: Two functions $f : A \to B$ and $g : A \to D$ are equal if $f = g$ (as sets). Equivalently, $f = g$ if and only if $f (x) = g(x)$ for every $x \in A$.

Question 6: Are the following two functions equal?

$f: \mathbb{Z} \to \mathbb{N}$, $f(x) = |x|+2$
$g: \mathbb{Z} \to \mathbb{Z}$, $g(x) = \begin{cases} -x+2, \text{ if } x<0 \\ x+2, \text{ if } x\geq 0 \end{cases}$

Question 7: From the textbook exercises, do #2,4,6, 9-12.

12.2 Injective and Surjective Functions

Definition: A function $f : A \to B$ is:

injective (or one-to-one) if for all $a,a' \in A$, $a \neq a$ implies $f (a) \neq f (a')$;
surjective (or onto B) if for every $b \in B$ there is an $a \in A$ with $f (a) = b$;
bijective if $f$ is both injective and surjective.

Which of these terms describes a function that hits all possible “output values” for f?
Which of these terms describes for which distinct values in the domain map to distinct values in the range

Question 1: Devise a function that is injective but not surjective.

Question 2: Devise a function that is surjective but not injective.

Question 3: Devise a function that is bijective.

Question 4:

Create a direct proof outline of showing $f : A \to B$ is injective.
Show $f(x): \mathbb{R} - \{0\} \to \mathbb{R}$, $f(x) = \frac{1}{x}$ is injective using the direct approach.
Create a contrapositive proof outline of showing $f : A \to B$ is injective.
Show $f(x): \mathbb{R} - \{0\} \to \mathbb{R}$, $f(x) = \frac{1}{x}$ is injective using the direct approach.
Which on of the above proof methods seemed easier to you? Why?
Is $f(x): \mathbb{R} - \{0\} \to \mathbb{R}$, $f(x) = \frac{1}{x}$ surjective?
Create a direct proof outline of showing $f : A \to B$ is surjective.
Show $f(x): \mathbb{R} - \{0\} \to \mathbb{R} - \{0\}$, $f(x) = \frac{1}{x}$ is surjective.

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

12.3 The Pigeonhole Principle Revisited

Question 1: Prove the pigeonhole principle, as formulated below:

The Pigeonhole Principle (function version):
Suppose A and B are finite sets and $f : A\to B$ is any function.
1. If $|A| > |B|$, then f is not injective.
2. If $|A| < |B|$, then f is not surjective.

Question 2: Use the pigeonhole principle to prove the following:

If $A$ is any set of 10 integers between 1 and 100, then there exist two different subsets $X \subset A$ and $Y \subset A$ for which the sum of elements in $X$ equals the sum of elements in $Y$.

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

12.4 Function Composition

Definition: Suppose $f : A \to B$ and $g : B \to C$ are functions. The composition of $f$ with $g$ is another function, denoted as $g \circ f$ and defined as follows:
If $x \in A$, then $g \circ f(x) = g( f (x))$. Therefore $g \circ f$ sends elements of $A$ to elements of $C$, so $g \circ f : A \to C$.

Question 1: Let $A = \{a,b,c\}$, $B = \{0,1\}$, and $C = \{1,2,3\}$. Make up your own functions $f : A \to B$ and $g : B \to C$, then find $g \circ f$.

Question 2: Let $f: \mathbb{Z} \to \mathbb{N}$ be defined as $f(x) = (x+1)^2$ and $g: \mathbb{N} \to \mathbb{R}$ be defined as $g(x) = \frac{x-1}{x}$. Find $g \circ f$.

Question 3: Prove $g \circ f$ is a function whenever $f : A \to B$ and $g : B \to C$ are functions

Question 4: Show function composition is associative, i.e. that if $f : A \to B$, $g : B \to C$, and $h : C \to D$, then $h \circ (g \circ f) = (h \circ g) \circ f$.

Question 5: Let $f : A \to B$ and $g : B \to C$ be functions. Prove or disprove the following:

If both $f$ and $g$ are injective, then $g \circ f$ is injective.
If both $f$ and $g$ are surjective, then $g \circ f$ is surjective.

Question 6: From the textbook exercises, do #4-5, 9-10.

12.5 Inverse Functions

Definition For a set $A$, the identity function on $A$ is the function $i_A : A \to A$ defined as $i_A(x) = x$ for every $x \in A$.

Definition: Given a relation $R$ from $A$ to $B$, the inverse relation of $R$ is the relation from $B$ to $A$ defined as $R^{-1} = \{(y, x) : (x, y)\in R\}$.
In other words, the inverse of $R$ is the relation $R^{-1}$ obtained by interchanging the elements in every ordered pair in $R$.

Question 1: Make up a relation $R$ from $A = \{a,b,c\}$ to $B= \{1,2,3\}$. find the inverse relation, $R^{-1}$.

Question 2: Prove the following theorem:

Let $f : A \to B$ be a function. Then $f$ is bijective if and only if the inverse relation $f^{-1}$ is a function from $B$ to $A$.

Definition: If $f : A \to B$ is bijective, then it’s inverse is the function $f^{-1}: B \to A$. The functions $f$ and $f^{-1}$ obey the properties:

Question 3: If $f : A \to B$ is bijective, what are the following compositions of functions. (What are the domain and codomain of these functions?)

$f \circ f^{-1}$
$f^{-1} \circ f$

Question 4: If $f : \mathbb{R} \to \mathbb{R}$, $f(x) = x^3+1$, find $f^{-1}$.

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

12.6 Image and Preimage

Definition: Suppose $f : A \to B$ is a function.

If $X \subseteq A$, the image of $X$ is the set $f(x) = \{f(x):x \in X\} \subseteq B$.
If $Y \subseteq B$, the preimage of $Y$ is the set $f^{-1}(y) = \{f^{-1}(y):y \in Y\} \subseteq A$.

Question 1: Define a function $f$ from $A = \{a,b,c,d,e\}$ to $B = \{1,2,3,4,5,6\}$. Find the following:

$f(\{a,b,d\})$
$f(\{d,e,f\})$
$f(\emptyset)$
$f^{-1}(\{1\})$
$f^{-1}(\{1,2,3\})$
$f^{-1}(\{6\})$

Question 2: Suppose $f : A \to B$ is a function, $W,X \subseteq A$, and $Y,Z \subseteq B$. Prove the following:

$f(W \cap X) \subseteq f(W) \cap f(X)$
$f(W \cup X) = f(W) \cup f(X)$
$X \subseteq f^{-1} \circ f(X)$
$f^{-1}(Y \cap Z) = f^{-1}(Y) \cap f^{-1}(Z)$
$f^{-1}(Z \cap Z) = f^{-1}(Y) \cap f^{-1}(Z)$
$f \circ f^{-1}(Y) \subseteq Y$

Question 3: Find examples for which equality doesn’t hold for the above expressions 1,3, and 6, respectively.

Question 4: From the textbook exercises, do #4,6,8.

Chapter 13 - Proofs in Calc

Question 1: Prove the Triangle inequality: If $x, y \in R$, then \[|x+y| \leq |x|+|y|\]

Question 2: Prove this alternate version of the Triangle inequality: If $x, y, z \in R$, then \[|x-y| \leq |x-z|+|z-y|\]

Question 3: Prove the Reverse Triangle inequality: If $x, y \in R$, then $|x-y| \geq \Big| |x|-|y| \Big|$

Question 4: Prove this alternate version of the Reverse Triangle inequality: If $x, y, z \in R$, then $|x-z| \geq \Big| |x-y|-|y-z| \Big|$

Chapter 14 - Cardinality in Sets

See discussion in Canvas.

MATH 3253 - Foundation of Mathematics

Course Notes - Fall 2022

Paul Regier

Chapter 1 - Sets

1.1 Introduction to Sets

1.2 The Cartesian Product

1.3 Subsets

1.4 Power Sets

1.5 Union, Intersection, Difference

1.6 Complement

1.7 Venn Diagrams

1.8 Indexed Sets

1.9 Sets that are Number Systems

1.10 Russel’s Paragraph

Chapter 2 - Logic

2.1 Statements

2.2 And, OR, Not

2.3 Conditional Statements

2.4 Biconditional Statements

2.5 Truth Tables for Statements

2.6 Logical Equivalences

2.7 Quantifiers

2.8 More on Conditional Statements

2.9 Translating English to Symbolic Logic

2.10 Negating Statements

2.11-12 Logical Inference

Chapter 3 - Counting

3.4 Factorials and Permutations

3.5 Counting Subsets

3.6 Pascal’s Triangle and the Binomial Theorem

3.9 The Division and Pigeonhole Principles

3.10 Combinatorial Proof

Chapter 4 - Direct Proof

4.1-2 Theorems & Definitions

4.3 Direct Proof

4.4 Using Cases

Chapter 5 - Contrapostive Proof

5.1 Contrapostive Proof

5.2 Congruence of Integers

5.3 Mathematical Writing

Chapter 6 - Proof by Contradiction

6.1 Proving Statements using Contradiction

6.2 Proving Conditional Statements using Contradiction

6.3-4 Which is simpler, contradiction or contrapositive?

Chapter 7 - Proving Non-Conditional Statements

7.1 Biconditional Statements

7.2 Equivalence

7.3 Existence

7.4 Constructive vs. Non-Constructive Proofs

Chapter 8 - Proof Involving Sets

How to prove \(a \in A\)

How to prove \(A \subseteq B\)

How to prove \(A = B\)

Chapter 9 - Disproof

Disproving Universal Statements

Disproving Existential Statements

Disproof by contradiction

Chapter 10 - Mathematical Induction

10.1 Proof by Induction

10.2 Proof by Strong Induction

10.3 Proof by Smallest Counterexample

10.4 Fundamental Theorem of Arithmetic

10.5 Fibonacci Numbers

Chapter 11 - Relations

11.1 Relations

11.2 Properties of Relations

11.3 Equivalence Relations

11.4 Equivalence Classes and Partitions

11.5 Integers Modulo n

11.6 Equivalence Classes and Partitions

Chapter 12 - Functions

12.1 Functions

12.2 Injective and Surjective Functions

12.3 The Pigeonhole Principle Revisited

12.4 Function Composition

12.5 Inverse Functions

12.6 Image and Preimage

Chapter 13 - Proofs in Calc

Chapter 14 - Cardinality in Sets