CIS 160 Final Cheat Sheet PDF

CIS 160 Final Cheat Sheet Contents 1 Logic 3 2 Number Theory...

CIS 160 Final Cheat Sheet Contents 1 Logic 3 2 Number Theory 3 2.1 Definitions:............................................................. 3 2.2 Proofs:................................................................ 3 3 Combinatorics 4 3.1 Definitions:............................................................. 4 3.2 Proofs:................................................................ 4 4 Sets 4 4.1 Definitions:............................................................. 4 4.2 Proofs:................................................................ 5 5 Proof Techniques 5 5.1 Induction............................................................... 5 5.1.1 Strong Induction...................................................... 5 5.2 Combinatorial Proofs........................................................ 5 5.3 Pigeonhole Principle........................................................ 5 5.4 The Probabilistic Method...................................................... 5 6 Graphs 5 6.1 Definitions:............................................................. 5 6.2 Proofs:................................................................ 6 6.3 Trees................................................................. 6 6.3.1 Definitions:......................................................... 6 6.3.2 Proofs:............................................................ 6 6.4 Graph Coloring........................................................... 6 6.4.1 Definitions:......................................................... 6 6.4.2 Proofs:............................................................ 6 6.5 Eulerian, Hamiltonian, and Tournament Graphs......................................... 7 6.5.1 Definitions:......................................................... 7 6.5.2 Proofs:............................................................ 7 6.6 Matchings:.............................................................. 7 6.6.1 Definitions:......................................................... 7 6.6.2 Proofs:............................................................ 7 6.7 Ramsey Numbers.......................................................... 7 6.7.1 Definitions:......................................................... 7 6.7.2 Proofs:............................................................ 7 7 Probability 8 7.1 Definitions:............................................................. 8 7.2 Fundamental Equations:...................................................... 8 7.3 Markov’s and Chebyshev’s..................................................... 8 7.4 Independence............................................................ 8 7.5 Random Variables......................................................... 8 7.5.1 Geometric Random Variable................................................ 8 7.5.2 Binomial Random Variable................................................. 9 7.5.3 Expectation......................................................... 9 7.5.4 Variance........................................................... 9 © 2020 8 Relations 9 8.1 Definitions:............................................................. 9 8.2 Proofs:................................................................ 9 8.3 Equivalence Relations....................................................... 9 8.3.1 Definitions:......................................................... 9 8.3.2 Proofs:............................................................ 10 8.4 Functions.............................................................. 10 8.4.1 Definitions:......................................................... 10 8.4.2 Proofs:............................................................ 10 © 2020  1 Logic The product of two odd numbers is an odd number. From L3T: A proposition is a statement that is either true or false. For all positive integers n, n is even iff 7n + 4 is even. N egation, denoted as ¬p, is the proposition that is true when p is From L3T: false and vice-versa. There are infinitely many prime numbers. Conjunction, p ∧ q, is the proposition that is true when both p and q From L3H: are true. Disjunction, p ∨ q, is the proposition that is true when at least one ! ! n n = of p or q is true. r n−r Exclusive or, p ⊕ q, is the proposition that is true when exactly one Pascal’s Formula: of p and q is true, false otherwise. If n and k are positive integers such that n ≥ k then Implication, p =⇒ q, is the proposition that is false when p is ! ! ! n n−1 n−1 true and q is false and true otherwise. The implication q =⇒ p = + k k−1 k is called the converse of the implication p =⇒ q. The implication ¬p =⇒ ¬q is called the inverse of p =⇒ q. The implication From L3H: ¬q =⇒ ¬p is the contrapositive of p =⇒ q. n ! X n Biconditional, p ⇐⇒ q, is the proposition that is true if p and q = 2n k k=0 have the same truth values and is false otherwise. From L3H: p is a suf f icient condition for q means p =⇒ q. p is a necessary condition for q means that ¬p =⇒ ¬q, or equivalently q =⇒ p. r ! ! ! X n m n+m = k r−k r k=0 2 Number Theory From L4T: 2.1 Definitions: The sum of the first n positive odd numbers is n2. From L4T: An integer n is even iff n = 2k for some integer k. An integer is odd For all integers n ≥ 0, if r 6= 1, iff n = 2k + 1 for some integer k. n X a(rn+1 − 1) An integer n is prime iff n > 1 and for all positive integers r and s, if ari = r−1 n = r, then r = 1 or s = 1. Otherwise, n is composite. i=0 An integer n being divisible by an integer k is denoted by k|n. By From L4T: the prime f actorization theorem, every positive integer can be For all non-negative integers n n uniquely represented as a product of primes. X 2i = 2n+1 − 1 i=0 2.2 Proofs: From L4T: From L1T: For all n ∈ N, n > 1 =⇒ n! < nn If the sum of two integers is even, then so is their difference. From L4T: From L1T: For all n ≥ 1, n lines separate the plane into For all integers n, if n is odd then n + n + 1 is odd. 2 n2 + n + 2 From L1T: 2 Let x be an integer. If x > 1, then x3 + 1 is composite. regions assuming that no two lines are parallel and no three pass From L1H: through a common point. If m and n are integers and m ≤ n then there are n − m + 1 integers Binomial Theorem: from m to n inclusive. For any real numbers a and b and non-negative integer n n ! From L2T: n X n n−k k (a + b) = a b For all real numbers x and all integers m k k=0 bx + mc = bxc + m From L4H: For any positive integer n From L2T: ! n If x and y are integers where x + y is even, then x and y are both n X n k (1 + x) = x k odd or both even. k=0 From L2T: From L4H: If 3n + 2 is odd then n is odd. Given a sequence of n integers, there exists a subsequence of con- From L2T: secutive integers whose sum is a multiple of n. For all real numbers a and b, if the product ab is an irrational number, From L5T: then either a, b, or both a and b must be irrational. If n is an integer greater than 1 then either n is prime or it can be From L3T: written as a product of primes. © 2020 From L5H: From L2H: Every sequence of n2 + 1 distinct real numbers x1 , x2 , x3 ,..., xn2 +1 For the number of r combinations of a set of n elements: contains a subsequence of length n + 1 that is either strictly increas- ! n n! ing or strictly decreasing. = r r!(n − r)! From HW2T: From L3H: For any positive integer w and non-negative, real number r, if r is 1 Using the Stars and Bars method, the number of r-combinations of irrational then r w is irrational. a set of n elements with repetition allowed is given by From HW3H: For every integer m ≥ 2, if there is no prime number p such that n+r−1 Number of combinations = √ (n − 1)!r! p ≤ m and p|m, then m must be a prime. From HW4T: 4 Sets For all n ∈ Z+ n X i · i! = (n + 1)! − 1 4.1 Definitions: i=1 A set is an unordered collection of distinct objects. The objects of a From HW4T: set are referred to as its elements or members. For all n ∈ Z+ n Two sets are equal iff they have the same elements. X n(n + 1)(n + 2)(n + 3) i(i + 1)(i + 2) = The cardinality of S, denoted by |S|, is the number of distinct ele- i=1 4 ments in S. From HW5H: A set A is said to be a subset of B iff every element of A is also an For all n ∈ Z+ n √ element of B, denoted by A ⊆ B. If A ⊆ B and A 6= B, then we say X 1 √ 0 or From HW2H: E[X] = x then it is proven respectively that there exists an outcome For any sets S, T, R in the sample space in event A or there is an event in the sample S \ (T \ R) 6= (S \ T ) \ R space where X ≥ x. In general, defining a random process in some mathematical context and deriving probabilities of events can be a S \ (T \ R) ⊆ (S \ T ) ∪ R useful tool for proving the existence of an arrangement or distribution From HW3H: where a defined event happens. For any sets A and Z 6 Graphs P(A ∩ Z) = P(A) ∩ P(Z) 6.1 Definitions: From R2: A graph consists of two sets, a non-empty set, V , of vertices or For any sets A, B, C nodes, and a possibly empty set, E, of 2-element subsets of V. Such a graph is denoted by G = (V, E). (A ∪ B) \ C = (A \ C) ∪ (B \ C) Each element of E is called an edge. We say that an edge u, v ∈ E 5 Proof Techniques connects vertices u and v. Two nodes u and v are adjacent if u, v ∈ E. Nodes adjacent to a 5.1 Induction vertex u are called neighbors of u. Induction is a proof technique that asserts that, for a proven base The number of neighbors of a vertex v is called the degree of v and case, induction hypothesis, and induction step, a proposition is suf- is denoted by deg(v). ficiently proven over the range of values between the base case and The value of δ(G) = minv∈V deg(v) is the minimum degree of G, the induction step. The base case proves the proposition for the the value ∆(G) = maxv∈V deg(v) is the maximum degree of G. lower or upper bound on the range of the value being inducted upon, An edge that connects a node to itself is called a loop and multiple the induction hypothesis is the formal statement assuming the the- edge between the same pair of nodes are called parallel edges. orem works for some arbitrary value within the range of induction, Graphs without loops and parallel edges are called simple graphs, and the induction step is the proof that, given the induction hypoth- otherwise they are called multigraph. esis, the statement holds for the proposition with the inducted value The girth of a graph G, g(G), is the length of the smallest cycle in incremented/decremented. G. © 2020 6.2 Proofs: 1. G is a tree. Handshaking Lemma: X 2. G is connected and has exactly n − 1 edges. deg(c) = 2|E| v∈V 3. G is minimally connected, i.e., G is connected but G − {e} is From L6T: disconnected for every edge e ∈ G. In any graph, there are en even number of vertices of odd degree. From L6T: Every graph with n vertices and m edges has at least n − m con- 4. G contains no cycle but G + {x, y} does, for any two non- nected components. adjacent vertices x, y ∈ G. From L6T: Every connected graph with n vertices has ≥ n − 1 edges 5. Any two vertices of G are linked by a unique path in G. From L15T: For every g, k > 0, there exists a graph G with χ(G) ≥ k and From L9T: g(G) ≥ g. Every connected graph G contains a spanning tree From HW7H: From L9T: For a connected graph with n ≥ 1 vertices and m ≥ 1 edges, If k is a positive integer and T is a full binary tree with k internal ver- n ≤ n2 − 2m tices then T has a total of 2k + 1 vertices and has k + 1 leaves. From HW8H: From L9T: For a connected graph with n ≥ 3 vertices, there exists exactly 1 Any binary tree of height at most h has at most 2 leaves. h cycle in the graph iff there are n edges. From HW8H: X From HW11H: Any tree T with n > 1 vertices has 2 + (deg(vi ) − 2) leaves. vi ∈V For a connected graph G without triangles with minimum degree deg(vi )≥3 δ(G) = d ≥ 0, G has at least 2d vertices. From HW9H: Any three-tree T with l leaves has l − 2 vertices of degree 3. 6.3 Trees From R7: Any tree T with maximum degree ∆ has ≥ ∆ leaves. 6.3.1 Definitions: From R7: A graph with no cycles is acyclic. All maximal paths in a tree must start and end with leaves. A tree is a connected acyclic graph. From R9: A vertex of degree greater than 1 in a tree is called an internal For a connected graph G and an arbitrary partition of G’s vertex set vertex, otherwise it is called a leaf. V into nonempty sets S and V \ S, if there exists only one edge e A f orest is an acyclic graph. between the vertices in S and the vertices in V \ S, then e must be A spanning subgraph of a graph G is a subgraph with vertex set in every spanning tree of G. V (G). A spanning tree is a spanning subgraph that is a tree. 6.4 Graph Coloring A rooted tree is a tree in which one vertex is distinguised from the others and is called the root. 6.4.1 Definitions: The level of a vertex, say u, is the number of edges along the unique path between u and the root. A graph is k-colorable if each vertex can be colored using one of the The height of a rooted tree is the maximum level of any vertex in the k colors so that adjacent vertices are colored using different colors. tree. The chromatic number of a graph G, χ(G), is the smallest value of A binary tree is a rooted tree in which every internal vertex has at k for which G is k-colorable. most two children. Each child in the binary tree is designated either A bipartite graph is a graph that is 2-colorable. a left child or a right child (but not both). A f ull binary tree is a binary tree in which each internal vertex has exactly 2 children. 6.4.2 Proofs: A three-tree is a tree such that all vertices have degree either 1 or 3. From L11T: A graph with a maximum degree at most k is (k +1)-colorable. From 6.3.2 Proofs: L15T: From L7T For any k ≥ 1, there exist triangle-free graphs with chromatic num- Every tree with ≥ 2 vertices has ≥ 2 leaves and deleting a leaf from ber greater than k. an n-vertex tree produces a tree with n − 1 vertices. From R11: From L7T: The following are equivalent A graph is bipartite iff it has no odd length cycles. © 2020 6.5 Eulerian, Hamiltonian, and Tournament Graphs an M − augmenting path. For Graphs G and H, the symmetric dif f erence G ⊕ H is a sub- 6.5.1 Definitions: graph of G ∪ H whose edges are the edges of G ∪ H that appear in An Eulerian circuit is a closed walk in which each edge appears either G or H, but not both. exactly once. A connected graph is Eulerian if it contains an Eule- An independent set of a graph is a set of pair-wise non-adjacent ver- rian circuit. tices. 0 A Hamiltonian cycle in a graph G is a cycle in which each vertex Hall s condition is the necessary and sufficient condition for Hall’s of G appears exactly once. A graph is Hamiltonian if it contains a Theorem. Hamiltonian cycle. A tournament graph is a directed graph with exactly one directed 6.6.2 Proofs: edge between any pair of vertices. From L11T: A tournament G = (V, E) is called k-dominated if for every set of k A matching M in G is maxmimum iff G contains no M −augmenting vertices v1 , v2 , v3 ,..., vk there exists another vertex u ∈ V such that path. (u, ui ) ∈ E, for i = 1, 2,..., k. Hall’s Theorem: Let G = (X, Y, E) be a bipartite graph. For any set S of vertices, let 6.5.2 Proofs: NG (S) be the set of vertices adjacent to vertices in S. G contains a From L10T: matching that saturates very vertex in X iff If δ(G) ≥ 2 then G contains a cycle. |NG (S)| ≥ |S|, ∀S ⊆ X From L10T: A connected graph G is Eulerian iff every vertex in G has even de- From HW14T: gree. If all vertices in a bipartite graph G = (X, Y, E) have the same de- From L10T: gree m > 0, then the partitions X and Y of the vertex sets are of the Let G be a graph with n ≥ 3 vertices. If every vertex in G has degree same magnitude. That is, |X| = |Y |. n ≥ then G is Hamiltonian. Note the converse is NOT necessarily From HW14H: 2 true. A bipartite graph G = (X, Y, E) has a perfect matching iff for all sub- From L14T: sets A ⊆ (X ∪ Y ), the inequality |A| ≤ |N (A)| holds. Every tournament graph has at least one Hamiltonian path. From R12: From L14T: Any k-regular bipartite graph has a perfect matching. n! There is a n-vertex tournament with at least distinct Hamilto- 2n−1 nian paths. 6.7 Ramsey Numbers From L15T: 6.7.1 Definitions: For any positive integer k, if n is large enough then there is a k- dominated tournament on n vertices. An independent set S in G is a subset of vertices such that no two From HW10H: vertices in S share an edge. The independence number of a graph For any Eulerian graph, an edge can be removed and the graph will G, denoted by α(G) is the size of the largest independent set in G. remain connected. For any graph G = (V, E), a set of vertices D ⊆ V is called a From R10: dominating set if every vertex in V \ D is adjacent to a vertex in For any graph G with an Eulerian Circuit, its edges can be partitioned D. into a set of edge-disjoint cycles (cycles that do not share any edges). A clique in a graph G is a set of vertices such that any pair of vertices share an edge. The Ramsey number R(k, l) is the smallest number n such that any 6.6 Matchings: graph with n vertices has a clique or size k or an independent set of 6.6.1 Definitions: size l. Another way to formulate this is: in any two-coloring on edges of the complete graph on n vertices, there is a monochromatic clique A matching in a graph is a set of edges with no shared end-points. of size k or a monochromatic clique of size l. The vertices incident on the edges of a matching M are called Diagonal Ramsey Number asks for the value of R(k, k) for any inte- M − saturated, the others are called M − unsaturated. ger k. A perf ect matching in a graph is a matching that saturates every vertex in the graph. 6.7.2 Proofs: A maximal matching in a graph is a matching that is not contained in a larger matching. A maximum matching is a matching of maxi- From L14H: mum size among all matchings in the graph. Let n be the number of vertices in G and m be the number of edges, 2m Given a matching M , an M − alternating path is a path that alter- and let d = ≥ 1 be the average degree. Then n nates between edges in M and edges not in M. 2 An M -alternating path whose endpoints are M -unsaturated is called α(G) ≥ 2d © 2020 From L14H: 7.4 Independence Any connected graph G = (V, E) with n ≥ 2 vertices and minimum degree σ(G) = σ contains a dominating set of size at most Two events A and B are independent if and only if: n(1 + ln(1 + σ)) 1+σ Pr[A ∩ B] = Pr[A] × Pr[B] From ! L15T: n 1−(k2) k IF 2 < 1, then R(k, k) > n. In particular R(k, k) > b2 2 c, Pr[A|B] = Pr[A] k for k ≥ 3. Pr[B|A] = Pr[B] From HW15T: Where I(G) is the size of the maximum independent set in G and Note: Independence does NOT imply Disjointness Q(G) is the size of the maximum clique G, I(G) = Q(G) Two random variables X and Y are independent if and only if: χ(G) ≥ Q(G) Pr[X = x ∩ Y = y] = Pr[X = x] × Pr[Y = y] 7 Probability for all values of x and y 7.1 Definitions: The sample space, denoted by Ω, of a random process or experiment is the set of all possible outcomes. 7.5 Random Variables The probability space is a sample space together with a probability A random variable X on a sample space Ω is a real-valued function distribution in which a probability is assigned to each outcome that assigns to each sample point ω ∈ Ω a real number X(ω). For ω ∈ Ω. a discrete random variable X and a real value a, the event X = a An event is any subset of the sample space. is the set of outcomes in Ω for which the random variable assumes the value a. 7.2 Fundamental Equations: Basic Equations For any events A and B such that A, B ⊆ Ω 7.5.1 Geometric Random Variable X Pr[A] = Pr[ω] ω∈A Conditions: The following must be met for a random variable to Pr[B] = 1 − Pr[B] have a negative binomial distribution: Pr[A ∩ B] Pr[A|B] = 1. Experiment consists of a sequence of independent trials Pr[B] Pr[A ∩ B] = Pr[A|B] Pr[B] 2. Each trial has two outcomes Inclusion-Exclusion Formula for Probabilities For two events A and B we have 3. The probability of success, p, is constant Pr[A ∪ B] = Pr[A] + Pr[B] − Pr[A ∩ B] 4. Trials are performed until a total of r successes have been ob- For any number of events, the formula applies just as PIE about sets served, where r ∈ Z+ where the probabilities of each individidual event are added, the pair- wise intersections subtracted, triowise probabilities added, and so pmf: For a random variable X where p represents the probability of on. success Union Bound For the union of any number of events Pr[X = x] = (1 − p)x−1 p n [ n X Pr[ Ai ≤ Pr[Ai ]] i=1 i=1 Mean and Variance: If X has a geometric distribution 1 7.3 Markov’s and Chebyshev’s E[X] = p Markov’s Inequality: 1−p E[X] V[X] = Pr[X > a] ≤ p2 a Memoryless Property: The geometric distribution is the only dis- Chebyshev’s Inequality: crete distribution with the memoryless property, defined by V[X] Pr[|X − E[X]| > a] = Pr[X ≥ x + s|X ≥ x] = Pr[X ≥ s] a2 © 2020 7.5.2 Binomial Random Variable V[X + Y ] = V[X] + V[Y ] Conditions: The following must be met for a random variable to n X Let Y be a random variable such that Y = Yi , where each have a binomial distribution i=1 Yi is a random variable. If E[Yi Yj ] = E[Yi ]E[Yj ] for every pair i, j 1. n trials with n fixed in advance such that 1 ≤ i ≤ j ≤ n, then 2. Each trial has two outcomes n X V[Y ] = V[Yi ] 3. Probability of success, p, is constant i=1 4. Trials are independent 8 Relations pmf: where x represents number of successes (0 ≤ x ≤ n), n rep- 8.1 Definitions: resents number of trials, and p represents probability of success ! A binary relation is a set of ordered pairs. n x n−x For sets A and B, a relation f rom A to B is a subset of the cartesian Pr[X = x] = p (1 − p) x product A × B. When A = B, we say that relation R is on set A. Mean and Variance: If X has a binomial distribution with parame- For a relation R on set A, we say that a relation is ref lexive if for all ters n and p then x ∈ A, (x, x) ∈ R. E[X] = np If (1, 2) ∈ R, we say that 1 is related to 2 by relation R, denoted by 1R2. A relation is irref lexive if for all x ∈ A, (x, x) ∈ / R. V[X] = np(1 − p) A relation is symmetric if for all x, y ∈ A, (x, y) ∈ R =⇒ (y, x) ∈ R. 7.5.3 Expectation A relation is antisymmetric if for all x, y ∈ A, xRy and yRx =⇒ x = y. The expectation of a random variable is the weighted average of the A relation is transitive if for all x, y, z ∈ A, xRy and yRz =⇒ xRz. possible values of X. X E[X] = i Pr[X = i] i 8.2 Proofs: By Linearity of Expectation, From L12T: n n 2 X X There are 2n relations on a set A of n elements. E[ Xi ] = E[Xi ] i=1 i=1 From L12H: There are 2n(n−1) reflexive relations on a set A of n elements. If X and Y are independent real-valued random variables then. E[X · Y ] = E[X] · E[Y ] 8.3 Equivalence Relations For any random variable Y that only takes on non-negative inte- 8.3.1 Definitions: ∞ X ger values, E[Y ] = Pr[Y > i] A relation R on a set A is an equivalence relation iff it is reflexive, i=0 symmetric, and transitive. The following is the definition of conditional expectation: If m is a positive integer then integers x and y are congruent modulo m, written as x ∼ = y (mod m), if m|(x − y). X E[Y |Z = z] = y Pr[Y = y|Z = z] y Let R be an equivalence relation on a set A and let a ∈ A. The As proven in lecture for random variables X and Y , equivalence class of a, denoted by [a]R , is the set of all elements of X A related (by R) to a. E[X] = Pr[Y = y]E[X|Y = y] If b ∈ [a]R , then b is called the representative of the equivalence y class [a]R. 7.5.4 Variance A directed graph, or digraphG = (V, E) consists of a set V of ver- tices and a subset E ⊆ V × V of edges or arcs. An edge of the from variance is the measure of how much a random variable deviates (u, u) is represented as an arc from u to itself. Note that a binary re- from its mean. The standard deviation is a measure of the same lation R on a set A can be represented as a directed graph in which thing but provides a tighter magnitude. the vertices represent the elements of A ad for every ordered pair (a, b) ∈ R, there is an edge from vertex a to vertex b. By definition, Note that all operations that can be performed on sets can be equiv- V[X] = E[X 2 ] − E[X]2 alently performed on relations, where the elements of relation R are its ordered pairs. By definition, p Let R be a relation from A to B. Then the inverse of R, written R−1 , σ[X] = V[X] is the relation from B to A defined by If X and Y are independent real-valued random variables then, R−1 = {(b, a)|(a, b) ∈ R} © 2020 Let R be a relation from A to B and S be a relation from B to C. The Two functions are equal if they have the same domain, have the same composition of S with R is the relation from A to C: codomain, and map each element of the domain to the same element of the codomain. S ◦ R = {(x, z)| there exists a y ∈ B such that xRy and ySz} Let f : A → B be a function. f is said to be one − to − one or Let R be a relation on set A. The powers R , n = 1, 2, 3,... are injective, iff for every x, y ∈ A such that x 6= y, f (x) 6= f (y). n defined recursively by f is called onto or surjective, iff for every element b ∈ B there is an element a ∈ A with f (a) = b. Rn+1 = Rn ◦ R f is a one−to−one correspondence or bijection, if it is both one=to- one and onto. 8.3.2 Proofs: Let f be a one-to-one correspondence from the set A to the set B. From L12H: The inverse function of f is the function that maps an element b ∈ B Let m be a positive integer. The congruent modulo m relation to the unique element a ∈ A such that f (a) = b. The inverse func- tion of f is denoted by f −1. Hence f −1 (b) = a when f (a) = b. Note R = {(a, b) : a ∼ = b (mod m)} that if f is not bijective then its inverse does not exist. is an equivalence relation on the set of integers. Let f : A → B and g : B → C be functions. The composition of the From L12H: function g with f is the function g ◦ f : A → C, defined by Let R be an equivalence relation on a set A. Then the following (g ◦ f )(x) = g(f (x)), ∀x ∈ A statements for elements a, b ∈ A are equivalent: 1. b ∈ [a] 8.4.2 Proofs: From L14H: 2. [a] = [b] Let A to B be finite sets of size a and b, respecitvely. There are ba 3. [a] ∩ [b] 6= ∅ number of ways to create a function from A → B. From L14H: From L12H: Let f and g be the functions. (f ◦ g)(x) = (g ◦ f )(x) is not always Let R be an equivalence relation on a set A. Then the set {[a]R |a ∈ true. A} is a partition of the set A. Each element of the set is called an From L14H: equivalence class of R. Conversely, given a partition {Ai } of the set Let f : A → B and g : B → C be two functions. Then A, there is an equivalence relation R that has sets Ai as its equiva- lence classes. 1. if f and g are surjective then so is g ◦ f. From L14T: 2. if f and g are injective then so is g ◦ f. A relation R on a set A is symmetric iff R = R−1 From L14T: 3. if f and g are bijective then so is g ◦ f. Let R be a relation on set A. Then R is transitive iff Rn ⊆ R, for all n ≥ 1. From HW14H: If sets R and S are equivalence relation on set A, the union of sets R and S are NOT necessarily an equivalence relation. The intersection of sets R and S is ALWAYS an equivalence relation. From HW14H: An antisymmetric equivalence relation R on set A has |R| = |A| 8.4 Functions 8.4.1 Definitions: Let A and B be sets. A f unction from A to B is a relation, f , from A to B such that for all a ∈ A there is exactly one b ∈ B such that (a, b) ∈ f. If (a, b) ∈ f , we write b = f (a). A function from A to B is also called a mapping from A to B and we write it as f : A → B. The set A is called the domain of f and the set B the codomain. if a ∈ A then the element b = f (a) is called the image of a under f. The range of f , denoted by Ran(f ), is the set Ran(f ) = {b ∈ B|∃a ∈ A such that b = f (a)} © 2020