PSE Lectures - Ep 1 - Introduction to the course and Naive Set Theory

Transcript

foreign is gonna give to us uh hopefully a really long and big uh uh series of lectures where we will try to cover all of the contents and related to Electric cryptography possible the idea is to start from the basics so Fields Rings groups this kind of stuff and hopefully at some point be able to arrive to the painting and understand as much as possible during the path so first of all thank you Madame for

doing all of that for us and sharing all of your knowledge the floor is yours so feel free to start okay so um I just posted a a link to my website um where you will always be able to find the notes relevant for the sessions um let me just introduce myself briefly and maybe I I would then like to hear a little bit about

every participant especially what is your mathematical background so originally from Israel but I I live in Berlin now I spend most of my life in in Academia most of my grown life in a in Academia doing mathematics in a field called the algebraic topology which is a kind of a mixture of a algebra in geometry and then a few years ago I left Academia to uh and transitioned to Tech

and now I I work for Aragon Association is a cryptography researcher yeah I guess we we can talk about me more if you want but how about you tell me a bit about yourself so we are 27 participants so maybe maybe it will take long to present yes I can try to give you an estimate of uh the general background of the audience uh there might be

exceptions of course but generally uh most of the participants are from PSE which basically means most of us are Engineers uh people that has probably degrees in things like computer science like electronic or electrical engineering uh background in Signal processing so background in maths yeah background in maths related to modular modular fields or modular mathematics and this kind of stuff of course but cryptographic wise things for example like the theory behind groups and Rings I don't I think we have a general grasp but I don't think the details are well

settled and from there on I think mostly everyone has interacted with uh elliptical cryptography in the sense of encryption signatures uh ellipticals multiplication algorithms this kind of stuff uh but on a label for which an engineer is necessary to implement Primitives or use The Primitives I would say so definitely the theory behind the scenes is what probably everyone is seeking uh and wanting to to get from from these lectures I don't know if that's yeah yeah it's good and let me start with an overview of what we

we're trying to do here I guess you can call it also motivation um so consider a a parabola in in the plane in in plane this has a shape let's say the the the most simple parabola is

intersecting the origin exactly here at the bottom and the equation of the parabola is a y equals x Square now we can say that that I get a polynomial in two variables that is for example y menus x square and the parabola p is the set of solutions to the polynomial

f x y that is to say a this is the set of all X comma y in the plane such that f of x y is equal to zero now this kind of a view is is an algebraic view um that is a many times you you know Parabola from analysis and in analysis we we have all sorts of a continuity arguments or even a smoothness arguments

but here we just do a a we just treat it as an algebraic object algebraic for now it means that it is constructed from a addition and multiplication possibly the vision and subtraction right um but but that's it um now this this kind of equation makes sense whenever you have addition and multiplication so for example this this makes sense over I will I will just you don't have

to know it now but there is a a a the collection of or what is called the prime field FPS which can be regarded as the collection of all numbers up to P minus 1 where you get a a addition modulo p and multiplication module p and here I mean that P is prime so as you can see in this kind of in

this kind of setting I can also ask I still have the polynomial what is the solution of f x y the solution set of f x y when I treated a um over the collection of a well collection of all a number zero up to P minus one with these operations uh and and this is this is roughly the idea behind a field in mathematics called algebraic geometry

that is we take a geometric object like the parabola a that can be expressed by algebraic means and then we study it over a different uh algebraic setups like a over FP but we keep remembering what the geometry that we have over the they're typically over the real numbers because it gives us intuition of what should be true an elliptic curve and say over r

um is an equation uh y square equals X cubed plus a x that's B where A and B for some real numbers and a we can of course a look at the the solution set of this polynomial let's say of

y squared minus X cubed minus a x minus B over the real numbers this is denoted as e over r now it turns out this a a if you you can look it in the web that if you if you draw the solution set you get something like this fish it could be a fish with the here

it could be a fish with the another another ellipse here but let's let's keep the simple one and what is happening here this is e r or simply e and I I can what I can do I can take if two points p and Q I can wait maybe this would be better

okay so I can take two points p and Q connect them with a line this line L needs to intersect the the curve in a third point this the reason for this is that we haven't a a polynomial of degree three so typically a polynomial of degree three will intersect a line with the three points so I draw the line I intersect the point and now look at this equation this is symmetric along the x-axis because we

have y square equals something so this means I can reflect along the x-axis and get a another point and I Define this other point R to be p plus Q so what I did here is defining a binary operation called Plus I Define the binary operation from the set of all points to the set of all points

