### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Discrete Mathematical Structures MATH 2513

OU

GPA 3.82

### View Full Document

## 19

## 0

## 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.

## Popular in Mathematics (M)

## Reviews for Discrete Mathematical Structures

### 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/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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.