MATH 163 Course Notes Fall 2024 PDF

Course notes for MATH 163: Introduction to Mathematical Reasoning University of Saskatchewan (ver. Fall 2024) A note on the text (Fall 2024) In 2019, the Department of Mathematics and Statistics introduced the course MATH 163: Introduction to Mathematical Reasoning for a...

Course notes for MATH 163: Introduction to Mathematical Reasoning University of Saskatchewan (ver. Fall 2024) A note on the text (Fall 2024) In 2019, the Department of Mathematics and Statistics introduced the course MATH 163: Introduction to Mathematical Reasoning for all students in their programs. This course was designed to make explicit in the curriculum notational and cultural norms within mathe- matics so as to ease the path of students through upper-year courses in mathematics. The emphasis on mathematical communication should also make this course very useful for stu- dents who are interested in disciplines such as computer science and mathematics education. These notes are designed to be a living textbook for MATH 163, and are written for students who are interested in mathematics but have little mathematics experience beyond high-school studies in pre-calculus. Notably, the implied reader of these notes has no experience with mathematical proof, writing, and formalism. Great effort is made to be explicit about notation, terminology, and that choices in these regards are cultural; they are not inherently right or wrong, however best practice for communicating to others dictates that we adhere to standard usage. The first version of these notes was created by Dr. Christopher Duffy during the Fall 2020 semester at the University of Saskatchewan, as the course was offered remotely during the COVID-19 pandemic. We have continued to revise and expand upon them during subsequent offerings of the course. Each section of the notes corresponds to roughly one week of material, and begins with a list of learning incomes and outcomes. The former list tells the reader what material they need to be familiar with in order to understand the upcoming material. Readers should return to the latter list once they have finished their work in section to be sure they have attained the learning outcomes. Each chapter of the notes ends with a section titled Test Your Understanding. The problems therein are meant to be a check of broad understanding of the key ideas in the section, and are (for the most part) not designed to challenge a reader. Detailed solutions to these exercises are included in the notes, but it’d be best for your learning to give the exercises your best effort before indulging yourself with the comfort of reading the solutions. As we wrote these hundreds of pages of notes from scratch, there are inevitably many errors. If you find any mathematical and/or typographical mistakes herein, and/or simply have feedback on these set of notes that you’d like to share, please feel free to contact me by e-mail. Dr. Gary Au ([email protected]) 2 Contents 1 Sets and Functions Part I 5 1.1 Preliminaries................................... 7 1.2 Relating Sets and Set Operations........................ 12 2 Sets and Functions Part II 21 2.1 Functions..................................... 24 2.2 Injections, Surjections and Bijections...................... 32 2.3 Operations..................................... 34 3 Relations Part I 43 3.1 Orderings..................................... 48 3.2 Graphs....................................... 52 4 Relations Part II 59 4.1 Equivalence Relations............................... 61 4.2 Set Partitions................................... 64 4.3 Equivalence Relations and Set Partitions.................... 70 5 Introduction to Formal Logic 77 5.1 What are Proofs?................................. 79 5.2 An Informal Introduction to Formal Logic: Statements and Truth Values.. 82 5.3 Modelling Mathematical Theorems with Formal Logic............. 87 5.3.1 Converse Statements........................... 92 5.3.2 If and Only If Statements........................ 92 5.4 Formulas and Quantifiers in Formal Logic................... 95 5.4.1 Quantifiers................................. 95 5.4.2 Proving statements with existential quantifiers............. 99 5.4.3 Multiple Quantifiers........................... 99 5.4.4 Negations of quantified statements................... 100 5.5 Optional Section: Limits to Infinity....................... 103 6 Mathematical Induction Part I 110 6.1 The Principle of Mathematical Induction.................... 113 6.2 Proving the Principle of Mathematical Induction................ 119 6.3 Starting induction at some n other than 0................... 122 7 Mathematical Induction Part II 128 7.1 The Principle of Strong Mathematical Induction................ 129 7.2 Further Examples of Proofs by Induction.................... 135 7.2.1 A proof with multiple cases....................... 135 7.2.2 Fibonacci Numbers............................ 137 7.3 Common Questions About Induction...................... 144 3 8 An Introduction to Graph Theory 149 8.1 Preliminaries................................... 152 8.2 Trees........................................ 155 8.3 Graphs and Counting............................... 159 8.4 Graph Colouring................................. 164 8.5 Graph Isomorphism and Unlabelled Graphs (Optional)............ 168 9 Complex Numbers 175 9.1 The Unit Circle: Defining Radians and Trigonometric Ratios (Refresher).. 179 9.2 Sneaking Up on Complex Numbers....................... 185 9.3 Defining Complex Numbers........................... 190 9.4 Euler’s Identity (Optional)............................ 198 10 Cardinality of Sets Part I 208 10.1 Cardinality of a Finite Set............................ 210 10.2 Binomial Coefficients — Combinatorially Speaking.............. 213 10.3 The Binomial Theorem.............................. 218 10.4 Binomial Coefficients — Algebraically Speaking................ 220 11 Cardinality of Sets Part II 227 11.1 Some Infinities Have The Same Size....................... 229 11.2 Some Infinities Are More Infinite Than Others................. 233 12 Some (More) Classic Results and Proofs 242 12.1 Inspired by Right Triangles........................... 243 12.2 Results Related to Number Theory....................... 247 12.3 Peeking into Infinite Series............................ 249 12.4 Introducing Ramsey Numbers.......................... 255 Index 264 Table of Notation 266 4 1 Sets and Functions Part I Learning Incomes. Exposure to the idea of a mathematical function. Familiarity with standard mathematical notation used in SK secondary-school courses Foundations of Mathematics 30 or Precalculus 30 Reading ability at a level at least that of an SK secondary-school graduate. Newly Defined Terms and Notation. element (∈), natural numbers (N), rational num- bers (Q), real numbers (R), integers (Z), set-builder notation, A equals B (=), A is a (proper) subset/superset of B (⊂, ⊆, ⊇, ⊃), the union of A and B (∪), the intersection of A and B (∩), Cartesian product of A and B (×), domain of the variable. A good conversation to have at the start of any class (in mathematics or otherwise) is one of motivation for the course material. Sometimes mathematics courses get away with a hand wave towards real-world application or improving reasoning skills, but I think we can do a little bit better here. We will spend most of our time in MATH 163 muddling with abstract nonsense. We’ll discuss abstract objects and ideas often without any clear or obvious application to industry. This isn’t to say that the work we do doesn’t have applications in these areas – in fact the opposite is true. However, applying the material in this course to other domains requires background knowledge that we don’t have. And so, at some point, you may find yourself thinking why am I learning this?. Put plainly, you are learning this material now so that when you take future courses in math- ematics, you are free from the burden of having to learn about the practice of mathematics while you are also learning new mathematical material. This course is designed to introduce you to standard norms and practices in mathematical notation and communication while also exposing to you some mathematical ideas that arise in many different mathematical domains. The College of Arts and Sciences at the University of Saskatchewan espouses a model of liberal arts education. The idea is that by studying material in a variety of disciplines — including classes in sciences and humanities — we can become more culturally literate members of our society. A university education isn’t the only means of attaining this literacy, and indeed one can argue that at times it isn’t a particularly effective means to this goal. For those of you who are unlikely to pursue further courses in mathematics or computer science, your learning in this course is unlikely to provide you with additional training to do anything in your (eventual) profession. For you, this course is part of your broader education in becoming a more culturally literate member of society. By immersing yourself in the course material you are learning what it is like to be a mathematician — to grapple 5 with abstract ideas that may only exist in our collective human consciousness. Our primary goal in this course is understanding mathematical theory, not performing com- putations or algebraic manipulations. More often than not, we will exhibit our understanding through written explanations in complete sentences. As we progress through the course, we will talk more about what it means to explain as a mathematician. For now, the key thing to remember is that defined terms have meanings — they are, in a sense, shorthand for precise ideas. Throughout these notes, newly defined terms are underlined. We define these terms to develop a common vocabulary so that we may communicate our mathematical ideas without ambiguity. Most of the time, our difficulty in understanding (and subsequently, being able to explain) stems from an incomplete grasp of definitions. But this is enough talking about mathematics for now. Let us move to actually talk some mathematics. 6 1.1 Preliminaries Intuitively, a mathematical set is a collection of unique objects. Let us begin by considering a set that we may already familiar with. Definition 1.1. The set of natural numbers is the set {0, 1, 2, 3,... }. We denote this set by N. Aside. Some people exclude 0 as being a natural number. This is perfectly fine and reason- able. This is a matter of preference, and there is no universal convention. In these notes, we shall use N+ to denote the set {1, 2, 3,...}.) Even without more formality, this first definition gives us a method to express the objects of a set. That is, we write down its members between braces: {0, 1, 2, 3,... }. Here the ellipsis denotes that we continue with the pattern. It is not an overstatement to say that sets underpin just about every mathematical concept that you have ever encountered. This is not an obvious statement, but something we will discover throughout this semester. Thus your background mathematics knowledge already gives you some intuition about sets! And so perhaps you are already familiar with the following definition. Definition 1.2. When X is a set and x is a member of X, we say that x is an element of X. When x is an element of X we write x ∈ X. We write x ∈ / X when x is not an element of X. Relying on our familiarity with the natural numbers we may write 4 ∈ N and 21 ̸∈ N. These notations are just shorthand for the sentences “4 is in the set of natural numbers” and “ 21 is not in the set of natural numbers”. The only reason to prefer the notation over the sentence is for brevity. Our notation for set membership extends nicely to describe multiple things being elements of the same set. For example, we can write “2, 4 ∈ N” to mean “2 ∈ N and 4 ∈ N”. In this class we are going to define a lot of terms. We do this so that we can develop a common vocabulary to communicate precise ideas. In every definition the newly defined term will be underlined. From then on when we use that term we all have the same understanding of what the term means. There are numerous ways to tell a reader what elements are contained in a particular set. If a set has few elements, then it may be defined by listing out the elements ex- plicitly. For instance, {1, 3, 5, 7} is the set of the first four odd numbers. The order in which we write the elements does not matter. The set {1, 3, 5, 7} is the same set as {1, 5, 3, 7}. Repeating elements also does not matter. The set {1, 3, 5, 7} is the same set as {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7}. 7 For sets with too many elements to list, we must provide the reader with a means to determine membership in the set. We can inform our reader that not all elements of the set have been listed, but that enough information has been provided for the reader to identify a pattern for determining membership in the set. For example, let X denote the set {2, 4, 6, 8,... , 96, 98}. Here X is the set of positive even integers less than 100. However, using an ellipsis to define a set may not always work: it assumes that the reader will identify the pattern we wish to characterize. Notice how many times the word reader is used in that last paragraph. This suggests that the purpose of using notation is to communicate unambiguously with a reader. We will return to this idea throughout the course. Some sets are used so commonly that they have standard names and notations. Some of these you may have seen before. Definition 1.3. The integers are the elements of the set {... , −3, −2, −1, 0, 1, 2, 3,...}. This set is denoted by Z. The rational numbers are the elements of the set   p | p, q ∈ Z and q ̸= 0. q This set is denoted by Q. The real numbers is the set of numbers that appear on the number line. This set is denoted by R. Aside. We use the symbol Z for integers because of the German word zhalen, which means numbers. We use the symbol Q for the rational numbers because of the Italian word quoziente, which means quotient. Both of these conventions go back hundreds of years. The symbols we use for these sets, N, Z, Q, R are written differently than we would write the letters N, Z, Q, R. These symbols are printed in blackboard script. They harken back to a time long ago (circa. 2019) when mathematics was primarily taught on a blackboard. Written this way, N will always refer to the natural numbers. Whereas we can use N as a label for other things if we need it. Notice that the definitions of Q and R express sets in a different way than just listing out the elements. In defining R we have just written a sentence. This is a perfectly acceptable way to define a set. For example, it is perfectly reasonable to say let S denote the set of students registered in MATH163. Let us look more closely at our definition of the rational numbers, Q: 8    p Q= | p, q ∈ Z and q ̸= 0. q In fact this jumble of symbols is a sentence. “Q = ” translates to “The set Q is defined to be”; p “ ” translates to “ those elements with the form pq ”; q “|” translates to “ where” ; “p, q ∈ Z and q ̸= 0” translates to “ p and q are integers and q is not equal to 0”. And so when we see   p Q= | p, q ∈ Z and q ̸= 0 q we think (and say and read) “The set Q is defined to be those elements with the form pq where p and q are integers and q is not equal to 0”. (Think for a moment — are you convinced that saying a number is rational is equivalent to saying it can be expressed in the form pq where p and q are integers and q is not equal to 0?) Our method for describing Q is easily adapted to define other sets. This method of describing a set is called set-builder notation. We will use this method quite often. Definition 1.4. Let X be a set, and let P (x) be a statement that is either true or false for each x ∈ X. The set {x ∈ X | P (x)} is the set of elements in X for which P (x) is true. The set X is called the domain of the variable. Often P (x) is a mathematical formula. For instance, suppose P (x) is the formula “x2 = 4”. By P (3) we mean the formula with 3 substituted for x, that is P (3) is the statement “32 = 4”. If the substitution results in a true statement for some particular value of x, we say that P (x) holds, or P (x) is true. Otherwise we say that P (x) does not hold, or P (x) is false. In our example, P (2) is true and P (3) is false. Example 1.5. Let X denote the set {0, 1, 4, 9,...}. Using set-builder notation we can express this set as X = {x ∈ N | there exists y ∈ N, so that x = y 2 }. 9 Here P (x) is the formula “there exists y ∈ N, so that x = y 2 ”. The formula P (x) is true whenever x is a perfect square. The formula P (x) is false whenever x is not a perfect square. Example 1.6. Let Y denote the set of positive even integers less than 100. The set Y can expressed as {z ∈ N | z < 100 and there exists n ∈ N+ so that z = 2n}. Take a moment to determine what P (z) is. Are you convinced that P (z) is true for every positive even integer less than 100 and false otherwise? Aside. There was no reason here to choose z as a variable over x in the definition of the set Y. Nothing would change if we replaced z with x in the definition of Y. Okay... I suppose the purpose of choosing z was so that I could add in this aside to make the point that variable names generally don’t matter... For the sake of brevity, an author may not explicitly identify the domain of the variable. Be careful of this, as such an author is relying on the reader to make the necessary assumptions. For instance, consider the set {x | (x2 − 2)(x − 1)(x2 + 1) = 0}. If the domain of the variable is assumed to be N, then {x | (x2 − 2)(x − 1)(x2 + 1) = 0} = {1}. If the domain of the variable is assumed to be R, then √ √ {x | (x2 − 2)(x − 1)(x2 + 1) = 0} = {1, 2, − 2}. Remember, the burden of clear communication is always on the author. (And so the burden is on me to communicate that we will reuse names for sets very often. Two sets named X, for example, in different parts of the notes usually aren’t referring to the same set. ) Another alternative is to include the domain of the variable in the condition defining mem- bership in the set. So, if X is the intended domain of the variable and P (x) is the condition for membership in the set we may write {x | x ∈ X and P (x)} to mean {x ∈ X | P (x)}. Example 1.7. Consider the set A = {x ∈ N+ | x is divisible by 2 or x is divisible by 3}. In this example P (x) is the formula “x is divisible by 2 or x is divisible by 3”. Let us consider some elements of the domain of the variable to understand which elements of N+ are elements of A. P (1) is the statement “1 is divisible by 2 or 1 is divisible by 3.” This is false, thus 1∈/ A. 10  P (2) is the statement “2 is divisible by 2 or 2 is divisible by 3.” Since 2 is divisible by 2 it follows that P (2) is true and so 2 ∈ A. P (3) is the statement “3 is divisible by 2 or 3 is divisible by 3.” Since 3 is divisible by 3 it follows that P (3) is true and so 3 ∈ A. P (4) is true and so 4 ∈ A. P (5) is false and so 5 ∈ / A. P (6) is the statement “6 is divisible by 2 or 6 is divisible by 3”. Since 6 is divisible by 2 it follows that P (6) is true and so 6 ∈ A.... this seems to be taking a while. Examining each element of N+ individually will take us more time than we have! Instead of this let us think a little about P (6). Looking at P (6) might give us some pause. We might expect P (6) to be false as 6 is divisible by 2 and 6 is divisible by 3. Usually in English we think of “or” as being a statement of exclusivity — either this is true or that is true. In mathematics this is not the case. By convention we assume an “or” statement to be inclusive. The statement “this is true or that is true” means that at least one of “this” or “that” is true. Thus A can be described as the set of all positive integers that are multiples of 2 together with those positive integers that are multiples of 3. For convenience we permit the existence of a set containing no objects. We call this set the empty set and we denote it as {}. Sometimes the empty set is denoted as ∅. This choice of notation is a matter of preference. Example 1.8. As sets are able to contain any objects, it is reasonable to think of sets that contain other sets. For example, If A = {0, 1} and B = {3}, then the set {A, B} is a set with two elements. The elements of the set {A, B} are themselves sets, which happen to also contain elements. Optional things to think about– How does this approach to mathematics compare from what you have seen in past math classes? Certainly there is no computation to be found, nor is there any half-hearted attempt to talk about real-world applications. Nor are there pictures to be seen anywhere. The only thing we really need, at this point, is our reading comprehension, as well as a commitment to thinking carefully about what we are reading. 11 1.2 Relating Sets and Set Operations Recall that, in the notes from Section 1.1, as we were discussing the importance of specifying the domain of a variable, we had the following line of mathematics: {x | (x2 − 2)(x − 1)(x2 + 1) = 0} = {1}. Reexamine the above equation carefully. Did our use of the equal sign give you pause? My guess is probably not — our previous intuition about the equal sign gives us a pretty good idea of what we mean when we write this statement. But as we are taking the time to carefully define lots of other notation, it is probably good to have an agreed-upon meaning for = when we talk about sets. Well, how would you define the notion of two sets being equal? What is the crucial criterion that makes two sets “the same”? After some pondering, you may settle on the idea that for the two sets to be the same, they should contain the same elements. Let’s state this precisely as follows: Definition 1.9. Let A and B be sets. We say A equals B when every element of A is an element of B and every element of B is an element of A. When A equals B we write A = B. When A does not equal B we write A ̸= B. (If X = Y , then certainly Y = X, right? Does this follow from our definition of =? ) This definition seems a bit unwieldy. But I assure you that it will come in handy when our sets are more complicated than just sets of numbers. There is a small bit of subtlety in our use of the equal sign in mathematics. Sometimes we use the equal sign to talk about two things (sets, numbers, etc.) being equal. For example, 28 = 7 × 4. Other times we use the equal sign to assign a label to a particular thing (set, number, etc.) For example, let f (x) = x2. In computer science the convention is to write := instead of = for this second use. Unfortunately this is not a widely adopted convention across other areas of mathematics. Equality isn’t the only way to relate to two sets, much in the same way the equality isn’t the only way to relate two numbers. You may be familiar with the following pieces of notation denoting relations between various sets. Definition 1.10. Let X and Y be sets. When every element of X is also an element of Y we say X is a subset of Y and Y is a superset of X. When X is a subset of Y we write X ⊆ Y or Y ⊇ X. When X is a subset of Y and X ̸= Y we say X is a proper subset of Y and we write X ⊂ Y or Y ⊃ X. 12 Example 1.11. Let A denote the set {0, 1, 2}. What are all of the sets that are a subset of A? What are all of the sets that are a proper subset of A? To determine this we look back at the definition of subset and proper subset. The set {1, 2, 4} is not a subset of A nor it is a proper subset of A. This set contains elements that are not elements of A. Whereas the set {1, 2} is a subset of A and is also a proper subset of A. As is the set {2}. On the other hand, {0, 1, 2} is a subset of A but not a proper subset of A. What about the empty set? For now we will take it to be true, by convention, that the empty set is a subset of every set. We will justify this in a later module. Take a moment now to list out the subsets of A. There are 8 of them. How many of these are proper subsets? Just as we can relate sets in a similar way to how we relate numbers, we can define operations for sets just like we have operations for numbers. Definition 1.12. Let X and Y be sets. The union of X and Y , denoted as X ∪ Y , is the set X ∪ Y = {x | x ∈ X or x ∈ Y }. The intersection of X and Y , written X ∩ Y , is the set X ∩ Y = {x | x ∈ X and x ∈ Y }. The Cartesian product of X and Y , written X × Y , is the set of all ordered pairs whose first element is from X and second element is from Y. That is, X × Y = {(x, y) | x ∈ X and y ∈ Y }. Aside. The Cartesian product is named for René Descartes. (17C France) Cartesian should sound familiar. The set R × R is the set of all ordered pairs where both elements are from R. This seems a lot like the Cartesian plane, which we often denote as R2. Often times when we think about operations we think of it as something to “do”. For example, from our experiences we would likely interpret “7 + 3” as “find the result when 3 things are added to 7 things”. This interpretation isn’t incorrect, but it is somewhat limiting. More broadly, “7 + 3” is a number. It is the same number as 10. This is why is would be correct to write 7 + 3 ∈ Z. The number represented by the symbols “7 + 3” is an integer. In all of mathematics we could replace the notation 10 with the notation 7 + 3 and nothing would change. 13 Look again at the definition of set union. The union of X and Y is a set. We can talk about its elements. We can use it in other operations. More often in this course (and beyond) it will be more helpful to think of X ∪ Y as set rather than an instruction. The same is true for set intersection. Aside. Recall our discussion in Example 1.7 about the mathematical meaning of the word “or”. Consider the sets {x ∈ N+ | x is divisible by 2} and {x ∈ N+ | x is divisible by 3}. In Example 1.7 we seemed to get at the idea that A = x ∈ N+ | x is divisible by 2 ∪ x ∈ N+ | x is divisible by 3 ,   but at the time we didn’t have the terminology and subsequent notation to express this idea. (The set A is defined as in Example 1.7) But now that we have an agreed-upon definition for set equality and set union we can verify that A = x ∈ N+ | x is divisible by 2 ∪ x ∈ N+ | x is divisible by 3.   But how do we verify such a thing? What would be deemed a valid verification? We will spend a lot of time in this class talking about proofs. Without going into too much details (for this early point in the course) we can consider a proof to be a justification of a mathematical fact. In this case our mathematical fact is A = x ∈ N+ | x is divisible by 2 ∪ x ∈ N+ | x is divisible by 3.   To justify that this is true, we can use our definition of equality for sets. (Take a moment now to go back and read it.) Let B = {x ∈ N+ | x is divisible by 2} and C = {x ∈ N+ | x is divisible by 3}. To convince our reader A = B ∪ C we must convince our reader that every element of A is an element of the set B ∪ C and every element of B ∪ C is an element of the set A. This is exactly what is meant by writing A = B ∪ C. We first convince our reader that every element of A is an element of the set B ∪C. Consider any element a ∈ A. Since a ∈ A, it is true that a is divisible by 2 or a is divisible by 3. If a is divisible by 2, then a is a multiple of 2 and so a ∈ B. If a is divisible by 3, then a is a multiple of 3 and so a ∈ C. In either case, we have a ∈ B ∪ C. Therefore every element of a is an element of B ∪ C. We now convince our reader that every element of B ∪C is an element of the set A. Consider any element d ∈ B ∪ C. Since d ∈ B ∪ C it is true that d is an element at least one of B or C. If d is an element of B, then d is a multiple of 2, and so must be divisible by 2. Thus we conclude that d ∈ A. Similarly, if d is any element of C, then d is a multiple of 3, and so must be divisible by 3. Thus we conclude that d ∈ A. In either case we see that d ∈ A. 14 Since every element of A is an element of B ∪ C and every element of B ∪ C is an element of A, then by definition of set equality we can conclude A = B ∪ C. We’ll come back to the structure of this argument at a later time. This is meant to be a first example of how a proof can look. What about set operations involving more than two sets? Unlike arithmetic, for which there is a default order of operations, there is not a universal convention for the order in which set operations are performed. And so we must use parentheses to let our reader know the order in which the operations of union and intersection should be done. For the Cartesian product we can make meaning of an expression with more than two sets as follows. Example 1.13. Points in three dimensions are often specified with a triple of real numbers (x, y, z), where x is the coordinate on the x-axis, y is the coordinate on the y-axis and z is the coordinate on the z-axis. We often refer to the set of all points as R3. Much as we can use the Cartesian product of sets to think about the Cartesian plane, we can use the Cartesian product to think about 3D space. Consider R × R × R. We didn’t explicitly define this, our definition of Cartesian product was the product of two sets. But our choice of notation is flexible enough that we would likely understand R × R × R to denote the set of ordered triples where each element is an element of R. Similarly, we can define the Cartesian product of any number of sets. Definition 1.14. Let k be a positive integer and let X1 , X2 ,... , Xk be sets. Denote by X1 × X2 · · · × Xk the set X1 × X2 × · · · × Xk = {(x1 , x2 ,... , xk ) | x1 ∈ X1 , x2 ∈ X2 ,... , xk ∈ Xk }. That is, X1 × X2 × · · · × Xk is the set of ordered k-tuples where the i-th element of the k-tuple is an element of Xi for each 1 ≤ i ≤ k. When X = X1 = X2 = · · · = Xk we write X1 × X2 · · · × Xk = X k. This definition might seem a little intimidating at first, but it is very similar to the definition of Cartesian product above. If we let k = 2 and write our this definition we get exactly our definition for Cartesian product above. Breaking down the definition into smaller pieces can also help with understanding: X1 × X2 · · · × Xk — this is the notation we use to refer to this set. (x1 , x2... , xk ) — this tells us that elements of this set are ordered k-tuples (like an ordered pair or an ordered triple, but with k parts instead of 2 or 3). x1 ∈ X1 , x2 ∈ X2 ,... , xk ∈ Xk — this tells us that the first element of this k-tuple (namely x1 ) is an element of X1 , the second element of this k-tuple (namely x2 ) is an element of X2 , and so on. 15 Example 1.15. Let A = {0, 1}, B = {7}, C = {cat, dog}. Then A × B × C = {(0, 7, cat) , (1, 7, cat) , (0, 7, dog) , (1, 7, dog)}, and A3 = {(0, 0, 0) , (0, 0, 1) , (0, 1, 0) , (0, 1, 1) , (1, 0, 0) , (1, 0, 1) , (1, 1, 0) , (1, 1, 1)}. With this notation it should now be clear why we use R2 to refer to the Cartesian plane — by definition we have R2 = R × R = {(x, y) | x, y ∈ R} Other things to think about You may notice that nothing in Module 1 requires one to “do mathematics” (such as performing computations or making algebraic derivations). These definitions and notations serve only our desire to communicate mathematical ideas with one another. Most of this notation was not standardized until the end of the 19th century. This fact is interesting for lots of reasons, chiefly among them is that the ideas of calculus were developed around two hundred years prior. It is only by way of modern mathematical conventions that today’s mathematicians are able to easily communicate with one another through research publications and presentations. For those with a background/interest in computing — certainly every programming language you have ever used can check for set equality. Can you devise a simple algorithm to check if two sets are equal? (... you had better hope your sets are finite!) For those with a background/interest in teaching — what would you tell a young student who wanted to make up and use their own symbols for numbers? Notice how =, ⊆, and ⊂ for sets seem reminiscent for =, ≤, and < for numbers. We can use < to define an ordering for numbers. Smaller numbers appear earlier in the ordering as compared to larger numbers. Can we define an ordering for sets using ⊂? What is an ordering, anyway? In this section we carefully defined equals (=) and subset (⊆) for sets. These definitions give us very specific criteria for when we may say two sets are equal or one set is a subset of another. Can you do the same for integers? That is, can you write down definitions of equals and less than that give specific criteria for when two numbers or equal or when one number is less than another? 16 Test Your Understanding 1. Recall that the odd numbers are... , −5, −3, −1, 1, 3, 5,.... Can you use set builder notation to express the set of odd numbers, and then use your definition to explain why 17 is indeed an odd number? 2. Recall our definition of Q, the set of rational numbers:   p Q= | p, q ∈ Z and q ̸= 0. q According to the definition above, is 17 a rational number? Why or why not? 3. Let A = {a1 , a2 , a3 , a4 }. (a) Can you give a proper subset of A that is not a subset of A? (b) Can you give a subset of A that is not a proper subset of A? 4. Let A = {x ∈ R | x ≥ 3} and B = {x ∈ R | x ≥ 18}. Can you describe the sets A ∪ B and A ∩ B, both in set notation and in plain English? 5. Let A = {1, 3, 5} and B = {7, 8, 9, 13}. Is it true that A ∪ B = {A, B}? 6. Consider the sets A = {1, 3, 5, 7, 9} , B = {2, 3, 4, 5}, and C = {1, 4, 7, 10}. List the elements in each of the following sets: (a) A ∪ B; (b) B ∩ C; (c) (A ∪ B) ∩ C; (d) A ∪ (B ∩ C). 7. Notice in the previous problem that (A ∪ B) ∩ C ̸= A ∪ (B ∩ C). Can you find examples of sets A, B, C where these two quantities are the same? 8. (a) Let A = {r, i, g, h, t} and B = {g, i, t}. Is it true that A ∪ B = A? And is it true that B ⊆ A? (b) Give an example of sets A and B (different from those in (a)) where A ∪ B = A. Is B ⊆ A also true for the sets in your example? (c) If you did (a) and (b) correctly, you are likely wondering if the following is in fact a mathematical fact: Let A and B be sets. If A ∪ B = A, then B ⊆ A. Can you explain in your own words why this statement is indeed true? 17 Test Your Understanding Solution 1. A possible answer is {x ∈ Z | x = 2y + 1 for some y ∈ Z}. This reads “The set of integers x where there is an integer y such that x = 2y + 1”. Using this definition, we can check that x = 17 is odd. Consider y = 8. Then 2y + 1 = 2 × 8 + 1 = 17. Since for x = 17, there is indeed an integer y where x = 2y + 1, it follows that x is indeed an odd number. An alternative description is {2y + 1 | y ∈ Z}. This reads “The set of numbers of the form 2y + 1 where y is an integer”. This is correct and equivalent to the above, and verifying that 17 is odd again comes down to finding y where 2y + 1 = 17. 2. Yes, 17 is rational. Given   p Q= | p, q ∈ Z and q ̸= 0 , q p 17 let p = 17 and q = 1. Then p, q are indeed integers, and q ̸= 0. Moreover, q = 1 = 17, and so 17 ∈ Q. Note that one could also have used (say) p = 1700 and q = 100 to certify that 17 is rational. (Aside: In addition to 17, what other numbers can be shown to be rational using the above argument?) 3. Given A = {a1 , a2 , a3 , a4 }, (a) This is not possible — every proper subset is a subset, and so there isn’t a proper subset that is not a subset. (This argument is akin to saying that since every poodle is a dog, there isn’t a poodle that is not a dog.) (b) The only example that would fit the description is the set A itself. Then A is a subset of A — every element in A is indeed in A! On the other hand, A is not a proper subset of A, so this gives the only subset that is not a proper subset. 4. We are given A = {x ∈ R | x ≥ 3} (i.e., the set of real numbers that are greater than or equal to 3) and B = {x ∈ R | x ≥ 18} (i.e., the set of real numbers that are greater than or equal to 18). Now, A ∪ B is the set of elements that is in A, or in B, or both. So for a number x ∈ R to be in A∪B, either x ≥ 3 or x ≥ 18. Since x ≥ 3 is the less restrictive condition here, we see that if x ≥ 3 then it’s in at least one of A and B. so we conclude that A∪B is the set of real numbers that are greater than or equal to 3. I.e., A ∪ B = {x ∈ R | x ≥ 3}. 18  Next, for A ∩ B, we want elements that belong to both A and B. What are the real numbers x where both x ≥ 3 and x ≥ 18 hold? Well, x ≥ 18 is the more restrictive condition here, and so when x ≥ 18, then x belongs to both A and B. Hence, we see that A ∩ B is the set of real numbers that are greater than or equal to 18. That is, A ∩ B = {x ∈ R | x ≥ 18}. (Did you notice that A ∪ B = A and A ∪ B = B in this case? Can you see what’s the “essence” behind this coincidence?) 5. We are given that A = {1, 3, 5} and B = {7, 8, 9, 13}, and would like to compare A ∪ B and {A, B}. By definition, A ∪ B is the set that contains elements that are in A, or in B, or both. Thus, A ∪ B = {1, 3, 5, 6, 7, 8, 13}. Next, {A, B} is the set that contains A and B as its two elements. Thus, {A, B} = {{1, 3, 5} , {6, 7, 8, 13}}. These two sets are not the same! A ∪ B contains seven elements, each of which is a number, while {A, B} contains two elements, each of which is a set. 6. Given A = {1, 3, 5, 7, 9} , B = {2, 3, 4, 5}, and C = {1, 4, 7, 10}, we see that (a) A ∪ B = {1, 2, 3, 4, 5, 7, 9}; (b) B ∩ C = {4}; (c) (A ∪ B) ∩ C = {1, 4, 7} (this is the intersection of our answer in (a) and the set C); (d) A ∪ (B ∩ C) = {1, 3, 4, 5, 7, 9} (this is the union of A and our answer in (b)). 7. It is possible! The easy way out is to define A, B, and C to be the same set. Then it’s rather obvious that (A ∪ B) ∩ C = A ∪ (B ∩ C). Another approach is to let A be the empty set. Then it’d work no matter what B and C are, because (A ∪ B) ∩ C boils down to B ∩ C, and A ∪ (B ∩ C) also boils down to B ∩ C. There are also examples where A, B, C are all distinct and non-empty. Can you think of one? 8. (a) Given A = {r, i, g, h, t} and B = {g, i, t}, we have A ∪ B = {r, i, g, h, t}. Notice that every element in A ∪ B is indeed in A, and that every element in A is indeed in A ∪ B. Hence, we do have A ∪ B = A. Also, since every element in B is in A, we also have B ⊆ A. 19 (b) To ensure that A ∪ B = A, we want to construct A and B such that, when taking the union, B does not contribute additional elements to A∪B that are not already in A. Thus, some examples that would work are Let A be {1, 2, 3, 4, 5} and B = {1, 2, 3}. Let A be the set of natural numbers, and let B be the set of positive even numbers. Let A be the set of all mammals, and let B be the set of all dogs. In all three cases, we have A∪B = A. And look, in all three cases, it also happens that B ⊆ A. (c) Having seen a few examples hinting at the general fact, we now try to convince ourselves that these examples above are not mere coincidences. That is, we want to construct an argument that shows that, whenever two sets A and B satisfy A ∪ B = A, it must also be the case that B ⊆ A. So let’s suppose we are given two sets A and B where A ∪ B = A. Now notice that for all sets A and B, it is always true that B ⊆ A ∪ B, because if an element is in B, then it is definitely also an element of A ∪ B (which contains elements from both A and B). So now we have B ⊆ A ∪ B. However, we were given that A, B satisfy A ∪ B = A. Since A ∪ B and A are identical sets, B ⊆ A ∪ B implies that B ⊆ A. Thus, we have shown that whenever A ∪ B = A, it always follows that B ⊆ A. 20 2 Sets and Functions Part II Learning Incomes. Material presented in Module 1 Exposure to the idea of a mathematical function. Familiarity with standard mathematical notation used in SK secondary-school courses Foundations of Mathematics 30 or Precalculus 30 Reading ability at a level at least that of an SK secondary-school graduate. Newly Defined Terms and Notation. function, domain, codomain, f : A → B, image, a pre-image, f (a), the pre-image, f −1 (b), range, range(f ), injection, surjection, bijection, operation, inverse, f −1. In Module 1 we saw an introduction to various notations and definitions for sets. From our work in the last module we should recognize the following ideas– Let A and B be sets. Each of the following are statements A=B A⊆B B⊆A A⊂B B⊂A Depending on what the sets A and B are, each of these statements are each either true or false. Whereas each of the following are sets A∪B A∩B A×B If A = {1, 7, 9} and B = {1, 7}, then A = B is false; A ⊆ B is false; B ⊆ A is true; A ⊂ B is false; and B ⊂ A is true. 21  A ∪ B = {1, 7, 9}; A ∩ B = {1, 7}; and A × B = {(1, 1) , (1, 7) , (7, 1) , (7, 7) , (9, 1) , (9, 7)}. Let us take a moment to return to Exercise 7 from Module 1. This exercise asked you to provide a proof for the following statement: Let A and B be sets. If A ∪ B = A, then B ⊆ A. In this context, a proof is written logical deduction that fully convinces a reader of the truth of the statement. This statement is making a claim about all possible pairs of sets, A and B. Thus, it is not enough to provide an example or two to fully justify that this statement is always true. We have seen two proofs in this course already – one in Aside 1.2 and one in Exercise 7. Let us consider, informally, how we might prove the above statement. We want to show that if some hypothesis holds, in this case A ∪ B = A, then our conclusion, namely B ⊆ A, holds. But of course these jumbles of symbols just correspond to sentences. Thus we should take a moment to remind ourselves what these symbols mean. Looking back at our definition for ∪ and =, the statement A ∪ B = A is exactly equivalent to the following statement: Every element that is in at least one of A and B is an element of A and every element of A is an element of at least one of A and B. This statement is not true for every pair of sets A and B; but it is only those pairs of sets that satisfy the hypothesis that we are interested in. Looking back at our definition of ⊆ we want to conclude that every element of B is an element of A. Okay, so how can we do this? Let us consider some element b ∈ B. We want to convince ourselves that, in fact, b ∈ A. From our hypothesis we know that every element that is in at least one of A and B is an element of A. Since b is an element of B, it is an element of at least one of A and B and thus is an element of A. Therefore b ∈ A. Thus no matter which element of B we chose, we can be sure that it is always an element of A. This is the same as saying B is a subset of A, which is what we were trying to prove. Now that we have convinced ourselves, the time has come to convince someone else. Un- fortunately, most written proofs strip away the extraneous detail and just focus on what is necessary. Theorem. Let A and B be sets. If A ∪ B = A, then B ⊆ A. Proof. Let A and B be sets so that A ∪ B = A. Consider b ∈ B. Since B ⊆ A ∪ B in general, we know that b ∈ A ∪ B. Now, by hypothesis, A ∪ B = A, and so we conclude that 22 b ∈ A. Thus, it follows that every element of B is an element of A, and we obtain B ⊆ A, as required. (Do you see that little box over there on the right? It is a convention in mathematics to write this little box at the end of a proof. This is a signal to the reader that the proof is done and the author expects them now to be convinced.) Depending on our expected reader, this proof is less than ideal. For someone who has just learned the meaning of all the different notation, this proof would be very difficult to read. On the other hand, for someone who is very comfortable with the notation, this proof has all of the necessary detail. We turn now to the main matter of Module 2: functions. We have spent years getting comfortable with the notation and terminology around functions like f (x) = x2. It turns out that these notations and terminology are flexible enough that we can use them for functions where the input and output may not even be numbers. Our goal in this module is to develop notation and terminology for functions. Of course, we first need to agree on what a function is! 23 2.1 Functions Our intuition around functions is likely some sense of “assigning”. That is, a function assigns a value (an output) to each input. A function, then, in some sense, can be considered to be a set of pairs: the input and the assigned output. Consider the following set A = { z, z 2 | z ∈ R}
Using our notation from the previous module we notice A ⊆ R × R — if we recall our definitions of the notation ⊆ and the notation × for sets, we should be convinced that every element of A is an ordered pair whose first entry is from R and whose second entry is from R. (If you are not easily convinced, then you should go back to Module 1 and re-read the corresponding definitions. This should not suggest you have done something wrong in your learning. We will spend lots of time in this course referring to concepts and definitions from previous modules.) The set A has many elements. Let us examine some of them. (0, 0) ∈ A as 0 ∈ R and 0 = 02 (−3, 9) ∈ A as −3 ∈ R and 9 = (−3)2 √ √ √
2
2.1, 2.1 ∈ A as 2.1 ∈ R and 2.1 = 2.1 With not a lot of thought we should be able to convince ourselves that the elements of A are exactly the points of the parabola f (x) = x2. Similarly, we can construct such a set for any function. For example consider g(x) = sin(x). The set of points of this curve are exactly the points in the set {(x, sin(x)) | x ∈ R} Let us consider another example. Let S be the set of students registered in MATH163 and consider the set {(s, g) |s ∈ S and g is the grade that student s gets in MATH163.} Aside.... this set doesn’t exist yet. Your grade in the course is far from determined! Much like our set representation for f (x) = x2 we have a set of ordered pairs in this set. In this case the ordered pair has a student as its first entry and that student’s grade as the 24 second entry. Much like our function f (x) = x2 we can consider the second entry in the ordered pair to be “assigned” to the first entry. With these examples in mind, we define a function as follows. Definition 2.1. Let A, B and f be sets. We say f is a function from A to B when f is a subset of A × B in which each element of A appears as the first entry of an ordered pair exactly once. When f is a function from A to B we write f : A → B. We say that A is the domain of f and that B is the codomain of f Aside. Let us parse the structure of this definition one part at a time: Let A, B and f be sets. – This sentence tells us the names of the objects we will need to define our new term. We say f is a function from A to B – The underlined part is the new term we are defining. when f is a subset of A × B in which each element of A appears as the first entry of an ordered pair exactly once. – This is what we mean when we use our newly defined term. Our new term is shorthand to express this idea. In other words, this is the criteria that the set f must satisfy so that we may call it a function. When f is a function from A to B we write f : A → B. – This sentence gives us a piece of notation to go along with our new definition. The piece of notation is shorthand for the underlined term in the second part. We say that A is the domain of f and that B is the codomain of f – Our new definition has a second definition hiding inside! The ordered pairs in f tell us which element of the codomain is assigned to each element of domain. To ensure that each element of A is assigned exactly one element of the codomain, we required that every element of A appears as the first entry of an ordered pair exactly once. Notice that we have no restriction on how many times an element of the codomain can appear. For instance, for f (x) = x2 we are okay with having (2, 4) ∈ f and (−2, 4) ∈ f. Let us consider some examples. Example 2.2. First we consider the notion of functions with which we are likely intimately familiar: functions from R to R. Consider the line y = 2x. Every point on this line is of the form (x, 2x) and all points of the form (x, 2x) appear on the line. 25 Consider the set f = {(x, 2x) | x ∈ R}. We notice that for any particular z ∈ R, the number z only appears in a single ordered pair: the ordered pair (z, 2z). For example, the real number 11 only appears as the first entry of the ordered pair (11, 22). 11 appears as the first entry of no other element of f. Thus this set fulfills our definition of f is a function from R to R. Example 2.3. Let A = {1, 7, 9}, B = {1, 7, 9, 10} and f = {(1, 7) , (7, 7) , (7, 9) , (9, 9)} Using our new definition of function we can ask: is f a function from A to B? Let us read the definition of function one part at a time: Let A, B and f be sets. – This is true. Certainly A, B and f are sets. f is a subset of A × B – This is true; every element of f is an element of A × B as each element is an ordered pair which as its first entry from A and its second entry from B. each element of A appears as the first entry of an ordered pair exactly once. – This is false; 7 appears as the first entry of an ordered pair twice. Both of (7, 7) are (7, 9) elements of f. The set f does not satisfy the definition of function from A to B and so we cannot say that f is a function from A to B. Exercise 2.4. Let A = {1, 7, 9}, B = {1, 7} and f = {(1, 7) , (9, 9)} Is f a function from A to B? In these last two examples our sets were named A, B and f to make it easy to think about the definition of a function. Most of the time the labels of our objects (sets, functions, etc.) will not match the labels that are used in the definition. Example 2.5. Let n a  a o a h= , b | ∈ Q and b is in lowest terms. b b For example, ( 12 , 2) ∈ h, but ( 12 , 3) ∈ 2
/ h and 4 ,2 ∈ / h. Can we say that h is a function from Q to Z? We appeal to our definition with Q playing the role of the domain, Z playing the role of the codomain and h playing the role of f. 26 Each of Q, Z and h are sets. Elements of h are ordered pairs, where the first element is a rational number in lowest terms and the second element is an integer. The  set h contains every ordered pair of this form. For any y ∈ Q in lowest terms, we have xy , y ∈ h. Thus x we see h a function from Q to Z. Let us return back to familiar territory with the function f (x) = x2. Quite likely we un- derstand the notation f (7) = 49. Put in terms of our new definition of a function, this is equivalent to saying (7, 49) ∈ f. As every function can be represented as a set, we can extend our use of this piece of notation for any function. Definition 2.6. Let A and B be sets and let f be a function from A to B. For (a, b) ∈ f we say b is the image of a and a is a pre-image of b. When b is the image of a we write f (a) = b. Example 2.7. Let h : Q → Z be the
function given
in Example 2.5. Let us apply our 4 4 definition of image to the element 9 , 9 ∈ h. Since 9 , 9 ∈ h we can say that 9 is the image of 49 and we can write h 94 = 9.
Exercise 2.8. Let A = {1, 7, 9}, B = {1, 7, 9, 10} and f = {(1, 7) , (7, 7) , (9, 1)} Which element of B is f (7)? Does it makes sense to talk about f (15)? Our definition of function requires that each element of A appear as the first entry in exactly one ordered pair of f. Thus for each a ∈ A the notation f (a) has unambiguous meaning; f (a) is the element of B so that the pair (a, f (a)) is an element of f. Example 2.9. Let S be the set of students in MATH163. Let N = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Let q be the function from S to N so that q(s) is the first entry in the student number of student s. In this case we can see that we can use our definition and corresponding notation to fully specify a function. By writing “... so that q(s) is the first entry in the student number of student s.” we are describing the set q = {(s, n) | s ∈ S and the first entry of the student number of s is n}. Describing q as the function so that q(s) is the first entry in the student number of student s is a lot easier than asking our reader to parse the jumble of notation we need to describe q using set-builder notation. 27 We can give all of the information about a function by stating its domain, its codomain and the image of each element of the domain. This is what we are doing when we write something like: let f : R → R so that f (x) = 2x + 3. By convention we understand this statement of notation to mean: let f be the function from R to R so that the image of an element x ∈ R is 2x + 3. This is equivalent to writing let f be the function from R to R so that f = {(x, 2x + 3) |x ∈ R} Let us return to the familiar ground of f (x) = x2. How do we interpret the notation f −1 (7)? Perhaps the word inverse or pre-image slipped past our mental lips as we read that last sentence? (It is okay if it didn’t!) Aside. Are you bothered by the fact that we didn’t specify a domain and codomain for f (x) = x2 ? From our shared experiences in mathematics we likely understood the domain to be R and the codomain to be R. Remember – all of these tools we are developing are to ease communication. If we are certain that our reader will understand what we mean, then we may not need to be so precise. Definition 2.10. Let A and B be sets, let f be a function from A to B and let b be an element of B. The pre-image of b is the set {a ∈ A | f (a) = b}. We denote this set as f −1 (b). Let us pick apart this definition one sentence at a time: Let A and B be sets, let f be a function from A to B and let b be an element of B. – This sentence sets up the rest of the definition. It tells us about the mathematical objects we will need to define our new term. The pre-image of b is the set {a ∈ A | f (a) = b}. – This sentence tells us the term that we are defining. For some particular b ∈ B the pre-image of b is defined to be the set of all elements of A that have b as their image. We denote this set as f −1 (b) – This sentence gives us a piece of notation to use for our new definition. When we see the symbols f −1 (b) we should say “the pre-image of b”. Aside. Look at all of the things that we need to understand before we can understand the meaning of the notation f −1 (b). We need to know what a set is. We need to know the definition of a function. We need to know about set builder notation. We need to know the meaning of the symbol f (a). We think of functions and related things to be relatively straight-forward ideas and they are. 28 But trying to precisely define these concepts takes work! However, there is a payoff: we are developing a shared vocabulary. Furthermore, you are sharing this vocabulary with fellow students and mathematicians throughout the (Western) world! The standardization of these notations is a relatively recent occurrence in the history of mathematics. It is only in the last hundred years or so that these notations have become standard. In fact, it isn’t really true to say that all of this notation is standard. For example, just as some people exclude 0 from N, so too do some use the symbol ⊊ to mean proper subset. There is nothing inherently correct or incorrect about these choices. They are just standards that make it easier for us to communicate. When we read a definition that we don’t understand, a usual reason is that we don’t yet understand all of the meanings of the words in the definition. As we grapple with new definitions we will need to backtrack at times to remember the proscribed meanings of all of the words in our new definition. Aside. In Definition 2.6 we defined a pre-image and in Definition 2.10 we defined the pre- image. These ideas are related. A pre-image is an element of the domain. The pre-image is a set of elements of the domain. Articles matter! Example 2.11. Let f : R → R so that f (x) = x2. The notation f −1 (49) denotes the set of all elements of R whose image is 49. We notice 72 = 49 and (−7)2 = 49 and so f −1 (49) = {−7, 7}. Example 2.12. Let S be the set of students in MATH163. Let N = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Let q be the function so that q(s) is the first entry in the student number of student s. Looking at my class list, I see that no student in MATH163 has a student number that begins with 0. The set {s ∈ S | q(s) = 0} contains no elements. This set is the empty set. We can express this idea much more compactly by writing: q −1 (0) = {}. Our definition of function requires that we specify a domain and a codomain. There is nothing in the definition of function that requires that every element of the codomain be the image of some element of the domain. We saw this in Example 2.12. Thus we can consider the set of elements of the codomain that appear as the image of some element of the domain. Definition 2.13. Let A and B be sets and let f be a function from A to B. The range of f , denoted range(f ), is the set of elements of B that are the image of some element of A. That is, we have range(f ) = {f (a) ∈ B | a ∈ A} We should understand the range of a function to be the set of all elements of the codomain that appear as an image of an element in the domain. √ Example 2.14. Let f : N → R so that f (x) = x. Though the codomain of f has been 29 defined to be the set of all real numbers, not every real number is the square root of some natural number. Here, the set range(f ) is the set of all numbers that are a square root of some natural number. Exercise 2.15. Let A = {1, 7, 9} and let f be the function from A to A so that f (1) = 1 and f (7) = 9 and f (9) = 9. What elements are contained in range(f )? Exercise 2.16. Let f : Z → R so that f (x) = 2x + 1. What is range(f )? And if we change the domain from Z to R, how does this change the range? Example 2.17. Continuing with Example 2.12. Since q −1 (0) = {}, there is no element s ∈ S so that q(s) = 0. Thus 0 ∈ / range(q). In fact, every student in this course has a student number that begins with 1. Therefore range(q) = {1}. Let us use some of our new notation and terminology to prove a mathematical fact: Theorem. Let A and B be sets. If f : A → B and g : A → range(f ) so that g(a) = f (a) for each a ∈ A, then for each b ∈ range(f ) we have g −1 (b) ̸= {}. Yikes! Let us parse this one part at a time. We start with our hypothesis: If f : A → B and g : A → range(f ) so that g(a) = f (a) for each a ∈ A, We are imagining the existence of these two functions, f and g, that satisfy the following: f has domain A and codomain B; g has domain A. The codomain of g is the set of elements of B that are the image of some element of a with respect to the function f. the image of an element of A with respect to the function g is the same as the image with respect to the function f. And now the conclusion: then for each b ∈ range(f ) we have g −1 (b) ̸= {}. We want to show that each element of range(f ) satisfies the following: the pre-image of the element is not the empty set. That is, for each b ∈ range(f ) there is an element of a so that g(a) = b (It may help you to work through this notation with a particular function f. Let A = {1, 7, 9} and B = {1, 2, 3, 4, 5, 6, 7}. Let f (1) = 2, f (7) = 2 and f (9) = 6. 30 Use the definition of range(f ) to determine what elements are contained in range(f ). What ordered pairs are contained in the set g? Use the definition of pre-image to determine elements are in the set g −1 (2).) To prove our mathematical fact we assume our hypothesis is true and try to conclude that our conclusion is true. Consider some element b′ ∈ range(f ). We want to conclude that g −1 (b′ ) is not the empty set. That is, we want to convince ourselves that there is an element of a′ ∈ A with the property that g(a′ ) = b′. Let us remember what it means for b′ to be an element of range(f ): since b′ ∈ range(f ) there exists a′ ∈ A so that f (a′ ) = b′. Since we assumed our hypothesis is true, we know that g(a′ ) = f (a′ ). Since f (a′ ) = b′ we know that g(a′ ) = b′. Thus a′ ∈ g −1 (b′ ). Which in turn implies that g −1 (b′ ) ̸= {}. Let us compact our reasoning into a proof. Proof. Let A and B be sets. Let f : A → B and g : A → range(f ) so that g(a) = f (a) for each a ∈ A. Consider b′ ∈ range(f ). Since b′ ∈ range(f ) there exists some a′ ∈ A so that f (a′ ) = b′. Since f (a) = g(a) for each a ∈ A it follows that g(a′ ) = b′. Thus a′ ∈ g −1 (b′ ). 31 2.2 Injections, Surjections and Bijections Consider all of the numbers on the number line. We call this set R. Some of these numbers have interesting properties. For example, the set of integers, Z, is the subset of the set of real numbers consisting of those real numbers that have no decimal part. The set of rational numbers, Q, is the subset of the real numbers that can be represented as a ratio of two numbers in Z. Much as we can consider sets of real numbers that have notable properties, so too can we think about particular functions that satisfy notable properties. Let A = {1, 4, 9} and B = {1, 7}. There are many different functions from A to B. (We will count them another day!) Some of these functions have their range equal to their codomain. For example, the function from A to B given by {(1, 7) , (4, 1) , (9, 1)} has codomain equal to {1, 7} and range equal to {1, 7}. Whereas the function {(1, 7) , (4, 7) , (9, 7)} does not have this property. Definition 2.18. Let A and B be sets and let f be a function from A to B. We say f is a surjection when range(f ) = B. When f is a surjection we say that f is surjective. Notice that if a function is a surjection, then the pre-image of every element of the codomain contains at least one element. Consider the function f : R → R so that f (x) = 2x + 1. This function has the extra property that the image of each element of the domain is unique; no two elements of the domain have the same image. That is, if x1 ̸= x2 , then f (x1 ) ̸= f (x2 ). On the other hand, the function f : R → R so that f (x) = x2 does not have this property We can notice f (−7) = f (7). Definition 2.19. Let A and B be sets and let f be a function from A to B. We say f is an injection when each element of the domain has a unique image. When f is an injection we say that f is injective. Notice that if a function is an injection, then the pre-image of every element of the codomain contains at most one element. Exercise 2.20. Let A = {1, 4, 9} and B = {1, 7} be sets. Can you find a function from A to B that is both an injection and surjection? Can you find a function from A to A that is both an injection and a surjection? 32 Definition 2.21. Let A and B be sets and let f be a function from A to B. We say f is a bijection when f is both an injection and a surjection. When f is an bijection we say that f is bijective. Exercise 2.22. Let A and B be sets and let f be a bijection from A to B. Is it possible for the pre-image of some element of B to contain no elements? Is it possible for the pre-image of some element of B to contain two elements? Aside. You might recognize the terms “one-to-one” and “onto” rather than the terms “injec- tive” and “surjective”. These terms are not incorrect to use, but they can cause confusion as literature that uses “one-to-one” for injective also tends to use “one-to-one correspondence” for a bijection, which can cause a mix-up. Also, the word “surjection” is particularly interesting. In French the word “sur” means “on top” or “above”. In a surjection we can imagine the elements of the domain sitting on top and covering up all of the elements of the codomain. 33 2.3 Operations Just as we have spent years of our mathematical lives talking about examples of functions without having to grapple with the definition of a function, so too have we used the word operation. In this section we grapple with a definition for this term. Consider the function f : N+ × N+ → N+ given by n X f ((n, m)) = m 1 For example, 3 X f ((3, 4)) = 4 = 4 + 4 + 4 = 12 1 and 2 X f ((2, 9)) = 9 = 9 + 9 = 18 1 (Are you confused by the symbol Σ? Do an internet search for sigma notation.) We observe f ((n, m)) = n · m for every n, m ∈ N+. Multiplication of positive integers is a function! We have spent years talking about addition and multiplication as operations. We now have the tools to define what we mean by the word operation in mathematics. Definition 2.23. Let A be a set. An operation on A is a function f : A × A → A. Our definition of operation is very broad, but we can see how operations that we know about nicely satisfy this definition Example 2.24. Let a : R × R → R so that a((a1 , a2 )) = a1 + a2. The function a is an operation. We usually call this function addition. Notice that there is nothing in the definition of operation that requires us to specify a particular symbol (e.g., · for multiplication) to denote our operation — we use these symbols due to ease of reference. It is much easier to define the symbol · and write 7 · 9, then it is to define the function f as above and consider f ((7, 9)). And so commonly used operations sometimes are associated with a symbol. 34 In your past study of lines and curves in R2 you may have encountered the idea of function composition. Definition 2.25. Let A, B and C be sets so that f1 : A → B and f2 : B → C. Then the composition of f2 and f1 is defined to be the following function: f2 ◦ f1 = {(a, f2 (f1 (a))) |a ∈ A}. The function f2 ◦ f1 has domain A and codomain C. This definition is a great example of how strictly adhering to our agreed upon notation can make things quite confusing! In this function, ordered pairs are of the form: (a, f2 (f1 (a))) That is, for a ∈ A we have (f2 ◦ f1 ) (a) = f2 (f1 (a)). We find the image of a by finding its image with respect to f1. And then taking that image and finding its image with respect to f2. We may understand composition a little better with the following picture: f2 ∘ f1 a f1 c = f2(b) = f2 ( f1(a)) f2 b = f1(a) A B C Aside. There is nothing wrong with appealing to a picture to help make a point more clear. However you should not depend on your picture to tell the entire story. For every picture there should be sentences explaining it! Example 2.26. Let A = {1, 4, 9}, B = {1, 7, 15} and C = {11, 14, 21, 29, 30}. Consider the functions f : A → B so that f = {(1, 7) , (4, 1) , (9, 1)}, and g : B → C where g = {(1, 11) , (7, 29) , (15, 21)}. 35 The function g ◦ f : A → C is then given by: g ◦ f = {(1, 29), (4, 11), (9, 11)}. Since g◦f is the name of a function we can meaningfully write statements such as (g ◦ f ) (9) = 11. This section is supposed to be about operations. And so we wonder if ◦ is an operation as we have defined the term above. Answering this question is... tricky and may depend on what the actual sets A, B and C are. We’ll back away slowly from this wondering and leave it for another time. Instead we consider another example of function composition. Exercise 2.27. A = {1, 4, 9} B = {1, 7, 15} and consider the functions f1 : A → B and f2 : B → A so that f1 = {(1, 7) , (4, 15) , (9, 1)} and f2 = {(7, 1) , (15, 4) , (1, 9)} Do you notice anything interesting about the functions f1 ◦ f2 and f2 ◦ f1 ? Let A and B be sets and let f be a bijective function from A to B. Since f is a bijective function, for each b ∈ B the set f −1 (b) contains a single element. Let g be the function from B to A so that g(b) is the unique element of a ∈ A such that f (a) = b. Consider now the function g ◦ f. By definition we see that the domain of g ◦ f is A and the codomain of g ◦ f is A. By definition we see that for any a ∈ A we have g ◦ f (a) = g(f (a) = a. Thus we notice that with respect to the function g ◦ f , the image of every element is itself! This seems particularly noteworthy, so let’s give this phenomenon a name. Definition 2.28. Let A and B be sets, let f be a bijective function from A to B and let g be a function from B to A. We say g is the inverse of f when (g ◦ f ) (a) = a for every a ∈ A. When g is the inverse of f we may label g as f −1. To better understand this definition, let us consider an example to try to get a handle on what it means. Example 2.29. Continuing from Exercise 2.27 we see f1 ◦ f2 = {(1, 1), (7, 7), (15, 15)} and f2 ◦ f1 = {(1, 1), (4, 4), (9, 9)} 36 By applying our definition we see: f2−1 = f1 and f1 = f2−1. Look again at the elements of the functions f1 and f2. The ordered pairs in f1 are reversed in f2. This is a much better way to think about the meaning of inverse function. Exercise 2.30. Let A = {1, 2, 3, 4, 5} and let B = {a, b, c, d, e} so that f (k) is the k-th letter of the alphabet. What is f −1 (c)? What pairs are contained in the set f −1 ? Exercise 2.31. If you have seen the idea of function inverse before, is this very precise definition equivalent to your previous understanding of the term? Looking back at the notes from above, we notice that we have assigned two different meanings to the notation f −1 (b). In Definition 2.10 we said that f −1 (b) is a set. Whereas in Definition 2.28 we defined it to be a single element. As much as we want to believe that mathematics may be accessing some sort of higher truth about the universe, we can’t escape the foibles of our own humanity. When we use the notation f −1 (b) we are expecting our reader to know from context which version of the notation we mean, much like when we use homonyms and homophones in written and spoken language. Exercise 2.32. Let A and B be sets and let f : A → B be a bijection. Is f −1 is a bijection? Is it true that (f −1 )−1 = f ? Aside. A common point of confusion for students of all stripes is that the following three pieces of notations denote three different functions: sin−1 (x), sin(x)−1 , and sin(x−1 ). The first of these denotes the function that is the inverse of the function sin(x). This function 1 is sometimes called arcsin(x). The second of these denotes function sin(x) , which is usually 1
referred to as csc(x). And the third of these denotes the function sin x. The root of the confusion is that the “superscript −1” is sometimes used to denote “inverse of a function” (as in the arcsin(x) case), and in other cases it means “reciprocal of a real number”. How did a bunch of supposedly very smart people settle upon this rather confusing notation? Well, let us try to convince you that “reciprocal of a real number” is in fact some kind of inverse function. Consider f : R → R where f (x) = 7x. Now, what’s the inverse function f −1 ? It’s not hard to see that f −1 (x) = x7. So when f multiplies an input by 7, the inverse function — the mechanism that “undoes” f — multiplies the input by the reciprocal of 7. 37  1 Thus, we can think of 7 as the multiplicative inverse of 7, and so it’s semi-reasonable to denote 17 as 7−1. Again, despite our best efforts, communicating mathematics is not easy. But with experience, we develop the helpful hunches that can make it easier for us to understand things, even when they are less-than-perfectly expressed. 38 Other things to think about For those interested in pure mathematics: At some point you may be tempted to write down the following: Let A be the set of all sets. That is, let A = {B | B is a set}. As A is seemingly a set, we have A ∈ A. On the face of it, this isn’t terribly unrea- sonable, but it is a bit odd. Though a little unnatural, letting a set be a member of another set doesn’t seem to cause any immediate trouble. However, consider the set X = {B | B ∈ / B}. The set X contains all sets B that do not have themselves as members. Our set A from above would not be an element of X. Is X an element of X? If X is an element of X, then X must satisfy the criteria X ∈ / X. Hmmm. Similarly, if X ∈/ X, then X must not satisfy the criteria X ∈ / X. Again we are troubled. We have that X ∈ X if and only if X ∈ / X. This phenomenon is called Russell’s Paradox. It is named after philosopher Bertrand Russell (1872 - 1970). Attempting to resolve this paradox forces us to come up with a precise definition of what we mean by set. This topic is well beyond the scope of this course, but is something the consider! 39 Test Your Understanding 1. Let A = {1, 2, 3, 4} and B = {a, b, c, d}. Determine if each of the following is a function from A to B. (a) f1 = {(1, d), (2, d), (3, d), (4, d)}, (b) f2 = {(a, 1), (b, 2), (c, 3), (d, 4)}, (c) f3 = {(1, a), (1, b), (1, c), (1, d)}, (d) f4 = {(4, c), (2, b), (3, a), (1, d)}. 2. Let A be the set of all current professors at the U of S, and let B be the set of all current students at the U of S. (a) Define the set f = {(a, b) | b is taking a class from a this semester}. Do you expect f to be a function from A to B? Why or why not? (b) Define the set g = {(b, a) | b is taking a class from a this semester}. Do you expect g to be a function from B to A? Why or why not? 3. Let S = {1, 2, 3, 4, 5, 6}, and let f : S → S be the function f = {(1, 2), (2, 4), (3, 6), (4, 2), (5, 4), (6, 6)}. (a) What is the domain, codomain, and the range of f ? (b) What is f −1 (3), the pre-image of 3? (c) What is f −1 (4), the pre-image of 4? (d) Is f injective, surjective, and/or bijective? Can you explain why? (e) Let g = f ◦ f. List the elements of g. 4. (a) Consider the function f : R → R where f (x) = 2x. Is f injective, surjective, and/or bijective? Can you explain why? And if f is bijective, can you find the inverse function f −1 ? (b) Consider the function g : Z → Z where g(x) = 2x. Is g injective, surjective, and/or bijective? Can you explain why? And if g is bijective, can you find the inverse function g −1 ? 5. Consider the operation f : Z × Z → Z such that f ((x, y)) gives the maximum of the two integers x and y. Is f injective, surjective, and/or bijective? Can you explain why? 40 Test Your Understanding Solution 1. With A = {1, 2, 3, 4} and B = {a, b, c, d}, (a) f1 = {(1, d), (2, d), (3, d), (4, d)} is indeed a function from A to B. Each element from A shows up as the first element of an ordered pair in f1 exactly once, and the second element of the ordered pairs all belong to B. In fact, this is the function that assigns all elements in A to the element d ∈ B. (b) f2 = {(a, 1), (b, 2), (c, 3), (d, 4)} is not a function from A to B, because f2 is not a subset of A × B. (However, one can check that f2 is a function from B to A.) (c) f3 = {(1, a), (1, b), (1, c), (1, d)} is not a function from A to B. The element 1 ∈ A appears in multiple ordered pairs, while other elements in A do not appear in any. (d) f4 = {(4, c), (2, b), (3, a), (1, d)} is indeed a function from A to B, for the same reason mentioned in (a). 2. (a) Recall that, for f ⊆ A × B to be a function from A to B, every element in A is assigned one element from B under f. Thus, the set f described here is most likely not a function from A to B, since there’s got to be a professor who teaches multiple students in the same term. Some professors might also be not teaching any courses (and thus students) this current term. (b) For the same rationale, g is also unlikely to be a function from B to A, since many students take courses from multiple professors in a given term. Moreover, there are probably also current students who are not taking any courses in a given term. 3. We are given S = {1, 2, 3, 4, 5, 6}, and the function f : S → S where f = {(1, 2), (2, 4), (3, 6), (4, 2), (5, 4), (6, 6)}. (a) We are given that f : S → S, and so both the domain and codomain of f are S. On the oher hand, the range of f is the set of elements in the codomain (i.e., S) that is assigned some element in the domain. Going through the elements of f , we see that the range of f is {2, 4, 6}. (b) To find f −1 (3), we want the elements s ∈ S where (s, 3) ∈ f. However, we see that none of the ordered pairs in f has 3 as the second element. So we conclude that f −1 (3) = {}, the empty set. (f −1 (3) being the empty set also follows from the fact that 3 is not in the range of f , as shown above.) (c) To find f −1 (4), we want the elements s ∈ S where (s, 4) ∈ f. We see that s = 2 and s = 5 qualify. Thus, f −1 (4) = {2, 5}. (d) f is not injective. We saw above that f (2) = f (5) = 4, so it is not true that every input in f is assigned a unique output. f is also not surjective — we saw above 41  that f −1 (3) = {}, so there are no element s ∈ S where f (s) = 3. Finally, since f is neither injective nor surjective, it is not bijective. (e) We can find the elements of g = f ◦ f by determining g(s) for every s ∈ S. (Note: This is manageable due to S being a set with only 6 elements. For a larger set, it is likely that we’d have to describe the composite function analytically rather than listing its elements exhaustively.) Notice that g(1) = f (f (1)) = f (2) = 4. Thus, (1, 4) ∈ g. Likewise, g(2) = f (2(2)) = f (4) = 2, and so (2, 2) ∈ g. Proceeding this way, we obtain that g = {(1, 4), (2, 2), (3, 6), (4, 4), (5, 2), (6, 6)}. 4. (a) For f : R → R where f (x) = 2x, we see that f is injective: If x ̸= y, then 2x ̸= 2y, and so f (x) ̸= f (y). Does, f indeed maps distinct inputs to distinct outputs. f is also surjective: Given x ∈ R, x2 must also be a real number, and we see that f x2 = 2 x2 = x. Thus, every x ∈ R is the image of some element. Since f is

both injective and surjective, f is bijective. Since f is bijective, it has an inverse function. From the analysis above, it is relatively easy to see that f −1 (x) = x2 is the inverse function of f. (b) For g : Z → Z where g(x) = 2x, we see that the same argument for why f is injective above also shows that g is injective. On the other hand, g is not surjective: Notice that 1 ∈ Z, but there does not exist x ∈ Z where g(x) = 1. Hence, g is not bijective, and thus does not have an inverse function. (Aside: Notice that while f and g have the same formula, the two functions have some fundamental differences due to the restriction of their domain and codomain.) 5. f is not injective: Notice that f ((1, 2)) = 2 (since 2 is the maximum element between 1 and 2). On the other hand, f ((2, 1)) = 2 as well. Now we found two distinct elements (1, 2) and (2, 1) that have the same output under f , and so f is not injective. (Aside: Recall that (1, 2) and (2, 1), both elements of the Cartesian product Z × Z, are ordered pairs, and thus are distinct. Don’t confuse them with {1, 2} and {2, 1}, which are the same since they are sets and the order of elements does not matter in that case.) Next, we argue that f is surjective. Given any x ∈ Z, notice that f ((x, x)) = x (because the maximum between x and x is x). Thus, every x ∈ Z is in the image of f. (In fact, the pre-image of every x ∈ Z has infinitely many elements!) Since f is not injective, we conclude that f is not bijective. 42 3 Relations Part I Learning Incomes. Comfort with notation for sets, particularly set builder notation and Cartesian product Learning Outcomes. Familiarity with broad idea of what a relation is Ability to decide if a set is a relation Ability to decide if a relation is: reflexive, antireflexive, symmetric, antisymmetric or transitive Ability to decide if a relation is a partial order Ability to decide if a relation is a graph Ability to give examples of relations that satisfy one or more of the following properties: reflexive, antireflexive, symmetric, antisymmetric , transitive, partial order, graph Newly Defined Terms and Notation. relation, power set, reflexive relation, antireflexive relation, symmetric relation, antisymmetric relation, transitive relation, partial order, graph. In the previous module, we characterized some familiar mathematical terms such as functions and operations by defining them in terms of sets. For instance, we saw that a function f from set A to set B is a subset of A × B with certain properties, and that an operation is a function (and thus it is a set). In this section, we continue this quest and look into what a relation really is. You are not going to believe this, but it is also a set. Definition 3.1. Let A, B be sets. We say R is a relation from A to B if R is a subset of A × B. We use the notation aRb to denote (a, b) ∈ R, and say that a is related to b. Example 3.2. Let A be set of all students at the University of Saskatchewan, and B be the set of mathematics courses being offered this term. Then the set R = {(a, b) | student a is enrolled in course b}. is a relation from A to B. Notice that a relation from A to B is simply any subset of A × B. On the other hand, a function from A to B not only has to be a subset of A × B, but also has the additional property that for every a ∈ A, there exists exactly one b ∈ B where (a, b) ∈ f. Thus, we see that every function is a relation, but the opposite is not true. In a function from A to 43 B, each a ∈ A is assigned to exactly one element in B. On the other hand, in a relation R, each a ∈ A can be related to zero, one, or many elements in B. For the rest of this module, we will focus on relations that relate elements within a set (instead of between two distinct sets). Given a set S we say that R ⊆ S × S is a relation on S. Just like with functions, for any set S there are many different relations on S. And just as we saw with injective, surjective and bijective functions, some of these relations have particularly interesting properties. For an example, consider the following subset of Z × Z: R1 = {(n1 , n2 ) | n2 − n1 ∈ N}. What are some elements of this set? For example, we have (1, 2) ∈ R1 as 2 − 1 = 1 and 1 ∈ N. More generally, notice that (1, n2 ) ∈ R1 whenever n2 − 1 ≥ 0, or equivalently n2 ≥ 1. So things like (1, 1), (1, 2), (1, 3),... are in R1. Likewise, notice that (n1 , 2) ∈ R1 when 2 − n1 ≥ 0, which happens exactly when n1 ≤ 2. Thus, R1 contains the ordered pairs (2, 2), (1, 2), (0, 2), (−1, 2),... and such. Let us draw a picture to gain some more intuition. In the diagram below, we draw an arrow from n1 to n2 when (n1 , n2 ) ∈ R1. ··· −2 −1 0 1 2 ··· We have only included integers from −2 to 2 in order to save space. As there are infinitely many integers, it would be impossible to draw this picture with all of the integers and the corresponding arrows! Hopefully, by now you have noticed that we have (n1 , n2 ) ∈ R1 exactly when n1 ≤ n2. With this set in hand, we never need to use the ≤ sign ever again! Instead of writing 9 ≤ 10 we can write (9, 10) ∈ R1 ! Of course at this point you wonder, “why would I ever want to do this?” The answer is that you absolutely wouldn’t. It is much easier for us to write and understand 9 ≤ 10, than to go through all of the struggle of understanding R1. So why did we introduce R1 this way? It’s because we already understand the relation ≤. In introducing the concept of relation, it is easier to us to first think about relations we are already familiar with. Arranging integers in increasing order gives us structure for the set of integers. We are well familiar with this structure — in fact most of the time we think about Z as having the 44 ordering built in. However, Z itself is a set, and elements in a set are unordered. But with the definition of R1 , the elements in Z “naturally” fall into order. Depending on the context, we might be interested in different sorts of structure on different sorts of objects all together! Aside. Above we examined the set R1 = {(n1 , n2 ) | n2 − n1 ∈ N}. With our notation from our definition of relation, we may meaningfully write 9R1 10. Now, what would we write if we instead labelled our set as follows? ≤ = {(n1 , n2 ) | n2 − n1 ∈ N} The statement 9 ≤ 10 now means (9, 10) ∈ ≤. Now we see that our new relations notation can in fact be aligned with how we customarily write “9 is less than or equal to 10”! When we introduced subset in Module 1, we waved our hands towards an analogy to ≤. We now have the tools to be a little more precise in comparing the concepts ≤ and ⊆. To do so, we first require some extra notation. Definition 3.3. Let U be a set. The set of all subsets of U is called the power set of U. We denote the power set of U as 2U. That is 2U = {A | A ⊆ U } For example, if U = {x, y, z}, then we have 2U = {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}. Aside. Here, U has 3 elements and the set 2U has 8 = 23 elements. This is not a coincidence. Now consider the set R2 = (A, B) | A, B ∈ 2U and every element of A is an element of B.  For example ({x} , {x, z}) ∈ R2. Let us consider the elements of R2. Each element is an ordered pair. Both entries of the ordered pair are subsets of U. And every entry of the first entry of the ordered pair is an element of the second entry of the ordered pair. This is exactly our definition of subset! We have encoded our definition of subset as a set much in the same we encoded ≤ as a set. (Notice how this is an ongoing theme in this course?) Let us draw a picture to gain some further intuition. In the image below, an arrow from an element to another tells us that the first element is related to the second element. 45  … … −2 −1 0 1 2 {x} {x, y} {y} {} {x, y, z} {x, z} {z} {y, z} The relation on subsets allows us to put the subsets of a set in a seeming order. (This order is from left to right in the picture.) But this doesn’t quite feel the same as the order we have for the integers. For any pair of integers, n1 and n2 at least one of the following statements is true n1 ≤ n2 n2 ≤ n1 But for our relation R2 above this is not the case. For example, both of the statements below are false. {y, z} {x, y} ⊆ {y, z} {y, z} ⊆ {x, y} We will consider orderings that arise from relations further in Section 3.1. Let us continue with another example of a relation that has nothing in common with or- derings. Let C be the set of classes offered at the University of Saskatchewan this semester that will have an exam scheduled during the final exam period. In putting together the final exam schedule, the Registrar’s Office aims to ensure that no student has two final exams at the same time. How is this accomplished? Just knowing the elements of the set C does not suffice. The Registrar’s Office must also know which c