FOUNDATIONS OF MATH
FOUNDATIONS OF MATH MATH 220
Popular in Course
Popular in Mathematics (M)
This 4 page Class Notes was uploaded by Evert Christiansen on Wednesday October 21, 2015. The Class Notes belongs to MATH 220 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/226033/math-220-texas-a-m-university in Mathematics (M) at Texas A&M University.
Reviews for FOUNDATIONS OF MATH
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/21/15
Math 220 Axioms for set theory November 14 2003 Notes on the Zermelo aenkel axioms for set theory Russell7s paradox shows that one cannot talk about the set of all sets77 with out running into a contradiction In order to have a self consistent language for talking about sets one needs some rules that say what sets exist and what sentences are legitimate descriptions of sets The most commonly used system of axioms for set theory is called ZFC77 in honor of Ernst Friedrich Ferdinand Zermelo 187171953 and Adolf Abra ham Halevi Fraenkel 189171965 The letter C77 refers to the Axiom of Choice discussed below Although there is no universal agreement on the order of the axioms the exact wording of the axioms or even how many axioms there are most mathematicians will accept the following list 1 Axiom of extension Two sets are equal if and only if they have the same elements in symbols VAVB A B ltgt Vzz e A ltgt z e B Although Axiom 1 describes when two sets are equal the axiom does not guarantee that any sets exist conceivably the whole theory could be vacuous The next axiom lls this vacuum by stating that at least one set does exist 2 Axiom of the empty set There exists a set with no elements in symbols HAVx x A By Axiom 1 the empty set denoted Q is unique The next three axioms describe ways to build new sets from existing ones 3 Axiom of unordered pairs Sets Ly exist in symbols VxVy HAVz E A ltgt s V 2 Axiom 3 also implies the existence of singleton sets the set is equal to the unordered pair L A standard way to represent the ordered pair x y is the set xy which exists by repeated application of Axiom 3 Discrete Mathematics Page 1 Dr Boas Math 220 Axioms for set theory November 147 2003 4 Axiom of unions Unions exist In the following symbolic form of the axiom7 think of A as a set of sets and B as the union of those sets VAHBV E B ltgt 300 E A x E Finite sets like Luz can be constructed by Axioms 3 and 4 5 Axiom of the power set Power sets exist In symbols7 VA3Bz e B ltgt x g A Here the statement x Q A77 is a shorthand expression for the statement W 11 E 96 1 6 AD 6 Axiom of in nity An in nite set exists One way to write this statement in symbols is 3A 6 A AVx E A gt U E An in nite set of the indicated form contains a copy of the natural num bers7 modeled as follows rst 0 corresponds to the empty set a then 1 cor responds to 7 then 2 corresponds to 7 and so on One would like to conclude that the set of natural numbers exists7 since there is a rule for identifying the natural numbers as a subset of a previously constructed set To justify this conclusion7 one has to know that a rule for selecting a subset necessarily de nes a set Hence the next axiom is needed 7 Axiom of selection If P is an open sentence7 and A is a set7 then the expression 2 E A l Pz de nes a set the subset of elements of A for which the property P holds A key point is that the set being de ned is required to be a subset of some previously given set A This requirement rules out 2 l z z Russell7s paradoxical set Axiom 7 is actually an axiom schema77 representing an in nite collection of axioms7 one for each statement P The next axiom too is an axiom schema Discrete Mathematics Page 2 Dr Boas Math 220 Axioms for set theory November 14 2003 8 Axiom of replacement The image of a set under a function is again a set In other words if A and B are sets and f A a B is a function with domain A and codomain B then the image fA is a set A function f may be described in set theoretic terms as the set of ordered pairs ab E A gtlt B fa 9 Axiom of regularity Every non empty set has an element that is disjoint from the set in symbols VAA Q gt 3xx E A m A Another name for this axiom is the axiom of foundation In contrast to most of the other axioms Axiom 9 does not guarantee the existence of any sets Instead the axiom rules out the existence of certain pathological sets In particular Axiom 9 implies that no set can be an element of itself this is one of the exercises below 10 Axiom of Choice Given any in nite collection of non empty sets it is possible to choose si multaneously one element from each set More precisely if f is a function whose domain is a non empty set A and whose codomain is a set E whose elements are non empty sets then there is a choice function77 g with the property that g E f for each x in A There are many equivalent formulations of the Axiom of Choice One of them is that the Cartesian product of an in nite number of non empty sets exists and is a non empty set In 1940 Kurt Godel proved that the Axiom of Choice is consistent with Axioms 179 assuming that those axioms themselves are self consistent On the other hand in 1963 Paul J Cohen showed that the negation of the Axiom of Choice is consistent with Axioms 179 again assuming that those axioms themselves are self consistent In other words the Axiom of Choice is independent of Axioms 179 Thus just as one can do geometry either with the Parallel Postulate or without the Parallel Postulate one can do set theory either with the Axiom of Choice or without the Axiom of Choice Most mathematicians accept Discrete Mathematics Page 3 Dr Boas Math 220 Axioms for set theory November 14 2003 the Axiom of Choice because that axiom appears to be a natural and useful property On the other hand the Axiom of Choice does have some surprising and counter intuitive consequences For example the Axiom of Choice implies that every non empty set admits a well ordering Also the Axiom of Choice implies the Banach Tarski paradox Consequently a few mathematicians prefer to work in the system ZF consisting of Axioms 179 without the Axiom of Choice For further reading 0 N Ya Vilenkin Stories about Sets Academic Press 1968 QA 248 V513 Suitable for bed time reading this little book is directed to anybody beginning with high school juniors and seniors77 according to the Foreword 0 Paul R Halmos Naive Set Theory Van Nostrand 1960 QA 248 H26 This slim volume is a very readable presentation of the elements of set theory by a master of mathematical exposition Exercises a Use Axiom 9 the axiom of regularity to prove that there is no set A for which A E A Hint if there were such a set A what would Axiom 9 say about the singleton set A b The description of Axiom 8 above uses the notion of the Cartesian prod uct of two sets A and B Use Axioms 177 to prove that the Cartesian product A gtlt B does exist as a set Hint the key point is to show that a suitable set exists from which A gtlt B can be selected Discrete Mathematics Page 4 Dr Boas
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'