um it turns out that by you can prove it by or it follows from a a simple theorems in Greek geometry that this operation is a is associative this is associative that is to say if I do and then plus a well R is taken let's say a k then this is the same the as P plus a Q Plus k

um I also have a have an inverse that is if I take a a point a r for example here here is R minus r is going to be just the the reflection along the x axis of r and zero point uh I have a problem but I can I can add in fact uh a pointed Infinity let's draw it here um so that for example if I take if I take the point here

then um I can look well if I want to to do the addition of the point in this uh origin added to itself then I need to draw a line between these two points this line is is simply tangent to the a to the curve and so it means it does not intersect the the the curve in another point but if I imagine that I have a point at Infinity then I could say that it would intersect a intersect the pointed Infinity

exactly once so this means that if I take the origin here let's call it k then k plus k is going to be the neutral element o and this is all to say that the set of all solutions to this uh a cubic equation is a is an abedin group now what what did I use in order to uh well I didn't prove but in order to

sketch the proof the set of all solutions is in a billion Group Well I basically um only used lines I used a lines and if you wish tangent line uh is something that is defined with uh well yeah I guess basically it's only lines and the equation of a line I mean if you have two points in the if um X1 y1 X2 Y2

are two two points in in the plane in R2 then the equation of a line is I hope I'm not making a mistake it should be something like y minus y1 and I have Y2 minus y1 uh x 2 minus X1 and then here it should be x minus X1 so you see the equation of a line again it you can regard it as the set of

all solutions to this polynomial if you I mean pass one expression to the other side it's going to be zero so it can be regarded as a set of of solutions to a a polynomial of degree one this this these guys are simply constant and the constants here can be computed in any place that has a addition and subtraction and also division by a non-zero element um and this kind of algebraic structure is called the field and again

this makes sense over any feed EEG what we call the prime field FP so now I can a a look at the set of solutions of the equation of e over the prime field FP I will have a natural um a natural binary operation

this plus from e FB sorry so I will have a natural operation from efp times efe for the line you write the equation of the line and then you you look for a third solution

that is the intersection well I mean a solution that is common to the equation of the line and to the equation of the elliptic curve this again you can do in any field then you you do a reflection this is basically a a taking the negative of the um of the y coordinate again you can do it in any field and you get a point and it turns out that this again it is a structure of an abelian group uh so this is the kind of object we we

would like to uh we would like to study of course um if you think of it not every algebra geometric object like the the parabola for example will have this this kind of a strange structure that is a in a billion group operation on the on the set of solutions but elliptic curves are special enough to admit that this additional structure and this is a very helpful in cryptography basically even without pairings the uh the advantage of an elliptic curve a

group is that a a it is hard for an attacker to do a Brute Force attack because adding a adding points on the elliptic curve is an expensive operation so you can it's expensive but not too much expensive so you you could encrypt if you do not too many um elliptic curve operations but if you do a Brute Force attack it becomes unfeasible and as far as as I know by by relying on what danbone said a the tendency even in just a

public key exchange algorithms on the web is to to pass to elliptic curve groups and then the uh the additional the additional uh gain that we we have with elliptic curves uh is what is called the pairing so special Maps I don't want to get into the details so

I will write something that is not precise just imagine that you do you you get a map from all the points on the elliptic curve times itself two and you could extract let's say a group G1 and here a group GT all of the same Prime order

such that this map satisfies a I will just write the equation um you probably know it but you don't have to understand the details um the the the main property of this uh this say special special Maps is that for any A and B you get a that if you apply the the special structure on a g to the A and G to the B you get a a this map e applied on G

with itself to the power of a b and this a a this structure does not exist generally on on a billion groups or it's at least typically it would not exist but on elliptic curve you you get it for free this kind of property allows you to actually build cryptographic protocols that did not exist before and the main example is the so-called BLS signature so so that's that's roughly where we are

heading but it is a long journey especially because of the approach we take so uh if you look at the notes uh you you can see that the title says Elementary regrowth account so what do I mean by that I guess the the literature in in elliptic curves cryptography can be the roughly divided into uh two types one is a the standard cryptographic or cryptography books

what these do according to what I saw is they they give an elementary account but it is not rigorous in that they use they they really start from for example from this kind of structure the the so-called pairing as a black box a a black box that has a certain property and if you take it as a black box and you take a few a few other thing things as a black box then you can indeed a a be convinced that the protocols work

uh the other Edge is a what you find in pure mathematics in pure mathematics the standard is to be completely rigorous that is to prove everything you you claim but elliptic curves are typically taught in in a master level in pure mathematics and therefore the account the textbook you find in in pure math on elliptic curves are not Elementary that is they rely on a quite a lot of stuff from Bachelor studies so in a way there is a hole in the

