# Final Review

Updated 2017-12-17

## Chapter 1

### Set

• Denoted by $$\{\}$$
• Element in the set: $$1\in \{1, 2\}$$
• Subset: $$\{1\}\subset \{1,2\}$$

### 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\}$$

#### Union

If $$x\in A$$ or $$x\in B$$ then $$x\in A \cup B$$

#### Intersection

If $$x\in A$$ and $$x\in B$$ then $$x \in A\cap B$$

#### Difference

If $$x\in A$$ and $$x\notin B$$ then $$x\in A-B$$

#### Compliment

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

#### Union

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

#### Intersection

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

## Chapter 2

### Statement

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

### Logical Operations

#### Conjunction

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.

#### Disjunction

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.

#### Negation

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:

• $$x$$ is an even number.

### Logical Equivalences

#### DeMorgan

$\neg (A\cap B)=\neg A\cup \neg B$

#### Distributive

$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$

### Implications

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

### Quantifier

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

• $$\forall x\in \mathbb N$$ (this would make the statement false)
• $$\exists x\in \mathbb N$$ (this would make the statement true)

#### Negation

$\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}

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:

• instead of assuming $$S_k$$ is true, we assume $$S_1, S_2,\dots, S_k$$ all to be true.

#### 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

### Relation

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

#### Relation Properties

• Relation $$R$$ is reflexive iff $$\forall x \in A, xRx$$
• Relation $$R$$ is symmetric iff $$\forall x, y\in A, xRy\implies yRx$$
• Relation $$R$$ is transitive iff $$\forall x, y, z\in A, ((xRy)\wedge(yRz))\implies xRz$$

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

• Denoted as $$[a]$$
• Where $$[a]=\{x\in A: xRa\}$$
• If there exists $$[a]=[b]$$, there is still only one equivalence class.

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

#### Partition

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]\}$$.

• Property 1: $$[a]+[b]=[a+b]$$
• Property 2: $$[a]\cdot[b]=[a\cdot b]$$

## Chapter 12

### Function

• A function is denoted as $$f:A\rightarrow B$$, where $$A$$ is the domain and $$B$$ is the codomain
• The range of function $$f$$ is the set $$\{f(a):a\in A\}=b:(a,b)\in f$$
• Two functions $$f$$ and $$g$$ are the same iff $$\forall x\in A, f(x)=g(x)$$

### Injective

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}

### Surjective

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}

### Bijective

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:

• If $$\lvert A \rvert >\lvert B\rvert$$ then $$f$$ is not injective
• If $$\lvert A \rvert <\lvert B\rvert$$ then $$f$$ is not surjective

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

• If $$\lvert A \rvert \geq \lvert B \rvert$$ then $$\exists$$ a surjective $$f:A\rightarrow B$$
• If $$\lvert A \rvert \leq\lvert B \rvert$$ then $$\exists$$ an injective $$g:A\rightarrow B$$
• If $$\lvert A \rvert =\lvert B \rvert$$ then $$\exists$$ a bijective $$h: A\rightarrow B$$

### Composition

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:

• $f^{-1}\circ f = i_A$
• $f\circ f^{-1}=i_B$

#### 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$$:

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

## Useful Definitions and Facts

### Parity & Multiplicity

• An integer $$n$$ is even iff if $$n=2a$$ for some $$a\in\mathbb Z$$
• An integer $$n$$ is odd iff $$n=2a+1$$ for some $$a\in\mathbb Z$$
• Integers $$k$$ and $$n$$ have the same parity if $$k$$ and $$n$$ are both even or odd.
• An integer $$n$$ is a multiple of an integer $$q$$ iff $$n=qk$$ for some $$k\in \mathbb Z$$
• A positive integer $$n$$ is a prime number iff $$n$$ has exactly two positive divisors, namely $$1$$ and $$n$$.

### Well-Ordering Principle

• Given a subset $$A\subset \mathbb N$$, and $$A\neq \emptyset$$, then there is an element $$x_0\in A$$ such that $$x_0$$ is the smallest element in $$A$$
• Given an integer $$b$$, any non-empty subset $$A\subset\{b, b+1, b+2,\dots\}$$ is well-ordered

### Division Algorithm

• Given integers $$a$$ and $$b > 0$$, there exists integer $$q$$ and $$r$$ for which $$a=gb+r$$ and $$0\leq r \lt b$$

### Fundamental Theorem of Arithmetic

• Every integer greater than 1 is either a prime number itself or is the product of prime numbers

### Greatest Common Divisor & Least Common Multiple

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

• The GCD of $$k$$ and $$n$$ is the largest integer that divides both $$k$$ and $$n$$
• The LCM of $$k$$ and $$n$$ is the smallest integer that is a multiple of both $$k$$ and $$n$$

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

### Congruence

• Given $$n\in \mathbb N, a,b\in \mathbb Z$$, $$a$$ is congruent to $$b\mod n$$, denoted by $$a\equiv b\mod n$$, iff $$n\mid a-b$$

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

• $a-c\equiv b-d\mod n$
• $a^2\equiv b^2\mod n$
• $ac\equiv bd \mod n$
• If $$a\equiv b \mod n$$ and $$b \equiv c \mod n$$ then

see above

### Image & Preimage

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

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