1.2.SETS AND EQUIVALENCE RELATIONS 3 first time,we list here some of the difficulties that they may encounter and some of the strategies of proof available to them.It is a good idea to keep referring back to this list as a reminder.(Other techniques of proof will become apparent throughout this chapter and the remainder of the text.) A theorem cannot be proved by example;however,the standard way to show that a statement is not a theorem is to provide a counterexample. Quantifiers are important.Words and phrases such as only,for all,for every,and for some possess different meanings. Never assume any hypothesis that is not explicitly stated in the theorem.You cannot take things for granted. Suppose you wish to show that an object exists and is unigue.First show that there actually is such an object.To show that it is unique,assume that there are two such objects,say r and s,and then show that r =s. Sometimes it is easier to prove the contrapositive of a statement.Proving the state- ment "If p,then g"is exactly the same as proving the statement "If not g,then not p.” Although it is usually better to find a direct proof of a theorem,this task can some- times be difficult.It may be easier to assume that the theorem that you are trying to prove is false,and to hope that in the course of your argument you are forced to make some statement that cannot possibly be true. Remember that one of the main objectives of higher mathematics is proving theorems. Theorems are tools that make new and productive applications of mathematics possible.We use examples to give insight into existing theorems and to foster intuitions as to what new theorems might be true.Applications,examples,and proofs are tightly interconnected- much more so than they may seem at first appearance. 1.2 Sets and Equivalence Relations Set Theory A set is a well-defined collection of objects;that is,it is defined in such a manner that we can determine for any given object z whether or not z belongs to the set.The objects that belong to a set are called its elements or members.We will denote sets by capital letters, such as A or X;if a is an element of the set A,we write aA. A set is usually specified either by listing all of its elements inside a pair of braces or by stating the property that determines whether or not an object r belongs to the set.We might write X={c1,x2,,n} for a set containing elements x1,x2,...,n or X ={xx satisfies P} if each x in X satisfies a certain property P.For example,if E is the set of even positive integers,we can describe E by writing either E=[2,4,6,...}or E=fx:x is an even integer and x >0h.1.2. SETS AND EQUIVALENCE RELATIONS 3 first time, we list here some of the difficulties that they may encounter and some of the strategies of proof available to them. It is a good idea to keep referring back to this list as a reminder. (Other techniques of proof will become apparent throughout this chapter and the remainder of the text.) • A theorem cannot be proved by example; however, the standard way to show that a statement is not a theorem is to provide a counterexample. • Quantifiers are important. Words and phrases such as only, for all, for every, and for some possess different meanings. • Never assume any hypothesis that is not explicitly stated in the theorem. You cannot take things for granted. • Suppose you wish to show that an object exists and is unique. First show that there actually is such an object. To show that it is unique, assume that there are two such objects, say r and s, and then show that r = s. • Sometimes it is easier to prove the contrapositive of a statement. Proving the state￾ment “If p, then q” is exactly the same as proving the statement “If not q, then not p.” • Although it is usually better to find a direct proof of a theorem, this task can some￾times be difficult. It may be easier to assume that the theorem that you are trying to prove is false, and to hope that in the course of your argument you are forced to make some statement that cannot possibly be true. Remember that one of the main objectives of higher mathematics is proving theorems. Theorems are tools that make new and productive applications of mathematics possible. We use examples to give insight into existing theorems and to foster intuitions as to what new theorems might be true. Applications, examples, and proofs are tightly interconnected— much more so than they may seem at first appearance. 1.2 Sets and Equivalence Relations Set Theory A set is a well-defined collection of objects; that is, it is defined in such a manner that we can determine for any given object x whether or not x belongs to the set. The objects that belong to a set are called its elements or members. We will denote sets by capital letters, such as A or X; if a is an element of the set A, we write a ∈ A. A set is usually specified either by listing all of its elements inside a pair of braces or by stating the property that determines whether or not an object x belongs to the set. We might write X = {x1, x2, . . . , xn} for a set containing elements x1, x2, . . . , xn or X = {x : x satisfies P} if each x in X satisfies a certain property P. For example, if E is the set of even positive integers, we can describe E by writing either E = {2, 4, 6, . . .} or E = {x : x is an even integer and x > 0}