literature what if somebody new comes in and they want to be convinced to know all the proofs but on the other hand they they cannot afford doing a bachelor in mathematics and then and then uh proceed so um the the aim of these notes is to feel what I I think is the bit of a whole in the literature to give both Elementary but rigorous account uh any questions remarks uh suggestions I might just mention something the only

thing in the literature I think that although doesn't go maybe as in depth or at the level that we would need as Engineers is maybe the notes from Alfred menethius from the University of Waterloo he has two books uh one analytical cryptography and the other one in like The Primitives for crypto so this is the only useful thing I found so far aside from the lectures that you will do which is what I'm like really excited about uh yeah it could be I mean I I don't know the literature that well um but but I did look around and it it

was hard so even even things in a cryptography like cryptography textbooks that have more details um typically they don't prove everything uh they they prove you know they they they do like uh they they they have like a cherry picking of propositions in theorems they prove these and they rely on stuff that uh you ought to to know from uh like previous knowledge so the AIM here is to prove almost everything so something like 80 90 of

the the materials but this takes time the the advantage is that you you really understand what makes the the thing tick this is a the reason mathematicians insist on a studying a subject with a with complete proofs and and of course it also then helps you to it should help you to to tweak a some constructions whenever you need it okay so this is a a this is the overview but we're going to start from the very

basic and the very basic is a sets so the slogan here is that you can think of a sets as the machine code of of mathematics that is from a a completely formal point of view you can construct all the mathematics from uh from sets so this is similar to to like assembly or or something like that in in encoding basically I said

is a collection of elements as such that for every object X in the in in some kind of in the full Universe of object

um we can say either X belongs to s and then we write like this X Epsilon s or X does not belong to S and then we write X naughtiness now we typically denote a a set with curly brackets

you can say s is equal to the set one two three but in our syntax a set you I mean when you describe the elements of the set you remove repetitions so in fact I could write as this this set is going to be equal also to 1 comma one comma two comma three um now you can Define you can define a set with basically a a two ways one is

to describe all the all the elements in the sets in the Set uh separated by a comma or you can describe a rule that gives you a all the elements in the set you can do s is equal to the set of all X's such that X is a number is a is an integer and X is greater or equal to 1.

okay and of course instead of writing the prescribed rule if a a the rule is kind of obvious from a first few examples then you can write s is equal to a one two three and so on and now uh famous sets one is the natural numbers so this is

the set one two three and so on and not including zero then I have the integers which is a um zero one two but also minus 1 times 2 a the rational numbers this is the set of all questions A over B such that A and B are integers and B is not equal to zero

and then I have the set of real numbers I don't Define it for now you can say it's the set of all decimal decimal representations but geometrically you have this this picture of the the line of numbers and you you have the complex numbers so the complex numbers are the the numbers of the form a plus b i are in the line of numbers and I is a is an external object object that is a a

when we Define the arithmetic of of the complex numbers we we say that I Square is equal to -1 okay so what can you do what kind of a a things you can do with sets well we need to have an anchor so we Define the empty set I guess in logic syntax you can say the empty set is the set of all X's such

that X is not is not equal to X and we get that um well of course two sets we say that two sets A and B are are satisfying this relation of of containment if for any X or for any A and A a is an element in b and just a warning

typically when people encounter this uh set theory syntax they make a confusion between contain and belong so contain is it means that just as I wrote with all the elements in a are in B and belong is is a relation between an element and a set but of course a set can be comprised of elements which are in turn a set for example you can take

the set whose unique element is the empty set using this I can actually construct the natural numbers assets and sets so I Define zero to be the empty set one is going to be

containing the empty set as an element and two as the set containing the empty set as an element and the set containing the empty set and so on so you see that the two is in fact I did I didn't Define it but what is what is called the Union the union of two sets using this you can you can simply say

that n is the union of all numbers that are that have have been defined before okay so so you see we can we can view the the natural numbers it says and then we have a typical operations and operations on sets so of course we have the Union

which means all the X's such that X is in a or X is in b we have the intersection so all the X's such that X is in a and X is in b and we have the complement or the the set difference a minus B which is all the X's such that X belongs to a X does not belong to B

but of course we don't have to uh to do these operations only on two sets we can do so if I is any set is a set of you can think of it as a set of indices and and suppose for every I we are given a set a i then you can form the the union of all

the AI I belongs to I this is simply defined as all the X's such that for every I x i x belongs or sorry there exists I such that X belongs to AI and similarly you can do the intersection so intersection of a i i in I instead of all X's such that

