1870 im quite apprehensive

Set

A collection of objects called elements.

Domain

The set of all possible input values for a function or relation.

Codomain

The set of all possible output values of a function.

Image/Range

The set of all ACTUAL output values of a function.

{b ∈ B | a ∈ A such that f(a) = b}

Function

A function from sets A to B is a subset of ordered pairs obtained from the Cartesian Product A x B, where ∀a ∈ A, there exists a single ordered pair with a as the first element.

Function Composition Requirement

For the composition of functions g⋅f to be valid, the image of f must be a subset of the domain of g.

In other words, the actual output values of f must be valid inputs for g

Function Composition Uncommutativity

In general, g⋅f does not equal f⋅g.

Function Composition Associativity

In general, for functions f, g, and h, (f⋅g)⋅h = f⋅(g⋅h).

What is the empty set?

The empty set is a set that contains no elements. It is denoted by $\emptyset$ or ${}${}.

What is set-builder notation?

Set-builder notation is a way to define a set by specifying a property that its elements must satisfy. For example, {{x | x > 0}} resents the set of all x such that x is greater than 0.

Express even numbers using set-builder notation.

$${x | x = 2n, n \in \mathbb{Z}}$$

Define the union of two sets.

The union of two sets A and B, denoted $A \cup B$, is the set containing all elements that are in A, or in B, or in both.

In set-builder notation, A∪B= {x ∣ x ∈ A ∨ x ∈ B}

Define the intersection of two sets.

The intersection of two sets A and B, denoted $A \cap B$ , is the set containing all elements that are common to both A and B.

In set-builder notation, A$\cap$B = {x | x ∈ A ∧ x ∈ B}

Define the relative complement of set B in set A.

The relative complement of B in A, denoted $A - B$ or $A \setminus B$, is the set of elements in A but not in B. In other words ‘A without B’

Define the symmetric difference of sets A and B.

The symmetric difference of A and B, denoted $A \triangle B$ , is the set of elements which are in either A or B but not in their intersection. $A \triangle B = (A - B) \cup (B - A)$

What are Venn diagrams used for?

Venn diagrams are used to visually represent sets and their relationships, such as unions, intersections, and complements. They consist of overlapping circles within a rectangle representing the universal set.

What is an ordered pair?

An ordered pair is a pair of elements $(a, b)$ where the order matters. $(a, b)$ is different from $(b, a)$ unless $a = b$.

Define the Cartesian product of two sets A and B.

The Cartesian product of A and B, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. $A \times B = {(a, b) | a \in A, b \in B}$

Define the identity function.

The identity function is a function that maps every element to itself.

It's often denoted as $I(x) = x$.

Define the inverse of a function.

The inverse of a function $f(x)$, denoted as $f^{-1}(x)$, is a function that, when composed with $f(x)$, yields the identity function: $f(f^{-1}(x)) = f^{-1}(f(x)) = x$.

Relation.

A set of ordered pairs. It describes a relationship between two sets of information. If $A$ and $B$ are sets, then a relation from $A$ to $B$ is a subset of $A \times B$.

Injective Function

Image is loyal.

A one-to-one function, where each element of the range is associated with at most one element of the domain.

Formally, $f: A \rightarrow B$ is injective if for all $x, y \in A$, if $f(x) = f(y)$, then $x = y$.

Surjective (onto) function

Image is cozy.

A surjective function, also known as an onto function, is a function where every element of the range is the image of at least one element from the domain. Formally, $f: A \rightarrow B$ is surjective if for all $b \in B$, there exists an $a \in A$ such that $f(a) = b$.

Bijective function.

Injective and Surjective, perfectly one-to-one

Criteria for function inverse

Passes horizontal line test (injective)

Bijection

Reflexive (Relation)

All relation vertices have loops.

For every element a ∈ A, (a, a) ∈ R.

Symmetric (Relation)

Every relation arrow is 2-way.

