1 Mathematical Preliminaries 1.1 Set Theory Definition 1 (Set). A set is collection of distinct elements, where the order in which the elements are listed does not matter. The size of a set $, denoted |S|, is known as its cardinality or order. ‘The members of a set are referred to as its elements. We denote membership of x in Sas x € S. Similarly, ifx is not in S, we denote e¢s. Example 1. Common examples of sets include the set of real numbers R, the set of rational numbers Q, and the set of integers Z. The sets R+,Q* and Z~ denote the strictly positive elements of the reals, rationals, and integers respectively. We denote the set of natural numbers N= {0,1,...}. Let n © Z* and denote fr] = ,.-.yn} We now review several basic set operations, as well as the power set. It is expected that students will be familiar with these constructs. Therefore, we proceed briskly, recalling definitions and basic examples intended solely as a refresher. Definition 2. Set Union Let A, B be sets. Then the union of A and B, denoted AU B is the set: AUB = {2:26 Aorz B} Example 2. Let A= (1,2,3) and B= {4,5,6}. Then AU B = {1,2,3,4,5, 6) Example 3. Let A = {1,2,3} and B= (3,4,5}. So AUB = {1,2,3,4,5). Recall that sets do not contain duplicate clements. So even though 3 appears in both A and B, 3 occws exactly once in AU B. Definition 3. Set Intersection Let A, B be sets. Then the intersection of A and B, denoted AM B is the set AN Box {xia 6 Aand xe BY Example 4, Let 4 = {1,2,3} and B= {1,3,5}. Then AN B = {1,3}. Now let C= {4}. So ANC =. Definition 4 (Symmetric Difference). Let A,B be sets. Then the symmetric difference of A and B, denoted AAB is the set: AMDB = {2:26 Aor 2B, but 2 ¢ ANB} Example 5. Let A= {1,2,3} and B= {1,3,5}. Then AAB = {2,5}. For our next two definitions, we let Ube our universe, That is, let U be a set. Any sets we consider are subsets of U. Definition 5 (Set Complementation). Let A be a set contained in our universe U. The complement of A denoted A® or A, is the set: Ax (eeUrag A} Example 6. Let 1,2,4}. Then A= (3,5) Definition 6 (Set Difference). Let A,B be sets contained in our universe U. The difference of A and B, denoted A\ Bor A~ B, is the set: A\ B= (2: Aandr¢ BY Example 7. Let U = [5], A= {1,2,3} and # = {1,2}. Then A\ B= {3} Remark: The Set Difference operation is frequently Inown as the relative complement, as we are taking the complement of B relative to A rather than with respect to the universe U. Definition 7 (Cartesian Product). Let A,B be sets. The Cartesian product of A and B, denoted Ax B, is the set: Ax B= {(a,0):0€ A,be BY Example 8. Let A= {1,2,3} and B= {a,}. Then A x B= {(1,a), (1,6), (2,4), (2,6),(3,2), (8,8)). 3Definition 8 (Power Set). Let $ be a set. The power set of S, denoted 25 or P(S), is the set of all subsets of S. Formally: 2 = (A: ACS} Example 9. Let $= {1,2,3}. So 2 = {0, {1}, (2, {3}, {1,2}, {1,3}, {2,3}, ,2,3}) Remark: For finite sets $, [25] = 2151; hence, the choice of notation. Definition 9 (Subset). Let A, B be sets. A is said to be a subset of B if for every x © A, we have © B as well. This is denoted A c B (equivocally, A © B). Note that B is a superset of A Example 10. Let A= [3], B = (6],C = (2,3,5}. So we have AC B and CC B. However, Ag¢ C as 1 ¢C; and Cg Aas ZA Remark: Let S be a set. The subset relation forms a partial order on 25, To show two sets A and B are equal, we must show AC B and BC A. We demonstrate how to prove two sets are equal below. Proposition 1.1, Let A= {6n:n €2},B = (2n:n€Z},C Proof. We first show that AC BAG. Let n € Z. So 6n € A. We show 6r € BNC. As 2 is a factor of 6, Gn = 2. (3n) € B. Similarly, as 3 is a factor of 6, 6m = 3- (2n) € C. So 6n € BNC. We now show that BOCCA Let x € BNC. Let m,nz €Z such that 2 = 21 = Snp. As 2 is a factor of x and 3 is a factor of 4, it follows that 2-3 ~ 6 is also a factor of x. Thus, x —Gns for some ns ¢ Z. Sox € A. Thus, BNC CA ‘Thus, A= BIC, as desired a Sn: n€Z}. So A=BNC. Proposition 1.2. Let A, B,C be sets. Then Ax (BUC) = (Ax B)U(AXC) Proof. Let (x,y) € Ax (BUC). Ify € B, then (x,y) € (Ax B). Otherwise, y € C and s0 (z,y) € (A x ©). Thus, A x (BUC) ¢ (A x B)U(AxC). Now let (4, f) € (Ax B)U (Ax C). Clearly, d€ A. So f must be in either B or C. Thus, (d, f) € Ax (BUC), which implies (A x B)U(A x €) ¢ Ax (BUC). We conclude that Ax (BUC) = (Ax B)U(AxC) a 1.2 Relations and Functions Definition 10 (Relation). Let X be a set. A k-ary relation on X is a subset Rc X* Example 11. The notion of equality = over Ris the canonical example of a relation. It is perhaps the most well-known instance of an equivalence relation, which will be discussed later. Intuitively, a ary relation R contains k-tuples of elements from X that share common properties. Computer scientists and mathematicians are interested in a number of different relations, including the adjacency relation (graph theory), equivalence relations, orders (such as partial orders), and functions. In this section, functions, asymptotics, and equivalence relations will be discussed. 1.2.1 Functions The notion of a function will be introduced first. Functions are familiar mathematical objects, which appear early on in mathematics education with the notion of an input-output machine, Roughly speaking, a function takes an input and produces an output, Some common examples include the linear equation fe) = ax +6 and the exponential f(x) = 2*, We denote a function as follows. Let X and Y be sets. A function is a map f : X — Y such that for every 1X, there is a unique y € Y where f(z) = y. We say that X is the domain and Y is the codomain. The range or image is the set f(X) = (f(x) :x € X}. More formally, a function is defined as follows Definition 11. Function Let X and ¥ be sets. A function f is a subset (or L-place relation) of X x Y such that for every x € X, there exists a unique y ¢ ¥ where (2,y) € f Let's consider some formal functions and one example of a relation that is not a function, Example 12. Let /:R — R be given by f(z) = 2. This is known as the identity map. Example 13. Let 9: RR be given by g(x) = 32%Example 14. Let h: 8 > R given by: weft. 283 Note that h is not a function as (3,—3) € h and (3,2) € h. The definition of a function states that there must be a unigue y such that (3,y) © A. If we revise h such that h(3) = —3 only, then h satisfies the definition of a function. From a combinatorial perspective, special types of functions known as injections and surjections are of great importance. The idea is that if we have two sets X and Y and know the cardinality of X, then an injection or surjection from X to ¥ yields results about ¥'s cardinality. We ean deduce similar results about Ys cardinality. An injection is also known as a one-to-one function. Recall the definition of a function states that the map £:X > ¥ maps each 2 ¢ X to a unique y CY. It allows for functions such as g : R> B given by ‘a(z) = 0. Cleatly, every + € R maps to the same y-coordinate: y= 0. An injection disallows functions such as these. The idea is that each y € Y can be paired with at most one 2 € X, subject to the constraint that each clement in X must be mapped to some clement from Y. So there can be unmapped elements in Y, but not in X. We define this formally as follows, Definition 12 (Injection). A function f : X -+ ¥ is said to be an injection if (1) = f(e2) —> 21 = 22 Equivocally, f is an injection if 1 #22 => (x1) # f(z2). Let's consider examples of functions that are injections, as well as those that fail to be injections. Example 15. Let X be a set. Recall the identity map id : X + X given by id(x) = x. ‘This function is an injection. Let id(rx) = id(a). Then we have id(xi) = 21 = id(x2) = x2, which implies that 21 = 2. Example 16. Consider the fnction 9 : R > R be given by g(z) = +?. Observe that g fails to be an injection, Let 9(21) = o(zz) = 4. We have x — 2 and 22 ~ ~2, both of which map to 4. If we instead consider RY RR by A(z) = 2°, we have an injection since we only consider the positive real numbers. Observe as ‘woll that both 9 and h do not map to any element less than 0. Remark: Let's reflect on what we know about injections. An injection is a function, in which any mapped clement in the codomain is mapped to exactly once. There may be elements in the codomain which remain unmapped. Asa result, for two sets X and Y, itis defined that X| < |Y| if there exists an injection f : X + Y. Intuitively speaking, an injection pairs each element from the domain with an element in the codomain, allow ing for leftover elements in the codomain. Hence, X has no more elements than Y if there exists an injection PX oy. Surjections or onto functions center around the codomain, rather than the domain. Recall the earlier example of g:R > R given by 9(2) = 2?, which satisties g(x) > 0 for every « € R. So the negative real numbers will never be maped under 9. Surjections exclude functions like g. Intuitively, a function is a surjection if every clement in the codomain is mapped. Any element of the codomain can have multiple domain points mapping to it, as long as each has at least one domain point mapping to it. We define this formally as follows. Definition 13 (Surjection). Let X and ¥ be sets. A function f: X + ¥ is a surjection if for every y € Y, there exists an 2 © X such that f(z) = y. ‘We have already seen an example of a function that is not a surjection. Let us now consider a couple examples of functions that are surjections, Example 17. Recall the identity map id : X + X. For any + € X, we have id(z] is a surjection. 2. So the identity map Example 18. Let X = {a,5,¢,d} and let ¥ = {1,2,3}. Define f : X > ¥ by f(a) = f(6) = 1. f(c) = 2 and ‘F(d) = 3. This fimetion is a surjection, as each y € Y is mapped under f, Observe that there are more X clements than Y elements, If X instead had two elements, then f would not be a surjection because at most two of the three elements in Y could be mapped.Remark: Similarly, let's now reflect upon what we know about surjections. A suxjection is a funetion in whieh every element of the codomain is mapped at least once. Some elements in the codomain may have multiple elements in the domain mapping to them. Therefore, if there exists a surjection f : X > Y, then |X| > [Y| ‘We now introduce the notion of a bijection. A function is a bijection if it is both an injection and a suxjection, Intuitively, a bijection matches the elements in the domain and codomain in a one-to-one manner. That is, cach clement in the domain has precisely one mate in the codomain and vice versa. For this reason, two sets X and ¥ are defined to have the same cardinality if there exists a bijection f : X + Y. Combinatorialists use bijections to ascertain set cardinalities. The idea is that given sets X and Y, with |Y| known, can we construct a bijection J: X + Y? If the answer is yes, then |X) = [Y| Definition 14 (Bijection). Let X and ¥ be sets. A bijection is a function f : X — ¥ that is both an injection and a surjection, Example 19. Some examples of bijections include the identity map, as well as the Imear equation f(x) = mr +b ‘We conclude by showing that the composition of two injective functions are injective, and that the composition, of two surjective functions are surjective. ‘This implies that the composition of two bijections is itself a bijection, which is an important fact when working with permutations (which we shall see later Proposition 1.3. Let f: XY and g: ¥ > Z be injective functions, Then go f is also injective Proof. Let 3,22 € X be distinct. As f is injective, f(r) # f(xy. Similarly, as g is injective, g(f(z)) 4 Gf f(22)). $0 (gof)(21) # (ge )(aa), a8 desired. As x1, 22 were arbitrary, we conclude that gof is injective. D Proposition 1.4. Let f:X > Y and 9: ¥ + Z be surjective functions. Then ge f is also surjective. Proof. Let 2 € Z. As g is surjective, there exists y € ¥ such that gly) = 2. Now as fis surjective, there exists 2 €X such that f(z) = y. Thus, (90 f)(2) = 2 As z was arbitvary, it follows that go f is surjective. 1.2.2. Equivalence Relations Equivalence relations are of particular importance in mathematics and computer science. Intuitively, an equiv- alence relation compares which elements in a set X share some common property. The goal is to then partition X into equivalence classes such that all the elements in one of these parts are all equivalent to each other. ‘This allows us to sclect an arbitrary distinct representative from each equivalence class and consider only that representative. ‘This idea of partitioning comes up quite frequently. The integers modulo n, denoted Z/nZ, is a canonical ex: ample. Big-Theta is another important equivalence relation. Equivalence relations allow us to prove powerful theorems such as Fermat's Little Theorem from Number Theory and Cauchy's Theorem from Group Theory, as well as to construct a procedure to minimize finite state automata via the Myhill-Nerode Theorem, In order to guarantee such a partition, an equivalence relation must satisfy three properties: reflexivity, sym metry, and transitivity. We define these formally below, restricting attention to binary relations, Definition 15 (Reflexive Relation). A relation R on the set X is said to be reflexive if (a,a) € R for every aeX. Definition 16 (Symmetric Relation). A relation R on the set X is said to be symmetric if (a,5) € R if and only if (6,a) € R for every a, € X, Definition 17 (Transitive Relation). A relation R on the set X is said to be transitive if for every a,b, € X satisfying (a,8), (0,¢) € R, then (a,e) € R. Definition 18 (Equivalence Relation). An equivalence relation is a reflexive, symmetric, and transitive rela- tion,