for every I X belongs to AI and now again if I want to I want to stay in this formal formal level and I want to talk about ordered pairs I mean ordered pairs definitely is something we we need to use in in our development um so you can say you can say the following a given

A and B the ordered pair let's call it for now OAB is simply the set containing I mean the set containing a a set with a alone is as an element and the set a b so this is It's a set of two elements and so given given two objects

A and B you get an ordered pair and and this means if you you check you can check OAB is equal to O A Prime B Prime for any a quadruplet of objects a b a prime B Prime the OAB is equal to O Prime the o a prime B Prime if and only if a is equal to a prime and B is equal to B Prime

let me give you maybe part of the proof of course if um OAB o a prime B prime it means that we have an equality of sets with one element a and the second element the set a comma B needs to be equal to the set a prime okay

this element belongs to a to OAB this this really means of course so either so basically this this means that which which is of course tells you that a is equal to a prime and a so this is just a just a sketch it follows that a b is going to be equal

to B Prime now that we have this ordered pair of course we we will denote a notation the ordered pair a b is simply denoted as a comma B and this is an object this is a set you see this definition is simply a definition of set and it is a set that has the property uh that is marked in red here

so this is really the property that we want from an ordered pair it means that it's it's a kind of construction that takes into account the order of the the elements and once we have this notion of ordered pair I can Define the so-called Cartesian product the Cartesian product um offsets

is simply the set of all ordered pairs a comma B such that a is in a and B is in b uh any questions so far ah yeah I have a question sorry so we need to raise a hand add and see how just yeah I also I actually also don't don't know but just speak up whenever uh

whenever you have a question later so am I understanding correctly you are trying to lay the groundwork and basically give the proofs of how sets work and it's kind of the groundwork the groundwork for understanding EC math later on is that correct uh yeah it's going to be the groundwork to understand almost everything we do easy is I mean is really down the road we will need to cover a a group Theory then we need to cover a finite field

Theory and only then we some Elementary number Theory and only then we can even Define a well I mean Define and study basic properties of addicted curves as I tried to say in the in the beginning of this uh uh part all modern mathematics can be built on sets or in fact B is built on sets so if you if you understand this I mean the this kind of ground uh knowledge will help you to to understand every type of mathematics so you don't need to

think about a a direct connection to elliptic curves or you you will see that basically every mathematical object is defined in term of this set theory syntax okay thank you but is this connection something that you have discovered recently that you can abstract everything and explain in terms of SAS or is that like no no this was a this was basically the the Holy Grail of logic in the the early 20th century that is mathematicians started to encounter a paradoxes

and they were really afraid that the whole Theory May collapse because you find paradoxical things so they said okay we need to have solid foundations a for the entire Theory and they looked for different things and eventually a a they they converged on this uh what is called the set theory axioms I'm not giving you here the axioms but I'm giving you something similar similar flavor that tells you how you can at least intuitively construct all mathematics from this uh set theory stuff and in the early 20th

century logicians really did the the full formal work of this this is the axioms are called ET ceremello Frankel and choice basically thank you uh one question closer to the topic you said you can use sets to Define any number and you showed zero one and two could you please also show three and four because it's not clear how you would create three or four with that yeah sure I mean basically three for example is

it's the one zero Union One Union two which is the set uh yeah I guess yeah so so this is the the empty set Union the set with the empty set Union the set with the empty set and

okay so what what we have here here we have no elements so I get a yeah so what you get is basically the empty set yes thank you they're expensive so now of course nobody talks in this way no I mean we say we we say three and it is understood that we can we can say three and everybody understand but if you really want to construct it

axiomatically you you you can use the empty set is kind of an encore and basically spawn everything everything else sorry Martin can you yeah I can you just give an intuition why the end so a set containing an empty set is equal to one at the moment this is a definition but why would you so if you would want to define the number one is as a set then you would look for a set with one

element and and since you actually from the axiomatic point of view the only thing the only set that you know really exists is the empty set so it is natural to Define one as the set containing a unique element and this unique element is the only thing you know in this word is that the this makes sense this makes a lot of sense thank you okay and then and then two should be a set with two elements but what do I know in this word well I

know that there is an empty set and I also know because I I defined one I know that there is a set containing uh containing the empty set so this would be my choice it's kind of a canonical in construction and okay so so we have this Cartesian product the Cartesian product is the set of all ordered pairs um you are probably familiar with this um but once we we defined ordered pair as a set uh then this is again a construction that can be done from completely completely uh the act the basic naive

axioms of sets and um now if we have a for example a to be the interval a one two the interval a 2 3 then you can draw say this is one two so this is a and this is a two three this is B and the Cartesian product is going to be this

