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