02 Injective, Surjective and Bijective Functions

it's a bit small but I think it would be easier for me if it's vertical than horizontal okay so at last time we talked about uh functions um I'll just remind you a function um for sets A and B a function f from A to B is a rule um that assigns for every a in a a unique element B in b h denoted um B is f of a and now um we talked about compositions so this is a what I write here is like the informal or slightly less formal definition of a function um but we saw a completely formal definition in in which H you define a function as a subset of the cartisian product of A and B and we talked about about compositions of functions and about the identity function and today I want to talk about H types of functions um so function f from A to B is um injective if um for any two elements a and a prime in a that are different F of a is different than F of a prime uh this the function f from A to B is subjective if for any B in B there exist some a in a such that F A is equal to B and finally a function is called bjective um if it is injective answer injective so maybe just a a few synonyms um injective maps are also called a monomorphisms subjective m is an epimorphism and a a bjective map is a isomorphism um we will see later on various um incarnations of the notion of isomorphism um between groups for example but the the terminology is is meant to say um in a specific context like if we talk about sets there is a notion of isomorphism of sets we talk about groups there would be isomorphism with groups and so on um but you don't have to dwell into this H alternative terminology at the moment ER and ah maybe even a third um a third synonym for injective we can we say sometimes we say one to one for subjective we say onto and is there an analog of bjective I guess so isn't bjective one to bjective is injective so it is in particular one to one but it's not a a bject um I guess you can say sometimes people say one to one correspondence and this this means bjective so these are all synonyms but I will mainly use injective subjective and bjective at the moment so just an intuition a injective map it means that it does not repeat itself I mean if if you give me two inputs then uh two different inputs then the the output of the function will be the subjective map means that for every element in the in the output set I can find the source okay I can find some some element that is mared by the by the function f to to this given output and bjective means um both right I do not repeat myself I mean the function do not repeat itself and um covers the the output set B right subjective another way to intuitively think about subjective Maps is that they cover the the output set and um the best the best illustration of these Notions is for a finite sets so let's let's suppose I have a a and b like so H and I could I could Define a function by just uh drawing some arrows that indicate um where does each input of a go in B and this would be this correspondence would I mean this this diagram would Corr respond to an injected function on the other hand uh if I have um a correspondence like this then this would be a subjective M and and finally if I have [Music] correspondence like this and this is bjective [Music] um so you see that for finite set what we should expect is that the the would exist as an injected function from A to B if and only if the number of elements in a is is smaller or equal than the number of elements in and similarly we should expect that there would exist a subjective map from A to B if and only if the number of elements in a is bigger equal than the number of elements in B and finally the there should be a bjective map between A and B if and only if they have the same number of elements okay so so this kind of reasoning is sometimes referred to as the pan Hall principle and I I would like I would like to uh to prove it so let A and B Be finite sets and then the first claim is that there exist I will write instead of a function I will write map F from A to B let's say an injective map F from A to B if and only if the number of elements in in a is smaller or equal than the number of elements in b um the second claim is that there exist subjective m f from A to B if and only if the number of elements in a is bigger or equal than the number of elements in and three there exist um projective um f from A to B if and only if the number of elements in a is equal to the number of elements of B okay so before we get to the proof I just want to clarify the statement let's say if the number of elements in in a is equal to the number of elements in B it does not mean that every function from A to B is bjective okay only that there exist a function and similar similarly to the other two because of course if you have non empty sets you can always Define a function that takes um all the elements in a into a single single element in B for example this is not subjective and not projective um okay so let's prove it [Music] and okay [Music] suppose if and if from A to B is injective and enumerate a is m a = A1 up to a [Music] right I mean when I say enumerate I mean sets if you remember do not come with a particular order of elements so if I want to work with a particular order I need to I need to choose one um but that's okay um I chose an an arbitrary order and now [Music] um for m i between one and N Den note bi I to be F of a i this is an element in B right it must exist uh and so the set B1 up to BN is contained in the set hence the number of elements in in B is bigger or equal than n which is the number of elements in n and conversely if um the number of elements in a is smaller or equal than the number of elements B um enumerate a and is again it's A1 up to a um and B is B1 up to BK of course by the Assumption K is bigger or equal than n and now [Music] Define f from A to B as F of a IAL b i okay and this is an injective function observe that f is injected okay um I guess the this the the two other closes of the the proposition are very similar so I don't feel a particular need to to prove them but if you want we can do it otherwise you can you can do it as an exercise is um is this clear do you want me to um go over the the proof of the other clauses uh I can see the relation that the set B is Bigg than from the C part of the group I'm sorry I can see the relation that b the set B is bigger than a from the proof yeah well because in the first part we um we have an injected function and we know I mean if the set B contains at least um n distinct elements the these these must be distinct these These are distinct because f is injected right and so if B contains n distinct elements then the number of elements in B is is at least n yes yes yeah or okay so did you ask about another thing how could it be that how could it that means those elements of B can is bigger than a the number of elements are a number of element you see here I write okay included inclusion is a is a relation between two sets and then smaller equal is a relation between numbers so I say number of elements in a is smaller equal number elements ah it's number of elements yes yes it's clear okay yeah I guess maybe just um for clarity let me do the second uh the second Clause so and suppose F from A to B is subjective um I I I enumerate b as uh B1 up to BK um and since f is rejective H for every I between one and K there exist an element AI in a such that F of a i is equal to b i right so so I mean of course by the definition of a function um I cannot map one input element into two distinct output elements so it means that um the number of elements in in a must be bigger or equal than the number of elements in B if you want the the the set A1 up to a let's let's put it like this A1 up to a are distinct since f is a function and this means that the number of elements in a has to be bigger or equal than K which is the number of elements in um conversely if the number of elements in a is bigger equal than the number of elements in b um I I write for example a b A1 up to a n [Music] and and I want to [Music] Define so I need to enumerate b as well B1 up to BK um where I know that K is smaller equal than n [Music] Define f from A to B by of a IAL B if I is between 1 and K right because if I is bigger than K I cannot I don't have b b but that's not a problem F of AI can can repeat in to for example B1 for I bigger than k then then f is projected right it covers all of the and the third CLA of course follows from the the the first and the second any questions about the the proof uh yeah it's a bit like spitting here but we defined last week this proof relies on in this right so we did find an index for one 12 a 1 2K and last week if I remember correctly we were defining the indices as some kind of function because um yeah it was it was uh I'm trying to remember maybe I'm saying something wrong but I I got the feeling that uh we were doing this like we were defining an index as a um as an increase every time like uh every time we we were adding a new item to the index we were creating a new a new element that was the previous set and adding a new set and that felt like a function to me that's why you mean this definition of natural numbers yeah well this this is different I mean what I I did last time with the definition of natural numbers is kind of a foundational approach and we I mean I did it to to demonstrate how how modern mathematics can be constructed from sets I still didn't Define the integers and the rationals and the reals as as sets but later on I I will show you how um but this is a kind of ponal to what we will do most of the time because we don't we don't dwell too much in the foundations I mean so you can I mean just for an illustration of how the foundations are are treated and then natural numbers are just you know usual and if you want when I when I enumerate a you can say that I I I Define a function let's call it a [Music] end from the set of natural numbers one up to n into a right and then I say that a end of I I denote as a I right uh yeah that's exactly my problem um because isn't there like when you define end isn't that assume that it's got to be a projection yes this is a b i me if a has n elements if a has an element then there exist a projection from the set one up to yeah right but you see okay my my problem but okay we don't have to do all on this uh is just that it seems to me that to Def to define the bje you need the indices and the indices are defined as a projection already um no this is I mean it's a good point may look circular but if you notice for the the bare definition of bjective injective and so on I didn't use any indices the indices I use only the proof right of the proposition yeah so I make a claim the claim is is well defined without without indices okay and then I prove it with indices okay okay right okay doesn't need IND theoretically there exists another proof that doesn't use in I no that's not what I'm saying I you will need you will need to enumerate in the proof but this there is I mean you need to distinct between the statement and the proof right I mean it is circular if if I try to define a notion with the notion itself this is circular right that's that's a problem right but if I Define the notion without referring to itself and then I use the defined notion in the proof then I claim that this notion satisfy a property and in the proof of the the the property of this claim I use the the notion that's okay it's legitimate okay but to be completely honest I mean if you want to prove it from the axioms you need to do a bit I mean to be a bit more formal but we don't this is why I call it na set the we don't ER we don't take too much time on the the foundation I guess you can say intuitively okay if a has an elements then I okay okay other other questions there's question the CH yes uh okay a y1 so in the in the the second part of the I mean the proof I said that I mean suppose a a number of elements of a is bigger equal than the number of elements in B then what I need to show is that there exist exist a subjective function from A to B so I need to Define it right and so I enumerate a and I enumerate B and by assumption I know that that K is smaller equal than than n and now I need to Define an actual function that will be subjective so I mean I want to cover all the elements in B so so I Define f of a i to be b i this already covers all the elements of but it's not yet a function because it is it is not defined on all input elements of a right I mean I I mean if if I is is bigger than k then I don't have the I if I is is equal to k + 1 for example then I don't have a b k + 1 but I might have a k + one so I need to say where does the I mean in order to to Really Define a function I need to say where does for example a k + 1 go so I don't care where it goes I just need to Define it um completely so I I say that it always go to B1 this is a kind of an arbitrary choice yes I I prove by showing that there is one subjective function yeah and of course let say not every function from A to B would be SED okay um the next is something that maybe is very clear to you but um I think stating it is is important because it's um it's going to be a repeated theme so suppose a B and C are sets and um f from A to B G from B to C functions if both f and g are injective and then so is G composed f g composed F I remind you it's it's a function from a to c um if both f and g are subjective then so is G compos F and the same for projective with both f and g projective G compos and um the reason I'm saying saying that it it is a repeated theme is that properties of of functions um would almost always the the types of functions that we talk about between sets but also between groups and between fields and so on H if we have a notion of a type of function we should always expect that it would be um closed under composition closed under composition is exactly what is expressed in the in the proposition I mean if you have two composable functions and two of them are of a particular type then the composition must be of this type this is an expected problem of every every every uh notion of of a function that we def so um in set it is injective subjective and projective um let me show you let's say the first part um suppose um and f and g are injected and um and now I consider this function G composed F from a to c to show that a a the G composed f is injective I need to choose two different elements in a and show that they are they are mapped into two different elements in see so let a different than a prime two elements in a then F of a is different than F of a prime since f is injected and now since G is injective G of f of a and G of f of a prime are different right you you you give it two two different input it has to give you two different outputs but this thing is by definition G composed F evaluated at a and this thing is G composed F evaluated this is definition okay so we know that g composed f is in I think uh there could be a counter case maybe because we are the proposition of that because we are assuming for the final St no no no we do not assume oh okay but of course if you have a counter example for finance sets it's it's also a counter example of the proposition right yeah I was think I thought we p no we do not assume finances but but even but this proposition is true also for finances this this I mean I'm I'm claiming a more General that's sure so if there was a a a a problem in in the finite case there would be a problem in the proposition right right okay um so just a general remark I mean I I try to be very precise so if the fact that I I didn't say that they are finite sets really means I mean I would I would I would be very careful stating whether my claim is true for only for finite sets or for all sets um so this this is the first H the first part of the the the proof and to show you the the second part for example um if um and G are subjective um and now we we consider again G composed f as a function from a to c and we need to the claim I mean we we want to show that this function is subjective so we take it means that for every output element in C there exist an input element in a such the G composed F of a is this output element so let C be an output element since G is SED here and there exist some B in B such that the G of B is equal to C and since f is subjective and there exist some element a in a such that F of a is equal to B and now I do G composed F evaluated at a this is by definition just write it in the second line this is by definition G of f of a but F of a is by definition B and G of B is by definition C so I took an arbitrary output element C and I I found the source a to is a so a g composed f is rejected and just like in the the previous claim three follows from one one and two right because if I compos two bjective Mass both of them are injected and subjective the composition of injective is is injective Proposition subjective any questions about what Pro okay um maybe one one more uh nice proposition about injective and subjective Maps is the following let A and B Be sets and F from A to B a subjective function then for any set C in any function um any functions G and H from B to C so I write it with two arrows such that g composed f is equal to H composed F we have G = to F sorry gal to H to maybe to to uh give you like this is a bit abstract um to give you an intuition of what this this means it it's kind of um we say that [Music] F in this case is right cancelable right cancelable refers to this this equation right it means that whenever I have an equation um like so so where where f is is on the right then then I can cancel F and I I get that g is equal to H right but composition is not a is not a commutative operation right F comp even if I could do F compos G and G composed F it's not necessarily equal so so hence the distinction between right cancelable and left cancel and the claim is that a subjective map is the same as or at least for a subjective map and we have a right cancelability and it's in fact in even on if I I don't want to um spend too much time on it let me just show you how how how you prove this so [Music] um let a b be any element right I want to show that g is equal to H so I I choose an element B B and I want to show that g of B is equal to H of B okay since f is rejective there exist some a in a such that F of a is equal to B and therefore um now I do G of b g of B is the same as G of f of a which is the same by assumption as age of f of a but age of f of a is a to B so I get the G of B must be equal to H for any I have a bit of an issue with this CU what if uh what about all those values that are not touched by f as uh f is subjective F touches everything oh is Ah that's it that's one okay yeah thank you um maybe an exercise um we Pro the following this if if from A to B is injective then it is left cancelable in that and for every g h from um let's say a Prime into a if or such that and F composed G is equal to F composed a H we have G isal to H okay so this is left okay um now would be I guess a good time for a break unless uh you have any questions all right H you can think of questions after the break and let's start again H so what I want to say about this this uh last proposition and and exercise is that it I mean it reveals um some phenomena that is usually referred to as a duality so once we we obstruct these properties I mean I didn't say it but the proposition is in fact if and only if so a function is subjective if and only if it is right cancelable and it is injective if and only if it is left cancelable and Via these these reformulations you can see that injective and subjective are dual Notions right in the sense that um I mean one of them simply means that you can cancel on the [Music] right equation like like the one in the in the purpose box and and the other says that you can cancel on the on the left the equation of um of the blue box and so it is it is a I think it is useful perspective generally as we go on we will deal a lot with injective and subjective functions with additional properties um and so they they are dual to each other I think it helps understanding the [Music] context the the next position I want to do well actually it's it's a theory uh let A and B be set and F A to be a function then if is bjective if and only if there exist a function which I denote as [Music] fus1 from B to a such that F composed F-1 is the identity function on B and F -1 composed f is the identity function [Music] a okay so in um in diagrams what this proposition tells you is that you start with a with the function f and f is bjective if and only if there exist a function f Min - one such that if you go f and then F minus one you get the identity function on a right here you have the identity and if you go f minus one and then F you get the identity function of B and um the function fus1 is called the the inverse okay okay so how do we prove it suppose f is and now I want to Define this function f minus1 which needs to be a function from B to a so I need to tell you for every input element in B what is the output of Fus one evaluated and since f is rejective there exist some element or maybe let's put it like this M for every B in B there exist some a in a such that F of a is equal to B and since f is injective this a is unique right the you cannot have any other a prime that is mapped to the input B and we Define fus1 evaluated at B to be a this a and this is this is um this is well defined this is the function by okay so I defin the function and and I want to show the two properties let's call it one and two uh to show this so let's start with one one um we want to show that F composed fus1 is the identity function on B H let B be an element in B then by [Music] definition there exist a unique element a in a such that F of a is equal to B and M f- one of B is equal to this a but then when I [Music] do when I do F composed fus1 evaluated at a sorry evaluated at B then then by definition of composition of functions this is the same as doing F on Fus one of B but Fus one of B is a so this is f of a and F of a is B so I get that F composed fus1 evaluated on every element B is just a the the same element be so this this means that F composed fus1 is equal to di function um two is is in a very similar manner so um we want to show that F -1 composed f is the identity function on a so I take an arbitrary element a in a um then um by definition by definition of of F-1 F-1 evaluated at F of a is equal to a right because Fus one you take an element B in B you find a source the source is unique because f is a bjective function so there exist a source this is B right you take an element B sorry uh you take you take an element B and B and um you define Fus one on B as I mean as the source of B under F so okay so if I take the element B to be F of a then the source I mean then then F minus one of B is is simply a and and this means of course that Fus one compos f is the identity function so this is One Direction of the of the theory right the theorem says if you have I mean f is a bjective function if and only if it has an inverse so what we proved so far is that if f is bjective then it has it has an inv uh any question questions about this part before we move to the next one okay so conversy suppose if has an inverse IE there exists some Fus one from B to a such that F composed fus1 is the identity of B and F-1 composed f is the identity on a so now we want to show we want let if show f is pro so um how do we show that f is let's say injected I take so remember this the picture you think is is is quite helpful for understanding the the dynamic of the proof I I am given F and F minus one and I know that they are inverse to each other in the in the sense of these two equations and now I I want to show that f is injective so I take two elements a and a prime in a and I want to show that F of a is different than F of a prime so let a and a prime be two different elements in a um then what I can do is I take F of a and F of a prime and I apply F minus one on them and I guess we can do it like this um and and and supposed by contradiction or towards contradiction that F of a is is equal to F of a prime then F-1 of f of a would have to be equal to Fus one of f of a prime right because Fus one is a function you give it the same input it has to give you the same output but we have this I mean Fus one F of a is simply a and Fus one of f of a prime is simply a prime so I get the contradiction because I assumed that a is different than this contradiction so this proves that f is injective and for surjectivity [Music] um and let B be a IAL element an arbitrary element in in the output set B and I need to find the source for for B what is going to be the source I'm going to apply F minus one on B then um f of f -1 of B is equal to B because F composed fus1 is the identity function of B so F-1 of B which is an element in a is a source for m b under F and this means the f is um f is SED okay so we we finished the proof and as a remark maybe exercise and they show appr proof that in the um above Fus one is always projective okay so it's really um if f is bjective then the inverse is bjective and if F has an inverse then the then the in the f is bjective the inverse is bjective it's kind [Music] of bjective you could say that it really means that I can h I can reverse the arrows if I had um let's say two finite sets I could [Music] Define a bjective function with these arrows but I could also I mean this is let's say A and B and let's say um this is f but I could also Define a f minus one by just reversing the arrows and okay so of course for finite sets the claim is is very easy it's not it's almost doesn't need any proof but the the the main the main new thing of of this this steering that it works for any sense this sets could be infinite and maybe slightly less trivial examples just need to look it up in notes so uh let a be the unity interval and B be the interval of all numbers bigger equal to three and smaller equal to 5 Define f from A to B is uh the following formula f of x is um 2x + 3 Define what I want to be the inverse so I will denote it as [Music] fus1 um from B to a let's let's put it like this Fus 1 of Y is equal to y - 3 divided by two then I claim I mean that F composed fus1 is the identity of B and F-1 composed f is the identity of a how do we see this say this is one and this is two so two one [Music] m i take f i compose it with f minus one so I take F of F-1 of Y this is f of y - 3 / 2 but what F does to an input is multiply the input by two and add three so I get Y and uh on the other side um I take fus1 and I evaluate it on on an input f of x this is by definition F-1 of of 2x + 3 but what fus1 does is substract three from the input and divide it by two so this is X and what this means is that f is the original F and and actually also F minus one are rejective right because we know by the theorem that if we I mean if we have an inverse then the function must be projected and you can view this geometrically I mean I have the the unit interval let's say and then I have another interval 3 to 5 they are not of the same length and they do not um they do not lie in the same place in the the the line of numbers but I can I can BL blow up and translate so I blow up by two you you can view this function as composition of two things first I blow up the interval 01 into the interval 02 I just taking X to a 2 x and then I translate the interval 02 into the interval 35 by by taking X to x + 3 okay and by and blowing up is a is a bjective function and translation is also a projective function and composition of two projective functions is projec okay so this um this tells you a little bit um what happens when I have infinite sets I mean they could be of a different size on the the real on the line of real numbers and still be I mean and would still have a a projective function between okay however there is a um a different notion of of [Music] size so you could say that in this example what may be a bit weird is that the size of the ER the unit interval is is small let's say smaller than the size of the interval 3 3 to 5 and nevertheless I was able to find a a bjective function between them and we know in in finite sets I should only be able to find a projective function if the sets have the same number of elements so in some sense this example tells you that the number of elements if I would Define a number of elements for infinite sets then the number of elements of these two sets should be should be the same and and it means that size of sets of infinite sets do not correspond precisely to the their length on the on the line of real numbers however um I could say so for infinite sets I could say that um the number the the set the number of elements in the some generalized sense of a set a is smaller or equal than the number of elements in B if there is an injective function from a and the number of elements in B is is bigger or equal than the number of elements in a if and only if I if there is a subjective function from B to a so this this is kind of a definition right I could extend the notion of size into Infinite sets with this um with with the the the Notions of injective and subjective functions and I would say that the number of elements in a is the same as the number of elements in B if if there is a bjective function so now okay I can make these definitions um but there is a question if if I can find two infinite sets that um for which there there is no bjective function between so [Music] in other words if I use this notion of size in a generalized sense would would I have two infinite sets that are not of the same size so let me be more precise this is a this is an aside I think we have a bit a bit more time so I will take the rest of the the session to do an aside this is Contra Theory and what contr theorem tells you is that [Music] um there is no subjective function from um let's say the natural numbers to the real number numers and again um this is an aside we are not going to use it in the the rest of the the lectures but I think it has an interesting application for programming languages so before I prove it let me just draw the coroller um let's see I think I formulated it so a fix programming language and consider the set P bar of all the programs um in this [Music] language and consider a subcollection P within P bar of all [Music] programs that output a decimal representation a decimal representation I mean um x dot X1 X2 and so on it's the output of a program is is always finite so this it must end at some xn and to be a valid decimal representation X needs to be an integer and all the X I are [Music] digits um and we we can I mean we can consider the um the output of a program p in P um you can say theoretical let's say theoretical output is going to be a what happens when I let the program run indefinitely when we let it run indefinitely right so I I get some some decimal representation that it could go on of course if it doesn't go on if it the program stops to print the decimal representation at some point then I consider the the rest of the decimal representation to be zeros and now I claim by a counter Ser there exist at least one number X in R and for which there is no program p in the language in fact but in p as well whose whose theoretical output is X and the reason is that the set of all programs in a given language can be a a correspond we can find a one to one correspondence between the set of all programs in a given language and the set of natural numbers so we it can [Music] find a bjective m a bjective function between P bar this I remind you is is all all programs and the natural numbers how do I do it I mean I have the program with only one character let's say it's the first character in the alphabet then I map it to the the natural number one then the program with one character who is the second character in the alphabet I I map it to two and so on okay so so so if and by contradiction or let's say if um for every real number is there would be and a program p in in p i mean a program that a prints that print X we would get a subjective map between let's say um p and and R right because it means for every real number X you would be able to find the source um a source P that Maps into X and A P of course p is contained in P bar P bar and is has a bje to um to the natural numbers so I would be able to find at least this is a objection I would be able to find a subjective map from the natural numbers to the set of all programs that actually print decimal representations and I would take this composition this this would be a subjective map between the natural numbers and the real numbers and this would contct cont Theory so subjective map um n r um and and this contradicts contr the uh I miss the part where the subjection is between n and p and not between n and p bar h i mean p is included into P bar yeah so you can always find a subjection from P into um P bar into P yes so just compose this rejection I mean you can compose these two you have I mean you have a projection from n to P bar yes in particular a subjection and you have a subjection from P bar to P the subjection from P bar to P is just saying for example you choose an element just an arbitrary element in p and you take an arbitrary element in P bar if it is in P then you map it into itself and if it is not in P you map it into the the element you chose in B okay okay so I mean you like this is p bar this is p it could it could be infinite I I choose one kind of Anchor Point and all the elements p i map I map to themselves and if I have a other elements I just map them to here oh the the rejection is between p and p bar so it's from P into P bar no because yeah the S is from P to to P okay okay so then I compos it so from n to P bar is a subjection from P bar to P I I can define a subjection and if if any real number could be printed theoretically by a computer program in P then I would get a subjection from from P to R so composing this subjections I would get a subjection from the the natural numbers into R and this is a contradiction to here does that means uh there so there is so there is a real normal that can be represented as a decimal representation no I assume that all real numbers are rep have a decimal representation but remember the decimal representation could be infinite so what this the counter theing tells you is that in a way you cannot this is kind of a noo theor for Randomness if you think I mean this this would be one interpretation but it tells you that you cannot you cannot possibly hope to to print all all possible decimal representation there would be one and in fact many decimal representations that are not printable by any program even theoretically sorry even theoretically it's not sorry say again even theoretically it's not possible to yeah even in theory yeah so so it tells you that even like if you want like to do a kind of Randomness you have you have a problem you cannot you cannot just completely randomly choose a a real number by a computer program can I come up with an example or is it just H this is theoretical but I thought you would like it let me give you a sketch of the the the the proof of counter theor um suppose by [Music] contradiction um that there exists a subjective map f from the natural numbers into the real numbers this means a that I can I can enumerate I mean f of f of n is some real number it has a decimal representation let's call it m xn dot X1 n X2 n sorry these two and and so on right now it means that I can put it in a table I put um f of one this is X1 dot X11 x 2 1 and x 31 and so on then I do I do the same for the second number F of 2 this is a X2 dot X2 sorry X1 2 X2 2 X3 2 and so on and generally I have in the n the N number I have xn dot xn One X N 2 x n 3 up to let's say x n n and it continues right so now I Define a new [Music] number by setting um Y is going to be some y y1 y 2 and and so on N point I have YN and why let's say Y is going to be [Music] X1 sorry X1 maybe we call it yeah let's [Music] say this for notations I guess it um well whatever uh we we can say that Y is going to be H X1 + 1 X1 + one H y1 is going to be um X1 so I have two basically two cases in one case if X12 is [Music] um smaller than N9 then I do a y1 is going to be X12 + one and if X12 is equal to 9 then I do then I Define y1 to be x 1 2 -1 and I continue in the same fashion I mean what I do is that this is called a diagonal argument I take the diagonal of the table and I modify I modify by plus or minus one each each element in the diagonal and by that I must have defined a new number because this number cannot have cannot be equal to F of one because its first it I mean its first element Y is different than the first element of of f of one it cannot be equal to F of two because the first digit I mean the the first digit after the the dot y1 is different than the first digit of of f of2 and so on so by this I defined a new a new real number that does not appear in this table so it mean and then I get a contradiction right it means this table is not does not cover the the enti entirety of the of the real numbers and that table can be mapped to the natural numbers out yeah table is the is is injection to the natural numbers because F of one is is this is this row F of two is is the other row and so on okay I'm sorry if this was too much but I thought it would Intrigue you a little bit because it says something something about programs H but it would not be ER I mean I would not rely on this this counter counterart in the the next lectures so you can uh you can read more details about it in the notes and I guess we are over time but H still is someone interested someone wants to ask a question all right then then uh see you next week thank you thanks thank you