and this Square but of course you don't have to uh you don't have to do it on a sets with a geometric meaning I mean you can you can do for example take a to be equal one and B to be equal to a let's say a 3 4 then you get all all the ordered pairs so a times B is a one three

am one four two three and two four so in particular the number of elements so if are finite the number of elements in a times B is the number of elements in a times the number of elements in b what I typically do in the the other

seminars I run is after about an hour we take a few minutes break do you want to do it I think it is helpful to just clear your head a bit maybe come up with questions on on the things we talked about and then we come back make sense how how much time do you think will be appropriate um let's do let's do 10 minutes okay okay and we can then we can then stretch the the session a little bit after 12 if you want

but I think it it's good to uh even if we didn't do much just to kind of contemplate on on what we we talked about and also take a break and uh um so so let's meet here in uh in 10 minutes okay feel free to speak up again once the minutes pass and I will pause the recording on the meantime here okay yep okay so I uh I apologize I I uh I didn't look at the chat uh so far and I

realized the the link was the link to the notes was broken so I attached the the notes as a PDF here basically we are we are covering the I think it's the first uh the first chapter any questions on what we did so far I I do have one um yeah so maybe the naming is a misconception that I have from like programming but for me sets are basically a group of organs like a space

where we have elements and those elements can be repeated but on the definition that you gave for expressing uh for example two or three would this be a multi said because we have the the empty set repeat it a lot of times so yeah but it is repeated in uh in a different way right like this I mean the empty set is not equal to the set okay so the structure is different although at the end the internal contents are kind of the same or built at least from the same thing yeah it

looks tautological but it's or or if you want it looks a kind of circular but it's not circular because because we add this uh brackets every time okay fair enough in fact from the axiomatic point of view of set theory the only objects in the world that you you can talk about are sets so everything else needs to be defined via sets and the only set we we know that exist in to begin with is the empty set so we we use the syntax of this curly brackets and commas and empty set to

construct everything else something that also has like a meaning by itself in in inside Theory no okay no no no no okay it's just a a set is a is a collection of elements uh you remove repetitions and a a a set can can be since a set is a legitimate object in the universe it can be an element in another set so and and again from the axiomatic point of view all the elements of a set if you define

them previously they need to be sets as well so so basically it's like sets which are sets of sets okay that makes sense thank you okay but um the the point of this this uh this this issue is not to give you a full account of the axiomatic uh framework just to give you a a feeling that really everything can be a can be constructed from this kind of assembly code a a and this this would mean and this is what the the the the the

mathematical logicians do it means that you can phrase all mathematics essentially all the Corpus we know of mathematics in in terms of sets like this and a basic uh deduction rule meaning that if if you have a proposition a a p and you have a proposition uh that P implies q and you know that P is true and also that P implies Q is true then you you can deduce that Q is true and from this a deduction we will call the modus ponens and the the axioms of

set theory you can approve rigorously all a mathematical propositions that is you you you can construct a finite sequence of deductions from the axioms that start I mean start from some of the axioms and and result in your proposition so essentially what this means is that at least theoretically you can put all the Corpus of mathematics in a computer program that validates the the proofs of every proposition

so this is this is complete a complete accuracy okay the next thing again in our really a a foundational discussion is the notion of a function so let me put quotes here on the definition so let's let a and b B said a function

from A to B is a rule that assigns for each element low lower case a in a an element which is denoted as F of a and this must must belong to B uh now the notation for a function

this a a colon a arrow B and uh for the the specific a assignment of element we do a kind of a maps to a notation so this a goes to F of a I should have said it assigns to every element A and A are unique f a f a in B so now you can think of it

as a a a is like the input the input set and B is the output set and a the function f is like uh is like a machine code or whatever f is a is a machine um that assigns to every to every input object in the input set an output object in the output set but of course a a

what is given here is only if you look from the axiomatic point of view I have a problem in this definition okay can somebody tell me what is the the problem in this definition what is not really defined in this definition no idea I mean a what about this could you give us give us a few more seconds

yeah sure what is not really axiomatically defined in this definition so why is this definition just in quotes okay so let me let me tell you the issue here is the word rule

we haven't defined what is a rule so of course intuitively and we will eventually not eventually soon enough we will leave the axiomatic uh space and we will be able to say something like Rule and everybody knows what it means but if you really insist on a a a rigorous axiomatic formal treatment you need to Define what is the rule so alternatively a what I can say formal um a function

if from A to B is a subset you can call it the graph of f if you wish or simply f it's a subset of the Cartesian product a times B two conditions need to be met so this I remind you this this Cartesian product is this collection of all ordered pairs and I claim that a function is a a sub

