Discrete Mathematical Structures
Discrete Mathematical Structures MATH 2513
Popular in Course
Popular in Mathematics (M)
This 2 page Class Notes was uploaded by Mason Larson DDS on Monday October 26, 2015. The Class Notes belongs to MATH 2513 at University of Oklahoma taught by Noel Brady in Fall. Since its upload, it has received 19 views. For similar materials see /class/229292/math-2513-university-of-oklahoma in Mathematics (M) at University of Oklahoma.
Reviews for Discrete Mathematical Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/26/15
MATH 2513 001 1 to DJ F m0 1 00 to H OJ Discrete Mathematics Fall 2005 Cardinality of Infinite Sets De nition Two sets A and B have the same cardinality7 denoted by lAl lBl7 if there exists a bijection f A a B This is the one cow one sheep de nition of cardinality The cardinality of a set A is less than or equal to the cardinality of a set B7 denoted by lAl lBl7 if there exists an injection 1 A a B De nition A set is said to be countably in nite if it has the same cardinality as the positive integers Zi A set is said to be countable if it is nite7 or countably in nite Examples The following sets are all countably in nite the set of even integers7 the set of odd integers7 the set of all integers7 ZJr x Z4 7 Z x Z7 Z x Z x Z7 an n fold cartesian product Z x x Z7 Examples Show that if A and B are disjoint7 countably in nite sets7 then A U B is also countably in nite Show that the same result holds if A and B are not necessarily disjoint Show that if A17 WA are n mutually disjoint7 countably in nite sets7 then A1 U U An is also countably in nite Show that the same result holds without the disjointness assumption Show that if AnheZJr is a countable collection of countable sets7 then the union 00 U An n1 is countable Theorem If lAl lBl7 and B is countable7 then A is also countable Examples The following sets of real numbers all have the same cardinality R 07 07 WQ 7r27 07707 071 175 for any a lt 57 laybt all laybl Theorem baby Cantor The set 01 is not countable In fact7 there is no surjective map 2 a 01 De nition An in nite set which is not countable is said to be uncountably in nite The set R is uncountably in nite Examples Show that the set of all irrational numbers is uncountably in nite Hint points 37 47 6 and 7 all combine to give an argument by contradiction De niton A real number r is called algebraic if it is the solution of a polynomial with integer coe icients Example Show that V is an algebraic number Show that every rational number is algebraic Show that the set of all algebraic numbers is countably in nite Therefore7 its compliment the set of transcendental numbers is uncountably in nite Theorem grown up Cantor For any set A we have lAl l73Al but lAl 7 Corollary There is an in nite hierarchy of cardinalities of in nite sets Wl lt WZW lt WWTM lt 14 Theorem SchroderBernstein Let A and B be sets lf W S 131 and 131 S W then 1A1 15 Example Trace through the proof of Schroder Bernstein above in the case that A B 2 and the two injective maps are n gt gt 2n and n gt gt 3n 16 Theorem There is an injective map 73Z a 07 1 Theorem There is an injective map 07 1 a PZ H 1 Corollary 73Z has the same cardinality as R This cardinality is called the power of the continuum It is an axiom of the foundations of math ematics which is known to be independent of the remaining axioms7 that there are no sets with cardinality strictly between 2 and R This axiom is known as the continuum hypothesis 18 Exercise Show that R2 and R have the same cardinality Hint We already know that there are many injective maps R a R2 If only we could nd an injective map going the other direction7 we d be done by Schroder Bernstein 19 Weird scenes inside the goldmineThe Cantor Set Let A0 017 and for each n 2 1 de ne 00 13k 23k AnAn71Ult 3n 7 3n h0 and nally de ne the Cantor set7 C7 to be the intersection C it n6Z a Show that C is uncountable b Show that C has no lengthl Hint C is a subset of each An Show that the total length of a given An is 23 Remarks The generalized continuum hypothesis states that there are no sets with cardinality strictly between any of the sets listed in Corollary 13 above It is independent of the axioms of set theory The result of Exercise 18 is remarkable It is hard to imagine a bijective map from R to R2 even a surjectiue map seems unreasonable There is a beautiful map due to Peano called the Peano curve which is a continuous map with domain the interval 07 1 and range the 2 dimensional square 01 If this sounds way out there but still strangely compelling7 you might want to consider taking a Topology or an Analysis course In these courses7 you would also learn lots more about the Cantor set