Equivalence Classes

1 MATH 321 Equivalence RELATIONS,WELL-DEFINEDNESS, MODULAR ARITHMETIC, AND THERATIONAL NUMBERSALLAN explore the notion of well-definedness when defining functionswhose domain is the set of all Equivalence Classes of an Equivalence we apply this to define modular arithmetic and the setQof ClassesWe shall slightly adapt our notation for relations in this document. Let bea relation on a setX. Formally, is a subset ofX X. Given two elementsx,y X, we shall writex yto mean (x,y) . From now on, we shall just usethe notationx y, and not explicitly reference as a subset ofX that a relation on a setXis anequivalence relationif is(i)reflexive: ( x X)(x x),(ii)symmetric: ( x,y X)(x y y x), and(iii)transitive: ( x,y,z X)((x y y z) (x z)).Suppose is an Equivalence relation onX. When two elements are related via , it is common usage of language to say they areequivalent.

2 Givenx X, theequivalence classofxis the set[x] ={y X:x y}.In other words, the Equivalence class [x] ofxis the set of all elements ofXthatare equivalent tox. Be mindful that [x] is a subset ofX, it is not an element , the set [x] contains much more than justx. The elementxis called arepresentativeof the Equivalence class [x]. Any element of an Equivalence class canserve as a an Equivalence relation on a setX, show that for any twoelementsx,y X,x yif and only if [x] = [y].We shall use the notationX/ to mean the set of all Equivalence Classes withrespect to . That is,X/ ={[x] :x X}.Notice thatX/ is a set whose elements are subsets ofX. We ve often referred tosuch a thing as afamilyof subsets ofX. As shown in Theorem (i),X/ isactually a partition YASHINSKIE xample N. Recall that we say two integersa,b Zarecongruentmodulonwhenn|(a b). As discussed in class, conguence modulonis anequivalence relation.

3 We shall writea bmodnto meanais conguent tobmodulon. The set of Equivalence Classes of integerswith respect to this Equivalence relation is traditionally denotedZ/nZ. This is lesscumbersome notationally than writing something likeZ/( modn).Exercise the relation of congruence modulo 5. Explicitly describethe Equivalence Classes [0] and [7] whose domain isX/ It is common in mathematics (more common than you might guess) to work withthe setX/ of Equivalence Classes of an Equivalence relation. Issues arise when oneattempts to define functionsf:X/ Ywhose domain isX/ . When defining any function, one usually describes what thefunction does to a typical element of the domain. In this case, a typical element ofthe domain is an Equivalence class [x], which is represented by some elementx typically wants to define whatf([x]) is in terms of the representativex. Thisis where one can get into trouble.

4 Consider the following us attempt to define a functionf:Z/5Z Zby the formulaf([m]) =m. Then we havef([0]) = 0, f([2]) = 2, f([3]) = 3, f([7]) = 7,and so on. But there is a major problem here. Since 2 7 mod 5, it follows that[2] = [7]. That is, [2] and [7] are the exact same element of the setZ/5Z. However,the function we ve defined above has the property thatf([2])6=f([7]). This isa clear violation of the definition of a function, and sofis not really a functionat all. Mathematicians would say that the function fis notwell-defined, whichreally just means thatfis not a function. The issue is that the rule forfmapsdifferent representatives of the same Equivalence class to different elements of us attempt to define another function with domainZ/5Z. Givenan integerm Z, letr5(m) denote the remainder, as in the Division Algorithm,aftermis divided by 5. Sor5(m) {0,1,2,3,4}.

5 For example,r5(13) = 3,because 13 = 2 5 + s define a functionf:Z/5Z {0,1,2,3,4},byf([m]) =r5(m).In this case, this function iswell-defined(we ll explain how one checks this below.)At first glance, the definition off([m]) appears to depend on the choice of therepresentativemof the Equivalence class, but it actually does RELATIONS AND WELL-DEFINEDNESS3We shall now explore how to ensure that we are defining actual functions out ofX/ . In what follows, let :X X/ be the function defined by (x) = [x]. Notice this is an honest function. It issurjective, but in general is not injective, because any two equivalent elements willhave the same thatf:X/ Yis a function, that is an honest well-defined function. Letg:X Ybe the functiong=f . Prove thatg(x) =g(x ) wheneverx x .The point of this exercise is that in order to have a well-defined functionf:X/ Y,then it must be the case thatf([x]) =f([x ]) wheneverx x.