collection so it's it's some partial collection of ordered pairs a comma B that need to satisfy two conditions one for every a in a there exists B in b belongs to let me call it let me call it f for now because we do the formal definition so this belongs to f there exist

a B and B Prime well A and A B and B Prime in b belongs to f a comma B Prime belongs to f B is equal to B Prime and we denote so if a comma B belongs to f

with the note B to be or F of a to be equal to B okay so this this is really a a the formal definition of a function it's really a collection you can you can identify it like at least intuitively with what what we call the graph of f the graph of f is is is the the set of all pairs a comma F of a

um but axiomatically we simply say a this is a a collection of pairs such that for every element in the input set there is an element in the output such that a a the pair belongs to to f um if I have a two pairs a comma b and a comma B Prime this really means intuitively that that or informally is that a b is the output of a but also B Prime is the output of a so it it must be that b Prime is equal to

to B so for any unique input I have a unique output as the subset of the Cartesian product between the sets A and B why as the subset like can can it not be like the entire Set uh of like the entire countryction product well then it would not satisfy Axiom 2.

at least if B has a has at least two because so if example if the number of elements in B is bigger or equal to two n times B is never a function because what you will get take take two elements be not equal to B Prime in b then a or you should also say if a is

not empty it is not empty um then belongs to a times B but also a comma B Prime it must belong to a times B so Axiom 2 so 2 is not satisfied yeah no but but of course intuitively

why it shouldn't it should not be a function because you are giving me for one input a you're giving me two different outputs B and B Prime and this this is not what we want we want uh this it's the same idea of like a computer program for every for every input there is a unique output and for every element in the declared set of inputs you you can actually activate the the function or the machine on this input so uh yeah and and notice let's make a few examples you take a

I want to define a function from the real numbers to the real numbers and I tell you what is the rule I tell you this function it takes X into x square okay so if you want an equation it's like f of x is equal to x squared alternatively I could take this function it will take this formula and say that this function goes to the non-negative real numbers

still X goes to x squared because x square is always non-negative let's call it f Prime f is not the same as F Prime because this is this you can you can think of it like uh like a uh a function in a in a typed in a typed programming language that is you declare the the set of input the type of input and you declare the type of output

and if you declare the type of for example of output to be different than I mean in two cases then you formally speaking you define a different routine so these two these two functions formally speaking are not equal of course eventually we will uh we will what is called abuse abuse notation and so on and identify such functions in I mean for convenience note

two functions F from A to B a g from C to D are equal if well first the domain this is called the domain and this is called the range it must be that the domain is the same

and the range is the same a a a in a F of a is equal to go a okay alternatively f is equal to G as sets as sets in a times B this is as sets

there is this notion of composition f is from A to B and G is from B to C functions then a we Define we set what is called G composed f see the the order is a is interchanging this is a function from a to c and it is defined well I need to tell

you what to do on an input and so on an input a i define you do F of a this you know how to do and then F of a is an element in b so I do G of f of a this is the reason for the the notation G composed F instead of f compose G so this is again in terms of computer programs is just concatenating I mean you you put the the output of the you put the output of f as the input of of G and of course

if I have a third function and let's say age from C to D a well now I can do let's draw it in a diagram I am given f g and H but in fact if I am given f and g I am given two functions f and g I can cook up a third function which we just called G composed f and since I also get G and H I can cook

up another function called H compose G and then I can either compose the red arrow with the blue arrow or I can compose the red arrow with a with the pink

sorry I can compose the pink arrow with the second red arrow so in other words I can do and all that composed f and I can also do age composed G composed f and I claim that I have an equality of functions here this is called associativity this this thing is composition

and just to give you a few examples well maybe one example I I think you know you know it basically intuitively but I just wanted to make it uh to make it precise but of course you can take a function from r r a let's say it does it takes X to x square and then you can construct another function G from R to let's say a r again it takes a y and puts it into a y

Cube and then G composed with f of x is by definition a y sorry I do x square and then I raise it to the power of 3 so this is X to the sixth and then a a for any set a the identity

function f this is denoted typically as a ID sometimes we put an a just to remind uh where is the the identity taking place um this this is of course defined as a maps to a if you want exercise for any functions I can do two things

I can do with I have a and b here I have the identity of a so I can do composed with the identity but I can also compose F from the other side with the identity of B and this gives me identity be composed if and you can show I mean this is this is

very easy just an exercise in the that identity B composed if is equal to F which is also equal to f composed with identity a okay so you can intuitively you can think of of the identity function as kind of the neutral element with respect to the the binary operation of composition any questions okay so the next uh the next thing I

