Logic: Propositions & Predicates | Geometry of Physics 01

[00:00:07]so welcome everybody to the course on the geometric anatomy of theoretical physics and you being advanced students you know that theoretical physics is all about casting our concepts about the real world into rigorous mathematical form for better or worse and but theoretical physics doesn't do that for its own sake but it does so in order to fully explore the implications of what our concepts about the real world are so to a certain extent the spirit of theoretical physics can be cast into the words of Wittgenstein who said what we cannot speak about clearly that we must pass over in silence well so indeed if we have concepts about the real world and it's not possible to cast them into precise mathematical form that usually is an indicator that some aspects of these concepts have not been well understood so if your ethical physics aims at casting these concepts into mathematical language but then mathematics is just that it's just a language and if we want to extract physical conclusions from this formulation we must interpret the language and that's not the purpose or the task of mathematics that's the task of physicists and that is where it gets difficult again but again mathematics is just a language and to again use Wittgenstein he says the theorems of mathematics all say the same namely nothing ok and so what does he mean by that well obviously he doesn't mean that mathematics is useless refers to the fact that if we have a theorem of the type a if and only if B a and B being propositions that obviously B says nothing else then a does and a says nothing else then B does it's a tautology okay now of course mathematically logically it's a tautology but psychologically or for understanding of a it may be very useful to have a reformulation of a in terms of B right so with this understanding that the mathematics just gives us a language for what we want to do the idea of this course is to provide proper language for theoretical physics and certainly for the for courses you have heard so far so the aims of the course the aim the overarching aim is to provide proper mathematical language for classical mechanics electro magnetism quantum mechanics and statistical physics now so these subjects you studied in the modules gp1 to tp4 here at a line or at many other universities and obviously we're not going to revise all the mathematics that are needed for these four subjects but rather we will develop mathematics from a higher point of view that we can now approach that you have some prior knowledge of these subjects and so far you have certainly used a fair amount of analysis in order to study these subjects further a fair amount of algebra mainly linear algebra but also non linear algebra at times and geometry in one or the other form so very often in classical mechanics you would appeal to geometric intuition in setting up a problem or finding the solution to a problem the same goes for electromagnetism algebra you mainly used in quantum mechanics that's the modern way to do quantum mechanics is by means of linear algebra and in statistical physics you use some geometry maybe without really realizing it by looking at convex cones of states and so on now if you take these four fields and you try to be pedagogical if you draw circles around them and so classical mechanics and electrodynamics certainly use a fair amount of analysis in geometry and so does general relativity for those of you who took that course or about to take it well quantum mechanics lies certainly well in intersection of analysis and algebra usually called functional analysis and well algebra and geometry let's do statistical physics justice ed more or less lies there of course this is not a pure picture this is mainly where the intersections of these fields come to play and here in the middle where these three fields intersect we have differential geometry as a mathematical subject and it's differential geometry that this course is mainly about so the mathematics of this course will be that part of the mathematics of these different theoretical subjects where these three fields intersect that's the rough idea of this course now the structure of this course and indeed the development of differential geometry that we're about to start starts well with sets so we'll talk about set theory because any space in classical mechanics the space of configurations or the phase space electromagnetism the space in which you work or in quantum mechanics the physical space over which you construct your hilbert space and so on all these spaces are certainly sets of points that's the coarsest structure of such a space it is a set but what precisely is a set well one can delude oneself into thinking one understands set by saying a set is a collection of elements but that just raises the question what a collection is and what elements are so we certainly need to do better and there is a fundamental problem if we start writing a book about mathematics of whose pages are all empty yet because what could the first definition be for definition you need notions that you already have in order to define a new notion but if you don't have any notion yet how do you start well the trick is to start axiomatically and so we'll have to write down axiomatic set theory but that then raises the question in what language would you possibly do that so actually before we come to set theory we need another building block down here and that will be logic and we will deal with propositional and predicate logic first that will define our language and then we'll be able to write down the axioms of set theory now once we have the axioms of set theory and we have our beautiful sets the question is what can we do with them and one thing we certainly need at least for these four subjects we need a notion of continuity for instance in classical mechanics are famously particles don't jump so the particle trajectory doesn't stop somewhere and start somewhere else again it's continued so you need a notion of continuity and such a notion you get by distinguishing certain subsets of the basic set you have and that leads to the notion of topology so we'll deal with topological spaces and all the notions associated with that now there is an abundance of topological spaces such an abundance that you cannot even classify them and so we will need to restrict somewhat to interesting topological spaces well topology topologists may disagree that only those I'm going to write down are the interesting ones but from the point of view of theoretical physics immediately interesting are the topological manifolds topological manifolds which we're going to define a topological spaces that locally around the point look like some R to the D now that's not enough if you have topological manifolds you also need in physics especially in classical physics you need a notion of derivative you need to be able to talk about the velocity of a curve and that cannot be done in topological manifolds what you need there you need differentiable manifolds and that's an entirely new beast and they will need to introduce the technology of charts and the technology of charts will for the first time make contact to much of the formulism you already used in the standard courses in fact all the standard courses have been formulated in charts so far I'll explain later a chart is like Sailor uses a chart of the world you travel across the globe and if you want to know where you are and where you want to say you take out Atlas and the Atlas you'll turn the pages and you'll find the appropriate chart around the point where you are in the real world you can navigate in the chart and there and the chart should be a one to one picture of the world locally because if you then move in the world such that in the chart you would leave the page you better turn the page and you'll find the other page that slightly overlaps with the chart in the Atlas so that you can then navigate on with the other chart and very much the same thing looking for another chart that overlaps and understanding how the overlap works that's the whole philosophy behind manifolds and certainly behind differentiable manifolds because differentiation the charts are parts of Rd like r2 for instance and them so you understand differentiation in the charts and we will lift the notion of differentiation that we understand well in the charts we'll lift it to the general concept of differentiation on the manifold that's already the entire philosophy it's it's roughly the same chart it's the technical term in this case that's right okay so we will certainly come to that now once we have differentiable manifolds maybe already before we'll come to a notion which well in some sense is yet another structure but it's bundles so the idea of bundles is you take a manifold and you take another manifold and to each point of a given manifold you attach the other manifold you build a bundle you could have a vector bundle at each point you attach the tangent space and so on and bundles are a very important concept in geometry in differential geometry and indeed much of modern physics can be understood or can be cast into the language of bundles so this is true for particle physics but also for gravity and so on certainly for quantum mechanics so I'm actually about here now already here we will learn that a notion of position vector should be forbidden there is no such thing as a position vector doesn't matter how often it's repeated there is no such notion now in bundles you learn there is no such thing as a wave function in quantum mechanics you get away with the notion of position vector unless you look too closely and then it fails and the same is true in quantum mechanics you get away with the notion of wave function but then it fails in fact a wave function is so a position vector is just a collection of coordinates but they do not constitute a vector and the wave function in quantum mechanics is not a function at all it's a section in a complex line bundle over the physical space you cannot understand this but you will at the end of the course so these notions are needed if you really want to say what's going on now ok so once we have bundles or maybe also alternative to bundle sometimes so don't take the picture too seriously it's a rough idea of how this building is constructed will have geometry geometry comes in form of so-called tensor fields on this structure so that could be symplectic geometry that would be the drama tree of classical phase space in mechanics but actually it's a much bigger subject because for virtually all dynamical systems of interest to us the phase space is equipped with the symplectic geometry there may be a metric geometry this is certainly the case in electromagnetism due to a certain extent needed drama tree just in the volume form and certainly it's the case in relativity and special and general relativity you need a so called lawrencium metric this is a structure that sits on top here but you need to understand more or less all of this in order to really professionally deal with geometry well and then to complete this then when I promised you that all these different subjects you learn about before so up to here it's just physical mathematics but then up here it's physics we have classical mechanics electromagnetism quantum mechanics statistical physics and special relativity and general relativity all of these physics can be understood and can be properly understood by mastering all these mathematics and again the purpose of this course is to develop these mathematics and then to show mainly by examples of how the insights you gain from here play out at the level of physics that's the ID of this course are there any questions so far okay so let's start with logic so chapter one is actually already axiomatic set theory in the first section here yes yes and the logic behind the logic is that now the first subsection will be propositional logic so I summarized the logic under axiomatic set theory because it's the language for axiomatic set theory so one point one is propositional logic now the key notion of propositional logic is a proposition definition a proposition P small p is well let's call it a variable whatever that means it's a variable that can take the values true or false and no others that's it that's a proposition from point of view of propositional logic so in particular it is not the task of propositional logic to decide whether a complex statement of the form there is extraterrestrial life it's true or not that's not the task of propositional logic propositional logic already deals with the complete proposition and it just assumes it's either true or false you can say well let this proposition B have the value true yeah yeah you can do that but if nothing is said it's either one not not true at the same time of course no other it's true or false you know this it's also not the task of propositional logic to decide whether a complex proposition of the type in winter it's colder than outside well this is a proposition at all well obviously the one I just mentioned doesn't seem particularly reasonable but it's not the task of propositional logic to decide this is important to realize this okay propositional logic deals as its atomic elementary notion with the notion of propositions now certainly you can build new propositions from old ones from given ones and one does so with the help of logical operators and they come in different forms and the simplest form is unary operators and there are four unary operators what's a unary operator unary operator takes one proposition P and makes from it a new proposition so the the one that sitting in the unary means you take one proposition as given you construct new ones and of course this one proposition can have values true or false now I said there are four unary operators let's write them down well a famous one is the not operation not P not P is again a new proposition proposition called not P in this proposition if P takes the value true this proposition takes the value folds and if P is false this proposition takes the value true it's one of them and you certainly saw this before well there are three others there's the identity let's call it EDP this is true folds there is something like we might call the tautology operator TP this is always true independent of what P is and there is this operator let's put it upside down P that's the contradiction that's false whatever P is and you quickly check that if P can be true or false these four are all the possibilities you have for defining a unary operator well the next step are binary operators in order to see how many of those we have well you need to start with two propositions that you assume are given and they can take the values true true true folds folds true and folds faults and so the easy one certainly known to all of you is the end P and Q and P and Q is a new proposition so this in total is one new proposition this is true false false false in the cases where this is true and this is true this is true and so on now there's a whole number of others and you can quickly calculate if for these four rows you can each row decide whether you put a true or a false we have two to the four equals sixteen binary operators yes that's right so a bi a unary operator takes one proposition and construct from it a new proposition yes but that's the notion of an operator it takes two variables from this set so it goes if you would say from a Cartesian product of the set true/false with the cetera falls to the set roof holds it's a map however I'm not saying it this way because we don't know yet what set is we don't know yet what a Cartesian product is this is a an elementary presentation of this one can do this even more abstractly and just write down deduction rules never writing never write down such a table and you write down deduction rules this is the even more abstract way of doing this I didn't choose it because it has no purpose whatsoever if you do standard logic if you do non-standard logic like intuitionist logic then you reduce certain deduction rules and then you get a logic that you can no longer express with these tables okay and well that is very esoteric I don't say it's not interesting I find it very interesting but every course has to define its bottom line and so this course defines the bottom line at not writing down propositional logic using deduction rules and axioms but rather presenting the tables because it's really sufficient for what we're going to do okay okay so now there are a number of others there is the or there is the exclusive-or and so on so the P or Q you know this is true true true false the exclusive-or is false true true false and so on so in medieval ages people were discussing whether the or that appears in some sentence actually means the inclusive or the exclusive or and obviously they appealed to the Bible in order to see how God used it well it was actually again Wittgenstein and Frigga and others who wore less around the turn of the century to the 20th century said no hang on it's just a table it's just a definition they have 16 binary operators each of them maybe deserve their name or not you have 16 of them you have the inclusive or you have the exclusive or and so on now this is all child's play and you've seen you've seen this before but I go to such lengths in writing this down because there's one binary operator which sometimes is little ill understood unless you're maybe very knowledgeable about these things and that's this implication arrow so from school days we use this implication error as saying I write down sim write down something that's true and now I do something valid and then I may write down this implication arrow and that means I did something okay now the implication arrow as much as the end is a binary operator that takes a proposition and another proposition and makes one new position out of it so this whole thing P implies Q is in total true or false when is it true and when is it folds from true follows true this is evaluated to be true from true follows false no no mistake you don't pass the test from false follows true you say no no no well yes yes yes yes you should write a team here that's at least the definition and from false follows false well that must be certainly wrong hungrily no it is not it's also true now this is the definition of the implication arrow and this is why I go to such great lengths about this well this principle that from a false assumption you can conclude anything and the whole thing is evaluated to be true deserves a name which this principle has been in place for a long time so the principle is called in Latin x-files awkwardly bit roughly translated it means from a false assumption you can conclude whatever you like x-files awkwardly bet and these first two they're kind of intuitive now the question is why on earth would you define the implication arrow like this and the answer is hidden in a little theorem it's very simply proving the theorem is P implies Q this statement I put it in brackets is actually equivalent to now this equivalent arrow the equivalence arrow we haven't defined I define it here on the left-hand side P equivalent q is true if both are true false if one of them is not and the other is and true again if both are false P implies Q is an equivalent statement to now careful not Q implies not P so the order if you put the knot in front the order is exchanged and because I didn't tell you about the binding strength yet you may be careful and put brackets around here now this looks funny it's quickly proving we'll do it in a second but the important thing about this logical mumble jumble is the corollary this actually means we can prove assertions by way of contradiction so see we know that P is true it's the assumption that P is true and we want to prove that then Q is true what we can do instead which is fully equivalent is to assume that what we want to prove is not true and to prove that that means that the assumption isn't true and we say Oh contradiction so Q must have been true well this is what this says so this statement says you can prove assertions by way of contradiction it's a very elementary principle a very sharp tool of mathematics now coming back to your question about these tables and what map this is such an operator if you formulated logic in terms of these deduction rules and axioms without the tables you could surgically remove certain deduction rules and one of them that you can be remove such that the whole thing cannot be written down by tables anymore would be one that destroys this theorem and then you would have a logic and build on it you would have a type of mathematics where proofs by contradiction are no longer allowed you probably in every good mathematics department you find one professor who follows that kind of I think they call it intuitionist logic and it's a pain because the cost as long as usual because you have to constructively prove everything you want to prove and some people make a strong point that that is very meaningful it's certainly a better result if you know something constructively but they make an even deeper point they say we do not trust the proofs by contradiction anyway we're not going into that with our definition we have logic that allows proofs by contradiction essentially by this by this definition well so how do you prove such a thing well this is important for the first vanilla problem in any exam well of course you use the tables and your constructors you have P Q you construct not P and not Q so true true true false false true false false false false true true false true false true and then you write down P implies Q and you know this from before it's true false true true you write down not Q implies not P while you construct it from here false implies false is true true implies false is false false implies true it's true exercise record limit and true implies true is certainly also true so we have true false true true true false true true are wonderfully these two columns are equivalent this is exactly the statement up here this is to prove of such statements by way of writing down in out in full the table the truth table okay so there are certain remarks in order remark one we agree on decreasing binding strength in the sequence decreasing okay not is very strong and it's not so strong or it's even less then we have an implication arrow and then we have an equivalence arrow okay so if you have more symbols you need to extend the sequence however the question is how many operators do you actually need well we had a few unary ones we had a few binary ones well what about higher order operators remark to higher order operators say the operator heart-shape that eats P 1 to P n statements will be an operator of order N or unary operators obviously of order 1 binary operators of order 2 higher order operators heart-shape can be constructed I should say all higher order operators can be constructed from one single we're not only high of any order in from one single binary operator and it's the so-called NAND operator P Q I write down the table of the nand operator P so let's have an up arrow for this guy so true true true folds fold true folds folds always the same order in case my writing gets worse NAND is false true true true because it's end but the negated version of it it's NAND not end and my statement is that any operator can be constructed from the NAND operator alone so in fact we do not really need this binding strength thing it's just a convenience all right so I guess there will be some finger practice problems on the first problem sheet on that yes and just to try question if you want writing equivalent operator in the tail surfaces is it only true when both sides are true or both sides of false or what's that much that's the definition of the equivalence operator it's true if both propositions take the same value yeah yeah that's because on the other blackboard yes okay further questions all right so this was a very quick recap of propositional logic and we'll proceed to predicate logic so section 1.2 predicate logic definition a predicate is what my one might informally describe as a proposition valued function of some variable of some variable or variables variable because it could depend on several so for example you could have a proposition P of X and it's truth value depends on what X is true or false dependent on X you could have a predicate that depends on two variables x and y and now it's true or false dependent on what the combination of X and y is now like in propositional logic it was not the task to study complex propositions it is strictly speaking not the task of predicate logic to tell you how these predicates are actually built you might ask okay so what could this be could this be Q of X and y is true if X is greater than Y as if x and y are numbers say real numbers and X is greater than Y that would be constructing such a predicate strictly speaking it is not the task of propositional logic to construct them because obviously in order to construct them you need some further language how you can combine objects x and y so first thing and then you might ask well what set do you take the exes from and from what set do you take the X and the y from and so on and the answer is no such thing we leave it entirely open what x and y what they are where they come from what their nature is they're just variables they say this is very weird because since elementary school days we've been conditioned to always say what set does it come from now the point is we need to leave this open in this fashion because we only want to define the notion of set later using this language so we cannot already use sets and in fact it will be a part of set theory to introduce a fundamental predicate that takes two objects and makes out of these two objects a proposition that's either true or false and you know this the fundamental so if I we're not using this here this comes later so I write here later we might define a fundamental predicate of two variables in this way using this element symbol and you see now if we already have a rough idea but don't use is just the outlook if you already have a rough idea x and y's well if they are sets and that's it actually the statement if ignored if x and y are sets then X element Y is a predicate of two objects which is either true or false okay but this will come later because so far strictly speaking in predicate logic of the first kind and so on you do not have this symbol yet so again I cross this out because it's only later at this level we're only dealing with these predicates as the elementary objects okay it's always important to know what the subject is not talking about in this case it's not talking about how to build these guys now however what we can do we can again construct new predicates from old ones construct new predicates from given ones and well there is the simple way we could define a queue of XY and z to be well you see the instead of : equal sign which means defined as because this whole thing for given XYZ is a proposition we can say it's defined to be equivalent to say P of X and R of Y and Zed but obviously if the X is supplied if the wine is that are supplied this is a proposition this is a proposition it two propositions that can be conjoined by the by the end operator and you have a new predicate now of three variables stuff like that very simple now a more interesting way is the following you can actually convert a predicate of one variable into a proposition convert predicate of one variable this can of course be extended into a proposition let's call this predicate P capital P of one variable so let's write it down let's write down the proposition which proposition the proposition is this funny upset down a X : P of X so what is the proposition well the proposition is all of this if you ask what does this guy in the Box mean the answer is its a proposition it's a proposition that has been constructed from a predicate of one way Herbal and we may read it believe me gloop and that's the proposition well we may read more reasonably for all X P of X is true so that is how we read this for all X P of X is true but how is it defined and this proposition is defined to be true defined to be true if P of X is true independent of X independent Li of X so if the X doesn't matter you can substitute whatever you like for X it's true this is the definition of this proposition and obviously this proposition has been constructed from this predicate now I warned you it's not our task here in principle to provide specific predicates nevertheless as an example as a feel-good example we might do so nevertheless so we could define a predicate P of X is defined as so now it becomes fishy but that's the feel-good part if you're good always involves an amount of imprecision X is a human being implies X now let's be politically correct X has been created this includes all Sates if you think God created it or the Father whatever and so but but this is the whole statement so there the whole proposition the whole proposition is this implication now I said we won't don't want to say where the X's come from well I don't I just hide this in here X is a human being means X has been created in the mother's womb or whatever well this is certainly always true then for all X P of X is true that's it it's nothing more nothing less yes and so far you said you don't know anything about X Y P but if the words could be also convert a predicate and other ways is a proposition let's say okay but for all X but for some X yes indeed absolutely thank you that's what I was coming to next there is the brother of this all quant or so this called the ol quandra and we can also define the existence quantification existence quanti vacation it does the same well a similar thing it takes a proposition of one variable and now there is a different mumbled Rumble in front of it which in total is a proposition and this here we will read there exists an X such that P of X this is how we read it but how do we define it what it's a proposition so we need to provide the proposition that defines it and that's simple because it's not all X not P of X so obviously brackets like this if you want them we don't eat them maybe we'll put a bracket around here for clarity so having available the all quant or you define the existence quarter as the negated all quantification if ocation of the negated predicate okay and an immediate corollary from this is well three very true rule is that for all X something is not true is equivalent to it's not true that there exists in X for which it is true if something isn't true for any X then certainly it's not true that the exists one where it's true very simple it seems simple and once it's written down is perfectly clear anything as mathematical training it's clear but if you go to the hairdresser from time to time you see that in many drum bubble shops on the door it says what hairdressers can do only hairdressers can do it sounds good but if you think about it it means they can do nothing a non hairdresser can do so if I is a non hairdresser can draw nice pictures it means a hairdresser cannot ok so careful with the negations and the all xx fusion to quickly run into things you don't want to say other questions so far okay so a remark the order also obviously we can use quantification also for predicate of more than one variable quantification for more for four predicates of more than one variable for predicates with more than one variable right so that looks like for all X P of x and y which is now a predicate of two variables well what does this yield we'll obviously this yields a predicate of just one variable namely the variable we didn't quantify over so usually one refers to this as the bound variable and to this Y that survives the quantification and then appears again we call this the free variable and well if you quantified once you quantified one of the variables away you have one variable left you can quantify again so that's remark one and the remark two is that the order matters remark to the order of quantification matters so for all X there exists a Y such that P of X in Y is generically different proposition then there exists a Y such that for all X P of X and Y and because the order matters one should avoid although it's very tricky to do so in the heat of calculation but one should seriously avoid writing quantification after the expression so very often we write this and that is true for all X Y Z or they exists in a Y such that this inverse is true and then we say for all X Y Z well you should arrange all the quantification before the predicate and then you have a clear idea of what the order is because sometimes you write one behind if you formulate not so formally and then sometimes one means you pull it to the front or you pull it here you don't know so it's best to stick to such an order and you know this from say statements about inverse and neutral elements now so neutral elements for all X in the real numbers they exist a real number zero such that X plus zero is X but it's of this type to have the inverse element no it was just the wrong way around I'm sorry you see already mistake again so for the neutral element there exists a neutral element zero such that for all elements X plus 0 is X law of the neutral element of the additive neutral element of the real numbers but for the inverse elements for every X you have a Y that means depending on what X is you can choose your wire differently something is true ok so there you have an application of this it's all very clear but nevertheless it's sometimes the root of some trouble okay so well this actually concludes our quick overview of predicate logic and but there's an immediate application to all of this is our section 1.3 and that's called axiomatic systems and theory of proofs you all met proofs your physics lectures and theoretical physics lectures mainly in a mathematics lectures and so on but what actually is a proof well it's a way of arguing why something is true of something else that you assumed is true but how do you argue what are the valid rules of writing down a proof well this can actually be defined and there are some subtleties in this that actually render some of the proofs that are sometimes given really actually non proofs and if you are very serious about proving something you need to know what the definition of a proof is well we start with the definition of an axiomatic system definition an axiomatic system and you see all this is preparation to write down the axiomatic system that defines set theory an axiomatic system is a finite sequence of propositions a 1 a 2 dot dot dot 2 a in now if one wants to be very smart about it one could object you and say what do you mean by finite and what we mean by numbers 1 2 3 4 5 2 n because if you haven't defined sets yet how on earth are you talking about numbers well you could write this down as a1 / a2 slashes 1/5 less less less less less so logicians call these pre mathematical numbers it's what you're doing Bavarian pubs okay so again if these lectures are attended by mathematical logician he will probably shout all the time well hang on a second this is a little bit too Nev it's true I'm not using the full first predicate logic approach to halt this thing it's already showed up in my use of tables and so on but it gives you the right ideas it's conceptually exactly what they do without going into too much of the formal nitty-gritty which for what we're going to do and what we're going to use it for would be fully redundant okay so this is supposed to give you the right idea it's the right idea it's not necessarily what a professional mathematical logician would write down if he publishes his new research monograph okay but this is putting the whole thing to to classroom use so this is my disclaimer doesn't mean that anything of this is wrong it's all is all right okay so an axiomatic system is a finite sequence of propositions and these propositions are called axioms which are called the axioms what's top definition what is the proof a proof of a proposition let's call it small P that's the thing we want to prove a proof of a proposition within an axiomatic system so the idea is I first give you axioms and then I set a homework problem prove P starting from the axioms a proof of proposition P within an axiomatic system a 1 to a n is a sequence and again is a finite sequence of propositions informally would say this finite sequence of propositions Q 1 to Q Capital m are the steps of the proof if you wish is a finite sequence of propositions Q 1 to Q M such that now obviously we need conditions for this to be to constitute the proof and the finite QM proposition is supposed to be the thing you want to prove the proposition you want to prove obviously if you have proved and you have steps at the end you better had the statement what you that you wanted to prove yes yes yes with like in finance name like infinite series and yes but the individual steps so actually a finite sequence of propositions I should add here or propositional schemes now we're very clear and the point is one single proposition in an axiomatic system can come in the form for all X this and that is true and then you can actually use the individual statements if I the proposition is for all X P of X it's just a proposition but you can actually take the P of X out and say well is it for all X then I can use P of X as an individual object which is then true in maybe infinitely many instances maybe for all the x's that could be and that we call a propositional scheme so there is some subtlety there but the actual steps of the proof must be a finite number of steps it's very important and when I was in my first semester I had the well today I would say I was fortunate that my analysis professor was an intuitionist so he didn't have contra proofs by contradiction that was one thing and the other thing is that he was sometimes really mad at some textbook proofs of analysis theorems and he very often said and this proof is not cyanide and we didn't understand what he meant well we now understand because in the form of fear of proofs you need a finite sequence of propositions it's very important anyway so it's such a sequence of steps and they need to satisfy certain conditions so proof is a finite sequence of propositions Q 1 to Q n such that well condition a is satisfied a one of the following such that one going on I'm young okay such that for any J that lies between one and the final step so that for any step of the proof either of the following is true either condition a is true and that means that this J step of the proof that this Q Dre is a proposition from the list of axioms it means at an arbitrary step in your proof you may pick one of the axioms and put it there very clear you may put it there be an OT tautology or the J's step of the proof is a plain tautology is a tool ecology I think I didn't define how many what a tautology is a tautology is a statement is a proposition that is always true independent of the elementary propositions it's made up of so to paly tautology eg P or not P this is a proposition right and because P appears in there and we don't know whether P is true or false generically we would know whether P or not P is true or false because it could depend on would depend normally on P but this specific combination P or not P well this is always this is always true as you can check from the table this is called a tautology a tautology is a proposition that is always true independent of the elementary propositions it's made of and so either this or this or for the J's step of the proof the condition M is satisfied so this stands for axiomatic this stands for tautology and this M stands for modus ponens which is a very old logical how do you say deduction rule but we'll write it down here I mean there's nothing in the name modus ponens such that there exists m m and n somewhere in the proof that we had some note not somewhere but actually before the current step so if for every step it's true that the so we're in the J's step of the proof we may use any of the previous steps step M and step n which are before the current step such there exist such guys such that the proposition Q M + q n so you take M step of the proof you take the nth step of the pro you put an end between implies the cue of the Jade step such that this is true so please realize this is a proposition okay so it could be that we have two steps before the proof and if I put them together by and and I can show that from this end implication arrow Q J is true for some m and some N before this Jade step this whole thing is true that also qualifies the Jade step as a valid one so the Jade step can consist of an axiom it can consist of a plain tautology or it can be deduced from two previously arrived steps steps we arrived at if this is true yes do you really need the last one or doesn't it follow out of a and T somehow I mean it's pretty much just in the assembly of proportion is this okay let's trollee know it you need it you definitely seriously desperately fully need it it's just probably some somewhere it's just sorry to intrude leaders you don't really see anything yes because you have some kind of kindergarten intuition about this thing you CIA if this is true then I can do this but remember this is a binary operator it's not more it's not more it has not this nice intuition about where the arrow goes the other thought goes or something it's just a binary operator this is a logical statement as one of the axioms will at the moment we don't have enough technology to provide a meaningful proof but in this course I will write out one proof in full according to this scheme one single one and that is I think the uniqueness of the empty set now there will be an axiom that stipulates the exists an empty set with such-and-such properties and then you have to show there's only one such set it's a very quick proof and intuitively we say 'yeah it's clear that it up if you know the definition of the implication arrow but if you really want to write it out I think it has something like 16 lines it's a 16 step proof if you write it out in full like this and I want to present one proof that is precise and the other proofs will be given in the form they're usually given by some quick arguments but the understanding of mathematicians is where here I mean even in the best journals and the most celebrated theorems are usually not proven in this fashion because this goes in the millions and billions I don't know of lines proving comparatively simple stuff okay so we don't do that we use electric this is kind of like machine code in computer science right almost like the zeros and the ones the binary code and actually the proofs we give in the higher language like C++ also okay so this is what we do in mathematics but the understanding is that the proofs we write in books we say well now it's obvious that dah dah dah dah the understanding is it's only a proof if your fellow mathematicians agree that in principle what was written down now could probably according to our intuition be broken down to proofs of this type okay and if somebody has the feeling that what you do here will not lead to approve of this type for instance not to a finite step proof or proof with finitely many steps then mathematicians will raise objection to this proof we will say well we're not convinced and then in principle as long as somebody says I'm not convinced a mathematician has to break down to prove more and more until you arrive here so you can obstruct any lecture in mathematics so it's don't tell anyone you can abstract any lecture in mathematics by you know okay no it doesn't matter because you can go back and your proof to an arbitrary point because the rough idea is that everything there has been there anyway it's an axiom or it's a tautology and all the other stuff has been arrived at by implication arrows that's the intuition and so it suffices to look at stuff that was before but because everything that comes after has been connected by an implication arrow but you cannot go further than the current step because that would imply that you used equivalence arrows if you use equivalence arrows you can go further down say oh and later I show so I can use it again now apart from some circularity it's the the directedness of this thing very roughly speaking intuitively speaking that allows you to go to any previous pair of previous steps even if there's something in between but not further okay fine okay so remark if P can be proven from an axiomatic system a 1 to a n we often write a 1 dot a n then this symbol means proves P Sauer short form for this and of course an obvious remark is that this definition of proof proof allows you to recognize the proof this definition allows to easily recognize a proof so in principle you can give this a computer you say computer please check is the following a proof of this that's very easy to check and altogether different manner is to find a proof different matter is to find a proof for a certain proposition and as you all know from your own experience even set problems where usually if you ask to prove something it can be proven it's not so easy and sometimes it's so difficult that if you find a proof where people before didn't you become a celebrated mathematician so the theory of proofs here doesn't give you any hint of how to prove things better but at least it tells you what you have written down right now that is a proof and that can be very useful of course ok a further remark is that obviously any tautology should it occur in an axiomatic system what's in the axioms if among the axioms there's a tautology can be removed from the list of actions without impairing the power of the axiomatic system and it's very poetic it means you can still prove the same stuff because if you don't pull your proposition from your tautology from the list of axioms you can put it any way so it's actually this axiom t-that guarantees that and an extreme case of this is that's why I'm mentioning it what is the axiomatic system for propositional logic axiomatic system that describes propositional logic what is the list of axioms there it's the empty sequence because in XML in propositional logic or we can prove our tautologies want to show something is true well but then you don't need any axioms because you can always pull a tautology into your proof by axiom T okay I push this up for thee for the camera so this will become important in a second but let's have one further definition namely an axiomatic system is consistent an axiomatic system is consistent called consistent if there exists a proposition Q which cannot be proven which cannot be proven from tea or within the system of from the axiomatic system from the axioms or to express this formally not a 1 to a n proves Q exists such a Q now what's the idea behind this surprising maybe definition or it's very simple yes and I may be wrong but I think a 1 sir that is proven that it can't be proven that the system is consistent we'll come to that my last statement of this today's lecture will deal with that ok so the idea behind the definition of consistent axiomatic systems is imagine or consider an axiomatic system containing contradictory propositions so for instance a one data whatever I'll pop up a pot then we have P well p s as one of the propositions and later on in the list we have not s so we have an axiomatic system that stipulates this then by the deduction rule M the one whose existence or justification was doubted tentatively then by M clearly yeah I can pull the s into my proof I can pull the not s into my proof by axiom a and then I can use these two by M and connect them with an end and I only need to check whether for an arbitrary Q this is always true is this a tautology yeah this is a tautology because s and not s as and not as is always false you remember but if some is the assumption is always false the implication arrow is defined such that the whole statement is always true x-files awkwardly bit so it's again the definition of the implication arrow which a dwelled on at the beginning so much which shows that this is true x-files look what limit whatever you like well whatever statement you like can be concluded so by M we can arrive at the truth of any statement Q can also arrive at the statement of not Q it doesn't matter so the problem is any statement can be proven if you have contradictory some shion's contradictory axioms now it's a sign of not having inconsistency of not having contradictory axioms if it's simply not true that every statement can be proven but here every statement can be proven hence we need to exclude that every statement can be proven there's just one example this is the general definition of consistency well having come this far we can now write down an impressively sounding theorem which is very trivial propositional logic is consistent propositional logic is consistent that's reassuring what's the proof well we have to it suffices to show suffice is to show that there exists a proposition that cannot be proved with in propositional logic that's clear there's at least one that cannot be proven then it's consistent now propositional logic has an empty set on empty sequence empty sequence of axioms you don't have any so the only rules for proof only T and M must carry any proof now let's look at T and M again the only way by which you can introduce an entirely new step is by writing down a tautology and then the modus ponens only allows you to take previous tautologies and to write down the QJ where all this thing is a tautology so the only thing you can prove are tautologies only tautologies can be proven but that means that is Q and not Q cannot be proven because not a tautology so we constructed the proposition that cannot be proven and so propositional logic is consistent and this is really trivial now again the important remark is that while it's perfectly fine and clear how to define consistency it's perfectly difficult to prove it for a given axiomatic system propositional logic being a big exception but if the X Ematic system becomes more powerful if you have more axioms like we're going to write down for set theory you might then again ask the question is this set of axioms consistent in this sense and it's very difficult to prove that in fact there famously these statements first arrived at by girder that say to certain extend it's even not possible to show this under certain circumstances and I will give only a very rough taste of what of one of the things good proved so that's a theorem Scootaloo and it roughly not being technically goes as follows any axiomatic system that is powerful enough to encode the elementary arithmetic of natural numbers which are the positive integers so you see I use imprecise language here what's elementary arithmetic well in elementary arithmetic it depends on what you need to prove it means you understand prime numbers you understand product stuff like that okay rather elementary stuff let's say elementary school mathematics hmm what exactly it is one would see the proof what you need but any axiomatic system it's powerful enough to encode elementary arithmetic of natural numbers is either inconsistent nevermind its successes with the arithmetic of the natural numbers is either inconsistent or contains yeah well it contains well you know or contains a proposition that can neither be proven nor disproven so variants of this formulation are it contain true statements that cannot be proven I mean this sent shockwaves through the mathematics world at the time was this beginning of the 20th century 20s 30s something like that because in mathematics of all the arts if you wish the notion of truth seem to be clear up to then truth or the truth something was true if it could be proven based on a system of assumptions this was the pure truth of mathematics but then girdle came along and he ironically proved this and variants of this now how does the proof proceed well the proof is complicated on its rather say the proof is involved but the basic idea of the proof is the following a sign to first assign to each mathematical or also meta mathematical statement or proposition a number the so called what later on people called now called girdle number well a mathematical statement is a squared plus B squared equals C squared something of this kind yarn for all kilala exists and so on and good I mean very roughly speaking says the plus sign gets a number the the exponent gets a number every variable gets a different number the equal sign gets a different number and then you can start talking about this equation you can say the left-hand side of this equation has more symbols than the right-hand side that would be a meta mathematical statement because obviously not a mathematical statement is a meta mathematical theory lessons that is more similar than the right-hand side but even to such statements such metal mathematical statements girdle would be able or devised how to do how to assign a number to even such a statement take Prime's everything everything gets a every elementary symbol is assigned a prime and then you take powers of primes and you multiply the powers get big numbers and then to meta mathematical statements you get a huge number boom there it is right now you do this for just everything okay and then once you did that in a sense you have a number for everything and because you have to multiply the numbers you need elementary arithmetic now you understand why there's this mysterious condition on the axiomatic system that you're using being able to handle the elementary arithmetic because this assignation of numbers and the calculation and so on requires this elementary arithmetic and then what you do you use a use a the barber chains all people in his village who do not shave themselves type argument to identify a proposition that is neither true nor false neither provable nor disprovable so you use some reflexive construction you notice I think from the proof that they're over countably many real numbers you know that proof you assume that you're right can write down every number in the real number in the form integer decimal point and then decimal places d1 d2 d3 d4 to the dirt and then you assume that you can number every such expression you sign a number to them but then you actually use the number of the expression to construct a new expression a new real number which you control is not in the previous list of numbers it's kind of reflexive you might want to revisit this proof this of a similar similar reflexive type and here you do the thing you assign to statements girdle numbers and then you produce a statement that uses the girdle number of the very same statement okay and then you arrive at such a contradiction and as you can see we define axiomatic system we defined what it is to be provable and thereby therefore what it means to be disprovable that means it can prove the opposite if you can prove the negation and we define what is consistent so according to our definitions we fully understand this theorem we understand this statement the theorem makes the proof is a different matter okay so at this place I will rest with the development of the language we're going to use to define axiomatic set theory which that we will start next time and we will start by looking at the element symbol which is nothing but a by a predicate of two variables because it takes a variable on the left X element Y a variable on the right was just a matter of notation to write the symbol in the middle rather than writing element brackets X comma Y okay it's just notational convenience and we we very often do this for predicate of two variables that we write the name of the predicate in the middle because it just saves you two brackets and a comma but this will be the elementary predicate of two variables and there is no other in set theory even the equal sign between sets will be defined in terms of the element sign and from this one elementary predicate of two variables which will not be further explained there will be nobody explaining to you in axiomatic set theory what it actually means that X is an element of Y and indeed x and y will both be sets so there's no such hierarchy like you are a set a grown-up set but you're only an element no no sets can be contained in sets and a priori one could even think about the question is a set an element of itself there's no a priori reason why you would exclude this would give you some kind of recursion and you could ask can you construct a set of all the sets that do not contain themselves if you don't like these sets containing themselves you could think well let's contain constrain the set universe to all those sets that do not contain themselves and then you very quickly actually in two lines you prove that this construction will do this next time is not a set the set or the let me call it the collection of all the sets that do not contain themselves you only use this element predicate this is no longer a set as you can prove by asking a question whether that set contains itself or not and that is neither prove nor disprove well both leads to a contradiction so that immediately shows okay so then the eve set theory is tricky and we need an axe system of axioms that regulates our use of the element predicate okay because we know nothing of it we just know there it is and now the axioms give you rules of how to deal with it it's a kind of an operational definition okay you see if it behaves like this or if you use it like this then you get what we can construct sets there are some actions to tell you these and those sets exist for instance there exists an empty set or if you have a set that exists the power set of the set that's the set of all the subsets of the set you have to postulate this by axiom and all the other sets we're actually going to construct from these previous sets well in fact you control that the only set you really need to postulate is the empty set so in principle every set we ever going to talk about is ultimately constructed from the empty set the set that contains the empty set in the set with the element empty set that stuff like this okay but they are actually I think nine axioms we'll see depends on how you write them down the number varies slightly there are about nine axioms that you can orate I think I wrote down that you can write down that regulates set theory and that reproduce the set theory on which all of modern mathematics is built and occasionally so you have an axiom that's called the axiom of choice for instance famously or zones lemma some people call it the axioms of axiom of choice and you wonder well do you really want to have that and why do we need to be so picky about the axioms there we go for instance if you do not postulate the axiom of choice you cannot prove you cannot that every vector space has a basis now this we use very often so you see already in our building down there where we're talking about sets there already there are some screws you have to justify in order to have the whole building stand as we want it to stand okay and there are other examples for that so at least for completeness and that's the purpose of today's lecture on of the next lecture is to really look at the foundations of the subject to have a good and justified justifiably good feeling about the further constructions that are to come see you next time with axioms of set theory thank you