Final Review

• Chapter 1
  • Set
  • Power Set
  • Set Operations
    • Union
    • Intersection
    • Difference
    • Compliment
  • Direct Product
  • Indexed Sets Operations
    • Union
    • Intersection
• Chapter 2
  • Statement
  • Logical Operations
    • Conjunction
    • Disjunction
    • Negation
  • Open Sentence
  • Logical Equivalences
    • DeMorgan
    • Distributive
  • Implications
  • Biconditional Implications
  • Quantifier
    • Negation
• Chapter 4-10
  • Direct Proof
  • Proof By Cases
  • Proof By Contrapositive
  • Proof By Contradiction
  • Existence Proof
    • Uniqueness Proof
    • Constructive Proof
    • Non-Constructive Proof
  • Mathematical Induction
    • Proof By Induction
    • Strong Mathematical Induction
    • Proof By Smallest Counterexample
• Chapter 11
  • Relation
    • Relation Properties
  • Equivalence Relation
  • Equivalence Class
    • Partition
  • Integer Modulo n
• Chapter 12
  • Function
  • Injective
  • Surjective
  • Bijective
  • Pigeonhole Principle
  • Composition
  • Inverse Function
    • Identity Function
  • Image & Preimage
• Chapter 13
• Useful Definitions and Facts
  • Parity & Multiplicity
  • Well-Ordering Principle
  • Division Algorithm
  • Fundamental Theorem of Arithmetic
  • Greatest Common Divisor & Least Common Multiple
    • Proposition 7.1
    • Proposition 10.1
  • Congruence
  • Pigeonhole Principle
  • Image & Preimage

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

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:

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

Chapter 13

…

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

Pigeonhole Principle

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