Godel Incompleteness Theorem Explained: Proof and Consequences

[00:00:00]okay so we can start so we were talking about together the incompleteness theorem and so let me restate what we want to show so Gathers incompleteness theorem and the the kind of to be in the right mindset we're trying to find a set of axioms that will describe what's correct and what's not correct for the natural numbers we know already that we cannot define the structure of natural numbers why can't we define the structure of how do you know that we cannot have a first order set of formulas that defines the structure of natural numbers yes right because of the non-standard models but note that so non-standard models show us that we cannot find so we want to define the model of natural numbers 0 1 2 and we write some formula set of formulas Sigma's and we took Sigma to be the set of all possible formulas that hold in the natural numbers and we ask does it define the structure and it turns out that we also have non-standard structures that also satisfy C but the faculties satisfy this Sigma means that there is no formula that holds here and doesn't hold here that's the whole point the whole point that they satisfy exactly the same formulas but what we are after is a way to find out which formulas are satisfied by the natural numbers these are the questions mathematicians ask what are the statements that are true about the natural numbers so we actually are trying to figure out this not trying to define it uniquely but trying to figure out what are the formulas here now the problem is writing it like this this is the set of all formulas at all in natural numbers is that we don't have any way of check given a formula if it belongs to you or not so this is where the Gators theorem comes into play and it says there is no proof system that satisfies the following three requirement so soundness for the natural numbers which means if I prove something units true in the natural numbers and secondly completeness for the natural numbers means every statement that's true well the rational numbers is provable in my system and the third one is checkable which means there is an algorithm or procedure that on every input string a find out if it is a legal proof or not and the check ability is what's missing from the attempt to say let's take all the formulas that hold in the natural numbers okay so there's the guidance theorem what I want to do is to prove it and then discuss some of its consequences because it is this really is a revolutionary theorem in mathematics it's changed as I said last time it changed the way we're thinking about mathematics because it tells us that if we take any notion of what is provable what is a valid proof in mathematics any notion that we have mathematical proof is any mathematician understands it so probably it satisfies soundness we believe that everything we prove in mathematics is correct it definitely checkable I mean we believe that if someone comes out and say I prove this conjecture here is my proof it may take us a couple of years to check it but we can check it it's well defined whether it's a proof or not therefore any proof system that we usually use for mathematics is not complete and may not complete means there are true statements that cannot be proven which is a revolution in the sense that the intuition about mathematics is that if something is true then we will eventually find the proof to it yes yeah I mean so the point is that gather just show that such things must exist because no system satisfies these three properties thirty years later there was another great mathematician which is Paul Cohen in the early 1960s and he was the first one to be able to show that for specific questions that people asked about mathematics we cannot show whether they are correct whether they're true or not so he showed it for things like hey so he I mean I I will have to explain a little bit what it mean so the Continuum Hypothesis is neither provable now refutable so what is the continuum polities if you know I mean those of you that were in this special lecture they know that if we look at sizes of infinity we know that the minimum size of infinity is the infinity of the natural numbers and then there is the infinity of the real numbers and cannot moved at the beginning of the 20th century that there is a strict separation here this is strictly bigger than this the real numbers are strictly bigger than the natural numbers is infinity but then a natural question arises is is there anything in between so we can ask is there is some kind of size a subset of the real numbers that is strictly bigger than the natural numbers but is strictly smaller than the full real numbers that's a very natural question to ask once you see cantos theorem Cantor's theorem tells us these the infinity is bigger than this infinity so you ask okay is it the next one and poor coin proved in 1960 that we cannot neither prove it no disprove it now you can say this is not a statement about natural numbers he came up with a technique the technique called the forcing technique and it's basically the only technique that we have so far for showing the things are independent you call it independent of the proof system and we can show by now we can show many many many properties many statements many mathematical statements we can show that they are independent so modern mathematicians that are aware of Gators theorem when they face an open problem they know that there are three options the answer will be yes the answer will be no the answer will be there is no answer and anyway so these are the consequences of of gathers the element let's show the proof the proof is surprisingly easy so yes I will talk about this maybe later I mean you do dragging me but get it already thought about it so so let's see this I mean so so and here you see what we're going to do is we started by showing that a we had a few theorems last time so we had at erm one and it says that no algorithm can decide for every binary string X and number okay if the Conoco of complexity of X equals K that was the first theorem we showed and it was kind of by using this trick of the berry paradox if I could decide it then I couldn't write a program that finds the first number the first string was gonna go of complexity is bigger than K but the program itself will show that it's gonna go of complexity as lesson K okay so that was very simple and from that we use that to reduce theorem two that says no algorithm can decide the halting problem so here we are given a program and an input and we ask will the program hold on this input so now we want to show we can reduce from any of these from this one from this one we want to show get your steering so I can I can it doesn't matter which one let's let's do it from Kolmogorov complexity to Dougal to so what we will use the same kind of argument we assume by way of contradiction then there is such a proof system and then if the such a proof system we will get a contradiction to theorem 1 so assume by way of contradiction that such a proof system exists so we have a so now I will show you how to use this proof system to serve the Kolmogorov complexity problem that we know we cannot solve right so now let us use it to solve the Kolmogorov complexity problem so what are we going to do so you're given I want to show you an algorithm that for every X and every K holds and tell you whether the Kolmogorov complexity of X is K or not right so the only point to note here is here is they are here is my algorithm so on input X and K X is a binary string now the only okay let me write it and then I'll explain the only input exit K what we're going to do is we are going to here I I described to how the algorithm is going to work right so go over all a strings of characters or finite strings of characters in the language of our proof system in lexicographic order with avocado I mean we start by all strings of length 1 then all strings of length 2 so of on increasing length okay so now I'm going over all strings of a characters of my proof system and what do I do when I get some string on string s check if it is a valid proof of K of X equals K o of K of X is not equal K now note that this program first of all - if I take a string and I have a statement why how do I know that I can check if this string is the proof of the statement or not yes because the proof system is checkable right so I have a subroutine the check if it's a proof of the statement or not right now why will it hold why will I get either get to a string that proves that K of X equals okay okay or I'll get to a straight proof of this because of completeness one of those two statements is correct either the complexity of X is K or the complexity of X is not K one of them is correct but my proof system can prove anything that is correct so eventually I'll get to a proof of one of those I go over all every proof is finite so I go onyx on order of the just all sequences in decreasing order of the sequences and in every order lexicographic over the sequences of this length right and then you know that since we have completeness my system does prove this or does prove this I'm going one by one over the proofs eventually I'll get to the proof of the correct statement so I this is an algorithm that outputs whether this is K so now how do I know that if I proved it then this is indeed the common law of complexity because of soundness so I used the check ability I use the completeness because to know that they have one of these two proofs and I use the soundness to know that if I did find the proof of this this is indeed the case I can trust it so that's very simple but I mean if you go into the literature and check for proofs of Gators theorem you'll find things which are very complex and long and they okay so there is some complication small complication hiding here and this is because I wanted the proof system from the natural numbers and that is this a question about natural numbers so I mean I have to translate this into a question about natural numbers so this is a natural number and a binary string I can definitely view it as a natural number so the question is how can I translate this into a natural number into a question about some statement about natural numbers right but the statement about natural numbers is so the and that's that's the only kind of a point that I'm sweeping under the wrong pill and this is how can we translate a statement K of X equals some number K to a statement about natural numbers because my proof system I mean that my proof system didn't I mean it's not that I was gather was claiming that this proof system should be able to answer any question you know is that God okay either the proof that the reason or does it prove the reasons I'm only very modest so I want to say it can answer questions above natural numbers so I have to convince you that this is indeed the question about number natural numbers right but what is this question is saying is that KX and K can be viewed as natural numbers because that's a binary string binary string is a natural number that's a natural number but what is K of X K of X if I can just translate it I want to show you is how to translate it into a statement about natural numbers so K of X equal K means the following there exist P such that P is a what language do beside the Kolmogorov complexity is in C++ okay a3 plus plus program of length okay that on the empty input outputs X and holes so and I also want to say no shorter program does it no no but I gave you him an algorithm that does it for every X and every K my algorithm does it for every a okay you here's my algorithm you give me input X K any X and K and here is our algorithm once this is for every X in Africa the algorithm will always give you the right answer right right it goes in increasing order through our possible proof but since there is for every X in every case either there will be a proof of this all there both of these days when there will be a proof it to be a finite proof so it's some finite step where I'll go and we'll find the proof and hold right but that's because these things are checkable and proofs are finite so I can enumerate just go over all finite candidates of being proofs for each other my check is that the proof using the chick ability if it's not a proof I throw it to the garbage if it is a proof I check does it prove one of these statements so I mean it's it's crucial that we have a check ability of our proof system but of course this is also a crucial fact have requirement for any proof system it's not something out the official there's no point in a proof system if you cannot check what is a proof an out is not a proof okay No the algorithm takes as input a single proof and just tells you is it a good proof or not that's everything you just invoke this algorithm over and over again you go over all sequences you take a sequence invoke your checker the checker tells you if it's proof or not go to the next sequence poke your checker okay so there's no cheating there okay so I want to show you why this is a statement about natural numbers but what is the statement there exist a program but you know you see what is a program a program is just a finite a I can write the program in in the language in which everything is like binary it's kind of a binary string so this is there exists a program is there exists a number and that is a C++ program is just a property of this number I mean I take the my binary string and I can describe which binary strings are legal C++ programs and that I can write it as a property of this string so the program can be written as the strings of zeros and ones that's what actually happens once you write a program the compiler had to when you went to run it it translates into a string of zeros and ones and the compiler actually checks if this is a legal C++ program or not so this is a property of this string it's the property of the number this is a legal program and the length scale is also a property of this number and so everything here is actually can be translated into a statement about numbers I mean we can do it in two steps we can say okay the gathers theorem tells you tells us what we see now is there is no proof system that can decide any statement about programs which is sound and complete and checkable about programs but having a statement about natural numbers allows us to have a statement that talks about programs because I can encode every program is a natural number okay so we proved the gainers theorem so we have everything that we need and this is okay so let me talk a little bit about the consequences of the gaiter theorem I mean from now on when we are done with what we wanted to do so we can just philosophize why do they need it it's all about I mean if you look at the proof and and ask why is it so complex it is due to two things first of all they they go into a lot of discussion of why can these translated to a property of natural numbers we just think for everybody who is familiar with computer and programming languages is pretty natural because you know that you write the program the program is being translated to a binary string binary is doing a natural number is the same there is a a compiler the checks it so all of these I mean that the proof was there much before there were real programs and real computers so most of the efforts goes into this saying this is the property of natural numbers no no the proof in the literature the classical proof of goodell is in the sense of saying I can say in the natural numbers a statement of the type this statement is false so so we gather actually constructed a gathered sentence which was a statement in in the language of natural numbers which encoded you see if you have if I have a statement 5x a sales to have a statement fight and I want to know if n/a satisfies Phi or not so what Goodell went is to so the real hard work of showing that this can be translated to a statement on in natural numbers which is much harder because you can this not a natural number and then once it could show that this can be translated into a statement about natural numbers he wrote a Phi sigh that says you know I am wrong basically and then if it's chosen it's wrong and if it's wrong then it's Jo in the got a contradiction but he put a lot of work into showing that such a statement could be translated to a statement about natural numbers which is not obvious at all because this is not a natural number this is a kind of an infinite structure so we kind of still convert it with the tools of with kind of the thinking of algorithms and computers and we I mean anyway I mean this proof is is is fresh I mean that I came up with it two days ago but but there are similar procedure okay so so what are the consequence of this oh we know so first corollary so we have lots of calories and in the first call Larry is as we said already that there are two mathematical statements that are not provable but if you see such a statement you should ask yourself I mean there's something fishy you okay all right how do we know that it's true so we can rephrase it I mean first of all and I know that there are true statements which are followed so well okay let's do it step by step our first step when I say provable I have to tell you in what system what proof system so this has to do for every sound and checkable proof system and that's probable in that system okay now how do I know that they are true I just know I don't know that the particular statement is true I just know that otherwise it would be complete and I can't have completeness on top of checkable and soundness so it's not that I can show you some concrete thing that they tell you it's true but we know because I have soundness and checkable it cannot be complete cannot be complete means there's something which is true in the and there is not provable right okay so that's the first thing the second thing that I can say okay so let's go to this question of how do we know that it's true so the conclusion is that there's this statement that we don't know if they are true or not I mean now this comes to the question to almost a philosophical question is mathematics an object that is really there in the world and I can ask is something true or not I mean is it raining outside or not it's well-defined they can go outside and see if it's raining or not but if I ask you other infinitely many pairs of prime numbers bla bla bla then it's not as I mean then is the natural numbers in object in reality or it's only whatever we put into it which is something that satisfies our axioms and so what is the notion of jersey so there is this kind of two views of mathematics is mathematics talking about a real object or it's just the invention of our minds but if we want to circumvent this difficulty we can take this statement and translate it to a different statement and it will say that for every cell for every a proof system for mathematics which is rich enough can talk about natural numbers so another corollary for every proof systems there will be statements that are neither provable no refutable in the system so if we don't want to talk about what's true we don't believe this mathematic is a real object and there's a not notion of truth but you can know that there's the statement that or you will not be able to show that because right either I mean we have Phi and we have not fine we know that in any structure for the natural numbers one of them will be true if it doesn't if it's a state if it's a sentence one of them is true and we don't know which because we sure we cannot through Phi if Phi is true we cannot prove not fight because of soundness and because they are not completely cannot prove Phi and now we can ask okay so we have this statement and this is for every system which is as strong as the natural number so what about what do we do in mathematics when it when mathematicians prove something do we have some kind of an proof system that we can formalize that captures what is a mathematical proof so the next step is to ask not just about natural numbers but about mathematics in general I prove some statement about groups I prove some statements about vector spaces I prove some statements about geometry it's not necessarily natural numbers we all have some kind of a notion of what is a mathematical proof so do we have a language so it turns out that I mean after goodell this became kind of a crucial question of trying to formalize what do we mean when we say mathematical proof so there was the what is a mathematical proof what is the proof system that mathematicians use and then there were a set theory address this issue Aqsa Matic set theory and there were people like Sam mellow and Frankel and like ten years in the 50s of percent per favore century and they came up with what is called ZF c which is these stencil tomato F Stanfill Frankel C stands for something different which is choice but anyway this is the proof system they came up with a former proof system that is accepted by any mathematician today that this is actually how we do mathematics so we have a formalism for how we do mathematics so now that we have a formalism for so the matter Frank and I came up with this proof system that is an accepted commonly accepted formal system of mathematical proofs and then so we have this notion and and indeed a the statement of a poll coin that I showed you before is about this set of C so I can phrase it more precisely that FC cannot prove that a R is the next size above the size of n and it cannot prove that ow is not the next size above n it can either prove it nor refute it and when we and this is called the continued apologies and these talk about our tools of mathematics and and there are many more mathematical statements like this so what do you do as a mathematician if you have such a problem I want to know whether there is a size between natural numbers and real numbers yes very nice we will enrich it so that's a nice solution I mean if this is what you want okay let's take Z FC plus the continued oppose this this is called this is called the Continuum Hypothesis so let it this may be my new system z FC plus the continued opposition may be now so most problems are solved our my problem solves now what yeah but can you show me that it's not solved just because of Gators theorem I mean this is also we suffer from the same problem of Gators theorem so I can add another I mean I will find something else that's not decidable and i'll add that to what will happen if i keep adding all kind of statements what what will be the kind of the limits when will it break down this process I'll get a contradiction maybe at some point it will become inconsistent does it become in consistent because we know that the more power you put to your own proof system the more likely it is to be able to prove everything or a statement in its negation so we would like to be very careful and say ok keep checking that this is consistent so we really want to be able to prove the statement the FC is consistent now note this is a very clear mathematical statement in just a for every alpha there is no proof of alpha and the proof of not alpha it's a mathematical statement very clear if I have a proof system that talks about mathematical statements it should be able to say this the F Series consistent right and can I prove it can I prove that our mathematics is consistent it's what do you think see if our mathematics is not consistent it means that actually everything in mathematics has a proof true things for things nonsense everything has a proof so can we show that mathematics is consistent so this is the second Gathers theorem and the second Gators theorem it says no a meaningful let's leave the meaningful and defined proof system can prove its own consistency now we need the caveat here the recent situation in which a system will be able to prove its consistency what is this situation now unless it is inconsistent right because if it inconsistent and it can prove anything then you can also prove I am consistent so yeah I mean meaningless but but the nice thing here is that this puts us in this very funny situation we don't know if mathematics is consistent which is a very troublesome situation we don't know method maybe mathematics is nonsense really but if someone ever proves to us that mathematics is consistent then we know that he proved to us that mathematics is inconsistent because if the system can prove its own consistency its inconsistent so we don't know if mathematics is nonsense in every if anybody ever shows that it is not nonsense its it proves that it is nonsense yes right so we really have to now start being careful about what we are doing but right but I mean III don't want to get into this but all those things the main thing is that we are in this really funny situation and so you know if I go I was I'm I did my PhD in this area of axiomatic set theory and when I was doing my page did you know the conferences where people submit papers to a conference I don't know if you know it where you go to academia you will know it you submit papers to the conference there is a committee that we've used the papers decide who will so there was a conference of satirist and they got papers and they got two papers from two very famous mathematicians and one of them proves some statement a and the other one proved not a now in any other area of mathematics people will say okay you know go home check it one of you is wrong but in set theory says oh maybe I mean maybe mathematics is inconsistent because this is a possibility we cannot rule it out so there was some kind of a big worry because both of them are very beautiful mathematicians and it's not inconceivable that both of them work correct and that Holl automatically collapses so luckily in those in this case one of them retracted this proof but if you ever show you see if you ever show inconsistency you know what you should do with it right don't tell anybody just use it to prove everything from now on I mean you will become the most famous politician because we know that from alpha and not alpha we can prove better for any better right so if you have a proof of inconsistency just keep it to yourself and carefully like once a year solve some big open problem not the one to give you you know hints on how to cheat so yeah so we're having this really really a very very strange situation and let me I mean okay so the AFC is a very kind of strong proof system this is what we believe that all of mathematics can be done in the set of C and we have this unclarity some statements that cannot be decided and we don't know if it's consistent what about si we're more modest and all we care about is not all of mathematics but only the natural numbers so for the natural numbers we have I already mentioned it to you if we don't want you see this is the statement here these statements they continue oppose this is not about natural numbers its voting infinities so we can ask what about statements about natural numbers do we have similar situation so for proof system in for natural numbers we use for troops on quash or natural numbers we use a weaker system weaker then the full set of SI system which is called piano arithmetic I already mentioned it before so it has things like you know statements like there is a 0 for every X zero plus x equals x and for every X 1 times x equals 1 and for every X for every Y X plus y equals y plus X and so on it's a very simple system it captures the basics properties of arithmetic plus the induction principle yes it's actually but I will not count it as a mistake and so that's per an arithmetic and it turns out that I know arithmetic we can prove that it is consistent so but not the system itself cannot prove it is consistent but they have seen which is the stronger theorem can prove that PA is consistent so mathematics what we use for mathematics can show that this system is consistent how will you prove that the system is consistent no how do you prove I mean if this is a good preparation for the exam if I ask you in the exam prove to me that the following set of formulas is consistent what will you do yes right what way and how do you show it can prove it yeah that's one way I mean find something that it can't prove but then you have to show me that it can prove it which is not easy but there is a much easier solution I mean you just yes using since friability we know that consistent and satisfiable is the same so if I show you a structure that satisfies it then I got consistency which structure do we know that satisfies all of those properties of natural numbers the natural numbers so this is just the statement that they have si prove that natural number can prove that natural numbers exist that's all because satisfiability means consistency and of course we want a mathematical proof system in which you can prove that natural numbers exist and it turns out that the only component that is missing here if I tell you there is a 0 there is a 1 there is a plus operation there is a times operation I almost gave you all of the natural numbers the component that is missing here is we need to add on top of it step in the saying plus there exist an infinite set I mean this there exists a set of all natural numbers by just talking about properties of numbers I will never prove to you that there is the set of all natural numbers so if we add the existence of an infinite set we get this is what's the full mathematics Scholes yes that n satisfies this I mean I didn't show you I mean it's it's a it's a it's a it's a really valid question because you ask me how do I show that and satisfies this I can ask you back what is n so that FC construct the natural numbers very carefully and so he says you know this will be the represent the number one and the number zero this is the empty set and this will be the number one and this will be the number two and so every number will be a set you can exist you can show in in axiom the action of set theory that the empty set exists that if there is a set and there is a set that contains only that set so for every end you will have the n plus 1 is the set consisting of the set N and what yeah anyway we can we can I don't want to get into this game so you can construct each of them and then you say there exists an infinite set so there is a set of all of those and then you have to define based on those what is plus what is interpretation of class was interpretation of x and show that it satisfies all those actions it's a lot of work it's a lot of work and it's you have to put this to know what are the axioms of set theory they basically tell you there exists an empty set if you have a set and you have a set it contains it we have two sets you have the Union and so on anyway that's a very delicate construction so okay and maybe one one more okay so now I can ask okay is there s if now that I know that the FC can show that it's consistent and that if they can construct a model of natural numbers can I show you a specific statement about natural numbers that is true now I have this structure that is true in the model but not provable can I show you a statement about natural numbers that is true and not provable if you see them and for example is P versus P equals NP could it be a statement which is true and not provable so I want to just finish with an example of such a statement just that you will see that things are not completely in the air so this I I want to I mean yeah there too many things one can go to from here but let me show you such a statement so for a statement about natural numbers I want to show you a statement about natural numbers that is true but with the action of natural numbers we cannot prove it but I can prove form a bigger system that is true right and so this is called Ramsey Ramsey theorems any of you heard about Ramsey humans before so I'm the theorems are really a fun area in mathematics in combinatorics so Ramsey theorem says the following I mean the simplest version of it says if you have a group of six people say I have a group of six people and some of them know each other and some don't so let us put an edge whenever I have two people that know each other so if I have a I have a small party and I invited six people and some of them know each other already and some of them don't there will always be three people such that either none of them know each other or all three know each other so where if I have six people no matter how they're arranged there will always be three of them such that either all three know each other or none of the three know each other no matter how I arrange it and more generally it says the following it says that for every for every number M there exist a number n such that every graph v/e on n vertices either a contains a clique of size M Oh free subset of size M so do you all know what is a clique in the graph if I have a graph a clique is the subset of the vertices that all the edges between them exist and a free set is a subset of the vertices that have no edges between them so this is a very interesting direction mathematics it tells you that if you have enough elements then there will be some simple structure inside you cannot avoid having a simple structure inside so if you take enough nodes if you have enough nodes and you try to now draw a graph between them edie edges right so I'll say that the simple structure is either a structure that has no nodes among them or a structure that has all the poor or no edges all the structures are all the possible edges those are very stupid structures and what the lambda theorem tells you if you have enough nodes then no matter how you put the edges you will not be able to kill all the simple structures there's going to be a simple structure of size M so for any end there is an M with a simple structure of size M and this is this is the direction of automatics which is a useful because it has lots of kind of surprising consequences and it's called Ramsey theorems and this is called the Ramsey numbers so the minimum such n is the Ramsey number of M and it turns out that we don't know much about them I mean the we know that in order to get three we need six and those numbers grow very fast and we we know what is there so this is the 3rd Ramsey number does the force number how many edges do I need to know if I would just want to get to how many vertices do I need in order to just get either a clique of size tool or a free set of size two yes right if I just take a graph of two edges of two vertices then either there is a free set of size two all there is the clique of size two so the Ramsey number for two is very simple it's to the Ramsey number for three is six it's a bit como complicated their arms in number four five or six or thing is already unknown it's already an open problem in mathematics but we can prove that they exist now if we add something which I will not go into the details we add something to the Ramsey requirement I mean the the requirement that I add is you see I I can say mine vertices are natural numbers so my vertices are one two three four five six so I want to add the requirement that there exist a click or a free set of size M such that the smallest vertex participating in this clique is M right there is no number smaller than M just participates in the clique I just add a small requirement that the I have identities for them points and I want to say I'll have a big enough set which is simple and it doesn't contain numbers which are smaller than its anyway it's not a very interesting problem except that we can show that it's true but you cannot prove it from the accent of natural numbers although it's just a statement of natural numbers so this statement is not really interesting the ramsey theorems are really interesting because there are key in many things in mathematics it's good to know today such a thing exists and by adding this small decoration to it we get a statement that we know it's true if you use full mathematics but it's just a statement about natural numbers for every M there exist an N such that we cannot prove it with just natural numbers okay so this is as far as I wanted to go in the I mean there are many other topics of the didn't cover but we don't have time to get into them in 20 minutes so are there any questions in this point yes this system said of C you see he asked ZF c is strong enough to show this power which Makita consistent so can I come up with a theorem is strong enough to show the death of C it consistent it's very simple they'd have C plus consistency of ZFC I will add it as an extra axiom so now I can prove the dead of C is consistent because it's an axiom here okay now you can ask you or maybe it's inconsistent but we know what happens to inconsistency oh no it's wicked as FC but pa+ never existed infinite set is is equivalent to the FC yeah that's that's a strange question we don't want to think about this situation because if the other says inconsistent it means that mathematical proofs are meaningless right because their FC captures mathematical proofs it's inconsistent means you can use mathematical proofs prove everything so you can prove that p is consistent you can prove its inconsistent you can prove anything you want so that that's not we all believes it's consistent they will use to be I mean that's why it called z FC that why's there they added the C for the axiom of choice so I can I don't know how much patience you have for this kind of abstract things the axiom of choice I can say something about the oxygen so the axiom of choice is the statement that if you have a collection of sets then you have a set that picks one elements from each of them which it's I don't even want to go into the same it sounds very strange why do I have to worry if I have a collection of non-empty sets I never said that picks one of anything but so that's called the axiom of choice axiom of choice but axiom of choice is very important because it's equivalent to many statements in mathematics so it's equivalent for example to the statement that every a vector space has a basis so this is definitely this is the theorem that you've probably heard about if you learn linear algebra linear algebra we take a vector space we say every vector space has a basis turns out that this statement is equivalent to the axiom of choice or it's equivalent to another statement which is really nice statement in geometry so in geometry there is a statement which is called Han Banach theorem which looks completely trivial which says if I have two convex oh two convex sets so a convex set is a set that if they take two points and I connect them then the line that connects them remains inside the set so if I take two convex sets in our n I can find a linear separator that separates them that sounds like a very natural thing is if they are not convex I cannot if they are not convex I can say this is one of my sets this is the other set I cannot find the linear separator between them I cannot separate in separate them by a linear cut so there is a statement that says if both sets are convex then I can find a linear separator between them this is called the Hahn Banach theorem it looks like obvious right if I draw it on the on that board it is also equivalent to the axiom of choice so it looks like Oh everything it's all natural it's all very natural properties why will this be so controversial that we have to specify in our proof system there is that FC with choice and there is the proof system that F without choice why why is it controversial it's controversial because it turns out that on top of all those nice properties it also has very unpleasant consequences so it has some unpleasant consequences so some unpleasant consequences of the axiom of choice so remember that some of choice is just this statement every linear space have bases every two convex sets can be divided a separated by a line very natural thing but what are they are so one of them is that if I look at the uniform distribution of the lie over the unit interval so I look at the unit interval and I look at the uniform distribution so we all know what it is right so what is the probability of the set from a quarter to 3/4 what is the probability of hitting this set in the uniform distribution half right what is the probability of hitting a set it contains only one point zero oh you know everything so one consequence of the action of choice is that there exists a set that has no probability so the probability of hitting it is not zero but the probability of hitting it is not bigger than zero it just doesn't have a probability so this is an unpleasant consequence of the axiom of choice so that's why it was controversial I mean do you want to have this so do you want to have this you cannot have both if you have these nice properties then you must have also this and another kind of I mean I can even describe to you the set but another unpleasant consequence of the axiom of choice is the following statement that you can take a ball in all three I don't know how to draw a ball in all three and divide it into eight pieces and divide it into eight pieces and without changing the geometry at all you just cut it into eight pieces and three of them can be put together to create a ball like the original one and five of them the five others can also be put together to create a ball like the original one without bending without stretching without anything just taking the pieces and moving them around now I'm not joking and and this is a very useful theorem because all you have to do is you buy some gold so this is also it's called the banner paradox and it's also something we can prove the axiom of choice so when we try to look very carefully at what you are doing in mathematics we run into problems so one of our big problems was that we cannot prove that we are consistent another small problem was this question of the axiom of choice that initially looks very natural but we can also get all kind of unpleasant consequences but everybody prefers to leave with this so mathematics today takes the axiom of choice is a common tools in mathematics and we just live with the fact that there are subsets of the real nine that have no probability and the ball can be divided in such a funny way but this is a mathematical ball any wheel ball you know it has atoms and I cannot cut the atoms in in their half in between so there is no danger that anybody will use it to generate gold okay so this is as much as I can tell you in this course it was a big pleasure for me thank you very much I one more thing I will have a the problem is that I'm going away next Thursday and I want to give you another chance to if you start preparing for the exam although the exam is only almost ten days from now so I guess it's it's very far in the future to start studying but if you want to have a I will have a very question answering session I want to just pick a time that is good forever so like Wednesday next week is the farthest I can do it other any do any people here that would like to come and have an exam on Wednesday Wednesday next week I just want to find a time that will be good for as many people as possible and then I'll find a room so yeah who has an exam next Wednesday when what time 9:30 in the morning anybody else is 9 the more anybody has an exam until Wednesday afternoon when 4 o'clock oh yeah so that's that's becoming problematic because you you probably will not have time AB the the peace of mind fall for it before your exam right yeah so I'll try to make it as late as possible Wednesday our afternoon and I'll put on Piazza and they learn the time and place for the review away session ok thank you very much