ZF and axiomatic set theory

0:04 hi in the previous video we have introduced first of logic in this video we will use first order logic to formulate the axioms of tamil frenkel set theory i assume that you are familiar with naive set theory but with first order logic for the first time we can write down what the axioms of set theory really are so that we can replace intuitive arguments about sets by arguments that just use these actions first we have to fix the signature the signature of set theory is remarkably simple we just need a single binary relation symbol used in infix notation namely for the relation that we intend to use for a is an element of b

0:49 so with our first order formulas and sentences we will be talking about structures whose elements we imagine as sets and now we can start writing down the properties that we expect from this relation for a better readability i introduce some intuitive and well-known shortcuts for example we write b subset c for the first order formula that says for all a if a is an element of b then a is an element of c so all elements of b are elements of c i will now present the tsar milo frankel axions abbreviated by zf so this is a theory in the signature that i just presented the first axiom is called extensionality

1:38 it says that if two sets have the same elements then they are equal to translate this into logic we use the universal quantifier we say for all x and y if x is a subset of y and y is a subset of x then x and y are equal recall that first order logic allows the equality symbol no matter what the signature is the second axiom is called empty set there exists a set that has no elements because of extensionality this set which has no elements is unique and we introduced a well-known symbol for the empty set to denote this element the third axiom of set f is the pairing axiom for all sets

2:24 a b there is a set c which has exactly the elements a and b written in first order logic this can be expressed by saying that for all x x is an element of c if and only if x equals a or x equals b again extensionality implies that given a and b this set c is unique and we use the shortcut curly brackets a b to denote this set most of the remaining axioms also look like this they state that certain sets must exist fourth axiom of set f is the union axiom it states that for every set a there

3:10 exists a set b that contains precisely the elements of the elements of a in first order logic this can be expressed by the formula that says that x is an element of b if there is an element y of a such that x is an element of y by extensionality this is set b only depends on a and is denoted by a big union symbol in front of a action number five is the power set axiom it states that for every set a there exists a set b that contains precisely the subsets of a so for every x x is an element of b if and only if x is a subset of a

3:56 this set b is denoted by curly p of a for power set axiom 6 is the infinity axiom we would like to assert the existence of infinite sets one way to do this is to claim that there exists a set a which contains the empty set so it's not empty and which is closed under forming the successor the successor of x is the union of x with the set that just contains x union is something that you surely know from naive set theory of course but we have not yet defined this notation in our axiomatic set theory a union b is another way of writing big cup applied

4:42 to the two element set then contains a and b so in our case the two element set that contains x and the union of x in first of the logic the infinity axiom reads as follows there exists a set a containing the empty set such that for every element of a there is also the successor of that element in the set a axiom number seven is called comprehension and it is actually not just one sentence but infinitely many this is where the hand waving starts even for the more ambitious naive set theory introductions in the first year of your mathematics or computer science curriculum

5:27 the reason is that already for stating this axiom you have to talk about first order formulas for every formula phi over the signature of set theory we have the following action for all y 0 y 1 up to y m there exists a z that contains precisely those elements of y 0 that satisfy phi again this set z is unique by x tangentiality and we have the following notation for z which you all know and you use every day we write curly brackets and then x in y zero vertical line and then comes the condition that x must satisfy in order

6:13 to be an element of that set in our case it must satisfy the formula phi these comprehension axioms are quite strong and together with the previous axioms we can deduce many many statements in mathematics just from these axioms the axioms we have seen so far are called charmelo set theory abbreviated just by zed let's have a look at an example i claim that zed implies the following sentence there does not exist an a such that all z are in a in other words there is no set containing all sets this might be counter intuitive to some

6:58 of you and this is why it is called an antinomi namely russell's antinomy so let's prove this from zed from zermelo said theory suppose that u is a structure over the signature of set theory that satisfies this sentence so there is an element a of the structure u that contains all other elements of u then we can apply comprehension to the first order formula x does not contain x so there is a set b that contains precisely those elements x of a that satisfy x is not in x

7:44 and now we might ask the question is b an element of b well b is an element of b only if b is in a well this is always satisfied since a contains all sets so we can forget about this condition we only have to check the condition after the vertical line so we get that b is in b if and only if b is not in b this is the condition after the vertical line and this is an obvious contradiction so proof finished proof by contradiction finished so you think oh cool that seems just like the right thing to work with