For every (a, b) ∈ R, (b, a) ∈ R.

Anti-symmetric (Relation)

No 2-way relation arrows except loops.

For every (a, b) and (b, a) ∈ R, a = b.

Transitive (Relation)

Pass-through arrows. In Hasse Diagrams, these extra arrows aren’t drawn.

(a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R.

Equivalence Relation

A relation that is reflexive, symmetric and transitive.

Partial Order

A relation that is reflexive, anti-symmetric and transitive.

Implication Operator

A => B, or ‘A implies B’. Equivalent to not A ∨ B.

Equivalence

A <=> B. A and B are the same.

Predicate

A statement that contains variables and whose truth depends on the values of these variables.

For example, $P(x)$ represents 'x is greater than 5'.

Quantifiers

Symbols used to express how many elements of a set satisfy a given predicate. The two main are universal and existential.

Universal quantifier

Denoted by $\forall$, asserts that a predicate is true for all elements in a domain.

For example, $\forall x P(x)$ means 'for all x, P(x) is true'.

Existential quantifier

Denoted by $\exists$, asserts that there exists at least one element in a domain for which a predicate is true.

For example, $\exists x P(x)$ means 'there exists an x such that P(x) is true'.

Negating a universally quantified statement

Change the universal quantifier to an existential quantifier and negate the predicate.

For example, the negation of $\forall x P(x)$ is $\exists x \neg P(x)$.

This translates to 'There exists an x such that P(x) is not true'.

Negating an existentially quantified statement?

Change the existential quantifier to a universal quantifier and negate the predicate.

For example, the negation of $\exists x P(x)$ is $\forall x \neg P(x)$ .

This translates to 'For all x, P(x) is not true'.

Logical argument

Formed from a collection of statements called premises, and a final one called the conclusion.

Valid Argument

If the conclusion is true whenever all the premises are true. Its arguments and conclusion must form a tautology.

Validity depends on the form of the argument, not the truth of the premises.

Consistent Proof System

Impossible to derive a contradiction from the premises, e.g. A => B∧¬B.

Complete Proof System

Any valid argument can be proven.

In other words, if an argument is valid, a proof can be constructed to show that the conclusion logically follows from the premises.

Tautology

A statement that is always true, regardless of the truth values of its components. In propositional logic, it is an expression that is true in every possible interpretation.

Contrapositive Proof

X => Y <=> ¬Y => ¬X

Countably Infinite

A set that can form a bijection with the set of natural numbers, Z⁺.

|Set| = |Z⁺|

Uncountably Infinite

A set that can form a bijection with the set of realnumbers, R.

|Set| = |R|

Natural Numbers

$$\mathbb{N} = {0, 1, 2, 3, … }$$

Set of Integers

Including negative numbers, zero, and positive numbers, denoted as $\mathbb{Z} = {…, -2, -1, 0, 1, 2, …}$

Rational Numbers

All numbers which can be expressed as a fraction $p/q$ where p and q are integers and q is not zero.

Denoted as $\mathbb{Q} = {p/q \mid p, q \in \mathbb{Z}, q \neq 0}$

Real Numbers

The set of all real numbers, which includes both rational and irrational numbers. Denoted as $\mathbb{R}$.

Addition principle (cardinalities)

If A and B are disjoint (mutually exclusive) sets, the cardinality of their union is the sum of their individual cardinalities: $|A \cup B| = |A| + |B|$. This extends to any finite number of disjoint sets.

Multiplication principle (cardinalities)

If constructing elements by making a sequence of independent choices, the total number of possible constructions is the product of the number of choices for each step.

If set A has cardinality m and set B has cardinality n, then the cardinality of $A \times B$ is $m \times n$.

Binomial Theorem

For any positive integer n: $(a + b)^n = \sum_{k=0}^{n} {n \choose k} a^{n-k} b^k$, where ${n \choose k} = \frac{n!}{k!(n-k)!}$ represents the binomial coefficient.

Pigeonhole Principle

When mapping n elements from A to k elements in B, there is an element in B such that $\lceil \frac{n}{k} \rceil$ elements from A are mapped to it.

Definition of Divisibility

An integer a is divisible by an integer b =/= 0 if there exists an integer k such that $a = bk$.

If p is an integer:

• p|p

• 1|p

• p|0

• If p|a, p|ab

• If p|a and p|b, p|(a + b

Quotients and Remainders

$a = bq + r$, where 0 \le r < |b||

q is the quotient,

r is the remainder

Definition of Modular Arithmetic

Definition: Modular arithmetic is a system of arithmetic for integers where numbers 'wrap around' upon reaching a certain value (the modulus).

Given integers a, b, and n, we say $a \equiv b \pmod{n}$ if and only if n divides $(a - b)$, This means that $a$ and $b$ have the same remainder when divided by $n$.

When this happens, we say that a is congruent to b modulo n.

Method of Repeated Squaring

Write exponent bottom to top as running product

Square the mantissa number and mod the result continuously until you reach the last

Multiply the results together only for rows where exponent is 1, doing the modulus each time.

Definition of Greatest Common Divisors

The largest positive integer that divides 2 integers.

The Euclidean Algorithm

gcd(a, b) = gcd(b, r) where r is the remainder.

Continue this process until the remainder is 0.

The last non-zero remainder is the GCD.

The Extended Euclidean Algorithm

If gcd(a, b) = 1, after finding gcd(a, b), reverse back up the chain to get to 1 = ax + by, where x and y are integers such that ax + by = gcd(a, b).

Log base change rule

$$log_{a}(m) = log_{b}(m) * log_{a}(b)$$

Multigraph

A triple (tuple) with a Vertex Set, Edge Set and function Phi mapping edges to vertices (not distinct)

Graph

A multigraph but without multiple edges or loops - edges can be defined uniquely by their endpoints. It has a vertex set and an edge set of 2-element subsets of V.

Digraph

A pair (V, A) of sets where V is the vertex set and A is the arc set, or edge set, made of ordered pairs of vertices from V.

Degree of a vertex

The number of edges incident to the vertex.Or, the number of subsets from E which include the vertex in their elements. If there are loops, each loop counts twice.

Euler’s Handshaking Lemma

The sum of degrees in a graph equals double the number of edges.

Isomorphism

A bijection, f, mapping V(G1) → V(G2), such that edges from G1 are equivalent to edges from G2, i.e. {u, v} ∈ G1 <=> {f(u), f(v)} ∈ G2.

Informally, a mapping between two graphs that preserves their structure, meaning there is a one-to-one correspondence between their vertices and edges, regardless of orientation,

Subgraph

A graph where the vertex set and edge set are subsets of the original.

Spanning Subgraph

A subgraph containing all the vertices of the original.

i.e., V(G’) == V(G)

Proper Subgraph

A subgraph that does not contain all the vertices or edges of the original graph, meaning it has at least one vertex or edge (or both) removed.

i.e., G’ =/= G

Induced Subgraph

A subgraph containing all the edges from G wherever it contains the vertices of the original graph G.

i.e. If G’ contains all the edges x,y ∈ E(G) wherever x, y ∈ V(G), it’s an induced subgraph.

Walk

The most basic: A sequence of alternating k+1 vertices and k edges. We only need to write the vertices.

Every walk from u to v contains a path from u to v.

(Path contains no repeat vertices)

Proof: r=repeated vertex
Go from u to r-1, then skip to last appearance of r, then go from r to v. Repeat for every repeat vertex.

Minimum Degree

Degree of the vertex with the lowest degree in the graph.

Connectivity

A graph is connected if there is a path between any 2 vertices.

i.e., for any vertices, u, v ∈ V(G) there’s a path from u to v.

Connected Component

The ‘parts’ of a graph that are connected but not connected to other parts.

Formally:

An inclusion maximal connected (induced) subgraph of G. This means that, for any subgraph C’ in G, where your connected component C is a proper subgraph of C’, C’ is not connected. (Meaning from your component C, adding stuff to reach C’ will make it not connected anymore, therefore nothing else can be added).

Eulerian Trail

A trail (no repeating edges) in a graph that visits every edge once.

Eulerian Tour

An Eulerian Trail that starts and ends at the same vertex.

Euler’s Theorem

A connected graph with at least one edge has an Eulerian Tour if and only if every vertex has even degree.

Proof: Eulerian Tour => All vertices have even degree

If an Eulerian Tour exists, it is traversed by going to a vertex and leaving a vertex, repeated until the starting vertex is reached once again. Therefore each traversal is done in groups of 2 edges. Therefore each vertex must have an even number of edges for this to be possible, so every vertex has even degree.

Proof: All vertices have even degree => Eulerian Tour exists

Imagine the maximal-length trail in G, called C.

First we prove it has to be closed by contradiction. Imagine it is not closed. Since every vertex has even degree, the endpoint of C has an extra edge which isn’t added, so we add it. So C wouldn’t be maximal anymore. Therefore by contradiction it has to be closed.

We now have a closed trail. To prove that it’s actually Eulerian, all that’s left is to prove that it contains every edge. So for the sake of contradiction, let’s assume it doesn’t include every edge. Therefore since G is connected, so there’s no separate vertices, there would exist a vertex with an edge not in C, but then C could be extended to include this edge, contradicting the maximality of C. Thus, it must contain every edge and therefore it’s an Eulerian Tour.

A connected graph with at least one edge contains an Eulerian Trail if and only if it contains either 0 or 2 vertices of odd degree.

Proof:

Let G be a connected (multi)graph with at least one edge.

(=>) Eulerian Tour => 0 or 2 odd vertices:

Let T be a Eulerian Trail in G, where the start vertex = u and the end vertex = v. If we consider the scenario where u=v, this means that T is a closed Eulerian Trail. By definition this is a Eulerian Tour, and it is known that a connected graph with at least one edge is a Eulerian Tour if it is a closed Eulerian Trail. Next, we consider the scenario where u =/= v. Since T is a Eulerian Trail, we can then add a single edge, uv, to T, creating T*. Since T was a Eulerian Trail, T* now closes the cycle, and therefore T* is an Eulerian Tour. This, by the previously-used Euler’s Theorem, means that all vertices have even degree. Now once again considering T, this would mean that if uv was removed, the vertices u and v are the only ones with an odd number of vertices, and hence an Eulerian Trail contains 2 vertices of odd degree.

(<=)

If a graph contains 0 vertices of odd degree, this means all vertices have even degree. By Euler’s Theorem, this means that it is an Eulerian Tour. An Eulerian Tour is a closed Eulerian Trail, and therefore the graph is an Eulerian Trail.

Next, we can consider a graph with 2 vertices of odd degree. Now, We proved that the graph is an Eulerian Trail. Now, remove the edge between 2 of the vertices u and v. Now, we know that each vertex except u and v remain even in degree, but u and v are odd. These now form the start and endpoints of an Eulerian Trail, but cannot be an Eulerian Tour anymore since it is no longer closed. Therefore, the graph is an Eulerian Trail.

Complete Graph

A graph where every pair of distinct vertices are adjacent, meaning there’s an edge between every pair. Denoted by Kn, where n is the number of vertices.

Bipartite Graph

A graph where the vertices can be partitioned into 2 disjoint sets, and each edge in the Edge set intersects V1 and V2.This means that no two vertices within the same set are adjacent.

Complete Bipartite Graph

A bipartite graph where every vertex in the one of the disjoint sets is adjacent to every vertex in the other disjoint set. So every v∈V1 and v∈V2 are adjacent. K_n,m denotes one where there are n vertices in the first set and m vertices in the second.

Adjacency Matrix

An n x n matrix where pairs of vertices are connected by an edge.

Formally:

For i ∈ [n], j ∈ [n], M[i, j] = 1 if {v_i, v_j} ∈ E and 0 otherwise.

Incidence Matrix

An n x m matrix that shows what edges are connected to each vertex.

Formally:

For i ∈ [n], j ∈ [m], M[i, j] = 1 if v_i ∈ e_j and 0 otherwise.

Biadjacency Matrix

An r x s matrix that shows how a bipartite graph is connected between its sets.

Formally:
For i ∈ [r], j ∈ [s], M[i, j] = 1 if {u_i, v_j} ∈ E and 0 otherwise.

Adjacency List

A list of vertices with their adjacent vertices listed next to them.

Example:

L_v1: [v2, v3]

L_v2: [v1]

For every i, j ∈ [n], the number of walks of length k from v_i to v_j are given by the adjacency matrix A^k_G[i, j].

Proof (by induction):

Base case, k=1: We can observe that with the original adjacency matrix, it is defined as A[i, j] = 1 when {v_i, v_j} ∈ E(G), and 0 otherwise. So it gives the number of walks of length 1 (edges) between each vertex. Since G is a graph and not a multigraph, there can only be 1 edge between each pair of vertices, and hence it’s true for k=1.

IH - For all k>1, for every i, r ∈ [n], the number of walks of length k-1 from v_i to v_r are given by the adjacency matrix A^k-1_G[i, r].

Inductive Step:

Now, we recognise that:

Shortest path

The distance dist(vi, vj) between 2 vertices in a graph, where if they’re equal it’s 0, if they aren’t connected it is infinity, and otherwise it is the minimum value of A[i, j] from 1 to n.

Forest

Graph not containing a cycle, connected or disconnected

Tree

Connected acyclic graph

Cycle

A closed trail of non-zero length where all vertices are distinct except the starting and ending vertex.

Any tree with at least 2 vertices has at least 2 leaves

Proof:

Let G be the tree with at least 2 vertices. Let P be the longest path in G. Call the endpoints of P u and v. There’s at least 1 edge, since there are 2 vertices and it’s connected, so u is not v.

Let u’ and u’’ be neighbours of u. The vertex u’ can be in P, since it doesn’t violate the endpoint rule. However, having both u’ and u’’ in P means you can travel from u→u’’→…→u’→u which contradicts the acyclic property of trees as it forms a cycle. Also, uu’’ can’t be in P because then the edge can be added to P and this contradicts the assumption that P was the longest path in G. Therefore, u has 1 neighbour and therefore it is a leaf. The same logic can be applied to v.

Cut-edge

An edge in a connected graph where removing the edge will cause the resultant graph to be disconnected.

In a connected graph, an edge is not a cut edge if and only if it belongs to a cycle.

Proof:
Let G be a connected graph.

(=>)

Let e be an edge xy ∈ E(G), between vertices x and y. Assume e is not a cut edge. If e is not a cut edge, this means that when e is removed, the graph obtained, G’, is still connected. This means you can reach x from y (and vice versa) through another path in G. Now, add back the edge xy to this path. This forms a cycle. As a result, the edge xy which is not a cut edge belongs to a cycle.

(<=)

Let C be a cycle in G. This means that for 1 <= i < j <= n , vi ∈ C, there exists a path from vi to vj, and there exists a path from vj to vi. Let C’ be the graph obtained from removing an edge ij from C.

Spanning Tree

A subgraph of a connected graph which is a spanning subgraph of G and is also a tree (connected acyclic graph).

Characterisation of Trees

Trees are connected and acyclic

Trees are acyclic and have n-1 edges

Trees are connected and have n-1 edges

Each 2 vertices have 1 path between them

Matching

A set of edges in a graph where each vertex incident to an edge has a degree of 0 or 1. The edges are non-overlapping.