Logical operator \(\land\) (pronounced AND) that returns true iff all parameters are true
| \(p\) | \(q\) | \(p \land q\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Logical operator \(\lor\) (pronounced OR) that returns true iff at least one parameter is true
| \(p\) | \(q\) | \(p \lor q\) |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Unary logical operator \(\neg\) (pronounced NOT) that returns true iff the parameter is false
| \(p\) | \(\neg p\) |
| 1 | 0 |
| 0 | 1 |
Binary logical operator \(\implies\) (pronounced implies) that returns true iff parameter 1 being true guarantees the truth of parameter 2
| \(p\) | \(q\) | \(p \implies q\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Binary logical operator \(\implies\) (pronounced if and only if, often abbreviated to iff) that returns true iff parameter 1 being true guarantees the truth of parameter 2 and parameter 1 being false guarantees that parameter 2 is also false
| \(p\) | \(q\) | \(p \iff q\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Laws that determine relational properties of boolean algebra
Mathematical declaration that is either true for false
Linking several statements with logical symbols
Formation of logical connectives so that result is always positive
Set \(U\) representing the domain of variables that a statement considers
Predicate logical operator (pronounced for all) denoting the universe of discourse for some statement to hold.
\(\forall s \in S [P(s)]\)
For instance \(\forall x \in \mathbb{N} ( 5x \in \mathbb{N}) \) restricts the universe of discourse to the natural numbers, however swapping for \( \forall x \in \mathbb{R}\) would falsify this claim.
Predicate logical operator (pronounced there exists) denoting the existence of an element in the universe that satisfies the statement.
\(\exists s \in S [P(s)]\)
For instance \( \exists \varphi \in \mathbb{R} [ \varphi^2 - \varphi -1 =0]\) claims the existence of some element satisfying this polynomial in the set of real numbers, however swapping for \( \exists \varphi \in \mathbb{N}\) would falsify this claim.
To negate some statement involving quantifiers, one can deduce that if a statement claims to not hold for all (\(\forall\)) elements, then equivalently one can say that there exists (\(\exists\)) some counterexample, so:
\( \neg(\forall x[ P(x)]) \iff \exists x ( \neg[P(x)]) \)
For statements disclaiming there exists some element that satisfies it, one can equivalently say that it is unsatisfiable for all elements, therefore:
\( \neg(\exists x [ P(x) ] ) \iff \forall x ( \neg[ P(x) ] ) \)
A boolean formula is satisfiable if there are some settings for its variables that can output a \(1\) (or 'true').
a common Satisfiability test where each x, y, and r value can either have a ¬, or not have a ¬ (hah) like (x₁∨y₁∨r₁)∧ (x₂∨y₂∨r₂)∧(x₃∨y₃∨r₃)
\(P\) is a set that containing all 'languages' for which there exists a polynomial time Turing machine that can recognise it. For more detail, refer to Theory of Computer Science.
\(NP\) is a set that containing all 'languages' for which there exists a nondeterministic polynomial time Turing machine that can recognise it. Equivalently, it can be a set containing all 'languages' for which there exists a polynomial time Turing machine that can verify its configuration. For more detail, refer to Theory of Computer Science.
Proving a statement directly
\( p \implies q \)
Proving a statement by demonstrating how the absense of an equivalence implies the condition not being met
\( \neg q \implies \neg p \)
Proving a statement by assuming the inverse of the statement to demonstrate inconsistencies with previously affirmed statements and axioms
\( \neg q \implies 0 \)
Proof by contradiction by demonstrating that if some statement were true, it would have to be true for some smaller number.
Proof by demonstrating the ability to construct some counterexample or contradictory element. For instance, Cantor proved th
WLOG, assumption that can be safely made in a proof since even if the assumption was incorrect, a construction could be made to logically extend the general case to the assumption
For instance when talking about convergent sequences \( \lim_{n \to \infty} A_n = 0\), one can assume WLOG that the sequence converges to 0 \( \lim_{n \to \infty} A_n = 0\), since even if it didn't one could just consider the construction \(\lim_{n \to\ \infty} A_n - L = 0\) instead
\(a,b \in \mathbb{R} \implies\)
Real Analysis can employ concepts such as boundedness, compactness and the definition of a Riemann integral to prove bounds on certain integrals, this subject does not delve into this topic (it is not discrete), however it's pretty neat
\(f \text{ is monotone decreasing} \implies (a-b)f(b) \lt \int_{a}^{b} f(x)dx \lt (a-b)f(a) \)
\( S \subseteq \mathbb{R}, A_{S} \geq G_{S} \)
Or in more detail...
\(S \subseteq \mathbb{R}, s \in S, N=|S|,\frac{ \sum_{n=1} s_{n} }{N} \geq \sqrt[N]{ \prod_{n=1} s_{n} } \)
As an extension, both means are equal when all elements are the same number
\(\forall k \in S, k \in \mathbb{R} , A_{S} = G_{S} \iff (\exists r \in \mathbb{R} | \forall k \in S, k \in \mathbb{R}, k=r)\)
Unproven statement with unknown truth
Unproven Statement that is taken to be a logically irreducible truth
Proven statement used to provide sufficient basis for a theorem
Proven statement that is an independent result
Proven statement with significance
Proven statement that is a direct result of a theorem
\( S \subseteq \mathbb{N} \: \forall s \leq x \)
\(\forall y ( \exists x [ P(x,y)]) \)
\(\exists ! x [ P(x)] \iff [ P(x) \land P(y) \iff x=y]\)
Well defined collection of elements characterized by some axiomatic set theory (commonly ZFC)
Collection of axioms which define the properties of sets along with the controversial axiom of choice
\(\varphi\) is a predicate
Statement that sets with the same elements are equal
\( \forall x\forall y [ \forall z (z \in x \iff z \in y) \implies x=y ] \)
Statement that nonempty sets with the same elements are equal
\( \forall x\forall y [ \forall z (z \in x \iff z \in y) \implies x=y ] \)
\( \forall x [ \exists a (a \in x) \implies \exists y ( y \in x \land \nexists z (z \in y \land z \in x) ] \)
\( \forall x [ x \neq \emptyset \implies \exists y \in x ( y \cap x = \emptyset) ] \)
A set's symbol is often a capitalized letter, and its representation is a set of braces around the set elements, which are separated by commas.
\(S = \{6,2,0,4,9\}\)
\(M = \{\text{Mario}, \text{Luigi}, \text{Peach}\}\)
\(\mathbb{N} = \{ 0,1,2,3, \cdots \}\)
\( \{ x : P(x) \}\)
\( \{ x \in U : P(x) \}\)
\(3\mathbb{Z} = \{ n \in \mathbb{Z} : 3|n \}\)
Object in a set, can be variables and conditions
Set operation forming the set of elements containd within the scope of 'A' or 'B'
\( A \cup B = \{x : x \in A \lor x \in B \}\)
Set operation forming the set of elements contained in both 'A' and 'B'
\( A \cap B = \{x : x \in A \land x \in B \}\)
Binary set operator of removing all items of set 'B' from set 'A'
\( A \setminus B = \{x \in A : x \notin B \}\)
\( A \setminus B = A \cap \overline{B}\)
Unary set operator
A complement set of a subset includes all the elements in the superset and not in the subset; the other part of the set. For the following, let \(X\) be the set space:
\( A^{c},\bar{A} = X \setminus A \)
\( A \cup A^{c} = X\)
\( A \cap A^{c} = \emptyset \)
\( A\setminus B = A \cap B^{c}\)
Set such that all its elements are also contained in another set (called a superset). The notation \(A \subset B\) is used to
\( A \subseteq B \iff A \cap \bar{B} = \emptyset\)
Subset that is not equal to its superset
\( A \subset B \iff (A \subseteq B \land A \neq B)\)
Set with no elements (hence a cardinality of 0)
\( \emptyset \)
\( |\emptyset| = 0 \)
Two sets are disjoint is they have a null set as their intersection, no element is in both setsAlso called Mutual exclusivity
\(A,B \text{ are pairwise disjoint } \iff A \cap B = \emptyset \)
Given some set \(S\) a partition is a family of mutually exclusive sets that form \(S\) under union
\(P \text{ is a partition on }S \iff \)
\( A \text{ is closed under } \cdot \iff \forall a_1 , a_2 \in A , a_1 \cdot a_2 \in A \)
intersections and unions are commutative (like addition and multiplication, order doesn't matter)
Laws that determine relational properties of sets
\(S \text{ is countable } \iff \exists f : S \to \mathbb{N} ( f \text{ is bijective})\)
Number representing quantity of elements in a set
Number representing the order of an element
Logical symbol \(\in\) denoting the inclusion of some element in some set
For instance \(42 \in \mathbb{N}\) is true and \(\pi \in \mathbb{Q}\) is not.
Logical symbol \(\notin\) denoting the exclusion of some element in some set
A theoretical set \(\xi\) that contains all possible sets including itself. Its existence is impossible in ZFC as it fails Russel's paradox (see Theory of Computer Science for more detail).
Visual representation of set, not valid as proof
Cardinal number representing countable infinity
Denoted as \(\omega \), is an ordinal number used to represent the order of the number after all finite numbers (which if you count from a finite ordinal number, is unreachable). \(\omega \), \(\omega +1\), \(2\omega\), \(\omega^2\), \(\omega^\omega\), \(\varepsilon _{0}\) (which is a notation for \(\omega^{\omega^{\omega}}\))
\(\omega : \forall n \in \mathbb{N} \omega \gt n\)
Cardinal number representing the smallest uncountable infinity
\(\mathcal{P}(\mathbb{N}) \text{ is uncountable}\)
Cantor's diagonalization argument.
Consider a sequence of sets \(\mathcal{C}_{n}\). Set \(\mathcal{C}_{0} = [0,1]\), removing the 'middle third' of the set to form \(\mathcal{C}_{1} = [0,\frac{1}{3}] \cup [\frac{2}{3},1]\), then removing the middle thirds for the remaining two thirds to form \(\mathcal{C}_{2} = [0,\frac{1}{9}] \cup [\frac{2}{9},\frac{1}{3}] \cup [\frac{2}{3},\frac{7}{9}] \cup [\frac{8}{9},1]\), and this process is conducted ad infinitum. Then:
\(\mathcal{C} = \bigcap^{\infty}_{n=1} \mathcal{C}_{n} = \lim_{n \to \infty}\mathcal{C}_{n}\)
It represents numbers representable by \( \sum^{\infty} \sum_{k=1} \frac{a_k}{3^k} : a_{k} = \begin{cases} 0 \\ 2 \end{cases}\), hence by Cantor's diagonal argument this set is uncountable
All subsets of \( \mathbb{N} \) that aren't empty have a first element. Induction hinges off this fact to prove for some first element and then prove this form holds for all elements in this subset.
\( \forall S : S \subseteq \mathbb{N} \land S \neq \emptyset, \exists s \in S : s \text{ is the first element}\)
\( \forall n \in \mathbb{N} \geq c, P(n) \iff ( P(c) \land ( P(k) \implies P(k+1)) )\)
A variant of induction that sets up a larger range of statements to draw from in proving some argument.
\( \forall n \in \mathbb{N} \geq c, P(n) \iff ( P(c) \land ( \bigwedge_{i=1}^{k-c} P(c + i) \implies P(k+1)) )\)
An algorithm is correct iff it:
Mathematical statement involving variables that holds after every iteration of a loop
Mathematical statement that when satisfied after an iteration of a loop, ends said loop
\( \exists k,M\in \mathbb{R} : \forall n \geq k,|f(n)| \leq Mg(n) \iff f \in O(g)\)
Big-O is a way of categorising functions by which functions eventually 'dominate' them, for instance, \(x^2 \in O(e^x)\) since there comes a point in the function where \(e^x\) will always be larger than \(x^2\)
Two coupled numbers from two sets that are bound by a relation. The order of this pair is crucial as the ordered pairs are formed as such
\( (a,b) : a \in A, b \in B \)
The following example creates a basic set of ordered pairs based on the cartesian product of two sets A and B
\( A \times B = \{(a,b) : a \in A , b \in B\} \)
Set of ordered pairs \(R\)
\( xRy \iff (x,y) \in R\)
Note that \(R\) acts as both a set and a characteristic function in this definition
The symbol \(\sim\) is used for equivalence relations (defined below)
\(R \text{ is reflexive } \iff \forall x \in X, xRx\)
\(R \text{ is symmetric } \iff (\forall x,y \in X, xRy \implies yRx)\)
\(R \text{ is antisymmetric } \iff (\forall x,y \in X, xRy \land xRy \implies x=y)\)
\(R \text{ is transitive } \iff (\forall x,y,z \in X, xRy \land yRz \implies xRz)\)
Relation \(\sim\) with the properties generally associated with equality of mathematical objects
\(\sim \text{ is an equivalence relation } \iff \sim \text{ is reflexive, symmetric, and transitive}\)
Subset of \(X\) with all the elements \(x\) that satisfy \(a \sim x\)
\( [a] = \{ x \in X : a \sim x \}\)
Relation that is reflexive, antisymmetric and transitive
\(R \text{ is a partial order } \iff R \text{ is reflexive, antisymmetric, and transitive}\)
Set containing all possible subsets of some set (this includes the null set)
\( \mathcal{P}(S) = \{ s : s \subseteq S \}\)
\( |\mathcal{P}(S)| = 2^{|S|} = \sum^{|S|}_{n=0} \binom{|S|}{n} \)
Diagram of power sets, the first branch for |A|-1 (where A is the set, so |A|-1 is the size of A minus one)
Relationship \(f : X \to Y\) where each domain elements \(X\) has a single mapping
\(f \text{ is a function } \iff ( \forall x,y,z \in X, xfy \implies \nexists z \in \mathbb{R} \setminus y : xfz)\)
\(f(x)=y \iff xfy\)
Property such that there are no mappings of different domain and same range. This is also known as a one to one relationship
\( f \text{ is injective } \iff (\forall x,y \in X, f(x)=f(y) \implies x=y )\)
Property such that every range element has a mapping. This is also known as a onto relationship
\( f \text{ is surjective } \iff (\forall y \in Y,\exists x \in X : f(x)=y)\)
Property such that injection and surjection holds.
\( f \text{ is bijective } \iff f \text{ is surjective and injective}\)
A 20th century algorithm that serves as an example of recursion
\( A(m,n) = \begin{cases} n+1 & m = 0 \\ A(m-1,1) & n=0,m \gt 0 \\ A(m-1,A(m,n-1)) & m,n \gt 0 \end{cases}\)
'The key to combinatorics is the counting principles with bijections.'
Principle that multiplication enumerates events occuring in succession (all events occur in conjunction)
\(\prod^{n}_{k=1} |C_k|\)
Principle that addition enumerates events occuring distinctly (if one event occurs, the other events do not)
\(\sum^{n}_{k=1} |C_k|\)
Principle that division by \(d\) de-enumerates unimportant events if each desired event has \(d-1\) unimportant events
Principle that when assigning one of \(n\) 'states' (or mappings) to an object in some set \(S\), if \(|S| \gt n\) then at least two objects must share the same 'state'. For instance, in a room of \(8=7+1\) people, there must be at least two people that were born on the same day of the week.
\( f: A \to B \text{ is surjective } \land |A| \gt |B| \implies \exists a_1,a_2 \in A [ f(a_1)=f(a_2) ] \)
When counting the cardinality of union sets, the idea is to add the sizes of the set together and then minus the amount of elements that were 'double-counted'
\( | \bigcup_{k=1}^{n} S_k| = \sum_{\emptyset \neq J \subseteq \{1,...,n\} } (-1)^{|J|+1} | \bigcap_{j \in J} S_j| \)
For two sets, \(|A| + |B|\) will count the elements of \(A \cap B\) twice, therefore
\( | A \cup B| = |A| + |B| - |A \cap B| \)
For three sets, the intersects of any two set will be counted twice, and the intersection of all three sets will be counted thrice, but in deleting all doubly counted elements, we will accidentally delete the elements of \(A \cap B \cap C\) from the count, so we add it back
\( | A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\)
Enumeration of ordered \(k\)-tuples that can be formed by selecting elements from a set \(S\) of \(n\) elements.
Disallowing multiple selections of the same element \(s \in S\) produces the following formula
\( P(n,k)=\frac{n!}{(n-k)!} \)
Allowing unlimited selections of the same element \(s \in S\) produces the following formula
\( n^k \)
Enumeration of unordered sets of size \(k\) that can be formed by selecting elements from a set of \(n\) elements without repetition.
\( C(n,k)=\frac{P(n,k)}{P(k,k)}=\frac{n!}{k!(n-k)!}=\binom{n}{k} \)
This is bijective to the enumeration of arrangements of an ordered \(n\)-tuple, of which elements are partitioned into a class of \(k\) and \(n-k\) elements and permutations of elements of the same class are not counted.
\( C(n+k-1,k)=\binom{n+k-1}{k} \)
Notation for the \(k\)th coefficients of a binomial of degree \(n\)
\( \binom{n}{k} = \frac{n!}{k!(n-k)!}\)
\( \binom{n}{0} = \binom{n}{n} = 1 \)
\( \binom{n}{k} = \binom{n}{n-k} \)
\( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \)
\( \binom{2n}{n} = \sum^{n}_{k=0} \binom{n}{k}^{2} \)
\( \sum^{n}_{k=0} \binom{n}{k} = 2^{n}\)
\( \binom{r+s}{n} = \sum^{n}_{k=0} \binom{r}{k} \binom{s}{n-k} \)
Sequence of 0s and 1s
\( ( c_k )^{n}_{k=0} : \forall k (c_{i} \in \{0,1\})\)
Binary string of length 0, denoted as \(\lambda\) in mathematics and as \(\varepsilon\) in computer science
Binary string that either is or contains another binary string that fits form XX (so 1010 is 10*10, which are two identical binary strings next to eachother)
Triangle formed by the binomial coefficients \( \binom{n}{k}\) where \(n \geq 0\) is the row and \(0 \leq k \leq n\) is the column.
General form of the expansion of a binomial
\( (x+y)^{n} = \sum^{n}_{i=0} \binom{n}{i} x^{i}y^{n-i} \)
The formula; "think recursively". For instance, think of yourself at a crossroads with two initial paths. The amount of total paths until you've reached some end is \(P(p_0)=2+P(p_1)+ P(p_2)\)
Catalan numbers count the amount of objects that fufil "ordered-parity balancing" such as Dyck words, balanced bracket expressions with length \(2n\). One may see the relevance of Catalan numbers with issues relating to the stack.
\( C_n = \frac{1}{n+1} \binom{2n}{n}\)
\( C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}\)
The permutations of \(n\) ( symbols and \(n\) ) symbols is represented by \( \binom{2n}{n}\). Now one must remove all invalid permutations that do not have "ordered-parity balancing" (So rejecting strings like '())(()' and accepting strings like '()(())'). One may think of it as a string of brackets where each '(' adds one to some value and each ')' minuses one to that value, with the value starting at 0, so for instance \( (())() \implies 1+1-1-1+1-1=0\). The string is invalid if the value doesn't equal 0 (this is already handled in \( \binom{2n}{n}\)) or if at any term the expression ever goes below zero (which we must now find a way to count and eliminate from \( \binom{2n}{n}\)).
For all strings invalid by the latter condition, we notice that when reading the string from left to right there is some specific interval at the string \(k\) where the value goes sub-zero and therefore invalid (hence the symbol at \(k\) must also be a ')'), and within these first \(k\) terms one can find \(\frac{k-1}{2}\) '(' symbols and \(\frac{k-1}{2} +1 = \frac{k+1}{2}\) ')' symbols (because there is an extra ')' that ruins the parity in these first \(k\) symbols; notice how both of them added is \(k\) as it should be). Now, if one swaps the parity of the first \(k\) symbols, the entire string should add up to 2, and is in bijection with strings invalid by the second condition. In this converted string, one has \((\frac{k+1}{2}) + (n- \frac{k-1}{2}) = n+1\) '(' symbols and hence \(n-1\) ')' symbols, and since these strings are in bijection with the second-condition invalid strings we can count the second-condition invalid strings with \( \binom{2n}{n+1}\). Therefore \(C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1} \binom{2n}{n}\)
Countable set of natural numbers, the simplest set on which addition is defined completely
\( \mathbb{N} = \{0,1,2,3,4,5,...\} \)
\( \mathbb{N} = \{0 \} \cup \{ a : a-1 \in \mathbb{N} \} \)
\( |\mathbb{N}| = \aleph_{0}\)
Countable set of integers, superset of \(\mathbb{N}\) on which subtraction is defined completely
\( \mathbb{Z} = \{b-a : a,b \in \mathbb{N} \} \)
\( |\mathbb{Z}| = \aleph_{0}\)
Countable set of rational numbers, superset of \(\mathbb{Z}\) on which division is defined completely except for division by zero
\( \mathbb{Q} = \{\frac{b}{a} : a,b \in \mathbb{Z} \land a \neq 0\} \)
\( |\mathbb{Q}| = \aleph_{0}\)
Uncountable set of real numbers, superset of \(\mathbb{Q}\) representing all numbers that some rational sequence can approach
\( \mathbb{R} = \{ a : ( \exists a_n : \mathbb{N} \to \mathbb{Q} )( \lim_{n \to \infty} a_n = a)\}\)
\( |\mathbb{R}| = \aleph_{1}\)
Uncountable set of complex numbers, superset of \(\mathbb{R}\) extending the reals to the complex field by defining all operations with respect to the imaginary unit
\( \mathbb{C} = \{ a+bi : a,b \in \mathbb{R} \} \)
Set of algebraic numbers
\( a \in \mathbb{A} \iff (\exists P(x) \text{ with rational coefficients } : P(a)=0 ) \)
Relationship between integers such that \(b\) is some multiple of \(a\).
\( a|b \iff \exists k \in \mathbb{Z}: b=ka \)
Property of an integer such that it has no divisor other than itself and 1
\( p \text{ is prime } \iff \nexists q \in \mathbb{N} \setminus 1 : q|p \)
Relationship between integers such that they share no common factors other than 1. In this situation, the two integers are said to be relatively prime or coprime
\( p,q \text{ are coprime } \iff \gcd (p,q)=1\)
The lowest common multiple of some set \(S\) is the smallest possible number such that all \(s\in S\) divide this number
\(\text{lcm} (S) = \min \{k : \forall s \in S, s|k \} \)
The greatest common denominatorof some set \(S\) is the smallest possible number such that all \(s\in S\) divide this number
\(\gcd (S) = \max \{k : \forall s \in S, k|s \} \)
\(\gcd (a,b) \cdot \text{lcm} (a,b) = a \cdot b \)
Lemma that asserts the uniqueness and relationship of the quotient and remainder of two numbers.
\(\forall a,b \in \mathbb{Z} b\neq 0, \exists! q,r \in \mathbb{Z} : a =bq +r : 0 \leq r \lt |b|\)
Algorithm used to find \(\gcd (q,d) \) in running time \(O(\log(\min (q,d)))\).
It works by recursively finding a number that is divisible by both the divisor \(d\) and the remainder, since if the number goes into the divisor and the remainder, it also goes into the quotient
\(q,r \in \mathbb{N},0 \leq r \leq d, q=kd+r\)
\(\gcd (q,d) = \gcd (d,r)\)
The concept of finding the remainder of the division of two integers, say \(x,n\), or in other words, how numerically far \(x\) is from being a multiple of \(n\)
\(x \equiv y \mod n \iff \exists k \in \mathbb{Z} ( x=kn+y ) \)
This means that \(n|x-y\) and we can say that \(x\) is congruent to \(y\) for modulo \(n\)
An alternative shortened notation for modular arithmetic is \(x \equiv y \mod n \iff [x]_n=y\)
Arithmetic with modular reduction is symmetric, symmetric, and transitive, as well as fufilling the following:
\( \gcd (a,n)=1 \implies \exists a^{-1} : a^{-1}a \equiv 1 \mod n \)
Integer such that when multiplied with another number \(a\) with modulo of some number \(n\), returns 1. It can be determined through reverse euclidean algorithm
\(f(x) = (ax+b) \mod 26\)
Linear cipher function that employs modular arithmetic to map each of the 26 letters with another letter. The function is best when a and b are chosen to make a bijective set for values of x from 1 to 26 (this is done by choosing \(a\) coprime to 26 and choosing ).
The rightmost digit of a number \(n\) can be though of as \( n \mod 10\) in the decimal system. This sheds light to a few tricks that can be used to enumerate the final digit of \(n\), for instance:
Denoted as \( \text{dr}(n) \), all digits added together until a single digit number reached, \(365 \to 3+6+5=14 \to 1+4=5\). Note that adding some digit 9 does not change the digital root since digital roots can be thought of as putting the number \(\mod 9\) since \(\forall k \in \mathbb{N}, 10^k \mod 9 = 1\) and when paired with BRT, proves digital roots show whether a number can be divided by 9
\(3|n \iff 3|\text{dr}(n)\)
\(9|n \iff 9|\text{dr}(n)\)
Method of representing an exponentiated number into products such that the powers are powers of two. This allows for each product term to be recursively resolved.
\([m^e]_n\)
Number with the property that its square root is an integer
\(k^2 = \sum_{n=1}^{k} 2n-1\)
Set of all integers from 0 to n-1; these elements are closed under \(\mod n\) addition
\(\mathbb{Z} \setminus n \mathbb{Z} = \mathbb{Z} \cap [0,n-1]\)
Set of all integers from 1 to n-1 that are coprime to n; these elements are closed under \(\mod n\) multiplication
\( (\mathbb{Z} \setminus n \mathbb{Z})^{\times} = \{ k \in \mathbb{Z}\cap [1,n] : \gcd (n,k)=1 \} \)
Function \(\varphi : \mathbb{Z} \to \mathbb{Z}\) that returns the cardinality of \( (\mathbb{Z} \setminus n \mathbb{Z})^{\times} \)
\( \varphi (n) = |(\mathbb{Z} \setminus n \mathbb{Z})^{\times}| \)
\( \varphi (n) = n\prod_{p|n} (1- \frac{1}{p}) \)
For the third lemma, this is proved by establishing a bijection between \( \mathbb{Z}_{nk}^{*}\) and \( \mathbb{Z}_{n}^{*} \times \mathbb{Z}_{k}^{*} \). This can be done by showing surjection and injection by the function \(f(X)=(X \mod n , X \mod k) \). To do this, modular arithmetic can be used to show surjection and Chinese remainder theorem to show injection.
The fourth lemma is a result of partitioning the set \(S = \{1,2,3,...,n\}\) into an array of sets that have some common divisor, so \(S_{d_i} = \{ s \in S : \gcd (s,n)= d_{i}\}\). Note that the sum of the cardinalities of these sets equals \(n\) since a number cannot have two GCDs with \(n\); the GCD partitions \(S\) into disjoint sets without repetition. The sets \(S_{d_i}\) can each have all elements divided by \(d_i\) since all elements are divisible by \(d_i\), now doing this turns each \(S_{d_i} \to \mathbb{Z}^{*}_{d_i}\), meaning that the cardinalities of each of these sets is represented as \( \varphi (d_i)\). Recall that these sets are just partitions of the original set containing all numbers up to \(n\), so we have proved this fourth lemma.
Showing that \(f : \mathbb{Z}_{nm}^{*} \to \mathbb{Z}_{m}^{*} \times \mathbb{Z}_{n}^{*} \) is bijective when \(\gcd (m,n) = 1 \) proves this statement, since bijectivity implies equal cardinalities. \( \gcd(x,nm) =1 \iff \gcd(x,m) =1 \land \gcd(x,n)=1 \iff \gcd([x]_m,m) =1 \land \gcd([x]_n,n)=1\) by Euclid's corrolary and Euclidean algorithm, so both the domain and codomain have the same cardinalitiy
\( \gcd (a,n)=1 \implies a^{\varphi (n)} \equiv 1 \mod n \)
Since \(\gcd (a,n) = 1\), it is true that \(\mathbb{Z}_{n}^{*} = a\mathbb{Z}_{n}^{*}\) (since multiplying each element by a coprime number and taking modulo n simply permutes the set). Remember that \( \phi (n) = |\mathbb{Z}_{n}^{*}|\) so therefore \( \prod^{\varphi (n)}_{i=1} x_i \equiv \prod^{\varphi (n)}_{i=1} ax_i \equiv a^{\varphi (n)}\prod^{\varphi (n)}_{i=1} x_i \mod n\). Multiplying both sides by \((\prod^{\varphi (n)}_{i=1} x_i)^{-1}\) leaves us with Euler's theorem.
Since \(\gcd (a,n) = 1\), let \(G = \mathbb{Z}_{n}^{*}\), and let \(H\) be a subgroup of \(G\). Any \(a \in G\) can be utilized to form \(H\) and since \( \varphi (n) = |G| \) and \( \exists k \in \mathbb{Z} : k = \frac{|G|}{|H|}\), then \(k|H| = \varphi (n) \). Now, \(a^{\varphi (n)} \equiv a^{k |H|} \equiv a^{|H|} \equiv 1 \mod n\).
Weaker variant and corrolary of Euler's theorem
\(p \text{ is prime } \implies a^{p-1} \equiv 1 \mod p\)
Consider all the possible strings with length \(p\) and combination with a set of \(a\) symbols (there are \(a^p\) of these)
Now consider all the unique \(a\)-ary necklaces of length \(p\), each necklace can be rotated \(p\) times to obtain unique strings with the exception of necklaces with one symbol (\(a\) of such necklaces exist).
\(a\) of these strings have one single orientation, therefore there are \(a^p-a\) combinations belonging to a necklace with \(p\) orientations. If there were \(k\) such necklaces and \(p\) orientations for each, then \(a^p -a = kp \implies a^p -a | p \implies a^{p-1} \equiv 1 \mod p\)
\(a^{\varphi(p)} \equiv 1 \mod p \implies a^{p-1} \equiv 1 \mod p\)
Note the follwing lemma:
\(1^p \equiv 1 \mod p\) (Base case, trivial)
\(k^p \equiv k \mod p\) (General assumption)
\((k+1)^p \equiv k^p + 1 \equiv k+1 \mod p\) (inductive proof, application of freshman's dream)
Consider the group \( ( \mathbb{Z}\setminus p \mathbb{Z} )^{\times} \) which has order \(p-1\).
Now consider its cyclic subgroup \( H \cong \mathbb{Z} \setminus k \mathbb{Z}\) generated by \( a \), hence\(a^k \equiv 1 \mod n\)
By Lagrange's theorem, \( k|p-1 \) Hence \( a^{p-1} \equiv a^{km} \equiv (a^{k})^{m} =1^{m} \equiv 1 \mod p\)
The smallest \( x : a^x \equiv 1 \mod n\) is called the order of a mod n, or \( \text{ord}_n (a) \)
Encryption scheme using a single key to handleencryption and decryption
Encryption scheme using separate keys for handling encryption (public key) and decryption (private key)
Asymmetric encryption scheme based on Euler's theorem to exploit the high time complexity of prime factorization.
\( m^{ed} \equiv m \mod n \) where:
Theorem that any system of modular equations with coprime moduli has a unique answer modulo \(N\) (the theorem doesn't include how to calculate this answer)
\( \exists! x \in \mathbb{Z}_N : \begin{cases} x \equiv a_1 \mod n_1 \\ x \equiv a_2 \mod n_2 \\ \vdots \\ x \equiv a_k \mod n_k \end{cases} \)
Assume distinct \(x,y\) satisfy the modular system, then \(n_i | x-y\). Since each modulo is coprime to one another, \(N | x-y\). This implies \(x-y \equiv 0 \mod N \implies x \equiv y \mod N\), so \(y\) is merely a translation by \(N\) of the unique answer \(y\). Therefore the answer is unique (injective) modulo \(N\)
Since the amount of combinations of different sets of \(\{a_1,a_2,...,a_k\}\) is \(N\) (the same as the possible values of \(x\)), the injectivity implies bijectivity (\(N\) possible values of \(x\), which are unique for any \(N\) choice of \(\{a_1,a_2,...,a_k\}\))
\(x = \sum^{k}_{i=1} a_i A_i\)
Element that may have relations to other vertexes through edges
Visually, vertexes are represented as dots
\(v\)
Subset of 2 vertexes denoting a symmetric relation between two vertexes
Visually, edges are represented as lines between the vertexes
\(e=\{ v_i, v_j \}\)
Ordered pair \(e= ( v_i, v_j ) \) of 2 vertexes denoting an ordered relation between \(v_i\) (source) to \(v_j\) (terminal)
Visually, edges are represented as arrows pointing from the source to terminal
\(e= ( v_i, v_j ) \)
Edge \(\{v_i, v_i\}\) such that the source vertex is also the terminal
A graph \(G\) is an ordered pair \( (V,E) \) where:
Graphs are formally defined through set theory, but can be visualised with circles for vertexes and lines connecting vertexes as edges. A matrix can also represent a graph and its edges.
Graph that employs directed edges
Graph that may contain the same edge multiple times
Graph that is not a multigraph and has no loops
Sequence of edges such that the terminal of the current edge is the source of the subsequent edge
Walk such that no edge is repeated
Trail such that no vertex is repeated
Amount of edges in path
Graph where e is associared as {x,v1} then {v1,v2} until {vn,x}
\(G \text{ is connected } \iff \)
Path where vn is never connected back to again once connected to
Vertex of an edge
\( e \text{ is incident to } v \iff \exists v \in e\)
In a directed graph, \(v_1\) and \(v_2\) are adjacent iff there exists some edge relating them, so
\( v_1 \text{ and } v_2 \text{ are adjacent} \iff \exists e \in E : e = \{v_1 , v_2\} \)
\( v_1 \text{ is in-adjacent to } v_2 \iff \exists e \in E : e = (v_1 , v_2) \)
\( v_1 \text{ is out-adjacent to } v_2 \iff \exists e \in E : e = (v_2 , v_1) \)
A degree of a vertex is the amount of edges that it interacts with (an edge usually adds 1 for the edges exit, but on a loop it adds 2, since you cound for the exit and entry)
\( \deg (v) = \sum_{e\in E} p(e) \)
\(v \neq u,w\)
\(p(e_{vv}) = 2\)
\(p(e_{vw}) = 1\)
\(p(e_{uw}) = 0\)
A matrix \(A\) with dimensions \(|V| \times |V|\) such that:
\( A_{ij} = \begin{cases} 0 & \{i,j\} \notin E \\ 1 & \{i,j\} \in E \end{cases}\)
Undirected graphs have symmetric matrixes
\( A_{ij} = \begin{cases} 0 & (i,j) \notin E \\ 1 & (i,j) \in E \end{cases}\)
Simple graphs where every node is connected to every other node
Graph with \(m+n\) vertexes where no m vertex connects to another m vertex and no n vertex connects to another n vertex
A path within a path (can be an empty path)
- Euler path (each edge traversed exactly once) - Hamiltonian path (each vertex reached exactly once)Connected graph with no circuits, such as binary tree structures
\(G \text{ is a tree } \iff |E|=|V|-1 \land G \text{ is connected}\)
Node of degree 1 on a tree
Collection of trees
\begin{lemma}[Kőnig's lemma] Let $G$ be a connected locally finite infinite graph, then $G$ contains an infinite simple path (ray) \end{lemma} - Euler circuit (each edge traversed exactly once) - Hamiltonian circuit (each vertex except for first vertex reached exactly once)Tree over another graph that connects to all vertexes using the pre-existing edges
Tree with a special node called a root
If two vertexes \(v,u\) share an edge, and a path from v to r (r for root) passes u, then r is a root. v is then called a parent and u a child
Distance of some vertex \(v\) from the root node
Mathematical expressions can be written without brackets by being represented in a rooted tree, where nodes are operators and numbers. Then it can be rewritten as an expression in various methods...
Parent, left, right
Left, right, parent
Left, parent, right
Graph that has no edge cross another edge
Region bound by edges