New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Honors Discrete Mathematics

by: Chaya Botsford II

Honors Discrete Mathematics MAD 2104

Chaya Botsford II
GPA 3.65

Jorge Viola-Prioli

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Jorge Viola-Prioli
Class Notes
25 ?




Popular in Course

Popular in Mathematics Discrete

This 8 page Class Notes was uploaded by Chaya Botsford II on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 428 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.

Similar to MAD 2104 at FAU

Popular in Mathematics Discrete


Reviews for Honors Discrete Mathematics


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/12/15
9SETS A set is a collection of objects called its elements and usually denoted by means of curly brackets Hence abc denotes the set whose elements are a b and c CAUTION The order in which the elements are written is irrelevant but the elements must be different When the set has in nitely many elements the above notation becomes impractical so we resort to the setbuilder notation This is manufactured by writing Adummy variable condition satis ed by the variable The semicolon here means quotsuch that J Viola Prioli For instance A x x E Z and 2x is read quotthe set of integers divisible by 2 That is A is the set of even numbers Here of course x is our dummy variable and could be replaced by a different symbol or letter Likewise the set of odd integers between 10 and 100 can be denoted by 2n1 E Z 4 lt n lt 50 or equivalently as 2n1 n E Z and 4 lt n lt 50 The empty set Q is the set with no elements A set builder notation for the empty set is Q x EZ x x Two sets are equal when they have the same elements For instance although with the tools at our disposal right now is not evident the sets x E Z 6x and x E Z 2x and 3x are equal DEFINITION A is a subset of B written A Q B if every element of A is an element of B Therefore to prove that A Q B one must show that if a E A then a E B J Viola Prioli Equivalent formulations for A Q B are A is contained in B and also B contains A Please notice the distinction between quotbelongs to and quotcontained in The former applies to elements in a set The latter refers to a set being a subset ofanother The template to prove the equality of two sets follows to prove that AB we must show that A Q B and also B Q A TIP The basic step in dealing with sets is making sure to understand and list them if possible what the elements are The elements of a set can be of different nature Observe the following examples J Viola Prioli a A 1 5 has three elements b B 1 5 2 6 is a set with three elements which are the numbers 1 and 6 and the set 5 2 We emphasize that B does not have four elements c C 2 Q has two elements the number 2 and the empty set cl D Q Q has two elements the empty set and the set whose element is the empty set e A 1 1 3 We conclude that 3 i A 1 3 E A 1 3 is not a subset of A f A 1 2 13 has three elements 1 2 and 13 B 1 2 v w has four elements Is A Q B J Viola Prioli To say that A is not a subset of B denoted by A Z B means that there exists an element of a that is not an element of B g Let us prove that ifA n E N last digit of n is a zero and B n E N 5n thenAQB To that end let a E A Therefore a 10 k for some integer k Since 10 2XS a 5 2k so a is a multiple of 5Thus a E B Observe that the empty set is a subset of any given set Also for any set A we have A Q A NOTATION In what follows A denotes the number of elements of the set A J Viola Prioli We are interested in nding the number of subsets of a set with n elements For instance if A has three elements we may assume A abc and proceed to list of its subsets beginning with the empty set then with the subsets of 1 element and so on We have Q a b c a b a c b c a b cA There are therefore 8 subsets Notice that 8 23 What we just illustrated for n 3 is generalized in our next THEOREM If A has n elements then A has exactly 2n subsets Observe that if n O A is the empty set which has only one subet Q itself so the formula is valid for n 0 We may assume n gt O and since we are interested only in counting we may assume that A 1 2 3 n without loss of generality Since a subset is totally identi ed by knowing each of its elements we can prepare n blocks which we align orderly Then we ll the jth block with a O ifj is not in the subset and with 1 ifj is an element of the subset That way each subset is identi ed with a binary string of length n Since there are 2n such binary strings as we proved in a previous section the conclusion follows J Viola Prioli For instance if n5 the string 0 O 1 1 0 corresponds to the subset 3 4 whereas 0 O O O 0 corresponds to the empty set and 1 1 1 1 1 identi es the set A 1 2 3 4 5 NOTATION The set of all subsets of A is denoted by 2 and called the power set of A We emphasize that 2A is not a number but iust a symbol to denote a set formed as explained above Thus ifA a b then 2A Q a b a b Of course the theorem above shows that the set 2A has 2IAI elements Notice how suggestive the notation chosen 2 is J Viola Prioli PROBLEM Assume A 20 Compute the number of subsets of A with at most 18 elements Solution There are 220 subsets of A Only one of them has 20 elements and there are 20 subsets with 19 elements Do you see why Can you list them Hence we have so far 21 subsets found These 21 subsets are precisely those we are not interested in Hence the answer is 220 21 See remarks Section 10 in our Syllabus for some additional problems with solutions J Viola Prioli


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Amaris Trozzo George Washington University

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

Bentley McCaw University of Florida

"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!"

Parker Thompson 500 Startups

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

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.