8 Pages
Unlock Document

Computer & Information Science
CIS 1166
David Shulman

Sets 1 Introduction to Sets This note is a summary of some material related to sets, material discussed in 2.1 and 2.2 of your textbook. Neither I nor Rosen provide a formal de▯nition of sets. There are some tricky problems that arise if one tries to be very strict and formal, but for our purposes it su▯ces to use the intuitive notion of a set as a collection of things. The kind of things that we put together in the same collection can be very disparate. We can have a set consisting of just the number 4, Charles De Gaulle’s favorite song and whatever thoughts George W. Bush is currently thinking at this very second. If our set is small enough, we can actually list all the elements in our set. To do so, we use the notation illustrated below: A = f3;8;12;23;43;ag . Here I have speci▯ed that A is a six element set with members 3, 8, 12, 23, 43, and a. It does not matter what order I list the elements and there is no point in listing an element more than once. When specifying my set (using what is called roster notation), I began with a left brace (and it has to be a brace and not a parenthesis or bracket), then listed my elements separated by commas but no comma after the last element and then ended with a right brace. If I want to say that an element belongs to a set, I use 2 and to say it does not belong I use 62. So, for example, 5 62 A but 12 2 A. I could also use set builder notation to specify sets. I would do so when dealing with in▯nite sets or sets too large to conveniently list all the elements of. We start with certain familiar sets such as those listed by Rosen on the bottom of page 116. N, Z, Q, R, C are very commonly used to refer to the 1 natural numbers, the integers (Zahlen in German), the rationals (quotients formed from integers), the reals, and complex numbers respectively. Some- times you will see caligraphic versions of R used for the real numbers if an author wants to used plain R for something else. Then we can build sets such as fxjx 2 Z ^ x ▯ 100g or fx 2 Rjx < 10g. Here inside braces, I begin by listing my variable and then I follow with a vertical line and then comes a condition that must be satis▯ed by my variable. The set I specify is then the set of all elements in my domain that satisfy the condition. Or I might begin with something like x 2 R to specify that I am only concerend with elements of R and then what I write after the j tells me what condition besides belonging to R must be sati▯ed in order to be an element of the set in question. 1.1 Set Equality Two sets X and Y are said to be equal i▯ they have exactly the same elements. So X and Y are equal i▯ 8z(z 2 X $ z 2 Y ). Thus the only thing that matters about a set is which elements belong and which do not belong to the set. So it cannot matter which order you use to list the elements if you specify the set using a roster and there is no reason to list an element more than once when using roster notation. To sum up, our notion of set equality is extensional not intensional. So I can think of the same set as the set of animals with at least one heart or the set of animals with at least one kidney if whoever has a heart also has a kidney and vice versa. The set of integers greater than 10 is the same as the the set of integers that are at least 11. It does not matter how I think about my set; all that really matters is who belongs and who does not belong to the set. 2 Example Sets Given an equation (say an equation in one variable), we might be interested in the solution set of that equation (the set of all possible solutions (solutions in our domain) to that equation). Sometimes this solution set is empty because there is no solution. So we need the empty set ;. Formally we 2 can de▯ne ; = fxjx 6= xg so the emptyset is the set of things that do not equal themselves; but everything is equal to itself hence the emptyset has no elements. Sometimes we might be interested not just in one equation but in many equations such as the set of all quadratic equations in one variable. We might be interested in the set B of possible solution sets for quadratic equations. We 2 know that ; 2 B if our domain is just the reals. For example 5x +x+9 = 0 has no real solution. B has many other elements such as f3;4g. B illustrates a case where it is useful to consider a set at least some of whose elements are themselves sets. I shall provide some more simple examples of sets. If we have some object c, we can always form the set whose sole element is c: fcg. For example, we can form f;g, which is not the same as ; because if we use jj to represent the cardinality of function (the how many elements function), then j;j = 0 but jf;gj = 1. And note that ; has 0 elements but 0 is a number and not the emptyset itself. If you give me any two elements x;y, I can form the set fx;yg whose only elements are x and y. And there are many more simple sets I can construct. I shall provide more illustration below. But we see here that I can form f;;f;gg, which is a two element set whose sole elements are the empty set and the singleton set whose sole element is the emptyset. 3 Relations and Operations with Sets Here I describe some simple relationships between sets and some operations that can be performed on sets. 3.1 Subset We say that set A is a subset of set B i▯ every element of A also belongs to B. So A ▯ B i▯ 8x(x 2 A ! x 2 B). Here ▯ is the symbol for subsethood. We have for any set A that A ▯ A. It follows from the de▯nition of subset that any set is a subset of itself. If we want to say that A is a subset of B and not vice versa, we say that A is a proper subset of B. Some examples of subsethood: f3;5g ▯ f3;6;5g, Q ▯ R, the set of even integers is a subset of the set of integers. The null set is a subset of any set. 3 Examples of nonsubsethood: The set of even integers is NOT a subset of the set of positive integers. -2 is even but not positive. The set of reals whose square is less than 10 is not a subset of the set of reals less than 3 because the square of 3 is less than 10 but 3 is not less than 3. A = f3;5;2g is not a subset of B = f2;3;4;8;f5g;g because 5 belongs to A but does not belong to B. f5g 2 B but 5 and f5g are di▯erent things. In general if A and B are any two sets and A ▯ B, then jAj ▯ jBj. We have some simple general rules: If A and B are two unequal sets, then we cannot have both A ▯ B and B ▯ A. Of course, if A and B are equal, then we do have both A ▯ B and B ▯ A. A ▯ B and B ▯ C implies A ▯ C. 3.2 Union and Intersection We might think of union and intersection as set theoretic versions of OR and AND. The union is de▯ned as follows: 8x(x 2 A [ B $ x 2 A _ x 2 B); something is in the union of A and B i▯ it is in A or it is in B. The intersection is de▯ned as follows: 8x(x 2 A \ B $ x 2 A ^ x 2 B); something is in the union of A and B i▯ it is in A and it is in B. So for example if A = f4;8;9;12;32g and B = f4;12;30;34g then A [ B = f4;8;9;12;32;30;34g and A \ B = f4;12g. If A is the set of integers divisible by 3 and B the set of integers divisible by 4, then A[B is the set of integers divisible by 3 or by 4 and A\B is the set of integers divisible by both 3 and 4 (and hence divisible by 12). So 12 is in the intersection but 9 is not; however 9 is in the union as is 20. If A and B are any ▯nite sets, we have jAj+jBj▯jA\Bj = jA[Bj. This is simple enough to demonstrate the number of elements in the union of A and B would be the sum of the numbers of elements in A and the numher in B except that you have to adjust for the fact that you should not double count the elements belonging to both A and B. If A is any set, then A [ ; = A while A \ ; = ;. We could also de▯ne a union or intersection of more than two sets, but that is really not necessary. We can compute the intersection of sets A, B, C, D, E, G for example by computing ((((A \ B) \ C) \ D) \ E) \ G and I do not need even need to write all these parentheses because associativity rules say compute in left to right order. 4 3.3
More Less

Related notes for CIS 1166

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.