#set document(title: "1.4 Functions", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 1.4#h(0.6em)Functions A #strong[function] is a rule that assigns each input exactly one output. We call the output the #strong[image] of the input. The set of all inputs for a function is called the #strong[domain]. The set of all allowable outputs is called the #strong[codomain]. We would write #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] to describe a function with name #math.equation(block: false, alt: "f")[$f$], domain #math.equation(block: false, alt: "X")[$X$] and codomain #math.equation(block: false, alt: "Y")[$Y$]. This does not tell us #emph[which] function #math.equation(block: false, alt: "f")[$f$] is though. To define the function, we must describe the rule. This is often done by giving a formula to compute the output for any input (although this is certainly not the only way to describe the rule). For example, consider the function #math.equation(block: false, alt: "f : N → N")[$f : N → N$] defined by #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals x squared plus 3")[$f ( x ) = x^(2) + 3$]. Here the domain and codomain are the same set (the natural numbers). The rule is: take your input, multiply it by itself and add 3. This works because we can apply this rule to every natural number (every element of the domain) and the result is always a natural number (an element of the codomain). Notice though that not every natural number is actually an output (there is no way to get 0, 1, 2, 5, etc.). The set of natural numbers that #emph[are] outputs is called the #strong[range] of the function (in this case, the range is #math.equation(block: false, alt: "open brace 3 , 4 , 7 , 12 , 19 , 28 , and so on close brace")[$\{ 3 , 4 , 7 , 12 , 19 , 28 , … \}$], all the natural numbers that are 3 more than a perfect square). The key thing that makes a rule a #emph[function] is that there is #emph[exactly one] output for each input. That is, it is important that the rule be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function. #examplebox("Example 1")[][ The following are all examples of functions: + #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] defined by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals 3 n")[$f ( n ) = 3 n$]. The domain and codomain are both the set of integers. However, the range is only the set of integer multiples of 3. + #math.equation(block: false, alt: "g : open brace 1 , 2 , 3 close brace → open brace a , b , c close brace")[$g : \{ 1 , 2 , 3 \} → \{ a , b , c \}$] defined by #math.equation(block: false, alt: "g open parenthesis 1 close parenthesis equals c")[$g ( 1 ) = c$], #math.equation(block: false, alt: "g open parenthesis 2 close parenthesis equals a")[$g ( 2 ) = a$] and #math.equation(block: false, alt: "g open parenthesis 3 close parenthesis equals a")[$g ( 3 ) = a$]. The domain is the set #math.equation(block: false, alt: "open brace 1 , 2 , 3 close brace")[$\{ 1 , 2 , 3 \}$], the codomain is the set #math.equation(block: false, alt: "open brace a , b , c close brace")[$\{ a , b , c \}$] and the range is the set #math.equation(block: false, alt: "open brace a , c close brace")[$\{ a , c \}$]. Note that #math.equation(block: false, alt: "g open parenthesis 2 close parenthesis")[$g ( 2 )$] and #math.equation(block: false, alt: "g open parenthesis 3 close parenthesis")[$g ( 3 )$] are the same element of the codomain. This is okay since each element in the domain still has only one output. + #math.equation(block: false, alt: "h : open brace 1 , 2 , 3 , 4 close brace → N")[$h : \{ 1 , 2 , 3 , 4 \} → N$] defined by the table: #figure(table( columns: 5, align: left, inset: 6pt, table.header([#math.equation(block: false, alt: "x")[$x$]], [1], [2], [3], [4]), [#math.equation(block: false, alt: "h open parenthesis x close parenthesis")[$h ( x )$]], [3], [6], [9], [12], )) #linebreak() Here the domain is the finite set #math.equation(block: false, alt: "open brace 1 , 2 , 3 , 4 close brace")[$\{ 1 , 2 , 3 , 4 \}$] and to codomain is the set of natural numbers, #math.equation(block: false, alt: "N")[$N$]. At first you might think this function is the same as #math.equation(block: false, alt: "f")[$f$] defined above. It is absolutely not. Even though the rule is the same, the domain and codomain are different, so these are two different functions. ] #examplebox("Example 2")[][ Just because you can describe a rule in the same way you would write a function, does not mean that the rule is a function. The following are NOT functions. + #math.equation(block: false, alt: "f : N → N")[$f : N → N$] defined by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals the fraction n over 2")[$f ( n ) = frac(n, 2)$]. The reason this is not a function is because not every input has an output. Where does #math.equation(block: false, alt: "f")[$f$] send 3? The rule says that #math.equation(block: false, alt: "f open parenthesis 3 close parenthesis equals the fraction 3 over 2")[$f ( 3 ) = frac(3, 2)$], but #math.equation(block: false, alt: "the fraction 3 over 2")[$frac(3, 2)$] is not an element of the codomain. + Consider the rule that matches each person to their phone number. If you think of the set of people as the domain and the set of phone numbers as the codomain, then this is not a function, since some people have two phone numbers. Switching the domain and codomain sets doesn't help either, since some phone numbers belong to multiple people (assuming some households still have landlines when you are reading this). ] === Describing Functions It is worth making a distinction between a function and its description. The function is the abstract mathematical object that in some way exists whether or not anyone ever talks about it. But when we #emph[do] want to talk about the function, we need a way to describe it. A particular function can be described in multiple ways. Some calculus textbooks talk about the #emph[Rule of Four], that every function can be described in four ways: algebraically (a formula), numerically (a table), graphically, or in words. In discrete math, we can still use any of these to describe functions, but we can also be more specific since we are primarily concerned with functions that have #math.equation(block: false, alt: "N")[$N$] or a finite subset of #math.equation(block: false, alt: "N")[$N$] as their domain. Describing a function graphically usually means drawing the graph of the function: plotting the points on the plane. We can do this, and might get a graph like the following for a function #math.equation(block: false, alt: "f : open brace 1 , 2 , 3 close brace → open brace 1 , 2 , 3 close brace")[$f : \{ 1 , 2 , 3 \} → \{ 1 , 2 , 3 \}$]. #figure(figph[Graph of the first quadrant, including axes and a rectangular grid. Points on grid at (1,2), (2, 1) and (3,3).], alt: "Graph of the first quadrant, including axes and a rectangular grid. Points on grid at (1,2), (2, 1) and (3,3).", caption: none) It would be absolutely WRONG to connect the dots or try to fit them to some curve. There are only three elements in the domain. A curve would mean that the domain contains an entire interval of real numbers. Here is another way to represent that same function: #figure(figph[Two rows containing the numbers 1, 2, and 3, from left to right. Arrows from the top 1 to bottom 2, from the top 2 to bottom 1, and top 3 straight down to bottom 3.], alt: "Two rows containing the numbers 1, 2, and 3, from left to right. Arrows from the top 1 to bottom 2, from the top 2 to bottom 1, and top 3 straight down to bottom 3.", caption: none) This shows that the function #math.equation(block: false, alt: "f")[$f$] sends 1 to 2, 2 to 1 and 3 to 3: just follow the arrows. The arrow diagram used to define the function above can be very helpful in visualizing functions. We will often be working with functions with #emph[finite] domains, so this kind of picture is often more useful than a traditional graph of a function. Note that for finite domains, finding an algebraic formula that gives the output for any input is often impossible. Of course we could use a piecewise defined function, like #math.equation(block: true, alt: "f open parenthesis x close parenthesis equals open brace x plus 1, if x equals 1; x minus 1, if x equals 2; x, if x equals 3")[$f ( x ) = \{ x + 1 & " if " x = 1 \ x − 1 & " if " x = 2 \ x & " if " x = 3$] . This describes exactly the same function as above, but we can all agree is a ridiculous way of doing so. Since we will so often use functions with small domains and codomains, let's adopt some notation to describe them. All we need is some clear way of denoting the image of each element in the domain. In fact, writing a table of values would work perfectly: #figure(table( columns: 6, align: left, inset: 6pt, table.header([#math.equation(block: false, alt: "x")[$x$]], [0], [1], [2], [3], [4]), [#math.equation(block: false, alt: "f open parenthesis x close parenthesis")[$f ( x )$]], [3], [3], [2], [4], [1], )) We simplify this further by writing this as a “matrix” with each input directly over its output: #math.equation(block: true, alt: "f equals open parenthesis 0, 1, 2, 3, 4; 3, 3, 2, 4, 1 close parenthesis")[$f = ( 0 & 1 & 2 & 3 & 4 \ 3 & 3 & 2 & 4 & 1 )$] . Note this is just notation and not the same sort of matrix you would find in a linear algebra class (it does not make sense to do operations with these matrices, or row reduce them, for example). One advantage of the two-line notation over the arrow diagrams is that it is harder to accidentally define a rule that is not a function using two-line notation. #examplebox("Example 3")[][ Which of the following diagrams represent a function? Let #math.equation(block: false, alt: "X equals open brace 1 , 2 , 3 , 4 close brace")[$X = \{ 1 , 2 , 3 , 4 \}$] and #math.equation(block: false, alt: "Y equals open brace a , b , c , d close brace")[$Y = \{ a , b , c , d \}$]. #figure(figph[Picture labeled f:X to Y with two rows of numbers and letters and arrows between the rows. Top row contains the numbers 1, 2, 3, and 4. Bottom row contains letters a, b, c, and d. Arrows point from 1 to d, 2 to a, 3 to c, and 4 to d.], alt: "Picture labeled f:X to Y with two rows of numbers and letters and arrows between the rows. Top row contains the numbers 1, 2, 3, and 4. Bottom row contains letters a, b, c, and d. Arrows point from 1 to d, 2 to a, 3 to c, and 4 to d.", caption: none) #figure(figph[Picture labeled g:X to Y with two rows of numbers and letters and arrows between the rows. Top row contains the numbers 1, 2, 3, and 4. Bottom row contains letters a, b, c, and d. Arrows point from 1 to d, 2 to a, 3 to a, and 4 to b.], alt: "Picture labeled g:X to Y with two rows of numbers and letters and arrows between the rows. Top row contains the numbers 1, 2, 3, and 4. Bottom row contains letters a, b, c, and d. Arrows point from 1 to d, 2 to a, 3 to a, and 4 to b.", caption: none) #figure(figph[Picture labeled f:X to Y with two rows of numbers and letters and arrows between the rows. Top row contains the numbers 1, 2, 3, and 4. Bottom row contains letters a, b, c, and d. Arrows point from 2 to a and also 2 to c, 3 to d, and 4 to b.], alt: "Picture labeled f:X to Y with two rows of numbers and letters and arrows between the rows. Top row contains the numbers 1, 2, 3, and 4. Bottom row contains letters a, b, c, and d. Arrows point from 2 to a and also 2 to c, 3 to d, and 4 to b.", caption: none) #solutionbox[ #math.equation(block: false, alt: "f")[$f$] is a function. So is #math.equation(block: false, alt: "g")[$g$]. There is no problem with an element of the codomain not being the image of any input, and there is no problem with #math.equation(block: false, alt: "a")[$a$] from the codomain being the image of both 2 and 3 from the domain. We could use our two-line notation to write these as #math.equation(block: true, alt: "f equals open parenthesis 1, 2, 3, 4; d, a, c, b close parenthesis g equals open parenthesis 1, 2, 3, 4; d, a, a, b close parenthesis")[$f = ( 1 & 2 & 3 & 4 \ d & a & c & b ) #h(2em) g = ( 1 & 2 & 3 & 4 \ d & a & a & b )$] . However, #math.equation(block: false, alt: "h")[$h$] is NOT a function. In fact, it fails for two reasons. First, the element 1 from the domain has not been mapped to any element from the codomain. Second, the element 2 from the domain has been mapped to more than one element from the codomain (#math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "c")[$c$]). Note that either one of these problems is enough to make a rule not a function. In general, neither of the following mappings are functions: #figure(figph[Three black dots in a row above and two white dots in a row below. An arrow points from the left black dot to the left white dot and from the right black dot to the right white dot.], alt: "Three black dots in a row above and two white dots in a row below. An arrow points from the left black dot to the left white dot and from the right black dot to the right white dot.", caption: none) #figure(figph[Three black dots in a row above and four white dots in a row below. Two arrows point from the left black dot to each of the two left-most white dots. Each of the other black dots have an arrow pointing down to the white dots below and slightly to the right of them.], alt: "Three black dots in a row above and four white dots in a row below. Two arrows point from the left black dot to each of the two left-most white dots. Each of the other black dots have an arrow pointing down to the white dots below and slightly to the right of them.", caption: none) It might also be helpful to think about how you would write the two-line notation for #math.equation(block: false, alt: "h")[$h$]. We would have something like: #math.equation(block: true, alt: "h equals open parenthesis 1, 2, 3, 4; a , c ?, d, b close parenthesis")[$h = ( 1 & 2 & 3 & 4 \ & a , c ? & d & b )$] . There is nothing under 1 (bad) and we needed to put more than one thing under 2 (very bad). With a rule that is actually a function, the two-line notation will always “work”. ] ] We will also be interested in functions with domain #math.equation(block: false, alt: "N")[$N$]. Here two-line notation is no good, but describing the function algebraically is often possible. Even tables are a little awkward, since they do not describe the function completely. For example, consider the function #math.equation(block: false, alt: "f : N → N")[$f : N → N$] given by the table below. #figure(table( columns: 8, align: left, inset: 6pt, table.header([#math.equation(block: false, alt: "x")[$x$]], [0], [1], [2], [3], [4], [5], [#math.equation(block: false, alt: "and so on")[$…$]]), [#math.equation(block: false, alt: "f open parenthesis x close parenthesis")[$f ( x )$]], [0], [1], [4], [9], [16], [25], [#math.equation(block: false, alt: "and so on")[$…$]], )) Have I given you enough entries for you to be able to determine #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis")[$f ( 6 )$]? You might guess that #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis equals 36")[$f ( 6 ) = 36$], but there is no way for you to #emph[know] this for sure. Maybe I am being a jerk and intended #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis equals 42")[$f ( 6 ) = 42$]. In fact, for every natural number #math.equation(block: false, alt: "n")[$n$], there is a function that agrees with the table above, but for which #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis equals n")[$f ( 6 ) = n$]. Okay, suppose I really did mean for #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis equals 36")[$f ( 6 ) = 36$], and in fact, for the rule that you think is governing the function to actually be the rule. Then I should say what that rule is. #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals n squared")[$f ( n ) = n^(2)$]. Now there is no confusion possible. Giving an explicit formula that calculates the image of any element in the domain is a great way to describe a function. We will say that these explicit rules are #strong[closed formulas] for the function. There is another very useful way to describe functions whose domain is #math.equation(block: false, alt: "N")[$N$], that rely specifically on the structure of the natural numbers. We can define a function #emph[recursively]! #examplebox("Example 4")[][ Consider the function #math.equation(block: false, alt: "f : N → N")[$f : N → N$] given by #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis equals 0")[$f ( 0 ) = 0$] and #math.equation(block: false, alt: "f open parenthesis n plus 1 close parenthesis equals f open parenthesis n close parenthesis plus 2 n plus 1")[$f ( n + 1 ) = f ( n ) + 2 n + 1$]. Find #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis")[$f ( 6 )$]. #solutionbox[ The rule says that #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis equals f open parenthesis 5 close parenthesis plus 11")[$f ( 6 ) = f ( 5 ) + 11$] (we are using #math.equation(block: false, alt: "6 equals n plus 1")[$6 = n + 1$] so #math.equation(block: false, alt: "n equals 5")[$n = 5$]). We don't know what #math.equation(block: false, alt: "f open parenthesis 5 close parenthesis")[$f ( 5 )$] is though. Well, we know that #math.equation(block: false, alt: "f open parenthesis 5 close parenthesis equals f open parenthesis 4 close parenthesis plus 9")[$f ( 5 ) = f ( 4 ) + 9$]. So we need to compute #math.equation(block: false, alt: "f open parenthesis 4 close parenthesis")[$f ( 4 )$], which will require knowing #math.equation(block: false, alt: "f open parenthesis 3 close parenthesis")[$f ( 3 )$], which will require #math.equation(block: false, alt: "f open parenthesis 2 close parenthesis")[$f ( 2 )$],… will it ever end? Yes! In fact, this process will always end because we have #math.equation(block: false, alt: "N")[$N$] as our domain, so there is a least element. And we gave the value of #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis")[$f ( 0 )$] explicitly, so we are good. In fact, we might decide to work up to #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis")[$f ( 6 )$] instead of working down from #math.equation(block: false, alt: "f open parenthesis 6 close parenthesis")[$f ( 6 )$]: #math.equation(block: true, alt: "f open parenthesis 1 close parenthesis equals, f open parenthesis 0 close parenthesis plus 1 equals, 0 plus 1 equals 1; f open parenthesis 2 close parenthesis equals, f open parenthesis 1 close parenthesis plus 3 equals, 1 plus 3 equals 4; f open parenthesis 3 close parenthesis equals, f open parenthesis 2 close parenthesis plus 5 equals, 4 plus 5 equals 9; f open parenthesis 4 close parenthesis equals, f open parenthesis 3 close parenthesis plus 7 equals, 9 plus 7 equals 16; f open parenthesis 5 close parenthesis equals, f open parenthesis 4 close parenthesis plus 9 equals, 16 plus 9 equals 25; f open parenthesis 6 close parenthesis equals, f open parenthesis 5 close parenthesis plus 11 equals, 25 plus 11 equals 36")[$f ( 1 ) = & f ( 0 ) + 1 = & 0 + 1 = 1 \ f ( 2 ) = & f ( 1 ) + 3 = & 1 + 3 = 4 \ f ( 3 ) = & f ( 2 ) + 5 = & 4 + 5 = 9 \ f ( 4 ) = & f ( 3 ) + 7 = & 9 + 7 = 16 \ f ( 5 ) = & f ( 4 ) + 9 = & 16 + 9 = 25 \ f ( 6 ) = & f ( 5 ) + 11 = & 25 + 11 = 36$] It looks that this recursively defined function is the same as the explicitly defined function #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals n squared")[$f ( n ) = n^(2)$]. Is it? Later we will prove that it is. ] ] Recursively defined functions are often easier to create from a “real world” problem, because they describe how the values of the functions are changing. However, this comes with a price. It is harder to calculate the image of a single input, since you need to know the images of other (previous) elements in the domain. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Recursively Defined Functions] For a function #math.equation(block: false, alt: "f : N → N")[$f : N → N$], a #strong[recursive definition] consists of an #strong[initial condition] together with a #strong[recurrence relation]. The initial condition is the explicitly given value of #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis")[$f ( 0 )$]. The recurrence relation is a formula for #math.equation(block: false, alt: "f open parenthesis n plus 1 close parenthesis")[$f ( n + 1 )$] in terms for #math.equation(block: false, alt: "f open parenthesis n close parenthesis")[$f ( n )$] (and possibly #math.equation(block: false, alt: "n")[$n$] itself). ] #examplebox("Example 5")[][ Give recursive definitions for the functions described below. + #math.equation(block: false, alt: "f : N → N")[$f : N → N$] gives the number of snails in your terrarium #math.equation(block: false, alt: "n")[$n$] years after you built it, assuming you started with 3 snails and the number of snails doubles each year. + #math.equation(block: false, alt: "g : N → N")[$g : N → N$] gives the number of push-ups you do #math.equation(block: false, alt: "n")[$n$] days after you started your push-ups challenge, assuming you could do 7 push-ups on day 0 and you can do 2 more push-ups each day. + #math.equation(block: false, alt: "h : N → N")[$h : N → N$] defined by #math.equation(block: false, alt: "h open parenthesis n close parenthesis equals n !")[$h ( n ) = n !$]. Recall that #math.equation(block: false, alt: "n ! equals 1 times 2 times 3 times ⋯ times open parenthesis n minus 1 close parenthesis times n")[$n ! = 1 ⋅ 2 ⋅ 3 ⋅ ⋯ ⋅ ( n − 1 ) ⋅ n$] is the product of all numbers from #math.equation(block: false, alt: "1")[$1$] through #math.equation(block: false, alt: "n")[$n$]. We also define #math.equation(block: false, alt: "0 ! equals 1")[$0 ! = 1$]. #solutionbox[ + The initial condition is #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis equals 3")[$f ( 0 ) = 3$]. To get #math.equation(block: false, alt: "f open parenthesis n plus 1 close parenthesis")[$f ( n + 1 )$] we would double the number of snails in the terrarium the previous year, which is given by #math.equation(block: false, alt: "f open parenthesis n close parenthesis")[$f ( n )$]. Thus #math.equation(block: false, alt: "f open parenthesis n plus 1 close parenthesis equals 2 f open parenthesis n close parenthesis")[$f ( n + 1 ) = 2 f ( n )$]. The full recursive definition contains both of these, and would be written, #math.equation(block: true, alt: "f open parenthesis 0 close parenthesis equals 3 ; f open parenthesis n plus 1 close parenthesis equals 2 f open parenthesis n close parenthesis")[$f ( 0 ) = 3 ; " " f ( n + 1 ) = 2 f ( n )$]. + We are told that on day 0 you can do 7 push-ups, so #math.equation(block: false, alt: "g open parenthesis 0 close parenthesis equals 7")[$g ( 0 ) = 7$]. The number of push-ups you can do on day #math.equation(block: false, alt: "n plus 1")[$n + 1$] is 2 more than the number you can do on day #math.equation(block: false, alt: "n")[$n$], which is given by #math.equation(block: false, alt: "g open parenthesis n close parenthesis")[$g ( n )$]. Thus #math.equation(block: true, alt: "g open parenthesis 0 close parenthesis equals 7 ; g open parenthesis n plus 1 close parenthesis equals g open parenthesis n close parenthesis plus 2")[$g ( 0 ) = 7 ; " " g ( n + 1 ) = g ( n ) + 2$]. + Here #math.equation(block: false, alt: "h open parenthesis 0 close parenthesis equals 1")[$h ( 0 ) = 1$]. To get the recurrence relation, think about how you can get #math.equation(block: false, alt: "h open parenthesis n plus 1 close parenthesis equals open parenthesis n plus 1 close parenthesis !")[$h ( n + 1 ) = ( n + 1 ) !$] from #math.equation(block: false, alt: "h open parenthesis n close parenthesis equals n !")[$h ( n ) = n !$]. If you write out both of these as products, you see that #math.equation(block: false, alt: "open parenthesis n plus 1 close parenthesis !")[$( n + 1 ) !$] is just like #math.equation(block: false, alt: "n !")[$n !$] except you have one more term in the product, an extra #math.equation(block: false, alt: "n plus 1")[$n + 1$]. So we have, #math.equation(block: true, alt: "h open parenthesis 0 close parenthesis equals 1 ; h open parenthesis n plus 1 close parenthesis equals open parenthesis n plus 1 close parenthesis times h open parenthesis n close parenthesis")[$h ( 0 ) = 1 ; " " h ( n + 1 ) = ( n + 1 ) ⋅ h ( n )$]. ] ] === Surjections, Injections, and Bijections We now turn to investigating special properties functions might or might not possess. In the examples above, you may have noticed that sometimes there are elements of the codomain which are not in the range. When this sort of the thing #emph[does not] happen, (that is, when everything in the codomain is in the range) we say the function is #strong[onto] or that the function maps the domain #emph[onto] the codomain. This terminology should make sense: the function puts the domain (entirely) on top of the codomain. The fancy math term for an onto function is a #strong[surjection], and we say that an onto function is a #strong[surjective] function. In pictures: #figure(figph[Four black dots in a top row and three white dots in a bottom row. Arrows point from the top dots to the bottom dots below them: the two white dots on the left have one arrow each point to them. The right-most white dot has two arrows pointing to it, coming from two different black dots. The image is labeled with the word "Surjective"], alt: "Four black dots in a top row and three white dots in a bottom row. Arrows point from the top dots to the bottom dots below them: the two white dots on the left have one arrow each point to them. The right-most white dot has two arrows pointing to it, coming from two different black dots. The image is labeled with the word \"Surjective\"", caption: none) #figure(figph[Four black dots in a top row and three white dots in a bottom row. Arrows point from the top dots to the bottom dots below them: the two white dots on the left and right have two arrows each pointing to them. The center white dot has no arrows pointing to it. The image is labeled with the words "Not surjective"], alt: "Four black dots in a top row and three white dots in a bottom row. Arrows point from the top dots to the bottom dots below them: the two white dots on the left and right have two arrows each pointing to them. The center white dot has no arrows pointing to it. The image is labeled with the words \"Not surjective\"", caption: none) #examplebox("Example 6")[][ Which functions are surjective (i.e., onto)? + #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] defined by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals 3 n")[$f ( n ) = 3 n$]. + #math.equation(block: false, alt: "g : open brace 1 , 2 , 3 close brace → open brace a , b , c close brace")[$g : \{ 1 , 2 , 3 \} → \{ a , b , c \}$] defined by #math.equation(block: false, alt: "g equals open parenthesis 1, 2, 3; c, a, a close parenthesis")[$g = ( 1 & 2 & 3 \ c & a & a )$]. + #math.equation(block: false, alt: "h : open brace 1 , 2 , 3 close brace → open brace 1 , 2 , 3 close brace")[$h : \{ 1 , 2 , 3 \} → \{ 1 , 2 , 3 \}$] defined as follows: #figure(figph[Two rows containing the numbers 1, 2, and 3, from left to right. Arrows from the top 1 to bottom 2, from the top 2 to bottom 1, and top 3 straight down to bottom 3.], alt: "Two rows containing the numbers 1, 2, and 3, from left to right. Arrows from the top 1 to bottom 2, from the top 2 to bottom 1, and top 3 straight down to bottom 3.", caption: none) #solutionbox[ + #math.equation(block: false, alt: "f")[$f$] is not surjective. There are elements in the codomain which are not in the range. For example, no #math.equation(block: false, alt: "n ∈ Z")[$n ∈ Z$] gets mapped to the number 1 (the rule would say that #math.equation(block: false, alt: "the fraction 1 over 3")[$frac(1, 3)$] would be sent to 1, but #math.equation(block: false, alt: "the fraction 1 over 3")[$frac(1, 3)$] is not in the domain). In fact, the range of the function is #math.equation(block: false, alt: "3 Z")[$3 Z$] (the integer multiples of 3), which is not equal to #math.equation(block: false, alt: "Z")[$Z$]. + #math.equation(block: false, alt: "g")[$g$] is not surjective. There is no #math.equation(block: false, alt: "x ∈ open brace 1 , 2 , 3 close brace")[$x ∈ \{ 1 , 2 , 3 \}$] (the domain) for which #math.equation(block: false, alt: "g open parenthesis x close parenthesis equals b")[$g ( x ) = b$], so #math.equation(block: false, alt: "b")[$b$], which is in the codomain, is not in the range. Notice that there is an element from the codomain “missing” from the bottom row of the matrix. + #math.equation(block: false, alt: "h")[$h$] is surjective. Every element of the codomain is also in the range. Nothing in the codomain is missed. ] ] To be a function, a rule cannot assign a single element of the domain to two or more different elements of the codomain. However, we have seen that the reverse #emph[is] permissible: a function might assign the same element of the codomain to two or more different elements of the domain. When this #emph[does not] occur (that is, when each element of the codomain is the image of at most one element of the domain) then we say the function is #strong[one-to-one]. Again, this terminology makes sense: we are sending at most one element from the domain to one element from the codomain. One input to one output. The fancy math term for a one-to-one function is an #strong[injection]. We call one-to-one functions #strong[injective] functions. In pictures: #figure(figph[Four black dots in a top row and five white dots in a bottom row. Arrows point from the top dots to the bottom dots below them. Each black dot has an arrow pointing to a different white dot. The center white dot has no arrow pointing to it. The image is labeled with the word "Injective"], alt: "Four black dots in a top row and five white dots in a bottom row. Arrows point from the top dots to the bottom dots below them. Each black dot has an arrow pointing to a different white dot. The center white dot has no arrow pointing to it. The image is labeled with the word \"Injective\"", caption: none) #figure(figph[Four black dots in a top row and five white dots in a bottom row. Arrows point from the top dots to the bottom dots below them. Two of the black dots have an arrow pointing to a different white dot. The other two black dots have arrows pointing to the same white dot. Two white dots have no arrows pointing to them. The image is labeled with the words "Not injective"], alt: "Four black dots in a top row and five white dots in a bottom row. Arrows point from the top dots to the bottom dots below them. Two of the black dots have an arrow pointing to a different white dot. The other two black dots have arrows pointing to the same white dot. Two white dots have no arrows pointing to them. The image is labeled with the words \"Not injective\"", caption: none) #examplebox("Example 7")[][ Which functions are injective (i.e., one-to-one)? + #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] defined by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals 3 n")[$f ( n ) = 3 n$]. + #math.equation(block: false, alt: "g : open brace 1 , 2 , 3 close brace → open brace a , b , c close brace")[$g : \{ 1 , 2 , 3 \} → \{ a , b , c \}$] defined by #math.equation(block: false, alt: "g equals open parenthesis 1, 2, 3; c, a, a close parenthesis")[$g = ( 1 & 2 & 3 \ c & a & a )$]. + #math.equation(block: false, alt: "h : open brace 1 , 2 , 3 close brace → open brace 1 , 2 , 3 close brace")[$h : \{ 1 , 2 , 3 \} → \{ 1 , 2 , 3 \}$] defined as follows: #figure(figph[Two rows containing the numbers 1, 2, and 3, from left to right. Arrows from the top 1 to bottom 2, from the top 2 to bottom 1, and top 3 straight down to bottom 3.], alt: "Two rows containing the numbers 1, 2, and 3, from left to right. Arrows from the top 1 to bottom 2, from the top 2 to bottom 1, and top 3 straight down to bottom 3.", caption: none) #solutionbox[ + #math.equation(block: false, alt: "f")[$f$] is injective. Each element in the codomain is assigned to at #emph[most] one element from the domain. If #math.equation(block: false, alt: "x")[$x$] is a multiple of three, then only #math.equation(block: false, alt: "x / 3")[$x / 3$] is mapped to #math.equation(block: false, alt: "x")[$x$]. If #math.equation(block: false, alt: "x")[$x$] is not a multiple of 3, then there is no input corresponding to the output #math.equation(block: false, alt: "x")[$x$]. + #math.equation(block: false, alt: "g")[$g$] is not injective. Both inputs #math.equation(block: false, alt: "2")[$2$] and #math.equation(block: false, alt: "3")[$3$] are assigned the output #math.equation(block: false, alt: "a")[$a$]. Notice that there is an element from the codomain that appears more than once on the bottom row of the matrix. + #math.equation(block: false, alt: "h")[$h$] is injective. Each output is only an output once. ] ] Be careful: “surjective” and “injective” are NOT opposites. You can see in the two examples above that there are functions which are surjective but not injective, injective but not surjective, both, or neither. In the case when a function is both one-to-one and onto (an injection and surjection), we say the function is a #strong[bijection], or that the function is a #strong[bijective] function. To illustrate the contrast between these two properties, consider a more formal definition of each, side by side. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Injective vs Surjective] A function is #strong[injective] provided every element of the codomain is the image of #emph[at most] one element from the domain. A function is #strong[surjective] provided every element of the codomain is the image of #emph[at least] one element from the domain. ] Notice both properties are determined by what happens to elements of the codomain: they could be repeated as images or they could be “missed” (not be images). Injective functions do not have repeats but might or might not miss elements. Surjective functions do not miss elements, but might or might not have repeats. The bijective functions are those that do not have repeats and do not miss elements. === Image and Inverse Image When discussing functions, we have notation for talking about an element of the domain (say #math.equation(block: false, alt: "x")[$x$]) and its corresponding element in the codomain (we write #math.equation(block: false, alt: "f open parenthesis x close parenthesis")[$f ( x )$], which #emph[is] the image of #math.equation(block: false, alt: "x")[$x$]). Sometimes we will want to talk about all the elements that are images of some subset of the domain. It would also be nice to start with some element of the codomain (say #math.equation(block: false, alt: "y")[$y$]) and talk about which element or elements (if any) from the domain it is the image of. We could write “those #math.equation(block: false, alt: "x")[$x$] in the domain such that #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals y")[$f ( x ) = y$],” but this is a lot of writing. Here is some notation to make our lives easier. To address the first situation, what we are after is a way to describe the #emph[set] of images of elements in some subset of the domain. Suppose #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] is a function and that #math.equation(block: false, alt: "A ⊆ X")[$A ⊆ X$] is some subset of the domain (possibly all of it). We will use the notation #math.equation(block: false, alt: "f open parenthesis A close parenthesis")[$f ( A )$] to denote the #strong[image of #math.equation(block: false, alt: "A")[$A$] under #math.equation(block: false, alt: "f")[$f$]], namely the set of elements in #math.equation(block: false, alt: "Y")[$Y$] that are the image of elements from #math.equation(block: false, alt: "A")[$A$]. That is, #math.equation(block: false, alt: "f open parenthesis A close parenthesis equals open brace f open parenthesis a close parenthesis ∈ Y : a ∈ A close brace")[$f ( A ) = \{ f ( a ) ∈ Y : a ∈ A \}$]. We can do this in the other direction as well. We might ask which elements of the domain get mapped to a particular set in the codomain. Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be a function and suppose #math.equation(block: false, alt: "B ⊆ Y")[$B ⊆ Y$] is a subset of the codomain. Then we will write #math.equation(block: false, alt: "f to the power minus 1 open parenthesis B close parenthesis")[$f^(− 1) ( B )$] for the #strong[inverse image of #math.equation(block: false, alt: "B")[$B$] under #math.equation(block: false, alt: "f")[$f$]], namely the set of elements in #math.equation(block: false, alt: "X")[$X$] whose image are elements in #math.equation(block: false, alt: "B")[$B$]. In other words, #math.equation(block: false, alt: "f to the power minus 1 open parenthesis B close parenthesis equals open brace x ∈ X : f open parenthesis x close parenthesis ∈ B close brace")[$f^(− 1) ( B ) = \{ x ∈ X : f ( x ) ∈ B \}$]. Often we are interested in the element(s) whose image is a particular element #math.equation(block: false, alt: "y")[$y$] of in the codomain. The notation above works: #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace y close brace close parenthesis")[$f^(− 1) ( \{ y \} )$] is the set of all elements in the domain that #math.equation(block: false, alt: "f")[$f$] sends to #math.equation(block: false, alt: "y")[$y$]. It makes sense to think of this as a set: there might not be anything sent to #math.equation(block: false, alt: "y")[$y$] (if #math.equation(block: false, alt: "y")[$y$] is not in the range), in which case #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace y close brace close parenthesis equals ∅")[$f^(− 1) ( \{ y \} ) = upright(∅)$]. Or #math.equation(block: false, alt: "f")[$f$] might send multiple elements to #math.equation(block: false, alt: "y")[$y$] (if #math.equation(block: false, alt: "f")[$f$] is not injective). As a notational convenience, we usually drop the set braces around the #math.equation(block: false, alt: "y")[$y$] and write #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$] instead for this set. WARNING: #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$] is not an inverse function! Inverse functions only exist for bijections, but #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$] is defined for any function #math.equation(block: false, alt: "f")[$f$]. The point: #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$] is a #emph[set], not an #emph[element] of the domain. This is just sloppy notation for #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace y close brace close parenthesis")[$f^(− 1) ( \{ y \} )$]. To help make this distinction, we would call #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$] the #strong[complete inverse image of #math.equation(block: false, alt: "y")[$y$] under #math.equation(block: false, alt: "f")[$f$]]. It is not the image of #math.equation(block: false, alt: "y")[$y$] under #math.equation(block: false, alt: "f to the power minus 1")[$f^(− 1)$] (since the function #math.equation(block: false, alt: "f to the power minus 1")[$f^(− 1)$] might not exist). #examplebox("Example 8")[][ Consider the function #math.equation(block: false, alt: "f : open brace 1 , 2 , 3 , 4 , 5 , 6 close brace → open brace a , b , c , d close brace")[$f : \{ 1 , 2 , 3 , 4 , 5 , 6 \} → \{ a , b , c , d \}$] given by #math.equation(block: true, alt: "f equals open parenthesis 1, 2, 3, 4, 5, 6; a, a, b, b, b, c close parenthesis")[$f = ( 1 & 2 & 3 & 4 & 5 & 6 \ a & a & b & b & b & c )$] . Find #math.equation(block: false, alt: "f open parenthesis open brace 1 , 2 , 3 close brace close parenthesis")[$f ( \{ 1 , 2 , 3 \} )$], #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace a , b close brace close parenthesis")[$f^(− 1) ( \{ a , b \} )$], and #math.equation(block: false, alt: "f to the power minus 1 open parenthesis d close parenthesis")[$f^(− 1) ( d )$]. #solutionbox[ #math.equation(block: false, alt: "f open parenthesis open brace 1 , 2 , 3 close brace close parenthesis equals open brace a , b close brace")[$f ( \{ 1 , 2 , 3 \} ) = \{ a , b \}$] since #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are the elements in the codomain to which #math.equation(block: false, alt: "f")[$f$] sends #math.equation(block: false, alt: "1")[$1$], #math.equation(block: false, alt: "2")[$2$], and #math.equation(block: false, alt: "3")[$3$]. #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace a , b close brace close parenthesis equals open brace 1 , 2 , 3 , 4 , 5 close brace")[$f^(− 1) ( \{ a , b \} ) = \{ 1 , 2 , 3 , 4 , 5 \}$] since these are exactly the elements that #math.equation(block: false, alt: "f")[$f$] sends to #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$]. #math.equation(block: false, alt: "f to the power minus 1 open parenthesis d close parenthesis equals ∅")[$f^(− 1) ( d ) = upright(∅)$] since #math.equation(block: false, alt: "d")[$d$] is not in the range of #math.equation(block: false, alt: "f")[$f$]. ] ] #examplebox("Example 9")[][ Consider the function #math.equation(block: false, alt: "g : Z → Z")[$g : Z → Z$] defined by #math.equation(block: false, alt: "g open parenthesis n close parenthesis equals n squared plus 1")[$g ( n ) = n^(2) + 1$]. Find #math.equation(block: false, alt: "g open parenthesis 1 close parenthesis")[$g ( 1 )$] and #math.equation(block: false, alt: "g open parenthesis open brace 1 close brace close parenthesis")[$g ( \{ 1 \} )$]. Then find #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 1 close parenthesis")[$g^(− 1) ( 1 )$], #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 2 close parenthesis")[$g^(− 1) ( 2 )$], and #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 3 close parenthesis")[$g^(− 1) ( 3 )$]. #solutionbox[ Note that #math.equation(block: false, alt: "g open parenthesis 1 close parenthesis not equal to g open parenthesis open brace 1 close brace close parenthesis")[$g ( 1 ) ≠ g ( \{ 1 \} )$]. The first is an element: #math.equation(block: false, alt: "g open parenthesis 1 close parenthesis equals 2")[$g ( 1 ) = 2$]. The second is a set: #math.equation(block: false, alt: "g open parenthesis open brace 1 close brace close parenthesis equals open brace 2 close brace")[$g ( \{ 1 \} ) = \{ 2 \}$]. To find #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 1 close parenthesis")[$g^(− 1) ( 1 )$], we need to find all integers #math.equation(block: false, alt: "n")[$n$] such that #math.equation(block: false, alt: "n squared plus 1 equals 1")[$n^(2) + 1 = 1$]. Clearly only 0 works, so #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 1 close parenthesis equals open brace 0 close brace")[$g^(− 1) ( 1 ) = \{ 0 \}$] (note that even though there is only one element, we still write it as a set with one element in it). To find #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 2 close parenthesis")[$g^(− 1) ( 2 )$], we need to find all #math.equation(block: false, alt: "n")[$n$] such that #math.equation(block: false, alt: "n squared plus 1 equals 2")[$n^(2) + 1 = 2$]. We see #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 2 close parenthesis equals open brace minus 1 , 1 close brace")[$g^(− 1) ( 2 ) = \{ − 1 , 1 \}$]. Finally, if #math.equation(block: false, alt: "n squared plus 1 equals 3")[$n^(2) + 1 = 3$], then we are looking for an #math.equation(block: false, alt: "n")[$n$] such that #math.equation(block: false, alt: "n squared equals 2")[$n^(2) = 2$]. There are no such integers so #math.equation(block: false, alt: "g to the power minus 1 open parenthesis 3 close parenthesis equals ∅")[$g^(− 1) ( 3 ) = upright(∅)$]. ] ] Since #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$] is a set, it makes sense to ask for #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis y close parenthesis vertical bar")[$| f^(− 1) ( y ) |$], the number of elements in the domain which map to #math.equation(block: false, alt: "y")[$y$]. #examplebox("Example 10")[][ Find a function #math.equation(block: false, alt: "f : open brace 1 , 2 , 3 , 4 , 5 close brace → N")[$f : \{ 1 , 2 , 3 , 4 , 5 \} → N$] such that #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis 7 close parenthesis vertical bar equals 5")[$| f^(− 1) ( 7 ) | = 5$]. #solutionbox[ There is only one such function. We need five elements of the domain to map to the number #math.equation(block: false, alt: "7 ∈ N")[$7 ∈ N$]. Since there are only five elements in the domain, all of them must map to 7. So #math.equation(block: true, alt: "f equals open parenthesis 1, 2, 3, 4, 5; 7, 7, 7, 7, 7 close parenthesis")[$f = ( 1 & 2 & 3 & 4 & 5 \ 7 & 7 & 7 & 7 & 7 )$] . ] ] ==== Function Definitions Here is a summary of all the main concepts and definitions we use when working with functions. - A #strong[function] is a rule that assigns each element of a set, called the #strong[domain], to exactly one element of a second set, called the #strong[codomain]. - Notation: #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] is our way of saying that the function is called #math.equation(block: false, alt: "f")[$f$], the domain is the set #math.equation(block: false, alt: "X")[$X$], and the codomain is the set #math.equation(block: false, alt: "Y")[$Y$]. - To specify the rule for a function with small domain, use #strong[two-line notation] by writing a matrix with each output directly below its corresponding input, as in: #math.equation(block: true, alt: "f equals open parenthesis 1, 2, 3, 4; 2, 1, 3, 1 close parenthesis")[$f = ( 1 & 2 & 3 & 4 \ 2 & 1 & 3 & 1 )$]. - #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals y")[$f ( x ) = y$] means the element #math.equation(block: false, alt: "x")[$x$] of the domain (input) is assigned to the element #math.equation(block: false, alt: "y")[$y$] of the codomain. We say #math.equation(block: false, alt: "y")[$y$] is an output. Alternatively, we call #math.equation(block: false, alt: "y")[$y$] the #strong[image of #math.equation(block: false, alt: "x")[$x$] under #math.equation(block: false, alt: "f")[$f$]]. - The #strong[range] is a subset of the codomain. It is the set of all elements which are assigned to at least one element of the domain by the function. That is, the range is the set of all outputs. - A function is #strong[injective] (an #strong[injection] or #strong[one-to-one]) if every element of the codomain is the image of #strong[at most] one element from the domain. - A function is #strong[surjective] (a #strong[surjection] or #strong[onto]) if every element of the codomain is the image of #strong[at least] one element from the domain. - A #strong[bijection] is a function which is both an injection and surjection. In other words, if every element of the codomain is the image of #strong[exactly one] element from the domain. - The #strong[image] of an element #math.equation(block: false, alt: "x")[$x$] in the domain is the element #math.equation(block: false, alt: "y")[$y$] in the codomain that #math.equation(block: false, alt: "x")[$x$] is mapped to. That is, the image of #math.equation(block: false, alt: "x")[$x$] under #math.equation(block: false, alt: "f")[$f$] is #math.equation(block: false, alt: "f open parenthesis x close parenthesis")[$f ( x )$]. - The #strong[complete inverse image] of an element #math.equation(block: false, alt: "y")[$y$] in the codomain, written #math.equation(block: false, alt: "f to the power minus 1 open parenthesis y close parenthesis")[$f^(− 1) ( y )$], is the #emph[set] of all elements in the domain which are assigned to #math.equation(block: false, alt: "y")[$y$] by the function. - The #strong[image] of a subset #math.equation(block: false, alt: "A")[$A$] of the domain is the set #math.equation(block: false, alt: "f open parenthesis A close parenthesis equals open brace f open parenthesis a close parenthesis ∈ Y : a ∈ A close brace")[$f ( A ) = \{ f ( a ) ∈ Y : a ∈ A \}$]. - The #strong[inverse image] of a subset #math.equation(block: false, alt: "B")[$B$] of the codomain is the set #math.equation(block: false, alt: "f to the power minus 1 open parenthesis B close parenthesis equals open brace x ∈ X : f open parenthesis x close parenthesis ∈ B close brace")[$f^(− 1) ( B ) = \{ x ∈ X : f ( x ) ∈ B \}$]. Consider the function #math.equation(block: false, alt: "f : open brace 1 , 2 , 3 , 4 , 5 close brace → open brace 1 , 2 , 3 , 4 close brace")[$f : \{ 1 , 2 , 3 , 4 , 5 \} → \{ 1 , 2 , 3 , 4 \}$] given by the table below: #figure(table( columns: 6, align: left, inset: 6pt, table.header([#math.equation(block: false, alt: "x")[$x$]], [1], [2], [3], [4], [5]), [#math.equation(block: false, alt: "f open parenthesis x close parenthesis")[$f ( x )$]], [3], [2], [4], [1], [2], )) + Is #math.equation(block: false, alt: "f")[$f$] injective? Explain. + Is #math.equation(block: false, alt: "f")[$f$] surjective? Explain. + Write the function using two-line notation. #solutionbox[ + #math.equation(block: false, alt: "f")[$f$] is not injective, since #math.equation(block: false, alt: "f open parenthesis 2 close parenthesis equals f open parenthesis 5 close parenthesis")[$f ( 2 ) = f ( 5 )$]; two different inputs have the same output. + #math.equation(block: false, alt: "f")[$f$] is surjective, since every element of the codomain is an element of the range. + #math.equation(block: false, alt: "f equals open parenthesis 1, 2, 3, 4, 5; 3, 2, 4, 1, 2 close parenthesis")[$f = ( 1 & 2 & 3 & 4 & 5 \ 3 & 2 & 4 & 1 & 2 )$]. ] Consider the function #math.equation(block: false, alt: "f : open brace 1 , 2 , 3 , 4 close brace → open brace 1 , 2 , 3 , 4 close brace")[$f : \{ 1 , 2 , 3 , 4 \} → \{ 1 , 2 , 3 , 4 \}$] given by the graph below. #figure(figph[The first quadrant of a coordinate plane. Horizontal axis labeled "x", vertical axis labeled "f(x)". Both axes labeled with the numbers 1 through 4, with an integer grid. Points at (1,3), (2,4), (3,1) and (4, 3).], alt: "The first quadrant of a coordinate plane. Horizontal axis labeled \"x\", vertical axis labeled \"f(x)\". Both axes labeled with the numbers 1 through 4, with an integer grid. Points at (1,3), (2,4), (3,1) and (4, 3).", caption: none) + Is #math.equation(block: false, alt: "f")[$f$] injective? Explain. + Is #math.equation(block: false, alt: "f")[$f$] surjective? Explain. + Write the function using two-line notation. Suppose #math.equation(block: false, alt: "f : N → N")[$f : N → N$] satisfies the recurrence relation #math.equation(block: true, alt: "f open parenthesis n plus 1 close parenthesis equals open brace the fraction f open parenthesis n close parenthesis over 2, if f open parenthesis n close parenthesis is even; 3 f open parenthesis n close parenthesis plus 1, if f open parenthesis n close parenthesis is odd")[$f ( n + 1 ) = \{ frac(f ( n ), 2) & " if " f ( n ) " is even" \ 3 f ( n ) + 1 & " if " f ( n ) " is odd"$] . Note that with the initial condition #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis equals 1")[$f ( 0 ) = 1$], the values of the function are: #math.equation(block: false, alt: "f open parenthesis 1 close parenthesis equals 4")[$f ( 1 ) = 4$] , #math.equation(block: false, alt: "f open parenthesis 2 close parenthesis equals 2")[$f ( 2 ) = 2$], #math.equation(block: false, alt: "f open parenthesis 3 close parenthesis equals 1")[$f ( 3 ) = 1$], #math.equation(block: false, alt: "f open parenthesis 4 close parenthesis equals 4")[$f ( 4 ) = 4$], and so on, the images cycling through those three numbers. Thus #math.equation(block: false, alt: "f")[$f$] is NOT injective (and also certainly not surjective). Might it be under other initial conditions? It turns out this is a #emph[really] hard question to answer in general. The #emph[Collatz conjecture] is that no matter what the initial condition is, the function will eventually produce 1 as an output. This is an open problem in mathematics: nobody knows the answer. + If #math.equation(block: false, alt: "f")[$f$] satisfies the initial condition #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis equals 5")[$f ( 0 ) = 5$], is #math.equation(block: false, alt: "f")[$f$] injective? Explain why or give a specific example of two elements from the domain with the same image. + If #math.equation(block: false, alt: "f")[$f$] satisfies the initial condition #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis equals 3")[$f ( 0 ) = 3$], is #math.equation(block: false, alt: "f")[$f$] injective? Explain why or give a specific example of two elements from the domain with the same image. + If #math.equation(block: false, alt: "f")[$f$] satisfies the initial condition #math.equation(block: false, alt: "f open parenthesis 0 close parenthesis equals 27")[$f ( 0 ) = 27$], then it turns out that #math.equation(block: false, alt: "f open parenthesis 105 close parenthesis equals 10")[$f ( 105 ) = 10$] and no two numbers less than 105 have the same image. Could #math.equation(block: false, alt: "f")[$f$] be injective? Explain. + Prove that no matter what initial condition you choose, the function cannot be surjective. For each function given below, determine whether or not the function is injective and whether or not the function is surjective. + #math.equation(block: false, alt: "f : N → N")[$f : N → N$] given by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals n plus 4")[$f ( n ) = n + 4$]. + #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] given by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals n plus 4")[$f ( n ) = n + 4$]. + #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] given by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals 5 n minus 8")[$f ( n ) = 5 n − 8$]. + #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] given by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals open brace n / 2, if n is even; open parenthesis n plus 1 close parenthesis / 2, if n is odd .")[$f ( n ) = \{ n / 2 & " if " n " is even" \ ( n + 1 ) / 2 & " if " n " is odd" .$] #solutionbox[ + #math.equation(block: false, alt: "f")[$f$] is injective, but not surjective (since 0, for example, is never an output). + #math.equation(block: false, alt: "f")[$f$] is injective and surjective. Unlike in the previous question, every integers is an output (of the integer 4 less than it). + #math.equation(block: false, alt: "f")[$f$] is injective, but not surjective (10 is not 8 less than a multiple of 5, for example). + #math.equation(block: false, alt: "f")[$f$] is not injective, but is surjective. Every integer is an output (of twice itself, for example) but some integers are outputs of more than one input: #math.equation(block: false, alt: "f open parenthesis 5 close parenthesis equals 3 equals f open parenthesis 6 close parenthesis")[$f ( 5 ) = 3 = f ( 6 )$]. ] Let #math.equation(block: false, alt: "A equals open brace 1 , 2 , 3 , and so on , 10 close brace")[$A = \{ 1 , 2 , 3 , … , 10 \}$]. Consider the function #math.equation(block: false, alt: "f : P open parenthesis A close parenthesis → N")[$f : P ( A ) → N$] given by #math.equation(block: false, alt: "f open parenthesis B close parenthesis equals vertical bar B vertical bar")[$f ( B ) = | B |$]. That is, #math.equation(block: false, alt: "f")[$f$] takes a subset of #math.equation(block: false, alt: "A")[$A$] as an input and outputs the cardinality of that set. + Is #math.equation(block: false, alt: "f")[$f$] injective? Prove your answer. + Is #math.equation(block: false, alt: "f")[$f$] surjective? Prove your answer. + Find #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 1 close parenthesis")[$f^(− 1) ( 1 )$]. + Find #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 0 close parenthesis")[$f^(− 1) ( 0 )$] . + Find #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 12 close parenthesis")[$f^(− 1) ( 12 )$]. #solutionbox[ + #math.equation(block: false, alt: "f")[$f$] is not injective. To prove this, we must simply find two different elements of the domain which map to the same element of the codomain. Since #math.equation(block: false, alt: "f open parenthesis open brace 1 close brace close parenthesis equals 1")[$f ( \{ 1 \} ) = 1$] and #math.equation(block: false, alt: "f open parenthesis open brace 2 close brace close parenthesis equals 1")[$f ( \{ 2 \} ) = 1$], we see that #math.equation(block: false, alt: "f")[$f$] is not injective. + #math.equation(block: false, alt: "f")[$f$] is not surjective. The largest subset of #math.equation(block: false, alt: "A")[$A$] is #math.equation(block: false, alt: "A")[$A$] itself, and #math.equation(block: false, alt: "vertical bar A vertical bar equals 10")[$| A | = 10$]. So no natural number greater than 10 will ever be an output. + #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 1 close parenthesis equals open brace open brace 1 close brace , open brace 2 close brace , open brace 3 close brace , and so on open brace 10 close brace close brace")[$f^(− 1) ( 1 ) = \{ \{ 1 \} , \{ 2 \} , \{ 3 \} , … \{ 10 \} \}$] (the set of all the singleton subsets of #math.equation(block: false, alt: "A")[$A$] ). + #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 0 close parenthesis equals open brace ∅ close brace")[$f^(− 1) ( 0 ) = \{ upright(∅) \}$]. Note, it would be wrong to write #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 0 close parenthesis equals ∅")[$f^(− 1) ( 0 ) = upright(∅)$] - that would claim that there is no input which has 0 as an output. + #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 12 close parenthesis equals ∅")[$f^(− 1) ( 12 ) = upright(∅)$], since there are no subsets of #math.equation(block: false, alt: "A")[$A$] with cardinality 12. ] Consider the set #math.equation(block: false, alt: "N squared equals N times N")[$N^(2) = N × N$], the set of all ordered pairs #math.equation(block: false, alt: "open parenthesis a , b close parenthesis")[$( a , b )$] where #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are natural numbers. Consider a function #math.equation(block: false, alt: "f : N squared → N")[$f : N^(2) → N$] given by #math.equation(block: false, alt: "f open parenthesis open parenthesis a , b close parenthesis close parenthesis equals a plus b")[$f ( ( a , b ) ) = a + b$] . + Let #math.equation(block: false, alt: "A equals open brace open parenthesis a , b close parenthesis ∈ N squared : a , b less than or equal to 10 close brace")[$A = \{ ( a , b ) ∈ N^(2) : a , b ≤ 10 \}$]. Find #math.equation(block: false, alt: "f open parenthesis A close parenthesis")[$f ( A )$]. + Find #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 3 close parenthesis")[$f^(− 1) ( 3 )$] and #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace 0 , 1 , 2 , 3 close brace close parenthesis")[$f^(− 1) ( \{ 0 , 1 , 2 , 3 \} )$]. + Give geometric descriptions of #math.equation(block: false, alt: "f to the power minus 1 open parenthesis n close parenthesis")[$f^(− 1) ( n )$] and #math.equation(block: false, alt: "f to the power minus 1 open parenthesis open brace 0 , 1 , and so on , n close brace close parenthesis")[$f^(− 1) ( \{ 0 , 1 , … , n \} )$] for any #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$]. + Find #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis 8 close parenthesis vertical bar")[$| f^(− 1) ( 8 ) |$] and #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis open brace 0 , 1 , and so on , 8 close brace close parenthesis vertical bar")[$| f^(− 1) ( \{ 0 , 1 , … , 8 \} ) |$]. Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be some function. Suppose #math.equation(block: false, alt: "3 ∈ Y")[$3 ∈ Y$]. What can you say about #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 3 close parenthesis")[$f^(− 1) ( 3 )$] if you know, + #math.equation(block: false, alt: "f")[$f$] is injective? Explain. + #math.equation(block: false, alt: "f")[$f$] is surjective? Explain. + #math.equation(block: false, alt: "f")[$f$] is bijective? Explain. #solutionbox[ + #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis 3 close parenthesis vertical bar less than or equal to 1")[$| f^(− 1) ( 3 ) | ≤ 1$]. In other words, either #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 3 close parenthesis")[$f^(− 1) ( 3 )$] is the empty set or is a set containing exactly one element. Injective functions cannot have two elements from the domain both map to 3. + #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis 3 close parenthesis vertical bar greater than or equal to 1")[$| f^(− 1) ( 3 ) | ≥ 1$]. In other words, #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 3 close parenthesis")[$f^(− 1) ( 3 )$] is a set containing at least one elements, possibly more. Surjective functions must have something map to 3. + #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis 3 close parenthesis vertical bar equals 1")[$| f^(− 1) ( 3 ) | = 1$]. There is exactly one element from #math.equation(block: false, alt: "X")[$X$] which gets mapped to 3, so #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 3 close parenthesis")[$f^(− 1) ( 3 )$] is the set containing that one element. ] Find a set #math.equation(block: false, alt: "X")[$X$] and a function #math.equation(block: false, alt: "f : X → N")[$f : X → N$] so that #math.equation(block: false, alt: "f to the power minus 1 open parenthesis 0 close parenthesis union f to the power minus 1 open parenthesis 1 close parenthesis equals X")[$f^(− 1) ( 0 ) ∪ f^(− 1) ( 1 ) = X$]. #solutionbox[ #math.equation(block: false, alt: "X")[$X$] can really be any set, as long as #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals 0")[$f ( x ) = 0$] or #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals 1")[$f ( x ) = 1$] for every #math.equation(block: false, alt: "x ∈ X")[$x ∈ X$]. For example, #math.equation(block: false, alt: "X equals N")[$X = N$] and #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals 0")[$f ( n ) = 0$] works. ] What can you deduce about the sets #math.equation(block: false, alt: "X")[$X$] and #math.equation(block: false, alt: "Y")[$Y$] if you know, + there is an injective function #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$]? Explain. + there is a surjective function #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$]? Explain. + there is a bijective function #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$]? Explain. Suppose #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] is a function. Which of the following are possible? Explain. + #math.equation(block: false, alt: "f")[$f$] is injective but not surjective. + #math.equation(block: false, alt: "f")[$f$] is surjective but not injective. + #math.equation(block: false, alt: "vertical bar X vertical bar equals vertical bar Y vertical bar")[$| X | = | Y |$] and #math.equation(block: false, alt: "f")[$f$] is injective but not surjective. + #math.equation(block: false, alt: "vertical bar X vertical bar equals vertical bar Y vertical bar")[$| X | = | Y |$] and #math.equation(block: false, alt: "f")[$f$] is surjective but not injective. + #math.equation(block: false, alt: "vertical bar X vertical bar equals vertical bar Y vertical bar")[$| X | = | Y |$], #math.equation(block: false, alt: "X")[$X$] and #math.equation(block: false, alt: "Y")[$Y$] are finite, and #math.equation(block: false, alt: "f")[$f$] is injective but not surjective. + #math.equation(block: false, alt: "vertical bar X vertical bar equals vertical bar Y vertical bar")[$| X | = | Y |$], #math.equation(block: false, alt: "X")[$X$] and #math.equation(block: false, alt: "Y")[$Y$] are finite, and #math.equation(block: false, alt: "f")[$f$] is surjective but not injective. Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] and #math.equation(block: false, alt: "g : Y → Z")[$g : Y → Z$] be functions. We can define the #strong[composition] of #math.equation(block: false, alt: "f")[$f$] and #math.equation(block: false, alt: "g")[$g$] to be the function #math.equation(block: false, alt: "g ∘ f : X → Z")[$g ∘ f : X → Z$] for which the image of each #math.equation(block: false, alt: "x ∈ X")[$x ∈ X$] is #math.equation(block: false, alt: "g open parenthesis f open parenthesis x close parenthesis close parenthesis")[$g ( f ( x ) )$]. That is, plug #math.equation(block: false, alt: "x")[$x$] into #math.equation(block: false, alt: "f")[$f$], then plug the result into #math.equation(block: false, alt: "g")[$g$] (just like composition in algebra and calculus). + If #math.equation(block: false, alt: "f")[$f$] and #math.equation(block: false, alt: "g")[$g$] are both injective, must #math.equation(block: false, alt: "g ∘ f")[$g ∘ f$] be injective? Explain. + If #math.equation(block: false, alt: "f")[$f$] and #math.equation(block: false, alt: "g")[$g$] are both surjective, must #math.equation(block: false, alt: "g ∘ f")[$g ∘ f$] be surjective? Explain. + Suppose #math.equation(block: false, alt: "g ∘ f")[$g ∘ f$] is injective. What, if anything, can you say about #math.equation(block: false, alt: "f")[$f$] and #math.equation(block: false, alt: "g")[$g$]? Explain. + Suppose #math.equation(block: false, alt: "g ∘ f")[$g ∘ f$] is surjective. What, if anything, can you say about #math.equation(block: false, alt: "f")[$f$] and #math.equation(block: false, alt: "g")[$g$]? Explain. Work with some examples. What if #math.equation(block: false, alt: "f equals open parenthesis 1, 2, 3; a, a, b close parenthesis")[$f = ( 1 & 2 & 3 \ a & a & b )$] and #math.equation(block: false, alt: "g equals open parenthesis a, b, c; 5, 6, 7 close parenthesis")[$g = ( a & b & c \ 5 & 6 & 7 )$]? Consider the function #math.equation(block: false, alt: "f : Z → Z")[$f : Z → Z$] given by #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals open brace n plus 1, if n is even; n minus 3, if n is odd .")[$f ( n ) = \{ n + 1 & " if " n " is even" \ n − 3 & " if " n " is odd" .$] + Is #math.equation(block: false, alt: "f")[$f$] injective? Prove your answer. + Is #math.equation(block: false, alt: "f")[$f$] surjective? Prove your answer. #solutionbox[ + #math.equation(block: false, alt: "f")[$f$] is injective. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Let #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] be elements of the domain #math.equation(block: false, alt: "Z")[$Z$]. Assume #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals f open parenthesis y close parenthesis")[$f ( x ) = f ( y )$]. If #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] are both even, then #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals x plus 1")[$f ( x ) = x + 1$] and #math.equation(block: false, alt: "f open parenthesis y close parenthesis equals y plus 1")[$f ( y ) = y + 1$]. Since #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals f open parenthesis y close parenthesis")[$f ( x ) = f ( y )$], we have #math.equation(block: false, alt: "x plus 1 equals y plus 1")[$x + 1 = y + 1$] which implies that #math.equation(block: false, alt: "x equals y")[$x = y$]. Similarly, if #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] are both odd, then #math.equation(block: false, alt: "x minus 3 equals y minus 3")[$x − 3 = y − 3$] so again #math.equation(block: false, alt: "x equals y")[$x = y$]. The only other possibility is that #math.equation(block: false, alt: "x")[$x$] is even an #math.equation(block: false, alt: "y")[$y$] is odd (or visa-versa). But then #math.equation(block: false, alt: "x plus 1")[$x + 1$] would be odd and #math.equation(block: false, alt: "y minus 3")[$y − 3$] would be even, so it cannot be that #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals f open parenthesis y close parenthesis")[$f ( x ) = f ( y )$]. Therefore if #math.equation(block: false, alt: "f open parenthesis x close parenthesis equals f open parenthesis y close parenthesis")[$f ( x ) = f ( y )$] we then have #math.equation(block: false, alt: "x equals y")[$x = y$], which proves that #math.equation(block: false, alt: "f")[$f$] is injective. ] + #math.equation(block: false, alt: "f")[$f$] is surjective. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Let #math.equation(block: false, alt: "y")[$y$] be an element of the codomain #math.equation(block: false, alt: "Z")[$Z$]. We will show there is an element #math.equation(block: false, alt: "n")[$n$] of the domain (#math.equation(block: false, alt: "Z")[$Z$]) such that #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals y")[$f ( n ) = y$]. There are two cases: First, if #math.equation(block: false, alt: "y")[$y$] is even, then let #math.equation(block: false, alt: "n equals y plus 3")[$n = y + 3$]. Since #math.equation(block: false, alt: "y")[$y$] is even, #math.equation(block: false, alt: "n")[$n$] is odd, so #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals n minus 3 equals y plus 3 minus 3 equals y")[$f ( n ) = n − 3 = y + 3 − 3 = y$] as desired. Second, if #math.equation(block: false, alt: "y")[$y$] is odd, then let #math.equation(block: false, alt: "n equals y minus 1")[$n = y − 1$]. Since #math.equation(block: false, alt: "y")[$y$] is odd, #math.equation(block: false, alt: "n")[$n$] is even, so #math.equation(block: false, alt: "f open parenthesis n close parenthesis equals n plus 1 equals y minus 1 plus 1 equals y")[$f ( n ) = n + 1 = y − 1 + 1 = y$] as needed. Therefore #math.equation(block: false, alt: "f")[$f$] is surjective. ] ] At the end of the semester a teacher assigns letter grades to each of her students. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither? #solutionbox[ Yes, this is a function, if you choose the domain and codomain correctly. The domain will be the set of students, and the codomain will be the set of possible grades. The function is almost certainly not injective, because it is likely that two students will get the same grade. The function might be surjective – it will be if there is at least one student who gets each grade. ] In the game of #emph[Hearts], four players are each dealt 13 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither? Seven players are playing 5-card stud. Each player initially receives 5 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither? #solutionbox[ This is not a function. ] Consider the function #math.equation(block: false, alt: "f : N → N")[$f : N → N$] that gives the number of handshakes that take place in a room of #math.equation(block: false, alt: "n")[$n$] people assuming everyone shakes hands with everyone else. Give a recursive definition for this function. To find the recurrence relation, consider how many #emph[new] handshakes occur when person #math.equation(block: false, alt: "n plus 1")[$n + 1$] enters the room. #solutionbox[ The recurrence relation is #math.equation(block: false, alt: "f open parenthesis n plus 1 close parenthesis equals f open parenthesis n close parenthesis plus n")[$f ( n + 1 ) = f ( n ) + n$]. ] Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be a function and #math.equation(block: false, alt: "A ⊆ X")[$A ⊆ X$] be a finite subset of the domain. What can you say about the relationship between #math.equation(block: false, alt: "vertical bar A vertical bar")[$| A |$] and #math.equation(block: false, alt: "vertical bar f open parenthesis A close parenthesis vertical bar")[$| f ( A ) |$]? Consider both the general case and what happens when you know #math.equation(block: false, alt: "f")[$f$] is injective, surjective, or bijective. #solutionbox[ In general, #math.equation(block: false, alt: "vertical bar A vertical bar greater than or equal to vertical bar f open parenthesis A close parenthesis vertical bar")[$| A | ≥ | f ( A ) |$], since you cannot get more outputs than you have inputs (each input goes to exactly one output), but you could have fewer outputs if the function is not injective. If the function is injective, then #math.equation(block: false, alt: "vertical bar A vertical bar equals vertical bar f open parenthesis A close parenthesis vertical bar")[$| A | = | f ( A ) |$], although you can have equality even if #math.equation(block: false, alt: "f")[$f$] is not injective (it must be injective #emph[restricted] to #math.equation(block: false, alt: "A")[$A$]). ] Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be a function and #math.equation(block: false, alt: "B ⊆ Y")[$B ⊆ Y$] be a finite subset of the codomain. What can you say about the relationship between #math.equation(block: false, alt: "vertical bar B vertical bar")[$| B |$] and #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis B close parenthesis vertical bar")[$| f^(− 1) ( B ) |$]? Consider both the general case and what happens when you know #math.equation(block: false, alt: "f")[$f$] is injective, surjective, or bijective. #solutionbox[ In general, there is no relationship between #math.equation(block: false, alt: "vertical bar B vertical bar")[$| B |$] and #math.equation(block: false, alt: "vertical bar f to the power minus 1 open parenthesis B close parenthesis vertical bar")[$| f^(− 1) ( B ) |$]. This is because #math.equation(block: false, alt: "B")[$B$] might contain elements that are not in the range of #math.equation(block: false, alt: "f")[$f$], so we might even have #math.equation(block: false, alt: "f to the power minus 1 open parenthesis B close parenthesis equals ∅")[$f^(− 1) ( B ) = upright(∅)$]. On the other hand, there might be lots of elements from the domain that all get sent to a few elements in #math.equation(block: false, alt: "B")[$B$], making #math.equation(block: false, alt: "f to the power minus 1 open parenthesis B close parenthesis")[$f^(− 1) ( B )$] larger than #math.equation(block: false, alt: "B")[$B$]. More specifically, if #math.equation(block: false, alt: "f")[$f$] is injective, then #math.equation(block: false, alt: "vertical bar B vertical bar greater than or equal to vertical bar f to the power minus 1 open parenthesis B close parenthesis vertical bar")[$| B | ≥ | f^(− 1) ( B ) |$] (since every element in #math.equation(block: false, alt: "B")[$B$] must come from at most one element from the domain). If #math.equation(block: false, alt: "f")[$f$] is surjective, then #math.equation(block: false, alt: "vertical bar B vertical bar less than or equal to vertical bar f to the power minus 1 open parenthesis B close parenthesis vertical bar")[$| B | ≤ | f^(− 1) ( B ) |$] (since every element in #math.equation(block: false, alt: "B")[$B$] must come from at least one element of the domain). Thus if #math.equation(block: false, alt: "f")[$f$] is bijective then #math.equation(block: false, alt: "vertical bar B vertical bar equals vertical bar f to the power minus 1 open parenthesis B close parenthesis vertical bar")[$| B | = | f^(− 1) ( B ) |$]. ] Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be a function, #math.equation(block: false, alt: "A ⊆ X")[$A ⊆ X$] and #math.equation(block: false, alt: "B ⊆ Y")[$B ⊆ Y$]. + Is #math.equation(block: false, alt: "f to the power minus 1 open parenthesis f open parenthesis A close parenthesis close parenthesis equals A")[$f^(− 1) ( f ( A ) ) = A$]? Always, sometimes, never? Explain. + Is #math.equation(block: false, alt: "f open parenthesis f to the power minus 1 open parenthesis B close parenthesis close parenthesis equals B")[$f ( f^(− 1) ( B ) ) = B$]? Always, sometimes, never? Explain. + If one or both of the above do not always hold, is there something else you can say? Will equality always hold for particular types of functions? Is there some other relationship other than equality that would always hold? Explore. Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be a function and #math.equation(block: false, alt: "A , B ⊆ X")[$A , B ⊆ X$] be subsets of the domain. + Is #math.equation(block: false, alt: "f open parenthesis A union B close parenthesis equals f open parenthesis A close parenthesis union f open parenthesis B close parenthesis")[$f ( A ∪ B ) = f ( A ) ∪ f ( B )$]? Always, sometimes, or never? Explain. + Is #math.equation(block: false, alt: "f open parenthesis A intersection B close parenthesis equals f open parenthesis A close parenthesis intersection f open parenthesis B close parenthesis")[$f ( A ∩ B ) = f ( A ) ∩ f ( B )$]? Always, sometimes, or never? Explain. One of these is not always true. Try some examples! Let #math.equation(block: false, alt: "f : X → Y")[$f : X → Y$] be a function and #math.equation(block: false, alt: "A , B ⊆ Y")[$A , B ⊆ Y$] be subsets of the codomain. + Is #math.equation(block: false, alt: "f to the power minus 1 open parenthesis A union B close parenthesis equals f to the power minus 1 open parenthesis A close parenthesis union f to the power minus 1 open parenthesis B close parenthesis")[$f^(− 1) ( A ∪ B ) = f^(− 1) ( A ) ∪ f^(− 1) ( B )$]? Always, sometimes, or never? Explain. + Is #math.equation(block: false, alt: "f to the power minus 1 open parenthesis A intersection B close parenthesis equals f to the power minus 1 open parenthesis A close parenthesis intersection f to the power minus 1 open parenthesis B close parenthesis")[$f^(− 1) ( A ∩ B ) = f^(− 1) ( A ) ∩ f^(− 1) ( B )$]? Always, sometimes, or never? Explain.