6 If not, then ourattempt at making a function is not really a function at all. The following theoremsays that this is theonlyissue we need to be an Equivalence relation onXand letg:X Ybe afunction with the property thatg(x) =g(x )wheneverx x .Then there exists a (well-defined) functionf:X/ Ygiven by the formulaf([x]) =g(x).Before we prove this theorem, let us return to Example 3. We started with thefunctionr5:Z {0,1,2,3,4}.Here,r5is going to play the role ofgin the statement of the theorem. To use thetheorem to verify thatf([m]) =r5(m) is well-defined, we must show thatr5(m) =r5(m ) wheneverm m mod m mod 5. Then there is somek Zsuch thatm=m + the Division Algorithm tom gives us integersqandrsuch thatm = 5q+ {0,1,2,3,4}andr5(m ) =rby definition ofr5. Combining the aboveequations shows thatm=m + 5k= (5q+r) + 5k= 5(q+k) + this, it follows thatr5(m) =r. Thus we have shown thatr5(m) =r5(m ) wheneverm m mod the above theorem, the functionf:Z/5Z {0,1,2,3,4}, f([m]) =r5(m)is YASHINSKIThis argument is typical of how one verifies that a functionf:X/ Yis well-defined.

7 One takes arbitrary elementsx,x Xfor whichx x , andthen one shows that the proposed expressions forf([x]) andf([x ]) give the sameelement ofY. In this case we would say that the expressionf([x]) depends only onthe Equivalence class ofx, not on the prove the theorem, we must take a slight digression into the foundations ofwhat a function actually Definition of a FunctionWe have been dealing with functions for quite some time now, but we neveractually gave them a proper definition. According to the text: A functionffromXtoY, writtenf:X Y, is a rule that pairs an elementx Xwith an elementy Y, writtenf(x) =y, such that the following propertyholds.( x X)( !y Y)[f(x) =y].The central issue here is that the term rule is undefined. This makes for anambiguous definition. This is really unacceptable in mathematics. Everything mustalways have a precise, unambiguous definition.

8 This deficiency (hopefully) did notimpede our understanding of functions. Instead, it is making it quite awkward toprove the above theorem. In order to prove that somethingisa function, we mustbe clear aboutwhata function mathematics is built upon the foundations of set theory. What thismeans, is thateverythingin mathematics is really a set. This includes numbers,ordered pairs, relations (as we saw in class), and functions. We often don t thinkof these objects as sets, but they must be defined as sets so that we can be clearabout what they are when we need to be. Here is the definition of a a setXto a setY, is a subset ofX Ywith thefollowing property:( x X)( !y Y)[(x,y) f].The setXis thedomainoffand the setYis thecodomainoff. For eachx X,the unique valuey Ysuch that (x,y) fis denoted byf(x) and is called thatfis a set. By definition, the statement (x,y) fis equivalent tothe statementf(x) =y.

9 So whenever we sayf(x) =y, we really mean (x,y) collection of ordered pairs infcompletely encode the rule off. On yourexam, the setfwas called thegraph us now define function X Yandg Y Zare functions. The compositionofgwithfis the setg f={(x,z) X Z: ( y Y)[(x,y) f (y,z) g]}.Exercise thatg f, as defined above, is a function. (Hint: for eachx X, prove existence and uniqueness ofz Zfor which (x,z) g prove uniqueness , suppose (x,z1),(x,z2) g f, and show thatz1=z2.) Equivalence RELATIONS AND WELL-DEFINEDNESS5We can translate the definitions of injectivity and surjectivity in terms of the X Ybe a function.(i) We sayfisinjectiveif( y Y)( x1,x2 X)([(x1,y) f (x2,y) f] (x1=x2)).(ii) We sayfissurjectiveif( y Y)( x X)[(x,y) f].Exercise thatf X Yis a function. Definef 1 Y Xbyf 1={(y,x) Y X: (x,y) f}.Prove that iffis both injective and surjective, thenf 1is a we shall prove Theorem (Theorem 1) Suppose is an Equivalence relation onXandg:X Yisa function such thatg(x) =g(x ) wheneverx x.

10 Definef (X/ ) Ybyf={([x],g(x)):x X}.We shall prove thatfis a function. Notice that every element ofX/ is of theform [x] for somex X. So let [x] X/ be an arbitrary Equivalence class, oneof whose elements isx X. Lety=g(x). Then([x],y)=([x],g(x)) shows that for every [x] X/ , there isy Ysuch that([x],y) f. Forthe uniqueness assertion, suppose that([x],g(x)) fand([x ],g(x )) fare suchthat [x] = [x ]. Thenx [x], which impliesx x by definition of equivalenceclass. Sog(x) =g(x ), by the assumed properties ofg. We conclude that for every[x] X/ , there is a uniquey Ysuch that([x],y) f. By definition,fis afunction. From now on, we shall no longer explicitly think of a functionf:X Yas asubset ofX Y, unless we need to. In fact, other people may look strangely atyou if you say things like (x,y) f, rather thanf(x) =y(remember, they areequivalent statements, by definition.) So now we can go about our lives treatingfunctions as we used to, secretly knowing that we ve built a rigorous foundation ofwhat a function really situation in which we have been a little lax is in definingordered pairs properly (and consequently Cartesian products).