Equivalence Relation and Partition A relation R on set X is an equivalence relation if it is reflexive, symmetric and transitive. .Example 1:Congruence relation is an equivalence relation. Example 2:The "greater than"relation is not an equivalence relation. .Example 3:The "greater than or equal to"relation is not an equivalence relation either. Theorem:An equivalence relation R on set X provides a partition of X. X A partition of X is a set of subsets of X, 91190 such that: 95 Any two of these subsets are disjoint; 94 The union of all these subsets is X. Example:X={0,1,2,3,4,5,6,7,8,9};A partition of X: {q0,91,92,q3,94,95}whre90={0,9},q1={1,8},92={2,7},93={3,6},q4={4},95={5}
Equivalence Relation and Partition A relation R on set X is an equivalence relation if it is reflexive, symmetric and transitive. Example 1: Congruence relation is an equivalence relation. Example 2: The “greater than” relation is not an equivalence relation. Example 3: The “greater than or equal to” relation is not an equivalence relation either. Theorem: An equivalence relation R on set X provides a partition of X. A partition of X is a set of subsets of X, such that: • Any two of these subsets are disjoint; • The union of all these subsets is X. Example: X={0,1,2,3,4,5,6,7,8,9}; A partition of X:
Equivalence Relation and Partition ■ Theorem:An equivalence relation R on set X provides a partition of X. Proof::The partition is P={l(e,)∈Rlx∈X. Take any p,p'P(pp).We show they are disjoint by deriving p=p which contradicts our assumption. Now suppose there exists z such that z∈p={yl(x,)∈R}andz∈p={yl(ax',y)∈R}.Since z∈p, we also have(r,z)∈R.For any y∈p',we have(r',)∈.This also applies to z∈p',which implies (x',z)∈R.Since R is symmetric,(z,x）∈R.Since R is transitive,(x,y)∈R,which means∈p.We have shown any element of p'is in p,which implies p'Cp.Similarly,pCp'.Hence,p=p'. p D
Equivalence Relation and Partition Theorem: An equivalence relation R on set X provides a partition of X. z x x ’ y y’ p p’
Equivalence Relation and Partition What remains is to show X=U p.Clearly,for any xU p,there is pE P such thatx p,which implies E X.Therefore,we have Up X.On the other hand,for any X,since R is reflexive,we definitely PEP have(x,x)∈R→x∈p*={l(x,)∈R}.Since p"∈P,we get that x∈Up.Therefore,we also have PEP XU p.Putting everything together we get that U p=X. X D米 Each element of the partition (also a subset of X)is called an eguivalence class
Equivalence Relation and Partition x p* Each element of the partition (also a subset of X) is called an equivalence class
Equivalence Relation and Partition Example 1:A congruence relation is an equivalence relation.Residue classes are its equivalence classes. ■Example2: Consider the set of positive real number sequences whose limits equal 0.Then the relation {1/n},{2/(2n+1)} r=an小.训= are in the same equivalence class. is an equivalence relation,and each equivalence class corresponds to a rate of shrinking. Proof: Obviously R is reflexive.If sequences an),n satisfy lim=1,then {1/2n}shrinks bn 1 lim =1. n-+a:1imn→o0 faster and thus is in a difference So R is symmetric. If sequences{an小，{bn},{on}satisfyim→e0=limn→e2g=l,then equivalence class. lim an lim an lim b=1. n→oCn n→e0bnma→oC So R is transitive
Equivalence Relation and Partition Example 1: A congruence relation is an equivalence relation. Residue classes are its equivalence classes. Example 2: {1/n}, {2/(2n+1)} are in the same equivalence class. {1/2n} shrinks faster and thus is in a difference equivalence class
Functions We have learned the following definition in high school: Suppose A and B are non-empty sets.We say f is a function or mapping from A to B if for each z A, there is a f(x)∈B.in this case,we write f:A→B. A is called the domain of f,B the codomain,and {f()A)the range. For any A,f()is called the image of x.For any y E B,if there is x such that f()=y,then x is called the preimage of y. Using the language of relations we just learned,we can rewrite it: Suppose A and B are non-empty sets.We say f is a function or mapping from A to B if R is a binary relation between A and B,and for each E A,there is exactly one y E B such that(,y)E R. This is the third definition of function,after the two taught in middle school and in high school,respectively
Functions We have learned the following definition in high school: Using the language of relations we just learned, we can rewrite it: This is the third definition of function, after the two taught in middle school and in high school, respectively