Theorems taught in class

1Logic¶

Double negation

$\lnot(\lnot p) \leftrightarrow p$

Idempotent rules

$p\wedge p \leftrightarrow p$

$p\lor p \leftrightarrow p$

Absorption rules

$p \wedge ( p \lor q ) \leftrightarrow p$

$p \lor ( p \wedge q ) \leftrightarrow p$

Commutative rules

$p \wedge q \leftrightarrow q \wedge p$

$p \lor q \leftrightarrow q \lor p$

Associative rules

$p \wedge ( q \wedge r) \leftrightarrow ( p \wedge q ) \wedge r$

$p \lor ( q \lor r ) \leftrightarrow ( p \lor q ) \lor r$

Distributive rules

$p \wedge ( q \lor r ) \leftrightarrow ( p \wedge q ) \lor ( p \wedge r )$

$p \lor ( q \wedge r ) \leftrightarrow (p \lor q ) \wedge ( p \lor r )$

Demorgan's rule

$\lnot ((\lnot p)\lor(\lnot q )) \leftrightarrow p \wedge q$

$\lnot ((\lnot p)\wedge(\lnot q )) \leftrightarrow p \lor q$

Implication

$p \to q \leftrightarrow \lnot p \lor q$

$p \to q \leftrightarrow \lnot q \to \lnot p$

Tautology and Contradictions

trivial

Proofs

$(p \to q)\wedge(q \to r) \to p \to r$

$: \lnot (\exists n : statement) \leftrightarrow \forall n: \lnot (statement) $

$ \lnot (\forall n : statement) \leftrightarrow \exists n: \lnot (statement) $

2Social Choice Functions¶

Arrow's impossibility theorem

Unanimity: If every voter prefers candidate a to candidate b, then $f$ should rank a above b.

Independence of Irrelevant Alternatives: To decide how $f$ ranks candidates a and b, only their relative rankings should matter.

The only social choice function satisfying the above two social choice function properties is dictatorship

3Proofs¶

The well-ordering principle

Every non-empty subset of non-negative integers has a smallest element

Theorem

Every positive integer bigger than 1 can be expressed as a product of primes

Theorem

$1+3+5...+(2n-1) = n^2$

The induction principle

If P(1) is true

If P(n-1) implies P(n)

Then P(n) is true for all n $\in$ N

Theorem

$1+2+...+n = n(n+1) / 2$

Theorem

$2^n \ge n^2 $

Theorem

All horses are the same colour. This is false. Horses exist in more than one colour

4Number Theory¶

Fundamental Theorem of arithmetic

Every integer > 1 has a unique prime factorization

Theorem

If a prime p divides ab, then p|a or p|b

Theorem

For any positive integer k there exist two consecutive prime numbers with difference $\ge$ k

The prime number theorem

Average gap between primes are ~ ln n

5Greatest common divisors and linear combinations¶

Theorem

The GCD of a & b is the smallest positive linear combination

Theorem

An integer C is a linear combination of a and b if $gcd(a,b) | c$

Theorem

$gcd(a,b)$ is the smallest positive linear combination of a & b

Theorem

$gcd(a,b)$ is divisible by every common divisor of a & b

$gcd(ka,kb) = k*gcd(a,b)$ for any positive integer k

$gcd(a,b) = 1$, $gcd(a,c) = 1$, $gcd(a,bc) = 1$

$gcd(a,b) = 1$, $a|bc$, then $a|c$

$a = qb+r$, then $gcd(a,b) = gcd(b,r)$

6Modular Arithmetic¶

Properties of congruences

Reflexivity: $a \equiv a (mod m)$

Symmetry: $a \equiv b (mod m)$ iff $b \equiv a (mod m)$

Transitivity: $a \equiv b (mod m)$ and $b \equiv c (mod m) \to a \equiv c(mod m)$

Theorem

If P is a prime, K is not divisible by p, then there exists a multiplicative inverse for k modulo p

Fermat's Little Theorem

Let p be a prime, K is not divisible by p, then $\displaystyle k^{(p-1)} \equiv 1 (mod p)$

$\displaystyle k^{p-2}$ is a multiplicative inverse for k mod p

Primality

If $2^{n-1} \ncong 1 mod n$, then n is not prime or n = 2

7Combinatorics¶

Bijection Rule

If there exists a bijection $F: x\to y$ for two finite sets x and y, then |x| = |y|

Division rule

If $F:x \to y$ is k to one then |x| = k|y|

The Choose function

$\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}$

Binomial theorem

$\displaystyle (x+y)^n = \sum_{k=0}^{n} {n \choose k}x^k y^{n-k}$

Theorem

$\displaystyle {n \choose k} = {n \choose n-k}$

For n sets

$|A_1\cup A_2 \cup A_3 ... \cup A_n|$

= sum of all sizes - sum of the sizes of all even numbered intersections + sum of the sizes of all odd numbered intersections

Euler's totient function

Let n be a positive integer and let $p_1,p_2,p_3 ... p_k$ be all distinct prime divisors of n

then $\phi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$

Multinomial

$\displaystyle \frac{n!}{n_1!n_2!n_3!...n_k!} = {n! \choose n_1!,n_2!,n_3!...n_k!}$

Multinomial Theorem

$\displaystyle (x_1+x_2+x_3...+x_k)^n = \sum_{n_1+n_2..n_k, n_i\ge 0} {n \choose n_1,n_2,n_3...}x_1^{n_1}x_2^{n_2}x_3^{n_3}$

8Graphs¶

Theorem

In every graph there is an even # of vertices of odd degree

Theorem

In a simple graph G(V,E) there are always u,v $\in$ V, u!=v, deg(u) = deg(v) (|v|$\ge$2)

Theorem

A connected graph contains an Eulerian circuit if and only if every vertex in it has an even degree

Theorem

A connected graph contains an Eulerian walk if and only if it has at most two vertices of odd degree

Theorem

A Hamiltonian cycle is a cycle in a graph which uses all the vertices, to determine whether it is Hamiltonian is NP-complete

Theorem

The Petersen graph has no three-edge colouring

9Trees¶

Theorem

There is a unique path between any two vertices in a tree

Theorem

Removing any vertex in a tree disconnects it

Theorem

Adding an edge between non-adjacent vertices of a tree creates a cycle

Theorem

If a tree has $\ge$ vertices then it has $\ge$ leaves

Theorem

# of edges = # of vertices - 1 in a tree

Cayley's Theorem

There are $n^{n-2}$ labeled trees on n vertices

Number of unlabeled trees on n vertices

$\displaystyle \frac{n^{n-2}}{n!} \le T_n \le 4^{n-1}$

10Planar Graphs¶

Theorem

A planar graph always has a drawing where all the edges are represented by straight lines

Euler's formula

Let g be a connected graph drawn in the plane with n vertices, m edges and f faces, then the number of faces = m - n + 2

Theorem

A planar graph on n vertices has edges m $\le$3n-6 for all n $\ge$ 3

Theorem

$K_5$ is not planar

Theorem

$K_{3,3}$ is not planar

Theorem

In a bipartite graph every cycle has an even length $ \ge$ 3

Theorem

A graph is not planar if and only if it contains a subdivision of $k_5$ or $k_{3,3}$ as a subgraph

Theorem

A graph is 2-colourable if and only if it is bipartite

Theorem

$k_{k+1}$ as a subgraph, there exist non-k-colourable for any k with no triangles in them(wtf?)

Theorem

If a graph has maximum degree k then it is k+1 colourable

Theorem

Every map is 4 colourable

Theorem

Every cubic planar graph with no bridges can be 3-edge coloured