Basic Set Theory - UH

1 Chapter 2 Basic Set TheoryA set is a Many that allows itself tobe thought of as a Georg CantorThis chapter introduces set Theory , mathematical in-duction, and formalizes the notion of mathematicalfunctions. The material is mostly elementary. Forthose of you new to abstract mathematics elementarydoes not meansimple(though much of the materialis fairly simple). Rather, elementary means that thematerial requires very little previous education to un-derstand it. Elementary material can be quite chal-lenging and some of the material in this chapter, ifnot exactly rocket science, may require that you ad-just you point of view to understand it. The singlemost powerful technique in mathematics is to adjustyour point of view until the problem you are tryingto solve becomes point at which this material may divergefrom your previous experience is that it will requireproof. In standard introductory classes in algebra,trigonometry, and calculus there is currently very lit-tle emphasis on the discipline ofproof.

2 Proof is, how-ever, the central tool of mathematics. This text isfor a course that is a students formal introduction totools and methods of Set TheoryAsetis a collection of distinct objects. This meansthat{1,2,3}is a set but{1,1,3}is not because 1appears twice in the second collection. The secondcollection is called amultiset. Sets are often specifiedwith curly brace notation. The set of even integerscan be written:{2n: n is an integer}The opening and closing curly braces denote a set, 2nspecifies the members of the set, the colon says suchthat or where and everything following the colonare conditions that explain or refine the correct mathematics can be spoken in set definition above is spoken The set of twicenwherenis an integer .The only problem with this definition is that wedo not yet have a formal definition of the integers are the set of whole numbers, both pos-itive and negative:{0, 1, 2, 3, ..}. We now in-troduce the operations used to manipulate sets, usingthe opportunity to practice curly brace setis a set containingno objects.

3 It is written as a pair of curly braces withnothing inside{}or by using the symbol .As we shall see, the empty set is a handy is also quite strange. The set of all humans thatweigh at least eight tons, for example, is the emptyset. Sets whose definition contains a contradiction orimpossibility are often membership symbol isused to say that an object is a member of a set. Ithas a partner symbol/ which is used to say an objectis not in a say two sets areequalif theyhave exactly the same 2. Basic SET THEORYE xample {1,2,3}then3 Sand4/ S. The set membership symbolis often used in defining operations that manipulatesets. The setT={2,3,1}is equal toSbecause they have the same members: 1,2, and 3. While we usually list the members of a setin a standard order (if one is available) there is norequirement to do so and sets are indifferent to theorder in which their members are a set is a finite set, the cardinality of a set is the numberof members it contains.

4 In symbolic notation the sizeof a setSis written|S|. We will deal with the ideaof the cardinality of an infinite set Set cardinalityFor the setS={1,2,3}we show cardinality by writ-ing|S|= 3We now move on to a number ofoperationson are already familiar with several operations onnumbers such as addition, multiplication, and two setsSandTis the collection of all objects that are in both is writtenS T. Using curly brace notationS T={x: (x S)and(x T)}The symbolandin the above definition is an ex-ample of a Boolean or logical operation. It is onlytrue when both the propositions it joins are also has a symbolic equivalent . This lets us write theformal definition of intersection more compactly:S T={x: (x S) (x T)}Example Intersections of setsSupposeS={1,2,3,5},T={1,3,4,5}, andU={2,3,4,5}.Then:S T={1,3,5},S U={2,3,5}, andT U={3,4,5}Definition sets andA B= then we say thatAandBaredisjoint, two setsSandTisthe collection of all objects that are in either set.

5 Itis writtenS T. Using curly brace notionS T={x: (x S)or(x T)}The symboloris another Boolean operation, one thatis true if either of the propositions it joins are symbolic equivalent is which lets us re-write thedefinition of union as:S T={x: (x S) (x T)}Example Unions of {1,2,3},T={1,3,5}, andU={2,3,4,5}.Then:S T={1,2,3,5},S U={1,2,3,4,5}, andT U={1,2,3,4,5}When performing set theoretic computations, youshould declare the domain in which you are set Theory this is done by declaring a universal set, at least for agiven collection of set theoretic computations, is theset of all possible we declare our universal set to be the integers then{12,23}is not a well defined set because the objectsused to define it are not members of the universalset. The symbols{12,23}do define a set if a universalset that includes12and23is chosen. The problemarises from the fact that neither of these numbers areintegers. The universal set is commonly that we have the idea of declaring a universalset we can define another operation on SET Venn DiagramsA Venn diagram is a way of depicting the relationshipbetween sets.

