DARTMOUTH COSC 030 - 01sets (10 pages)

Previewing pages 1, 2, 3 of 10 page document
View Full Document

01sets

Previewing pages 1, 2, 3 of actual document.

View Full Document
View Full Document

01sets

75 views

Pages:
10
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Discrete Math Computer Sci Documents
• 4 pages

• 4 pages

• 5 pages

• 3 pages

• 6 pages

• 2 pages

• 9 pages

• 5 pages

Unformatted text preview:

CS 30 Discrete Mathematics Professor Teaching Assistants Sagar Kale Head TA Yining Chen Chief grader Richard Rick Dionne Ninja Nan Hu Amit Chakrabarti Ninja Hang Christine Qi Ninja Shikhin Sethi Ninja The Language of Mathematics Math is not just a tool it is a way of communicating ideas It is a language We must Jirst become comfortable with it The building blocks of this language Sets Integers More general numbers rational real complex Functions Logic More advanced math sets are the only building blocks we need all else can be built from sets http www cs dartmouth edu cs30 Review of Sets A set is a collection of distinct objects These objects elements or members of the set If x is an element of the set S we write x S read x belongs to S or x is in S Example the set of fruits I like F apple banana fig mango pear apple is an element of F so apple F apricot is not so apricot F Review of Sets II An element either belongs to a set or does not No such thing as partially belonging to a set No such thing as number of copies of an element in a set Example set of letters in DARTMOUTH COLLEGE D A R T M O U H C L E G A C D E G H L M O R T U Finite and Infinite Sets The sets seen so far are all Jinite sets Number of elements cardinality of the set Notation S cardinality of set S E g F apple banana fig mango pear results in F 5 Not all sets are Jinite E g the set of all even natural numbers E 2 4 6 8 10 12 is an inJinite set Other inJinite sets N 1 2 3 4 the set of natural numbers Z 3 2 1 0 1 2 3 the set of integers Q 0 1 1 2 2 1 3 2 3 9 5 22 7 rational numbers R the set of real numbers includes 2 etc Describing a Set There are two main ways 1 Roster notation list out all the elements F apple banana fig mango pear 2 Set builder notation describe the property of a generic element of the set and write x some property of x F x x is a fruit and I like x Read F is the set of all x such that x is a fruit and I like x Other Interesting Possibilities A set with just one element is called a singleton set E g 5 Note that the set 5 is not the same as the integer 5 A set may have no elements at all This very special set is called the empty set and denoted or The elements of a set might themselves be sets e g A H I M O T U V W X Y B C D E H I K O X H I O X Quick quiz what is the cardinality of the above set Answer 3 Describing Large or Infinite Sets For informal descriptions using an ellipsis is Jine e g 2 4 6 8 or 0 1 2 99 But in formal mathematical writing such as in this course you should use set builder notation This avoids ambiguity e g when you see 1 3 5 7 is it 1 3 5 7 9 11 13 15 17 x x is an odd positive integer 1 3 5 7 11 13 17 19 23 x x is an odd prime number 1 3 5 7 11 13 15 17 21 23 25 27 y y is an odd number that does not end in 9 Depicting Sets Venn Diagrams 11 51 21 121 201 81 A Z C 25 11 B 36 100 51 76 256 21 121 201 81 A 6 Z C 25 49 1 Operations on Sets Union 49 1 B 36 100 76 256 6 606 606 A 1 11 21 51 81 121 201 B 6 36 76 256 606 C 1 25 36 49 81 100 121 256 Z set of all integers A C 1 11 21 25 36 49 51 81 100 121 201 256 S T x either x S or x T Operations on Sets Intersection Disjoint Sets 11 51 A 21 121 201 81 100 Z C 25 11 49 1 B 36 76 256 6 606 A C 1 81 121 S T x x S and x T 51 A 21 121 201 81 100 Z C 25 49 1 B 36 76 256 6 606 Two sets with no elements in common e g A B above Mathematically S and T are disjoint if S T Subsets Basic Facts about Subsets If a set A lies completely within a set B then we say that A is a subset of B We write A B We will use A B to mean A B and A B For any set A we have A A If A B and B A then A B Mathematically A B means that every element of A is also an element of B In other words if x A then x B Venn diagram blob for A sits inside blob for B For any set A we have A Quick quiz are there any subset relationships between A A B and A B A A B A B A Operations on Sets Difference 11 51 A 21 121 201 81 100 Operations on Sets Complement 11 B 36 76 256 6 606 A C 11 21 51 201 S T x x S and x T 51 A 21 121 201 81 100 Z C 25 49 1 Why does this make logical sense DeJinition says if x then x A but is the empty set so we can never have x We ll revisit this issue when we study logic For now think in terms of Venn diagrams Z C 25 In fact this is the only rigorous way to prove that two sets A and B are equal Break your proof into two parts First prove A B Then prove B A 49 1 B 36 76 256 6 606 A complement all integers except those in A x x Z and x A More Facts about Sets For any two sets A and B A B A The sets B and A B are disjoint If A B then A B A Many interesting distributive laws e g A B C A B A C A B C A C B C But beware A B C A C B C Cartesian Product A more sophisticated operation on sets produces a set of ordered pairs a b A B a b a A and b B black red table black pen black hair black table red pen red hair red table pen hair e g if A table pen hair B red black then A B table red table black pen red pen black hair black hair black Set versus Ordered Pair What is the …

View Full Document

Unlocking...