SET THEORY + LOGIC
SET THEORY + LOGIC MATH 340
Popular in Course
Popular in Mathematics (M)
This 3 page Class Notes was uploaded by Antone Homenick on Friday October 30, 2015. The Class Notes belongs to MATH 340 at SUNY Potsdam taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/232395/math-340-suny-potsdam in Mathematics (M) at SUNY Potsdam.
Reviews for SET THEORY + LOGIC
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/30/15
Math 340 Set Theory and Logic De nitions These are almost all of the de nitions used in the course Math 340 Set Theory and Logic with jason howald Fall 2007 You will be required to gradually memorize this entire document Don7t panic 7 its easier than it sounds ltalized comments need not be memorized 1 A mathematical theory is called universal if it is theoretically possible to understand all other mathematical questions in terms of that theory Finding a universal mathematical theory was a great achievement of early 20th century mathematics Set theory is universal in the sense that all mathematical ideas can be boiled down to set theory To express the universality of the theory we must explain how things that do not look like sets such as numbers functions and properties can be understood as sets There are several alternative universal theories 2 A set is a collection grouping or assembly of different things A set cannot contain multiple copies of the same thing In a perfectly rigorous set theoretical system the word set should be formally unde ned but I don t want to torture you with subtleties Besides even when we leave terms formally unde ned we all secretly know what they mean anyway 3 We write x E y to indicate that y is a set and x is one of its elements 4 For sets A and B we write A B to indicate that A and B have exactly the same elements In other words a set is completely determined by what it contains Unlike say a box which has other properties in and of itself such as size and color 5 For a set A its cardinality written lAl is how many elements it has This de nition isn t really fair A is an in nite set For that case much more work is needed to understand cardinality 6 We write e1 1 l 1 en called list notation to indicate the set containing just those things listed 7 We write variable things conditions called set builder notation to indicate all possible indicated things for which the indicated conditions are true 8 We write Z for the set of all integers round numbers including zero and the negatives 9 We write o for the set 01 2 l l of all integers including zero but excluding negatives 10 We write N for the set 012l l l as another name for on Whether 0 is should be 9 an element of N is debated This question will not be a concern to us but see Dr Miller for details if you wish 11 We write Q for the set of all rational numbers each of which can be written 11 for integers p and q 12 We write R for the set of all real numbers 13 For two sets A and B their Cartesian product written A X B is the set of all ordered pairs ab a E Ab E B Cartesian is an adjectival form of the last name of Rene Descartes credited with the invention of the xy coordinate system which can be understood as R X R 14 For two sets A and B the union of A and B written AUB is the set x x E A or x E B That is all the elements of A with all the elements of B put together in one big setl Mnemonics the symbol U looks like a U for union unite unify etc In collective bargaining a union is a large collective including people from di erent organizations 15 For two sets A and B the intersection of A and B written A N B is the set x x E A and x E B That is the elements common to both sets I don t know of any mnemonics for the symbol Intersect is Latin inter between secare to cut 16 For two sets A and B the set difference written A B or A 7 B and pronounced A without B or A minus B is the set x x E A and x B That is the elements in A but not El 17 For a set A the complement of A written A is the set of everything not in Al What everything Including the mysterious motives of cats This notation is used only when there is enough context to determine what kinds of things we re talking about limiting the scope of everything appropriately 18 For two sets A and B we say A is a subset of B and write A Q B to mean Vx E A x 6 Bl Mathematicians seriously disagree about whether A C B should allow for the possibility that A B That is someone tells you that A C B can you deduce that A f B 9 Some hold that by analogy with x lt y and x S y A C B should not allow equality and the symbol A Q B should be used equality is allowed Others prefer to write A C B even in the case of equality and reserve A g B to communicate that the sets are not equal I was trained in the latter style but the text uses the former style I am attempting to change my habits and always write Q for subsets but I should write A C B it is more likely that Iforgot than that I really meant A f B 19 20 21 22 23 24 25 26 27 28 29 30 31 32 A relation R on two sets A and B is a subset of A X Bi If D and R are sets a function f z D A R is a relation on D and R with the property that VI 6 D Big E R z y E or any given I E we write for that unique y for which zy E fiThis de nition of a function makes a function a special kind of set instead of a primary concept Other systems make the function concept primary but we have the universality of set theory in mind so we have to understand everything as a set We are rarely so committed to this functionas a set business that we will write peculiarities like f N g For a function f z D A R the domain of f is the set Di For a function f z D A R the codomain of f is the set R A valid function de nition is a speci cation of the form Let f z D A R via H i providing in order the function symbol the domain D the range R and the action on a generic element It For a function f z D A R the image of f is the set z E D which need not be the entire set Rt For a function f z D A R the range of f is another word for the image of Although the meanings of codomain and image are xed and agreed upon the meaning of range is in flux between its older usage codomain and its newer usage image Mathematicians use context to gure out what is intended but learners should ask if unsure For two functions f z A A B and g z B A C their composition written g o f is the function agfa a E A with domain A and codomain Ci Note For a E A g o a gfa 6 C If the functions are processes make a bigger better process by doing one then the other The symbol a can be pronounced following to keep track of which process is rst It can also be pronounced composed with If the codomain of one doesn t match the domain of the neat composition is impossible A function f z A A B is called injective when Vzy E A if then I y In other words no two domain elements go to the same range elementi Also called onetoone but this has deceptive connotations so I prefer injective A function f z A A B is called surjective when Vy E B Hz 6 A y In other words everything in B is the image of something in Al Also called onto A function f z A A B is called bijective if it is both injective and surjectivei A bijection creates a one to one correspondence between A and Bi Given a function f z A A B its inverse written f l is a function from B to A so that for all b E B ff 1b b and for all a E A f 1fa at Not all functions have inverses but if there is an inverse there is only one If there is an inverse for f then f is bijective This is usually the best way to prove that a function is bijective the superscript 1 is specialized notation and is not an exponent There are no reciprocals here Given a function f z A A B and a subset Y C B the preimage of Y written f 1Y is the set I E A E Y which is a subset of Al Notice that the superscript 1 is used in a di erent way here and does not mean function inverse Given a function f z A A B and a subset X C A the image of X written fX is the set z E X which is a subset ofBi In the bizarre case that X might be both a subset ofA and an element ofA eg A 12 3 1 2 this notation is ambiguous and must be avoided Math 340 Set Theory and Logic De nitions These are almost all of the de nitions used in the course Math 340 Set Theory and Logic with jason howald Fall 2007 You will be required to gradually memorize this entire document Don7t panic 7 its easier than it sounds ltalized comments need not be memorized 1 A mathematical theory is called universal if 2 A set is 3 We write I E y to indicate 4 For sets A and B we write A B to indicate 5 For a set A its cardinality written lAl is 6 We write eh i l l en called list notation to indicate 7 We write variable things conditions called set builder notation to indicate 8 We write Z for 9 We write a for 10 We write N for 11 We write Q for 12 We write R for 13 For two sets A and B the union of A and B written A U B is 14 For two sets A and B the intersection of A and B written A N B is 15 For two sets A and B the set difference written AB or A 7 B and pronounced A without B or A minus B77 is 16 For a set A the complement of A written A is 17 For two sets A and B we say A is a subset of B and write A Q B to mean
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'