want to talk about is what is called a so let me just make a definition injective if for any a in sorry for any pair of elements and a prime in a is different than F of a prime that is intuitively

F the routine F does not repeat outputs on the on different it I mean on different inputs it is rejective for any output or for any element in the output set there actually exist an element in the input set such that is equal to B so every possible element in the output set is actually obtained as an output um by by some element in the input set

and bijective it is injective and subjective so the picture just to give you a a simple illustration is is with the finite sets if I have a a and b pictured like this then you can picture f as is a bunch of arrows but the bunch of arrows they need to give an error for every element in

so this thing is is this function f is not injective this this function f is actually subjective and not right it is it is subjective because every every element in the output set B is obtained but there is repetition these two these two input elements uh sorry not these two these these two the the pink the two pink elements are

mapped into the the same element so this is not injective and and from this from this example you can you can pretty much guess what is going on a for for finite sets and that is to say for finite sets the number of elements in a

is smaller equal to the number of elements in b if and only if there exists injective function if from A to B the number of elements in a is bigger equal to the number of elements in b there exists a subjective map and a third the number of elements

in a is equal to that of B there exists a bijective a function f from A to B okay so a I'm not sure it makes sense to to to give a complete proof but a let me let me do a sketch you can find the full proof in the notes

but it it will also be a good exercise if you don't look at the proof and you try to prove it um let's do for example one a a if the number of elements in a is smaller equal to the number of elements in b enumerate a a and b is for example a is equal to A1 up to a n

and a a b is equal to B1 up to a b k where we assume that K is bigger equal than n and then Define F of a i equals bi I between 1 and 1 and n um this function is clearly injective a

I is different than J then or if a i is different than AJ then clearly clearly F of a i is different than F of h a okay and so it's so f is injective and conversely conversely

a there exists an injective function we enumerate a so a is is A1 up to and a a and then it follows that b B contains

F of A1 up to F of a n which is a set this is a a of size exactly n the number of elements in this set are is exactly n because f is injective and so it follows that the number of elements in B is bigger equal to a to n which is the number of elements in

uh so this is a this is a a good thing to remember that a injective surjective and bijective in terms of finite sets they really mean they're really equivalent to to Simply measuring uh which set is bigger but of course notice that even if the number of elements in a is smaller equal it could be that there is a function from A to B that is not injective right for example I mean here is a here's B

a has two elements which is strictly a less than the number of elements in B but they give you a function that Maps the two elements to the same element so this is not injective function and the statement is that there exists an injective function all right so the next proposition which I think will be basically the end of the of the session any sets

not necessarily finite is bijective there then there exists exist a function which I I will denote is f minus one from B to a F composed with f minus 1

is equal to the identity of B and F minus 1 composed f is equal to the identity a can can we also assume that the identity of B and the identity of a are the same so are also equal simply since the application is adjective uh we do we do not assume that A and B the assets they could be different sets but of course they uh if they are finite they need to have the same number of elements but here we don't even assume that they are finite

okay so what you just said does not imply that the identities of both sets are equal they can be different still this holds yeah I mean look two functions are equal if and only if their input set and output sets are equal so identity a is going to be equal to Identity b as a function in our setup if and only if a is really equal to B think of it is like a computer program that this is a computer program identity a it gets an input a and an output a a

could be like int right for example it gets an integer and it it spits out an integer and if you just Define the same program as a it gets a real number and it outputs a real number or let's say float this is formally speaking it's a different it's a different function even if they do the same thing they do you take X and you do X plus one it's a it's this it's hearing the identity of course doesn't do anything but generally speaking two functions are equal if and only if their input and

output sets are the same and if they operate the same on elements is this is this clear yeah yeah that makes complex sense thank you very much Okay so but what what is happening here is a a this proposition tells you intuitively is that you you take the the set a you get a function which you start with the function which is a biject then it means that you could Define another function which we we simply

formally call F minus one soon I will justify this notation and this F minus 1 is is kind of an inverse in the sense that if you you start with an element a you map it by F you map it to F of a and then since F of a is an element in B I can map it back by F minus 1. I can map it by F minus 1 to a well formally it is f minus 1 of f of a but we say that F minus 1 of f of a is the identity of a so this means that I

get back to a this is equal to a and but I could also do the other side I could start with an element B map it I I ran out of space but I can map it into a into sorry F minus 1 of B then F minus 1 of B is an element of a so I can apply f I can apply F I get F of f minus 1 of B and since you see F of f minus 1 is the identity

