Equivalence relations - Columbia University
equivalence relation, provided we restrict to a set of sets (we cannot just de ne this as an equivalence relation on the \set" of all sets, since this is too big to be a set) For example, we could de ne this relation on a set such as P(R), the set of all subsets of the real numbers The
EquivalenceRelations
These three properties are captured in the axioms for an equivalence relation Definition An equivalence relation on a set X is a relation ∼ on X such that: 1 x∼ xfor all x∈ X (The relation is reflexive ) 2 If x∼ y, then y∼ x (The relation is symmetric ) 3 If x∼ yand y∼ z, then x∼ z (The relation is transitive ) Example
95 Equivalence Relations
Corollary If A is a set, R is an equivalence relation on A, and a and b are elements of A, then either [a] \[b] = ;or [a] = [b]: That is, any two equivalence classes of an equivalence relation are either mutually disjoint or identical Theorem 2 Let R be an equivalence relation on a set A Then the equivalence classes of R form a partition of A
Equivalence Relations - Mathematical and Statistical Sciences
An Important Equivalence Relation Let S be the set of fractions: S ={p q: p,q∈ℤ,q≠0} Define a relation R on S by: a b R c d iff ad=bc This relation is an equivalence relation 1) For any fraction a/b, a/b R a/b since ab = ba (Reflexitivity) 2) If a/b R c/d, then ad = bc, so cb = da and c/d R a/b (Symmetry)
Equivalence Relations and Functions
Equivalence Relations and Functions October 15, 2013 Week 13-14 1 Equivalence Relation A relation on a set X is a subset of the Cartesian product X£X Whenever (x;y) 2 R we write xRy, and say that x is related to y by R
Math 127: Equivalence Relations
De nition 4 Let ˘be an equivalence relation on X The set [x] ˘as de ned in the proof of Theorem 1 is called the equivalence class, or simply class of x under ˘ We write X= ˘= f[x] ˘jx 2Xg Example 6 If we consider the equivalence relation as de ned in Example 5, we have two equiva-lence classes: odds and evens
Section 42: Equivalence Relations
Then ~ is an equivalence relation because it is the kernel relation of function f:S N defined by f(x) = x mod n Example: Let x~y iff x+y is even over Z Note that x+y is even iff x and y are both even or both odd iff x mod 2 = y mod 2 Therefore ~ is an equivalence relation because ~ is the kernel relation of
QUIVALENCE ELATIONS
equivalence relations, partitions, and quotient sets are important Example 3 1 Define the following equivalence relation on Z (Znf0g): (a;b)˘(c;d),ad =bc: Then (Z Z)=˘“is” the rational numbers More about this later Example 3 2 Let ˘be the equivalence relation on R defined by x ˘y if and only if x y is an integer multiple of 2p
Daniel ALIBERT Ensembles, applications Relations d
Une relation réflexive, symétrique et transitive est appelée une relation d'équivalence Définition Soit E un ensemble, muni d'une relation d'équivalence R Pour tout élément x de E, on appelle classe d'équivalence de x et l'on note C(x) le sous-ensemble de E formé des éléments y tels que x R y soit vrai
[PDF] relation binaire exercices corrigés pdf
[PDF] relation d'équivalence et classe d'équivalence
[PDF] exo7 relation binaire
[PDF] liste des verbes d'action
[PDF] liste des verbes d'état cm2
[PDF] exercice sur les verbes d'état et d'action cm2
[PDF] les verbes d'action pdf
[PDF] film éthique et culture religieuse
[PDF] les verbes d'état pdf
[PDF] tous les verbes d'état
[PDF] liste des verbes attributifs
[PDF] upload file magazines gaumont 262 web
[PDF] exercice de maths rapport et proportion
[PDF] gaumont pathé
Math 127: Equivalence Relations
Mary Radclie
1 Equivalence Relations
Relations can take many forms in mathematics. In these notes, we focus especially on equivalence relations,
but there are many other types of relations (such as order relations) that exist. Denition 1.LetX;Ybe sets. ArelationR=R(x;y) is a logical formula for whichxtakes the range ofXandytakes the range ofY, sometimes called arelation fromXtoY. IfR(x;y) is true, we say thatxis related toybyR, and we writexRyto indicate thatxis related toybyR.Example 1.Letf:X!Ybe a function. We can dene a relationRbyR(x;y)(f(x) =y).Example 2.LetX=Y=Z. We can dene a relationRbyR(a;b)ajb.There are many other examples at hand, such as ordering onR, multiples inZ, coprimality relationships,
etc. The denition we have here is simply that a relation gives some way to connect two elements to each
other, that can either be true or false.Of course, that's not a very useful thing, so let's add some conditions to make the relation carry more
meaning. For this, we shall focus on relations fromXtoX, also called relationsonX. There are several properties that will be interesting in considering relations: Denition 2.LetXbe a set, and letbe a relation onX.We say thatisre
exiveifxx8x2X.We say thatissymmetricifxy)yx8x;y2X.
We say thatisantisymmetricifxy^yx)x=y8x;y2X.
We say thatistransitiveifxy^yz)xz8x;y;z2X.Example 3.LetX=Z, and dene a relationbyxygcd(x;y) = 1. Let's consider what
propertiessatises. Re exivity: NO. Takejxj>1, then gcd(x;x) =x6= 1, soxxis almost never true. Symmetry: YES. Since gcd(x;y) = gcd(y;x), we denitely have symmetry. Antisymmetry: NO. Obviously we can't have symmetry and antisymmetry at the same time. Transitivity: NO. Takex= 10;y= 9;z= 20. Then we havexyandyz, but we denitely don't getxz.1 Example 4.LetX=R, and dene a relationas is standard. Let's consider what properties satises. Re exivity: YES. Certainlyxxis always true.Symmetry: NO. It doesn't make sense thatxy)yx.
Antisymmetry: YES. Ifxy^yx, it is standard to conclude thatx=y.Transitivity: YES. Ifxy^yz, we know thatxz.What we are most interested in here is a type of relation called anequivalence relation.
Denition 3.A relationRonXis called an equivalence relation if it is re exive, symmetric, and transitive.Example 5.Dene a relationonZbyxyifxandyhave the same parity (even or odd). We claim thatis an equivalence relation: Re exivity: Sincexhas the same parity asx,xx. Symmetry: Ifxy, thenxandyhave the same parity. Thusyandxhave the same parity, and henceyx. Transitivity: Ifxy, thenxandyhave the same parity. Ifyz, thenyandzhave the same parity. Sinceyhas only one parity, we can thus conclude thatxandzhave the same parity, soxz.Thereforeis an equivalence relation.What we notice about this example is that the equivalence relation we dened sliced upZinto two
groups: the evens, and the odds. Everything in the evens group is related to everything else in the evens
group under, and everything in the odds group is related to everything else in the odds group under,but there are no relations between the evens and odds. In general, this is exactly how equivalence relations
will work.Theorem 1.LetXbe a set. Let
S=fRjRis an equivalence relation onXg;
and letU=fpairwise disjoint partitions ofXg:
Then there is a bijectionF:S ! U, such that8R2 S, ifxRy, thenxandyare in the same set ofF(R). Proof.We rst dene the functionF. Given a relationR, dene [x]R=fy2XjxRyg. We then dene the functionFbyF(R) =f[x]Rjx2Xg. We must rst show thatFis well dened; that is, thatF(R) is a pairwise disjoint partition ofX.We note that there are two properties to verify: that these sets are pairwise disjoint, and that they
cover all ofX. First, let us consider pairwise disjointness. Letx2X, and note thatx2[x]Rby symmetry, sox2 [A2F(R)A. This veries thatF(R) covers all ofX. Now, let us suppose that for somey2X, we also have thatx2[y]Rfor somey2X. Letz2[y]R. Thenyxandyz, so by symmetry and transitivity, we havexz. Thus,z2[x]R8z2[y]R, so [y]R[x]R. But theny2[x]R, so by repeating this argument we obtain [x]R[y]R. Thus, [y]R= [x]R, and hencexappears only in the set [x]RinF(R). This establishes pairwise disjointness.Hence, the function is well-dened.
2Next, we establish bijectivity.
For injectivity, suppose thatR1andR2are equivalence relations onX, andR16R2. Then there existx;y2Xthat are related under one ofR1;R2, but not the other; wolog, sayxR1yandx6R2y. Then y2[x]R1, buty =2[x]R2, and henceF(R1)6=F(R2). Thus, the function is injective. For surjectivity, letUbe a pairwise disjoint partition ofX. Dene a relationRonXbyxRy(x;yare in the same set inU). It is straightforward to establish that this is an equivalence relation, and
thatF(R) =U. HenceFis surjective. We note, moreover, that the property described onFis immediate by denition ofF. This theorem allows us fundamentally to think about equivalence relations as giving a mathematicallyprecise way to simply break up a set into a partition that has properties we like. Indeed, we often care
almost exclusively about the partitioning we have performed, and hence we give this a special name. Denition 4.Letbe an equivalence relation onX. The set [x]as dened in the proof of Theorem 1is called theequivalence class, or simplyclassofxunder. We writeX==f[x]jx2Xg.Example 6.If we consider the equivalence relation as dened in Example 5, we have two equiva-
lence classes: odds and evens. We can then writeZ==ffodd integersg,feven integersgg.2 Modular Arithmetic
The most important reason that we are thinking about equivalence relations is to apply them to a particular
situation. Specically, we are interested in developing some theory around what is usually called modular
arithmetic. Denition 5.Letn2Nand leta;b2Z. We say thatais congruent tobmodulonifnj(ab). We write this asab(modn).We note the following theorem, whose proof is left as an exercise to the interested reader (but is quite
straightforward).Theorem 2.Letn2Nand leta;b2Z. TFAE:
1.ab(modn).
2.aandbleave the same remainder when divided byn.
3.a=b+knfor somek2Z.
Notice that this theorem is sucient to establish the following corollary: Corollary 1.Congruence modulonis an equivalence relation onZ. This is immediate, as the dividing ofZinto classes based on what remainder is left when dividing bynis clearly a pairwise disjoint partition ofZ, since remainders are unique by the Division Theorem. Hence,
using part (b) of Theorem 2 together with Theorem 1, we immediately have that congruence forms an equivalence relation onZ. Denition 6.Letn2N. We denote byZnorZ=nZthe set of equivalence classes under the relation of congruence modulon. 3 Now, what we'd really like to do is think about how we can perform arithmetic operations modulon, and if there is a consistent way to do so. That is to say, is there a well-dened way to understand
[a]n+ [b]n? Certainly, we could think of this as [a+b]n, but the question that must be answered here is whether this is a well-dened operation. Since there are many dierent elements in [a]n, would the arithmetic look dierent if we selected a dierent representative, instead ofa? The good news is that, in most cases, the answer is no. The following theorem establishes that performing addition, multiplication, and subtraction is well-dened modulon. Theorem 3.Leta1;a2;b1;b22Z, and letn2N. Suppose, further, thata1a2(modn)andb1 b2(modn). Then
1.a1+b1a2+b2(modn).
2.a1b1a2b2(modn).
3.a1b1a2b2(modn).
Proof.The proofs of all three properties are similar. We include here only the proof of property 2, and
leave the remaining proofs as an exercise. Note that asa1a2(modn), we have by Theorem 2 thata1anda2have the same remainder when divided byn, so there existq1;q2;rsuch that 0r < nanda1=q1n+r,a2=q2n+r. Likewise, there existq01;q02;r0such that 0r0< nandb1=q01n+r0andb2=q02n+r0.Consider, then
a1b1a2b2= (q1n+r)(q01n+r0)(q2n+r)(q02n+r0)
=n(q1q01n+q1r0+q01rq2q02nq2r0q02r) +rr0rr0 =n(q1q01n+q1r0+q01rq2q02nq2r0q02r): Then we have thatnj(a1b1a2b2), and hence by denitiona1b1a2b2(modn).This allows us to perform these three basic arithmetic operations modulon.Example 7.Determinexso that
3x+ 9 = 2x+ 6 (mod7):
Solution.We can perform subtraction, addition, and multiplication modulo 7. Moreover, as the theorem shows, we can replace a number with any other number that it shares congruence with modulo 7. First, we subtract 2xfrom both sides, and then subtract 9 from both sides, to obtain x 3 (mod7): In general, we'd prefer to have positive numbers, so since34 (mod7), we can writex4 (mod7):Ok, this is pretty great, but it's missing one operation! How do we perform division modulon? Or
even, can we? 4