Set Theory A set is a collection of objects or elements Typically the type of all the elements in a set is the same For example all the elements in a set could be integers However it is possible to have different types of elements in a set An analogy for this is that usually a bookbag contains just books But sometimes it may contain other elements such as pencils and folders as well We have two standard methods of denoting the elements in a set 1 Explicitly list the elements inside of a set of curly braces as follows 1 2 3 4 2 Give a description of the elements in a set inside of a set of curly braces as follows 2x x N In order to understand the second method we must define the various symbols that are used in this notation Here is a list of the symbols we will be using translates to such that is an element of is a subset of Note in the book they define this symbol as is a proper subset of and use to mean is a subset of Now we have to define what a subset is A subset is also a set So if we have sets A and B A B if for all x A x B In layman s terms a set A is a subset of a set B if all the elements in the set A also lie in the set B We still have to define what 2x x N really means Here it is in English The set of all numbers of the form 2x such that x is an element of the natural numbers Note The set N denotes the natural numbers or the non negative integers according to the book So the set above could also be listed as 0 2 4 6 Now that we have gotten that out of the way let s talk about the empty set The empty set is a set with no elements in it In our standard notation we could denote it as It is also very common to use to denote the empty set It s important to denote that the following are not equal 0 and 0 The first two are sets while the third is an element However the empty set has no elements while 0 contains one element zero Typically sets will be denoted by uppercase letters There are some other sets we should be familiar with since they come up so often Here they are Z 0 1 1 2 2 the set of integers N 0 1 2 3 the set of non negative integers Z 1 2 3 the set of positive integers Q a b a b Z b 0 R the set of real numbers Also one last definition A for a set a is known as the cardinality of A which equals the number of elements in A Set Operators Now we are ready to discuss set operators We can use several operators on existing sets to define new ones The first two operators are binary operators union and intersection In each of these examples let A and B be sets union A B x x A x B intersection A B x x A x B complement A x x A relative complement B A x x B x A In English the union of two sets contains all elements in either set and the intersection of two sets contains all elements in BOTH sets To define the complement we must define what an universe is For each set there is a possible set of elements This possible set of elements is known as the universe Typically you will be told what the universe is for each problem Most of the time it is the set of integers or real numbers The complement of a set contains all the elements in the universe that are NOT in the set itself You can think of relative complement as the subtraction between two sets B A refers to a set that subtracts out all the elements from A out of B Now if a particular element of A wasn t in B to begin with there s no need to take it out of B at all Also an identity that we can use is that B A B A Equality of Sets There are three essentially different ways that we can show two sets to be equal The first two are going to be analogous to methods used in logic 1 Use the laws of set theory 2 Use the table method I will go through the laws of set theory showing you why they work through something called a Venn Diagram Then we will consider working through showing A A B A B Table Method Another way to think of showing set equality is to look at a Venn Diagram and consider each possible position an arbitrary element can be located In essence we know that two sets A and B are equal if x A x B for an arbitrary element x What we can do is an exhaustive search of all the places an element x could like in a Venn diagram If in each situation the above bidirectional implication holds they we proven the statement for an arbitrary x proving the two sets to be equal Let s look at an example showing that A A B A B A 0 0 1 1 B 0 1 0 1 A B 0 0 1 0 A B 0 0 0 1 A B A B 0 0 1 1 Finally a third way to show that two sets A and B are equal is to prove that A B AND B A Let s use this idea to show once again that A A B A B Part 1 Show that A A B A B Consider an arbitrary element x A We must show that x A B A B Now consider the situation that x B In this particular situation by definition we know that x A B and thus MUST BE an element of A B A B since A B is a subset of A B A B So the only situation we have not proven the statement to be true for is if x B But if this is the case then by definition we know that x A B which implies that x A B A B as desired proving part 1 Part 2 Show that A B A B A It suffices to show A B A A B A One requirement for x A B is that x A proving the first part Furthermore one requirement for x A B is that x A proving the second part of the and thus we have shown that A B A B A Here is a more difficult example See if you can show that these two sets are equal using either of the methods I have presented thus far A B C B B C
View Full Document
Unlocking...