of B it means that if I started with an element lowercase b i I have to end up in the same in the same place I started okay so this this is why we say that by objective maps are invertible and the proof is actually very easy let P be an element in the the set B set capital B now I need to tell you what is a a f minus 1 of B but first since

f is subjective if there exists a Aron a such that F of a is equal to B moreover since f is injective a this a is unique that is you cannot have a prime different than a that is is mapped by F

into B Because by definition in an injective map if you give it two different inputs it it gives you two different outputs so Define F minus one of B is equal to n this is well defined this is a function this defines a function right what do I need to to verify I need

to say okay well a function it needs to be defined on every element in the the input set but now the input set of f minus 1 is B but here I could have said for everybody because what I did was completely General so in fact this function is defined for every input element in b and I need to verify that for every it gives a unique output but this a we thought we said that a is unique

so I have a well-defined function I need to prove two things so I need to show that if composed or let's say F minus one composed f is the identity of let a be in a then by definition I take F minus 1 of f of a look at what we did here I mean f minus 1 of some element this is B

I look for The Unique element a that satisfy F of a equals B and then F minus 1 of this B is by definition a and similarly you can do this is this left is an exercise this is basically the proof all right this is a good place to stop the the session but of course questions and remarks are always welcome feel free

no question so far it's time to speak is okay I guess we will assume everything is clear yeah so let me just just end up with a a few remarks a kind of a meta remark meta remarks a one is that I like that people ask many questions I I think this is the the best the best way to learn uh in general in mathematics to even allow yourself to ask silly questions so don't don't be afraid of a a looking silly in

front of your uh whatever in front of the other participants the quickest way to learn if you don't understand something you you ask so uh and and in fact really you can see that a people who people who really understand well they have a well-formulated questions uh and and so this is this is really a a a huge a huge component in the learning and second uh this session of course was a very slow uh but I I plan to accelerate

of course you should tell me if something is too slow or too fast and so I would be happy to hear your feedback also after the session we have a Discord Channel uh sorry I have an answer question of sorts so uh is there in all of this is there is it like firmly based on proven blocks or is there some conjecture like in your in your opinion or some the proof of which is still in question no no everything everything is uh everything is proven from the axioms

from what is called a a zfc it can be proven of course zfc as you saw we Define the natural numbers uh this was already quite cumbersome if you really want to prove things in the zfc form uh it would take you much longer because you need to deal with the formalities and the delicate syntax and so on but it can be done everything in the everything that we will get to elliptic curves pairings over finite field it can be proven from the the standard axioms

of mathematics the so-called the terramelofranco and and the Axiom of choice so no conjecture so in principle you could really check all of the all of the theory that we talk about you could run a computer program that checks the validity of the proofs and so on other questions okay uh yeah I have a small question yes yes yes oh it's just when we've seen the the

statements about the cardinality of set say B in regards to the function that may exist between them uh I think we've said that if yeah if a and b are finite but uh yeah for finances so can we extend this to infinite sets and if not what are the restrictions okay that's that's a very good question but of course to make it to make it meaningful you we need to Define what is the number of elements of a when a is not finite so and it turns out that there is an extension

of a a the natural numbers that goes beyond a Beyond them and and allows you to do arithmetic of infinities and in this arithmetic of infinities you could have so for any any infinite set you will have some kind of object called the cardinal cardinality and you will have a certain type of calculus Theory between cardinalities and the calculus Theory will be such that the cardinality of a is smaller equal to the cardinality of B if and only if

there is an injective function so you could actually extend this proposition to infinite sets but then you need to make sense of what is cardinality and this this is a whole a whole course in in in mathematics so we will not cover oh great okay thanks but yeah for for recreation recreationally participants you can look for a the Contour for example Contour diagonal

argument this this tells you that the cardinality of the natural numbers is is strictly smaller strictly smaller than the cardinality of the real numbers okay so let's say but you need to Define cardinality in a precise way yes a other questions uh yes one question so it's something I I cannot remember so for instance like the function of uh like a turing machine if it stops or not so this is from like a program to a Boolean

so that is a function that is not computable so it's also a function even if is not computable yes definitely in our in our treatment a function is just a subset of the okay right of course eventually in this this uh this will definitely be the case for the the elliptic curve stuff that we do eventually we most of the functions we actually work with need to be efficiently computable even not just just generally computable many times

we will simply use the existence of a function even though it it is uh not in any in any visible way computable uh so there is kind of uh a use of of a this kind of of a a notion of a function without relating to computability because it it tells you something about existence of a certain certain structures okay thanks um let's finish here I hope it was not

too slow and but again feel free to uh tell me your opinion on the Discord Channel and I hope to see you next week thank you very much for everything Madan see you next week