DOC PREVIEW
Berkeley COMPSCI 70 - Lecture Notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 70 Discrete Mathematics for CSFall 2006 Papadimit rio u & Vazirani Lecture 1Introduction to SetsA set is a well defined collection of objects considered as a whole. These objects are called elements ormembers of a set, and they can be anything, including numbers, letters, people, cities, and even other sets.By convention, sets are usually denoted by capital letters and can be described or defined by listing itselements and surrounding the list by curly braces. For example, we can describe the set A to be the setwhose members are the first five prime numbers, or we can explicitly write: A = {2, 3, 5, 7, 11}. If x is anelement of A, we write x ∈ A. Similarly, if y is not an element of A, then we write y 6∈ A. Two sets A and Bare said to be equal, written as A = B, if they have the same elements. The order and repetition of elementsdo not matter, so {red, white, blue} = {blue, white, red} = {red, white, white, blue}. Sometimes, morecomplicated sets can be defined by using a different notation. For example, the set of all rational numbersdenoted by Q can be written as: {ab| a, b are integers, b 6= 0}. In English, this is read as “the set of allfractions such that the numerator is an integer and the denominator is a non-zero integer.”CardinalityWe can also talk about the size of a set, or its cardinality. If A = {1,2,3,4}, then the cardinality of A, denotedby |A|, is 4. It is possible for the cardinality of a set to be 0. This set is called the empty set, denoted by thesymbol /0. A set can also have an infinite number of elements, such as the set of all integers, prime numbers,or odd numbers.Subsets and Proper SubsetsIf every element of a set A is also in a set B, then we say that A is a subset of B, written A ⊆ B, or Ais contained in B. We can also write B ⊇ A, meaning that B is a superset of A, or B contains A. A propersubset is a set A that is strictly contained in B, written as A ⊂ B, meaning that A excludes at least one elementof B. For example, consider the set B = {1, 2, 3, 4, 5}. Then {1, 2, 3} is both a subset and a proper subsetof B, while {1, 2, 3, 4, 5} is a subset but not a proper subset of B. Here are a few basic properties regardingsubsets:• The empty set is a proper subset of any nonempty set A: /0 ⊂ A.• The empty set is a subset of every set B: /0 ⊆ B.• Every set A is a subset of itself: A ⊆ A.Intersections and UnionsThe intersection of a set A with a set B, written as A ∩ B, is a set of all elements which are members ofboth A and B. Two sets are said to be disjoint if A ∩ B = /0. The union of a set A with a set B, written asA∪ B, is a set of all elements which are either members of A or B. For example, if A is the set of all positiveeven numbers, and B is the set of all positive odd numbers, then A∩ B = /0, and A∪ B = Z+, or the set of allpositive integers. Here are a few properties of intersections and unions:• A∪ B = B∪ ACS 70, Fall 2006, Lecture 1 1• A∪ /0 = A• A∩ B = B∩ A• A∩ /0 = /0ComplementsIf A and B are two sets, then the relative complement of A in B, written as B − A or B\A, is the set ofelements in B, but not in A: B\A = {x ∈ B | x 6∈ A}. For example, if B = {1, 2, 3} and A = {3, 4, 5}, thenB\A = {1, 2}. For another example, if R is the set of real numbers and Q is the set of rational numbers, thenR\Q is the set of irrational numbers. Here are some important properties of complements:• A\A = /0• A\/0 = A• /0\A = /0Important SetsIn mathematics, some sets are referred to so commonly that they are denoted by special symbols. Some ofthese numerical sets include:• N denotes the set of all natural numbers: {0, 1, 2, 3, ...}.• Z denotes the set of all integer numbers: {. . . , −2, −1, 0, 1, 2, . . .}.• Q denotes the set of all rational numbers: {ab| a, b ∈ Z, b 6= 0}.• R denotes the set of all real numbers.• C denotes the set of all complex numbers.In addition, the Cartesian product (also called the cross product) of two sets A and B, written as A× B,is the set of all pairs whose first component is an element of A and whose second component is an elementof B. In set notation, A × B = {(a, b) | a ∈ A, b ∈ B}. For example, if A = {1, 2, 3} and B = {u, v}, thenA× B = {(1, u), (1, v), (2, u), (2, v), (3, u), (3, v)}. Given a set S, another significant set is the power set of S,denoted by P(S), is the set of all subsets of S: {T | T ⊆ S}. For example, if S = {1, 2, 3}, then the power setof S is: P (S) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. It is interesting to note that, if |S| = k,then |P(S)| = 2k.CS 70, Fall 2006, Lecture 1


View Full Document

Berkeley COMPSCI 70 - Lecture Notes

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?