muchen 牧辰

Final Review

Updated 2017-12-17

Chapter 1


Power Set

Suppose \(A=\{1, 2\}\) then its power set is a set of all subsets of \(A\): \(\mathcal P(A)=\{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\)

Set Operations

Suppose sets \(A=\{1,2,3\}, B=\{3, 4, 5\}\)


If \(x\in A\) or \(x\in B\) then \(x\in A \cup B\)


If \(x\in A\) and \(x\in B\) then \(x \in A\cap B\)


If \(x\in A\) and \(x\notin B\) then \(x\in A-B\)


If \(x\in A\) then \(x\notin \bar A\)

Direct Product

Direct product of two sets is \(A\times B\) that outputs an ordered set \((a, b)\) such that \(a\in A, b\in B\).

Indexed Sets Operations


\[\bigcup_{i=1}^{n}A_i=A_1\cup A_2\cup A_3\cup \dots\]


\[\bigcap_{i=1}^{n}A_i=A_1\cap A_2\cap A_3\cap \dots\]

Chapter 2


A statement is a claim. A statement can be true or false.

Logical Operations


Binary operator also known as and. Denoted by \(\wedge\). Suppose \(A\) and \(B\) are statements \(A\wedge B\) is true if and only if \(A\) and \(B\) are both true.


Binary operator also known as or. Denoted by \(\vee\). \(A\vee B\) is true if \(A\) is true, \(B\) is true, or both is true.


Denoted by \(\neg\). If \(A=\neg B\), then \(A\) is true if and only if \(B\) is false.

Open Sentence

A statement that can’t be determined to be true or false unless a quantifier is given. An example would be:

Logical Equivalences


\[\neg (A\cap B)=\neg A\cup \neg B\]


\[A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\]


Implication: \(P\implies Q\)

Converse: \(Q\implies P\)

Contrapositive: \(\neg Q \implies \neg P\)

Negation: \(\neg (P\implies Q)\equiv \neg P \wedge Q\)

Biconditional Implications

Also referred to as “if and only if”

\[P\iff Q\equiv (P\implies Q)\wedge(Q\implies P)\]


An example of quantifiers to the open sentence example (above) would be:


\[\neg \forall \equiv \exists,\quad \neg \exists \equiv \forall\]

Chapter 4-10

Direct Proof

To prove \(P\implies Q\), the structure is:

\[\begin{align} &\text{Assume P is true}\\ &\vdots\\ &\text{Therefore Q is true} \end{align}\]

Proof By Cases

Usually use when there there is a disjunction in the proof.

Proof By Contrapositive

To prove \(P\implies Q\), the structure is:

\[\begin{align} &\text{Assume Q is false}\\ &\vdots\\ &\text{Therefore P is false} \end{align}\]

Proof By Contradiction

To prove \(P\implies Q\), the structure is:

\[\text{Assume the hypothesis is negated}: \neg Q \wedge P,\\ \vdots\\ \text{finds contradiction}\\ \text{Therefore the negated statement is false (original hypothesis is true)}\]

Existence Proof

To prove \(\exists x, R(x)\), where \(R(x)\) is the statement. Just provide an example.

Uniqueness Proof

To prove \(\exists x, R(x)\), \(x\) is unique, provide an example \(x=d\) for which \(R(d)\) is true (existence proof) and show that \(d\) is the only unique example.

Constructive Proof

Gives an explicit example that proves and existence proof.

Non-Constructive Proof

Proves an example exists without actually providing it.

Mathematical Induction

Proof By Induction

To prove the statements \(S_1, S_2, S_2\dots\) are all true, the structure is:

\[\begin{align} &\textbf{(basis step)}\text{ Prove }S_1\text{ is true}\\ &\textbf{(induction step)}\text{ Given any integer } k\geq1, \text{Prove } S_k\implies S_{k+1}\\ &\vdots\\ &\text{By induction hypothesis...}\\ &\vdots\\ &\text{Therefore }S_n\text{ is true} \end{align}\]

Strong Mathematical Induction

Strong induction works the same as regular induction, except:

Proof By Smallest Counterexample

This is a hybrid of proving by induction and proving by contradiction. To prove \(S_1, S_2, \dots\) are all true, the structure is:

\[\begin{align} \textbf{(basis)}&\text{ Prove } S_1 \text{ is true}\\ \textbf{(contradict)}& \text{ For the sake of contradiction, assume not every }S_n\text{ is true}\\ &\text{Let smallest integer }k>1 \text{ such that } S_k \text{ is false}\\ &\text{Then }S_{k-1} \text{ is true and } S_k \text{ is false; get contradiction} \end{align}\]

Chapter 11


Definition: a relation \(R\), on a set \(A\) is a subset \(R\subset A\times A\).

Relation Properties

Equivalence Relation

A relation \(R\) is an equivalence relation iff \(R\) is reflexive, symmetric, and transitive.

Equivalence Class

Equivalence relations on \(A\) divides \(A\) into subsets called equivalence class. The equivalence class containing \(a\) is the subset \(\{x\in A:xRa\}\) of \(A\) consists of all elements of \(A\) that relates to \(a\).

Theorem 11.1: Suppose \(R\) is an equivalence relation on set \(A\) and \(a,b\in A\). Then \([a]=[b]\) iff \(aRb\)


A partition of set \(A\) is a set of non-empty subsets of \(A\) such that the union of all subsets equals \(A\) and intersection of any two subsets equals \(\emptyset\).

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

Integer Modulo n

The equivalence classes of the equivalence relation \(\equiv (\text{mod } n)\) are \([0], [1], \dots, [n-1]\), for some \(n\in \mathbb N\). Then the integer modulo n is the set \(\mathbb Z_n=\{[0], [1], \dots, [n-1]\}\).

Chapter 12



A function is injective iff \(\forall x,y\in A, x\neq y\implies f(x)\neq f(y)\).

To prove a function is injective, the proof structure is (contrapositive):

\[\begin{align} &\text{Suppose }x,y\in A \text{ and } f(x)=f(y)\\ &\vdots\\ &\text{Therefore x=y} \end{align}\]


A function is surjective iff \(\forall b\in B, \exists a\in A\) such that \(f(a)=b\)

To prove a function is surjective, the proof structure is (direct):

\[\begin{align} &\text{Suppose } b\in B\\ &\vdots\\ &\text{*Existential proof for } \exists a\in A \text{ for which } f(a)=b* \end{align}\]


A function bijective iff the function is both injective and surjective

Pigeonhole Principle

Suppose \(A\) and \(B\) are finite sets and \(f:A\rightarrow B\) is any function, then:

Suppose \(A\) and \(B\) are finite sets and \(A\neq \emptyset, B\neq \emptyset\), then:


Suppose \(f:A\rightarrow B, g:B\rightarrow C\), then the composition is \(g\circ f:A\rightarrow C\)

Theorem 12.1: If \(f:A\rightarrow B\), \(g:B\rightarrow C\), \(h:C\rightarrow D\), then \((h\circ g)\circ f=h\circ (g\circ f)\)

Theorem 12.2: If \(f:A\rightarrow B\) and \(g: B\rightarrow C\), if both \(f\) and \(g\) are injective, then \(g\circ f\) is injective

Inverse Function

For a bijective \(f:A\rightarrow B\), its inverse is the function \(f^{-1}:B\rightarrow A\).

Composition with inverse yields identity function:

Identity Function

\[\forall x\in A, i_A(x)=x\]

Theorem 12.3: Function \(f\) is bijective iff the reverse relation \(f^{-1}\) is a function \(B\rightarrow A\)

Image & Preimage

Suppose \(f:A\rightarrow B\):

Chapter 13

Useful Definitions and Facts

Parity & Multiplicity

Well-Ordering Principle

Division Algorithm

Fundamental Theorem of Arithmetic

Greatest Common Divisor & Least Common Multiple

Given \(k,n\in (\mathbb Z-\{0\})\),

Proposition 7.1

If \(a,b\in \mathbb N\), then there exists integers \(k\) and \(l\) for which \(\gcd(a,b)=ak+bl\)

Proposition 10.1

Suppose there are \(n\geq2\) integers \(a_1, a_2, \dots, a_n\). If a prime number \(p\) divides \(a_1\cdot a_2\cdots a_n\), then \(p\) divides at least one of the integers \(a_i\).


Assuming \(a\equiv b\mod n\) and \(c\equiv d\mod n\) for \(a,b,c,d\in \mathbb Z\), then:

Pigeonhole Principle

see above

Image & Preimage

Theorem 12.4: Suppose \(f: A\rightarrow B\) and \(W,X\subset A, Y,Z\subset B\)