MATH 220
# Final Review

Updated 2017-12-17

- Denoted by \(\{\}\)
- Element in the set: \(1\in \{1, 2\}\)
- Subset: \(\{1\}\subset \{1,2\}\)

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

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** of two sets is \(A\times B\) that outputs an *ordered set* \((a, b)\) such that \(a\in A, b\in B\).

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

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.

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.

**Implication**: \(P\implies Q\)

**Converse**: \(Q\implies P\)

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

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

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:

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

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

\[\begin{align} &\text{Assume P is true}\\ &\vdots\\ &\text{Therefore Q is true} \end{align}\]Usually use when there there is a disjunction in the proof.

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)}\]To prove \(\exists x, R(x)\), where \(R(x)\) is the statement. Just provide an example.

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.

Gives an explicit example that proves and existence proof.

Proves an example exists without actually providing it.

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

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}\]Definition: a **relation** \(R\), on a set \(A\) is a subset \(R\subset A\times A\).

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

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

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

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 apartitionof \(A\).

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]\)

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

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*

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

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

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\]

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

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

…

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

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

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

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

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

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

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

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

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\]