8:30 and this is what camilo also thought until frankel came in fact in 1922 two mathematicians namely frankly and skolem independently from each other discovered that cermelo said theory is not strong enough to cover all statements that we naively would accept as valid axions the reason is that zed does not imply the existence of some sets whose existence we would like to assume i will give an example let zero be the natural numbers that is the set n that contains exactly the element zero one two and so on we will later see how to code the natural numbers in the middle of set theory let z one

9:16 be the power set of n and let's set to be the power set of the power set of n and in general let is that i plus 1 be the power set of set i all these sets exist in semi low set theory no problem but how about the set that contains all of those said i it turns out that said does not imply the existence of this set this is what frankl saw in 1922 and what he then fixed by introducing an axiom that is stronger than comprehension this will be axiom number eight and comes

10:02 after the break to define the remaining actions of zf we need some fundamental concepts an ordered pair a b is the set that has just two elements namely the set that just contains a and the set that contains exactly a and b this set

10:49 surely exists by our axioms namely by the pairing action a binary relation is a set of ordered pairs a function is a relation f such that if x and y is in f and x and z is in f then y must be equal to z instead of x and y or the pair x and y is in f we write f of x equals y all of these definitions you surely know but you might now see them in a different light knowing first order logic the domain of a function f is the set of all x such that there exists a y with f x

11:36 equals y this expression is not covered by the comprehension axiom the reason is that x is not guarded by sunset in our notation for comprehension x must be an element of some set that we already know to exist but in this case here it is easy because we we know that x will be an element of the union of the union of f so by comprehension we can be sure that the set i wrote down the domain of f really exists similarly we define the image of f as the set of all y such that there exists an x with f of x equals y if the image of f is contained in some set b we use the well-known notation f colon

12:24 domain f to b in this notation b can be larger than the image of f now comes axiom eight the replacement axiom actually it is again infinitely many axioms so it should rather be called an axiom scheme let me first give you the idea note that if u satisfies tamel's axioms and s is a subset of the domain of u in the naive sense then there might not be an element a in u that contains exactly the elements of s so s is only a set on the meta level not an element of u likewise if f is a function from u to u in the

13:09 naive sense then it might not be a function in the sense we just defined and in particular the image of a set d under f might not be an element of u note that if f would be a set then the image of d under f is also a set again by comprehension if we would add the existence of the image of d under f for functions f in the naive sense we would create a contradiction in our axiom system similar to russell's antinomy so the idea of the replacement axiom is that we only add the existence of the image of d under f for definable functions

13:55 in first of the logic this can be formulated as follows for every first order formula phi in the signature of set theory with three variables v1 up to vn x and y we add the following axiom we say that if phi defines a function which can be expressed in first order logic by saying that for every x there is at most one y that satisfies phi then there exists an element u which is the image of d under the function defined by phi let me first write this as a first order formula and then explain the formula so in this formula we specify exactly what the elements of this set

14:41 u are it's precisely those elements y such that there exists an x in d which is mapped to y under the function defined by phi finally there is an axiom which is perhaps the least important called the axiom of foundation perhaps for aesthetic reasons we would like to exclude that sets can be their own element and we even formulate something stronger namely every non-empty set x has an element y such that the intersection of x and y is empty in other words every set x has an element which is minimal with respect to the element relation

15:28 so we don't want infinite descending chains with respect to the element relation in this way of course we also prevent that there is a set with a element a because that would also give an infinite descending chain with respect to the element relation so what i have drawn here on the right in red is not possible if we assume foundation the axioms one up to nine is referred to as tarmelo frankelset theory short zf inside theory we distinguish between sets and classes this is motivated by the desire to speak for example about the class of all finite graphs there is no set of all finite graphs

16:16 otherwise we would derive a contradiction similarly as in the proof of russell's antinomy the reason is simply that the vertices of a graph can be arbitrary sets so a set of all graphs would give you the power to talk about the set of all sets and then we can reproduce the contradiction from russell's antinomy it is possible to give an extrematic and clean treatment of the distinction between sets and classes in zf let u be a model of zf we now consider the expansion of u by new constant symbols for each element of u we introduce a new constant symbol that denotes that element we write u subscript u for the expanded structure now

17:03 the subsets of u that are definable over u subscript subscript u are called classes note that every set a so every element of u gives rise to a class c a namely the class defined by the formula x is an element of a [Music] your hands around my still killing me