6 Each set is shown as a circle and circlesoverlap if the sets following are Venn diagrams forthe intersection and union of two sets. The shadedparts of the diagrams are the intersections and BA BNotice that the rectangle containing the diagram islabeled with aUrepresenting the universal a setSis thecollection of objects in the universal set that are notinS. The compliment is writtenSc. In curly bracenotationSc={x: (x U) (x / S)}or more compactly asSc={x:x / S}however it should be apparent that the compliment ofa set always depends on which universal set is is also a Boolean symbol associated with thecomplementation operation: thenotoperation. Thenotation for not is . There is not much savings inspace as the definition of compliment becomesSc={x: (x S)}Example Set Compliments(i) Let the universal set be the integers. Then thecompliment of the even integers is the odd inte-gers.(ii) Let the universal set be{1,2,3,4,5}, then thecompliment ofS={1,2,3}isSc={4,5}whilethe compliment ofT={1,3,5}isTc={2,4}.

7 (iii) Let the universal set be the letters{a, e, i, o, u, y}.Then{y}c={a, e, i, o, u}.The Venn diagram forAcisAcWe now have enough set- Theory operators to use themto define more operators quickly. We will continue togive English and symbolic two setsSandTis the collection of objects inSthat are not difference is writtenS T. In curly brace nota-tionS T={x:x (S (Tc))},or alternatelyS T={x: (x S) (x / T)}Notice how intersection and complementation can beused together to create the difference operation andthat the definition can be rephrased to use Booleanoperations. There is a set of rules that reduces thenumber of parenthesis required. These are calledop-erator precedence 2. Basic SET Theory (i) Other things being equal, operations are per-formed left-to-right.(ii) Operations between parenthesis are done first,starting with the innermost of nested parenthe-sis.(iii) All complimentations are computed next.(iv) All intersections are done next.(v) All unions are performed next.

8 (vi) Tests of set membership and computations,equality or inequality are performed operations like the set difference or thesymmetric difference, defined below, are not includedin the precedence rules and thus always use Operator precedenceSince complementation is done before intersectionthe symbolic definition of the difference of sets can berewritten:S T={x:x S Tc}If we were to take the set operationsA B Ccand put in the parenthesis we would get(A (B (Cc)))Definition differenceoftwo setsSandTis the set of objects that are in oneand only one of the sets. The symmetric difference iswrittenS T. In curly brace notation:S T={(S T) (T S)}Example Symmetric differencesLetSbe the set of non-negative multiples of two thatare no more than twenty four. LetTbe the non-negative multiples of three that are no more thantwenty four. ThenS T={2,3,4,8,9,10,14,15,16,20,21,22}Anothe r way to think about this is that we need num-bers that are positive multiples of 2 or 3 (but not both)that are no more than important tool for working with sets is theability to compare them.

9 We have already definedwhat it means for two sets to be equal, and so byimplication what it means for them to be now define another comparator for two setsSandTwe say thatSis a subset ofTif each element ofSis also anelement ofT. In formal notationS Tif for allx Swe havex Tthen we also sayTcontainsSwhichcan be writtenT S. IfS TandS6=Tthen wewriteS Tand we saySis apropersubset SubsetsIfA={a, b, c}thenAhas eight different subsets: {a} {b} {c}{a, b} {a, c} {b, c} {a, b, c}Notice thatA Aand in fact each set is a subset ofitself. The empty set is a subset of every are now ready to prove our first new notation is required and we must intro-duce an important piece of mathematical culture. Ifwe say A if and only if B then we mean that eitherA and B are both true or they are both false in anygiven circumstance. For example: an integer x iseven if and only if it is a multiple of 2 . The phrase if and only if is used to establishlogical equiva-lence.

10 Mathematically, A if and only if B is a wayof stating that A and B are simply different waysof saying the same thing. The phrase if and onlyif is abbreviated iff and is represented symbolicallyas the double arrow . Proving an iff statement isdone by independently demonstrating that each maybe deduced from the sets are equal if and only ifeach is a subset of the other. In symbolic notation:(A=B) (A B) (B A)Proof:Let the two sets in question beAandB. Begin byassuming thatA=B. We know that every set SET THEORY27a subset of itself soA A. SinceA=Bwe maysubstitute into this expression on the left and obtainB A. Similarly we may substitute on the right andobtainA B. We have thus demonstrated that ifA=BthenAandBare both subsets of each other,giving us the first half of the now thatA BandB A. Thenthe definition of subset tells us that any element ofAis an element ofB. Similarly any element ofBis an element ofA. This means thatAandBhavethe same elements which satisfies the definition of setequality.