Introduction to Mathematical Logic & Set Theory (Math 125A & 135) Foundations

[00:00:00]welcome everybody this is the introductory video for both math 125 a and 135 so these two courses uh are both logic courses but they are independent of each other they are not they are different topics and they don't need each other they're both mathematical logic and one of them as we're going to see is about the foundations of logic and formal systems and the other one is more about the axioms to develop other mathematics i'll get into that in a second so but they have the very basic ideas is common so that's why i'm doing this joint video so one of the main goals of mathematical logic is to develop the foundations for mathematics there are other goals but we do other things in mathematical logic but one of them is that to develop the foundations for all of mathematics so if you imagine mathematics as a big building that is where things are built on top of each other and you can be editing then logic one of the aspects of logic is to look at the foundations of that what is all these standing on so the first thing we need to look at is a formal system so this will be a place where we can develop mathematics uh in a formal way what are these formal systems uh good for so what do we need them for so what i mentioned before that uh they are gonna give us the foundations for the whole edifice of mathematics so in a way um they tell us that we can be if you're doing something in the formal system we can be sure that uh going to be correct and and there is no subjectivity to it there is no i'm trying to convince this other mathematician about it it's like this is a formal system but that's in theory because in practice it's very hard to actually do approves in the formal system but it's good to know the foundations are there i get back to this thing about doing it in a second um for instance a hundred and maybe 30 40 years ago uh cantor and bernard russell and other people started to find uh paradoxes uh reasonings that were completely solid they looked like reasonable they look like the reason mathematicians were doing at the time and that led to contradictions like for instance the barber paradox um which instead theory becomes um considered a set of all the sets that don't contain themselves i don't know if you heard about this but once mathematicals are becoming more abstract and abstract and people were doing abstract uh proofs then it was easy to fall into the trap of doing something that is uh not allowed or that would lead to a contradiction um so it was good to develop something where we can know that we are standing on on a strong footing um a second um reason that where the promotions are good is that in logic we can study them as mathematical objects themselves because now formal system approve a theorem a construction they become themselves concrete mathematical objects so we can study proofs theorems in a mathematical way so we can use mathematics to study mathematics itself so that's why it's called meta mathematics um and that's where kind of that's how we can prove girls theorem that some things are not true uh for that we need to we need to be able to prove about things being proved or not and a third application is that um computers can play with formal systems that's a more modern thing but it's actually becoming more and more popular so i was saying that uh in practice it's very hard to write a proof in a formal system like when you write a proof you're writing in english and you're just trying to convince a mathematical reader that your argument has no holes and it's like perfect logical and sound but if you want to write the full proof like step by step in a formal system you go crazy um but if you manage to do it and you do it on a computer computer can go and check step by step that every step you did was correct you don't need a human to do that because now it's very formal so so now you have essentially a proof that your proof is 100 correct um and that's actually useful for something so it started to be useful for uh some programs like uh to verify that a program is doing what it's supposed to be doing so to prove that program is doing what it's supposed to do which is sometimes very important if the program is controlling something that is very important like i don't know your heart now uh in the last couple decades people started to actually prove like write down full detailed proofs in a formal system of some well-known theorems mathematics and sometimes these tax tasks are like huge because like for big theorems there are a lot of little things that are not written but if you want to convince the computer that everything is right you need to add every step and now there are programs that help you uh do the still the small steps and so you don't go too crazy you still got a bit crazy i guess but um so right having a formal system allow us to now get computers to help us very fireproofs and maybe even write some to start introducing formal systems one thing we need to think about is okay what is a proof here is a definition a proof is an argument that uses logical steps to show that mathematical statements follow certain assumptions let's deepen into what this actually means there are a few things here are important first what we're talking about proving here are concrete mathematical statements we're not talking about proving an ambiguous statement about the weather we're talking about concrete mathematical statements so we need to be explicit about what we mean by a concrete mathematical statement and for that we need to define a formal language a proof is made out of logical steps we all know in practice when writing a proof we can use any reasoning we like so long as everybody agrees that the steps we are taking are logical but if you want to talk about proofs as concrete objects to be able to prove things about them we need to be explicit about which logical steps we are allowed to use these logical steps are called rules third we need assumptions when you write a proof you always use previous knowledge that previous knowledge usually comes in forms of theorems that were proved before and those theorems use previous knowledge and if you keep on going backwards you will eventually reach statements that are so basic they just cannot prove but they are basic enough that you don't need to prove them those are the axioms more than a hundred years ago this man wanted to build a formal system for all of mathematics where all statements could be proved in a purely formal and in technical way but that i mean in a way that only involves manipulating symbols following certain rules in a purely mechanical way without having to even know what the symbols mean this way you could be sure about something being true or not in a purely mechanical way that nobody could argue with let's see how that worked out at the end so let's see what a formal system is it consists of three things a language set of rules and a list of axioms language to define a language we need symbols they are like the letters of the alphabet and grammatical rules that tell us how to put the symbols together here is a standard list of symbols the first symbols zero one plus times belongs to form what is called a vocabulary and those are variables you can change them for some other symbols if you want to work with something else these ones are good enough the latter ones equality and or not exist for all the variable symbols and the parenthesis are called the logical symbols and they are essentially fixed in all first order logic you can modify them slightly for instance here you can add the implication symbol because you can just define it from the other so you may add it or not but essentially these are the logical symbols okay then we need to put the symbols together and for that we need grammatical rules here's a standard set of rules but don't worry about the details i don't want to get into them right now i just want you to see what they look like essentially when you see a string of symbols you're going to be able to tell if it makes sense or doesn't for instance this one here obviously doesn't make sense while this other one for every x there exists a y such as y plus y equals x or y plus y equals x plus one it's a sequence of symbols that makes sense all right let's go into the rules these are the rules of logical thinking the rules that we use when we write proofs for example there is a rule that says that if you can prove not phi that is the negation of phi where phi is a grammatically correct sequence of symbols and you can prove v or psi then you can prove psi for instance if v was the sentence x equals y and psi was the sentence z equals 1 then this rule will read as follows we express such rules in the following format if you can prove the statements on the top we can produce statements on the bottom here is an example of a full set of rules of first of the logic again don't worry about the details i just wanted to show you what they look like axioms these are the statements that describe the very basic behavior of whatever you're working with numbers sets groups rings what are we working with the axioms don't need to be proved they are used as basic assumptions within our proofs if you're going to use them in our proof they better be true so they're very obviously true and hopefully we'll have enough axioms to derive everything we want i will see this is too much to offer here's an example of a list of axioms these are the annual axioms they are the standard actions to work with when you're working with the natural numbers they start with the very basic properties of 0 one plus and times and then we have the actions for induction which allow you to do proofs by induction there is another list of actions that is used to axiomatize all of mathematics called the zermero franco set theory okay so now we know what a formal system is here come the key points the language is complete so all mathematical statements can be expressed in this language once you get used to working in this language you're going to see that every mathematical statement you want to make you can make it in this formal language using these grammatical rules so that's good all right then the rules they're also complete okay this is not a simple observation like the previous ones there is no reason to believe at first that these few rules are going to be enough to formalize all arguments mathematicians wants to make arguments come in all shapes or forms but surprisingly they are enough this is another ghetto's famous theorems it's called the completeness theorem and it says that if you can prove something you can prove it using only these rules it actually says that if a statement is true in all possible universes then it can be proved using these rules okay there are some subtleties here that i'm leaving for another time the axioms though are not complete and this is what the incompleteness theorem says girl proved both the completeness and incompleteness theories it's not that he couldn't make a piece his mind about completeness or incompleteness it's just that completeness was about the rules and incompleteness was about the axioms okay so the two courses split right here so 125 is going to be about the language part and the rules part of the formal system and uh and also about semantics about the language and probability and other things we're going to prove those completeness theorems that we just mentioned and uh the good old one is not an easy one very competent theorem that's going to be our main theorem at the end of the class um and then 135 is going to be about the axioms part and in that one we're going to develop the axioms for set theory and set theory these are the axioms where all mathematics can be done so these are actions for all the mathematics and they are kind of now widely accepted as the action for mathematics which as we just mentioned they are not complete i mean the area of set theory of logic studies uh theorems and mathematics or statements that are they cannot be proved from the axioms that are beyond these axioms uh but we know where i'm getting to that maybe you're gonna mention a couple of those but uh we're not gonna get into those much we're just gonna go slowly through the actions to understand the whole development of set theory and how it works as a foundation for mathematics and we're going to look at something that follows from this development which is the study of ordinals and cardinals that are very important in set theory okay that's it for today and next time we'll do separate videos one for 125 one for 135 and we'll go into the different topics see you next time