INJECTIVE, SURJECTIVE, and BIJECTIVE FUNCTIONS - DISCRETE MATHEMATICS

welcome back to discrete mathematics today we're going to take a look at injective surjective by ejective functions and then we'll take a look at inverses so let's get straight into this one-to-one functions or injective functions state that if X 1 is not equal to X 2 then f of X 1 should not be equal to f of X 2 and of course we take a function from F or a function f from X to Y so here we have our domain going to the codomain and I'm going to illustrate this with diagrams for each one so what this says is that if X 1 is not equal to X 2 so for instance X 1 and X 2 here are different then we should always get X 1 going to a different Y value than X 2 so this would be acceptable what would it be acceptable is if X 2 also pointed to Y 1 in fact if we have this case then what it means is that this X 2 is actually just X 1 in disguise so that's what it means if it's injective so we'll prove that an equation is injective and when we have an equation like this f of X is equal to 3x minus 2 before I said that X 1 not equal to X 2 implies that f of X 1 not equal to f of X 2 it's easier to prove the contrapositive so what we can say is that f of X 1 is equal to f of X 2 implies that X 1 is equal to X 2 so we're going to show this so how do we do this well we start off and we say okay let's assume f of X 1 is equal to f of X 2 so what are those functions look like well for f of X 1 we're going to get 3 times X 1 minus 2 is equal to 3 times x2 - - okay so we can bring the twos over the other side so then we're going to get 3 X 1 is equal to 3 X 2 then we can divide both sides by 3 so we get X 1 is equal to X 2 so we have proven that it is in objective or one-to-one so what does this look like graphically with this so 3x minus 2 probably looks something like this where this value right here is minus 2 so when we take a look at our x-axis so let's say we pick this 3 here it corresponds to this value up here which would be 7 and when we do this we notice that if we go to the left or go to the right there's no other value that goes to the exact same y value so there's no other X we can choose that gives us the same Y 3 is the only value that's going to give us f of X is equal to 7 so that is a proof that 3x minus 2 is injective so let's take a look at another equation f of x equals x squared so let's take a look here f of x1 is equal to f of X to start out with that so this means that x1 squared is equal to x2 squared okay so let's take the square root of both sides well that means that plus or minus x1 is going to be equal to plus or minus x2 so here's the question does x1 equal x2 and the answer is going to be no why because well plus or minus x1 that means that positive x1 can be equal to negative x 2 so for example that's like saying that three is equal to negative three and that's clearly not good that's not right for an injective function so it is not injective in fact when we take a look at the graph here I'm sure you guys all know the x squared graph it looks like this so let's pick x equals three then we get this value which we'll call nine what objective says or what a one-to-one function says is that no other point or no other x value except for three should give you nine but when we go over here and we take a look at X is equal to negative three that also gives us nine but that means that negative three and three should be the same point which we know it's not true therefore x squared is not going to be injective so that's injective functions surjective functions or on two functions state something a little bit different here we have f going from x to y so f is surjective if for all y there is some element X where f of X is equal to Y so what this just means is that the codomain is equal to the range so for all possible values of Y there is some X that gives you Y so for instance this y1 might map on to X sorry this should be the other way so x1 will give you y1 x2 will give you Y 2 but let's say there's nothing for y3 let's say we can never get to y3 well then the functions not on 2 because we need some element X 3 that gives you y3 so that's how we know a function is on 2 when everything in Y has some element X that you can get to Y so how do we do this well let's show that f of X equal to 5x plus 2 is surjective so what I'm going to do is I'm going to say okay let's let y is equal to f of X and we'll just work with Y here so Y is equal to 5x plus 2 now we want to solve this equation in terms of X so we have Y minus 2 is equal to 5x so Y minus 2 over 5 is equal to X so now that we have this equation in terms of X equaling whatever we can now check values of Y and make sure there's a corresponding X so I'm saying okay we want to check if it's surjective for the real numbers so if we pick Y is equal to 0 and that means that X is equal to negative 2 over 5 okay if Y is equal to 1 then X is going to be equal to negative 1 over 5 so if F maps from the reals to the reals then yes this is surjective because all of our Y values are rational all of our X values are rational so we're good but what about if we map F from the integers to the integers well we've seen here that if Y is equal to 7 then X is equal to 1 so that's good we can get 7 but can we get 5 well if Y is equal to 5 then that means that X is going to be equal to 3/5 but this 3/5 is not in the integers so we can't get Y is equal to 5 from the set of integers which means that this y equal to 5 is not in the range and if it's not in the range then it can't be a surjective function so this function here is surjective dependent on which set of numbers were mapping to and from so what we could do is offer an even trickier question so let's say we have F mapping from the set of real numbers to the set of integers so what this means now is that Y is only going to be integers but these X values here they can be any real number so is this function surjective and the answer is going to be yes it is surjective because all of these X values that get y equal to some integer they are going to be fractions rational fractions so we're good so when you take a look at surjective functions you have to consider your range your codomain your domain and you need to see okay what set of numbers are these values coming from because that's very crucial when we do pi jected functions all we mean is other injective and surjective so you take a function f of X and you say okay I need to prove it's injective and I need to prove it's surjective and when you do both it is ejective so what is my jected mean well it means for f going from x to y each x maps to exactly one unique y so for instance we can get a nice map like this where all x's go to all wise and that's okay what this means is that you can't get let's say we have three things here we cannot get one of our X's or two of our X's going to the same Y value so if we have x1 and x3 they could not go to the same value they all have to go to exactly one unique value and because it's also surjective all of the values in Y have to be used so all of these values here have to be used and that means each of them go to exactly one in the domain and because in a function we have to use all the values in the domain that means that the domain is also all used so what does this mean about the size of x and y well all this means is that the size of X or the size of our domain is equal to the size of the codomain so if this isn't true then we can't have a bijective function we can have a bijective partial function but we can't have a bijective function so this is a very good test to see if you even have a function in the first place but that's a little bit more intro to analysis sort of thing as opposed to a discrete math one course so the cardinalities should be the same okay so we've talked about by actions injections surjections we should probably talk about inverses because inverses are related directly to by directive functions so if f mac maps from x to y the inverse maps from Y to X so what this means is that if we have an x1 value and it takes our function f to y1 then we can just go backwards and take the inverse of F to get it back so when we say that f of X is equal to Y we also get that F inverse of Y is equal to X so sometimes you'll get a question on an exam that says find the inverse of let's say f of X is equal willed it the same question 5x plus 2 then what you have to do and in discrete math this is a little bit tricky because here we say inverse if it does not you that f of X is equal to 5x plus 2 is a bijection then we have a problem because well an inverse this implies something this implies that the function is by jected which means that you have to prove that it's injective and you have to prove that it's surjective now luckily when you ask for an inverse when you prove that a function is surjective you always get the inverse so luckily you get a quick solution to finding an inverse because it's already part of your proof in fact on my second midterm tribe tutor calm discrete math one section midterm two there is a question where you have to find a bijection so you will ultimately end up getting the inverse as well even though I don't ask for it so here's a question let's say I have F of F inverse of Y and I have f of X is equal to Y and F inverse of Y is equal to X what does this function evaluate to well so we have F and this F inverse of Y is equal to X so then we get f of X and f of X is equal to Y so f of F inverse of Y is just equal to Y and we know this should be true because when we take a look here we first take y1 we map it over to x1 and then we take F back and we get to Y so when you take the inverse and then or sorry when you take just the function f and then you invert it you just get back to where you started so what we have here is kind of like a cycle we'll call it a cycle this is informal so I'll write that informal put cycle in quotation marks it's just a good way to remember it that F of F inverse they cancel each other out it's kind of like saying three times one third of a variable X where you take an x-value you multiply it by a third and then you multiply by three and you just get this equal to X sort of like doing the same thing in fact consider this your f and consider this your f inverse and surprise-surprise this is actually an F F inverse X question like these are actual functions f of X is just equal to three X and F inverse of X or F inverse of Y is just equal to one-third X so that's a nice way of doing it sorry there should be one third why okay so that was in verses by ejections injections and surjections like I mentioned before there is a midterm to at trip tutor come if you check out the discrete math one section midterm two there are some questions there there's also a final which covers a lot of other material so you can check that out there if you have any questions you can leave them in the comments below or you can go to reddit.com slash are slash tribe tutor there's a nice little community there where I answer questions other people can answer to and it's archived so you'll get to see everything anyone has ever asked in a nice little location so if you enjoyed the video share with your friends if not leave constructive criticism below and I hope you guys have a great day

Channel: TheTrevTutor

Views: 513,304

Rating: 4.9201221 out of 5

Keywords: bijection discrete math, surjective injective bijective, injective surjective and bijective functions, injective surjective and bijective, bijective, bijective injective surjective, bijective function, injective function, injective, surjective and injective functions, injective and surjective functions, surjective, functions discrete math, discrete mathematics functions, discrete math functions, surjective function, functions, function inverse, Codomain

Id: bZred_Ksz2k

Length: 17min 14sec (1034 seconds)

Published: Tue May 19 2015