Updated 2017-12-17
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:
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:
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:
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\).
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\).
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\).
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]\}\).
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:
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
For a bijective \(f:A\rightarrow B\), its inverse is the function \(f^{-1}:B\rightarrow A\).
Composition with inverse yields identity function:
Theorem 12.3: Function \(f\) is bijective iff the reverse relation \(f^{-1}\) is a function \(B\rightarrow A\)
Suppose \(f:A\rightarrow B\):
…
Given \(k,n\in (\mathbb Z-\{0\})\),
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\).
Assuming \(a\equiv b\mod n\) and \(c\equiv d\mod n\) for \(a,b,c,d\in \mathbb Z\), then:
see above
Theorem 12.4: Suppose \(f: A\rightarrow B\) and \(W,X\subset A, Y,Z\subset B\)